MATLAB中按顺时针排序多边形点

Question

我有两个向量，分别是多边形的8个顶点的x和y坐标。 我想要对它们进行排序（按顺时针方向），以获得正确的向量（以正确绘制多边形）。

原始向量：

x=[5 5 7 7 9 9 5 7]

y=[8 6 6 8 6 8 10 10]

排序后的向量：

x=[5 7 9 9 7 7 5 5]

y=[6 6 6 8 8 10 10 8]

- brio

Answer 1

步骤1：查找顶点的非加权平均值：

cx = mean(x);
cy = mean(y);

步骤2：找到角度：

a = atan2(y - cy, x - cx);

第三步：找到正确的排序顺序：

[~, order] = sort(a);

步骤4：重新排列坐标：

x = x(order);
y = y(order);

- Ben Voigt

---

如果这些点构成一个凹多边形怎么办？有没有解决这种情况的方法？ - Sibbs Gambling

可以使用相同的顶点创建不止一个多边形。这将找到其中一个，并且在某种意义上它将是最小凸多边形。我期望质心总是位于所选多边形内部。 - Ben Voigt

我认为这个排序方式是错误的。“对于逆时针角度（上半平面，y>0），角度为正；对于顺时针角度（下半平面，y<0），角度为负。”请参见我的答案：https://dev59.com/E2Yr5IYBdhLWcg3wH23K#44972382 - Joe

@Joe：更改排序顺序绝对是微不足道的（只需取反其中一个“atan2”输入，或取反输出，或在第4步中颠倒“order”向量），不值得大惊小怪。而且问题说目的是“绘制它们”，所以排序的反转始终不会有任何影响。 - Ben Voigt

Answer 2

本文将为您提供 Ben Voigt 算法的 Python 版本（numpy）:

def clockwise(points):
    x = points[0,:]
    y = points[1,:]
    cx = np.mean(x)
    cy = np.mean(y)
    a = np.arctan2(y - cy, x - cx)
    order = a.ravel().argsort()
    x = x[order]
    y = y[order]
    return np.vstack([x,y])

例子：

In [281]: pts
Out[281]: 
array([[7, 2, 2, 7],
       [5, 1, 5, 1]])

In [282]: clockwise(pts)
Out[282]: 
array([[2, 7, 7, 2],
       [1, 1, 5, 5]])

- mclafee

---

我认为这个排序方式是错误的。“对于逆时针角度（上半平面，y>0），角度为正；对于顺时针角度（下半平面，y<0），角度为负。”请参见我的答案：https://dev59.com/E2Yr5IYBdhLWcg3wH23K#44972382 - Joe

Answer 3

我尝试了@ben-voight和@mclafee提供的解决方案，但我认为它们排序的方式是错误的。

使用atan2时，角度以以下方式表示：

Matlab Atan2

对于逆时针角度(上半平面，y > 0)，角度为正；对于顺时针角度(下半平面，y < 0)，角度为负。

Wikipedia Atan2

这意味着使用Numpy或Matlab的升序sort()将按逆时针方向进行。

可以使用Shoelace公式进行验证

Wikipedia Shoelace

Python Shoelace

因此，将上述答案调整为使用降序排序，则Matlab中的正确解决方案为

cx = mean(x);
cy = mean(y);
a = atan2(y - cy, x - cx);
[~, order] = sort(a, 'descend');
x = x(order);
y = y(order);

在numpy中的解决方案是

import numpy as np

def clockwise(points):
    x = points[0,:]
    y = points[1,:]
    cx = np.mean(x)
    cy = np.mean(y)
    a = np.arctan2(y - cy, x - cx)
    order = a.ravel().argsort()[::-1]
    x = x[order]
    y = y[order]
    return np.vstack([x,y])

pts = np.array([[7, 2, 2, 7],
                [5, 1, 5, 1]])

clockwise(pts)

pts = np.array([[1.0, 1.0],
                [-1.0, -1.0],
                [1.0, -1.0],
                [-1.0, 1.0]]).transpose()

clockwise(pts)

输出：

[[7 2 2 7]
 [5 1 5 1]]

[[2 7 7 2]
 [5 5 1 1]]

[[ 1. -1.  1. -1.]
 [ 1. -1. -1.  1.]]

[[-1.  1.  1. -1.]
 [ 1.  1. -1. -1.]]

请注意使用[::-1]来反转数组/列表。

- Joe

---

你所说的是正确的。我同意，但你的解决方案也没有考虑到凹多边形的特性。在这种情况下，如果有两个以上的点在同一角度上，你不知道它们将以什么顺序产生，这可能会使实际顺序中的某个未来点提前，从而产生错误的排序顺序。 - Prem KTiw

是的，没错。为了让这个算法正常工作，多边形必须非常非常规矩 :) - Joe

Answer 4

该算法不适用于非凸多边形。 相反，考虑使用MATLAB的poly2cw()

- Netanel

---

由于输入不是一个多边形，而只是一组无特定顺序的点，因此您无法将输入分类为凸多边形或非凸多边形（如果我正确理解了问题）。输出是以某种方式排序的点，形成一个简单的多边形（边缘永远不会相交）。 - Ben Voigt