math - 如何确定多边形点列表是否按顺时针顺序排列？

Question

有一个点列表，如何查找它们是否按顺时针顺序排列？

例如:

point[0] = (5,0)
point[1] = (6,4)
point[2] = (4,5)
point[3] = (1,5)
point[4] = (1,0)

会说它是逆时针方向(或者对某些人来说是逆时针方向)。

Answer 1

对于非凸多边形(例如新月形)，某些建议的方法将失败。这是一个适用于非凸多边形的简单方法(它甚至适用于像 8 字形这样的自相交多边形，告诉您它是否大部分是顺时针方向)。

边缘求和，(x₂ − x₁)(y₂ + y₁) 。如果结果为正，则曲线为顺时针方向；如果结果为负，则曲线为逆时针方向。 (结果是封闭面积的两倍，采用 +/- 约定。)

point[0] = (5,0)   edge[0]: (6-5)(4+0) =   4
point[1] = (6,4)   edge[1]: (4-6)(5+4) = -18
point[2] = (4,5)   edge[2]: (1-4)(5+5) = -30
point[3] = (1,5)   edge[3]: (1-1)(0+5) =   0
point[4] = (1,0)   edge[4]: (5-1)(0+0) =   0
                                         ---
                                         -44  counter-clockwise