有了一个点列表,我如何确定它们是否是顺时针顺序的?

例如:

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

会说它是逆时针的(对某些人来说是逆时针的)


当前回答

下面是基于这个答案的一个简单的Python 3实现(反过来,它是基于已接受答案中提出的解决方案)

def is_clockwise(points):
    # points is your list (or array) of 2d points.
    assert len(points) > 0
    s = 0.0
    for p1, p2 in zip(points, points[1:] + [points[0]]):
        s += (p2[0] - p1[0]) * (p2[1] + p1[1])
    return s > 0.0

其他回答

从其中一个顶点开始,计算每条边对应的角度。

第一个和最后一个将是零(所以跳过它们);对于其余部分,角度的正弦值将由归一化与(点[n]-点[0])和(点[n-1]-点[0])的单位长度的叉乘给出。

如果这些值的和是正的,那么你的多边形是逆时针方向绘制的。

我认为为了使某些点顺时针方向,所有的边都必须是正的而不仅仅是边的和。如果一条边是负的,则逆时针方向给出至少3个点。

在测试了几个不可靠的实现之后,在CW/CCW方向方面提供令人满意结果的算法是由OP在这个线程(shoelace_formula_3)中发布的算法。

与往常一样,正数表示CW方向,而负数表示CCW方向。

求出这些点的质心。

假设有直线从这个点到你们的点。

求line0 line1的两条直线夹角

而不是直线1和直线2

...

...

如果这个角是单调递增的,而不是逆时针递增的,

如果是单调递减,则是顺时针递减

Else(它不是单调的)

你不能决定,所以这是不明智的

找出y最小的顶点(如果有平手,则x最大)。假设顶点是A,列表中的前一个顶点是B,列表中的下一个顶点是c。现在计算AB和AC的叉乘的符号。


引用:

如何确定一个简单多边形的方向?在 常见问题:计算机。图形。算法。 维基百科的曲线定位。