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

例如:

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

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


当前回答

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

其他回答

如果使用Matlab,如果多边形顶点按顺时针顺序排列,函数ispolycw将返回true。

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

虽然这些答案是正确的,但它们在数学上的强度比必要的要大。假设地图坐标,其中最北的点是地图上的最高点。找到最北的点,如果两个点相等,它是最北的,然后是最东的(这是lhf在他的答案中使用的点)。在你的观点中,

点[0]= (5,0)

点[1]= (6,4)

点[2]= (4,5)

点[3]= (1,5)

点[4]= (1,0)

If we assume that P2 is the most north then east point either the previous or next point determine clockwise, CW, or CCW. Since the most north point is on the north face, if the P1 (previous) to P2 moves east the direction is CW. In this case, it moves west, so the direction is CCW as the accepted answer says. If the previous point has no horizontal movement, then the same system applies to the next point, P3. If P3 is west of P2, it is, then the movement is CCW. If the P2 to P3 movement is east, it's west in this case, the movement is CW. Assume that nte, P2 in your data, is the most north then east point and the prv is the previous point, P1 in your data, and nxt is the next point, P3 in your data, and [0] is horizontal or east/west where west is less than east, and [1] is vertical.

if (nte[0] >= prv[0] && nxt[0] >= nte[0]) return(CW);
if (nte[0] <= prv[0] && nxt[0] <= nte[0]) return(CCW);
// Okay, it's not easy-peasy, so now, do the math
if (nte[0] * nxt[1] - nte[1] * nxt[0] - prv[0] * (nxt[1] - crt[1]) + prv[1] * (nxt[0] - nte[0]) >= 0) return(CCW); // For quadrant 3 return(CW)
return(CW) // For quadrant 3 return (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

Javascript实现的lhf的答案 (再次强调,这只适用于简单的多边形,即不适用于图8)

let polygon = [ {x:5,y:0}, {x:6,y:4}, {x:4,y:5}, {x:1,y:5}, {x:1,y:0} ] document.body.innerHTML += `Polygon ${polygon.map(p=>`(${p.x}, ${p.y})`).join(", ")} is clockwise? ${isPolygonClockwise(polygon)}` let reversePolygon = [] polygon.forEach(point=>reversePolygon.unshift(point)) document.body.innerHTML += `<br/>Polygon ${reversePolygon.map(p=>`(${p.x}, ${p.y})`).join(", ")} is clockwise? ${isPolygonClockwise(reversePolygon)}` function isPolygonClockwise (polygon) { // From http://www.faqs.org/faqs/graphics/algorithms-faq/ "How do I find the orientation of a simple polygon?" // THIS SOMETIMES FAILS if the polygon is a figure 8, or similar shape where it crosses over itself // Take the lowest point (break ties with the right-most). if (polygon.length < 3) { return true // A single point or two points can't be clockwise/counterclockwise } let previousPoint = polygon[0] let lowestPoint = polygon[1] let nextPoint = polygon[2] polygon.forEach((point, index)=>{ if (point.y > lowestPoint.y || (point.y === lowestPoint.y && point.x > lowestPoint.x)) { // larger y values are lower, in svgs // Break ties with furthest right previousPoint = polygon[(index-1) >= (0) ? (index-1) : (polygon.length-1)] lowestPoint = polygon[index] nextPoint = polygon[(index+1) <= (polygon.length-1) ? (index+1) : (0)] } }) // Check the angle between the previous point, that point, and the next point. // If the angle is less than PI radians, the polygon is clockwise let angle = findAngle(previousPoint, lowestPoint, nextPoint) return angle < Math.PI } function findAngle(A,B,C) { var AB = Math.atan2(B.y-A.y, B.x-A.x); var BC = Math.atan2(C.y-B.y, C.x-B.x); if (AB < 0) AB += Math.PI*2 if (BC < 0) BC += Math.PI*2 return BC-AB; }