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

例如:

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

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


当前回答

The cross product measures the degree of perpendicular-ness of two vectors. Imagine that each edge of your polygon is a vector in the x-y plane of a three-dimensional (3-D) xyz space. Then the cross product of two successive edges is a vector in the z-direction, (positive z-direction if the second segment is clockwise, minus z-direction if it's counter-clockwise). The magnitude of this vector is proportional to the sine of the angle between the two original edges, so it reaches a maximum when they are perpendicular, and tapers off to disappear when the edges are collinear (parallel).

因此,对于多边形的每个顶点(点),计算两条相邻边的叉乘大小:

Using your data:
point[0] = (5, 0)
point[1] = (6, 4)
point[2] = (4, 5)
point[3] = (1, 5)
point[4] = (1, 0)

把边连续地标为 edgeA是从point0到point1的段 点1到点2之间的edgeB ... edgeE在point4和point0之间。

那么顶点A (point0)在两者之间 edgeE[从点4到点0] 从point0到' point1'

这两条边本身就是向量,它们的x坐标和y坐标可以通过减去它们的起点和终点的坐标来确定:

edgeE = point0 - point4 = (1,0) - (5,0) = (- 4,0) and edgeA = point1 - point0 = (6,4) - (1,0) = (5,4) and

这两个相邻边的外积是用下面矩阵的行列式来计算的,这个矩阵是通过将两个向量的坐标放在表示三个坐标轴的符号(i, j, & k)下面来构造的。第三个(零)值坐标在那里,因为外积概念是一个三维结构,所以我们将这些2-D向量扩展到3-D,以便应用外积:

 i    j    k 
-4    0    0
 1    4    0    

假设所有的叉乘都产生一个垂直于两个向量相乘平面的向量,上面矩阵的行列式只有一个k(或z轴)分量。 计算k轴或z轴分量大小的公式为 A1 *b2 - a2*b1 = -4* 4 - 0* 1 = -16

这个值的大小(-16)是两个原始向量夹角的正弦值,乘以两个向量大小的乘积。 实际上,它值的另一个公式是 A X B(叉乘)= |A| * |B| * sin(AB)。

为了得到角度的大小你需要用这个值(-16)除以两个向量大小的乘积。

|A| * |B| = 4 *根号(17)= 16.4924…

所以sin(AB) = -16 / 16.4924 = -.97014…

这是一个度量顶点后的下一段是否向左或向右弯曲,以及弯曲的程度。不需要取arcsin函数。我们只关心它的大小,当然还有它的符号(正的还是负的)!

对闭合路径周围的其他4个点都这样做,并将每个顶点的计算值相加。

如果最终的和是正的,就顺时针,负的,逆时针。

其他回答

这是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);
}

求出这些点的质心。

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

求line0 line1的两条直线夹角

而不是直线1和直线2

...

...

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

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

Else(它不是单调的)

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

虽然这些答案是正确的,但它们在数学上的强度比必要的要大。假设地图坐标,其中最北的点是地图上的最高点。找到最北的点,如果两个点相等,它是最北的,然后是最东的(这是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)

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

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

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

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; }