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

例如:

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

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


当前回答

正如这篇维基百科文章中所解释的曲线方向,给定平面上的3个点p, q和r(即x和y坐标),您可以计算以下行列式的符号

如果行列式为负(即定向(p, q, r) < 0),则多边形是顺时针方向(CW)。如果行列式为正(即定向(p, q, r) > 0),则多边形是逆时针方向(CCW)。如果点p, q和r共线,行列式为零(即定向(p, q, r) == 0)。

在上面的公式中,由于我们使用的是齐次坐标,我们将1放在p, q和r的坐标前面。

其他回答

以下是基于上述答案的swift 3.0解决方案:

    for (i, point) in allPoints.enumerated() {
        let nextPoint = i == allPoints.count - 1 ? allPoints[0] : allPoints[i+1]
        signedArea += (point.x * nextPoint.y - nextPoint.x * point.y)
    }

    let clockwise  = signedArea < 0

这是OpenLayers 2的实现函数。有一个顺时针多边形的条件是面积< 0,这是由这个参考确定的。

function IsClockwise(feature)
{
    if(feature.geometry == null)
        return -1;

    var vertices = feature.geometry.getVertices();
    var area = 0;

    for (var i = 0; i < (vertices.length); i++) {
        j = (i + 1) % vertices.length;

        area += vertices[i].x * vertices[j].y;
        area -= vertices[j].x * vertices[i].y;
        // console.log(area);
    }

    return (area < 0);
}

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

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

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

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

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

求出这些点的质心。

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

求line0 line1的两条直线夹角

而不是直线1和直线2

...

...

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

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

Else(它不是单调的)

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