在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），角度为负。

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

Answer 4

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