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

例如:

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

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


当前回答

以下是基于上述答案的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

其他回答

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


引用:

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

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

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

一些建议的方法在非凸多边形(如新月形)的情况下会失败。这里有一个简单的方法,它可以用于非凸多边形(它甚至可以用于自相交的多边形,如数字8,告诉你它是否主要是顺时针)。

对边求和,(x2−x1)(y2 + y1)如果结果是正的,曲线是顺时针的,如果结果是负的,曲线是逆时针的。(结果是封闭面积的两倍,采用+/-惯例。)

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

以下是基于上述答案的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

正如这篇维基百科文章中所解释的曲线方向,给定平面上的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的坐标前面。