按顺时针或逆时针方向对凸多边形的顶点进行排序

Question

我正试图以顺时针或逆时针的方式对多边形的顶点进行排序。我试图计算多边形内的平均点[x_avg, y_avg]，并计算顶点与该平均点的所有角度。但我的代码给出了错误的角度。我正在使用公式"；atan((m1-m2(/1+m1m2(("；以计算平均点与任何垂线之间的相对角度。请告诉我代码出了什么问题？或者，我可以使用什么算法来计算有序顶点？这是代码：

import math
def rounding_polygon(polygon):
x, y = zip(*polygon)
print(x,y)
x_avg = sum(x)/len(x)
y_avg = sum(y)/len(y)
angles = []
print('x_a = ', x_avg, 'ya =', y_avg)
x1, y1 = polygon[0][0], polygon[0][1]
m_com = (y_avg-y1)/(x_avg-x1)
for v in polygon:
x2, y2 = v[0], v[1]
m_curr = (y_avg-y2)/(x_avg-x2)
slope = (m_com-m_curr)/(1 + (m_com*m_curr))
curr_angle = math.degrees(math.atan(slope))
angles.append([curr_angle, v])
angles = sorted(angles)
vertices = [x[1] for x in angles]
print('angles = ', angles)
print('vertices = ', vertices)
return vertices
polygon = [[1, 5], [4, 1], [7, 8], [7, 1], [1.8, 5.4]]
vertices = rounding_polygon(polygon)
print(vertices)

Answer 1

atan函数在有限的范围(半个圆(内给出结果。要获得全角度范围的-Pi..Pi，您应该使用atan2函数，该函数接受两个参数——y-difference和x-difference。

示例使用最低的(如果两个点具有相同的Y，则为左侧(点作为排序的基点。

import math
polygon = [[1, 5], [4, 1], [7, 8], [7, 1], [1.8, 5.4]]
lowest = min(polygon, key = lambda x: (x[1], x[0]))
vertices = sorted(polygon, key=lambda x: math.atan2(x[1]-lowest[1], x[0]-lowest[0]) + 2 * math.pi)
print(vertices)
>>[[4, 1], [7, 1], [7, 8], [1.8, 5.4], [1, 5]]

为什么选择最低点？在比较点方向角期间排除非传递性(当A>B、B>C但C>B时(