matlab - 在MATLAB中对顺时针多边形点进行排序

Question

我有 2 个向量，它们是多边形 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]

Answer 1

第 1 步：找到顶点的未加权平均值：

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

第2步：找到角度：

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

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

[~, order] = sort(a);

第 4 步：重新排序坐标：

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

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]])

Answer 3

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

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

Matlab Atan2

该角度对于逆时针角度为正（上半平面，y > 0），对于顺时针角度为负（下半平面，y < 0）。

维基百科 Atan2

这意味着使用 Numpy 或 Matlab 的升序排序（）将逆时针进行。

这可以使用鞋带方程来验证

维基百科鞋带

蟒蛇鞋带

因此，调整上面提到的答案以在 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]用于反转数组/列表。

Answer 4

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