如何确定多边形点列表是否按顺时针顺序？

Question

有一个点列表,我如何找到顺时针顺序？

例如:

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

会说它是逆时针(或逆时针,对某些人来说).

Answer 1

在非凸多边形(例如新月形)的情况下,一些建议的方法将失败.这是一个非常简单的非凸多边形(它甚至可以使用自相交的多边形,如图8,告诉你它是否主要是顺时针方向).

边上的和,(x ₂ - x ₁)(y ₂ + y ₁).如果结果为正,则曲线为顺时针,如果为负,则曲线为逆时针.(结果是封闭区域的两倍,带有+/-约定.)

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

Answer 2

所述叉积测量两个向量的垂直岬的程度.想象一下,多边形的每个边都是三维(3-D)xyz空间的xy平面中的向量.然后,两个连续边的叉积是z方向上的矢量,(如果第二段是顺时针,则为正z方向,如果是逆时针,则为z方向).该矢量的大小与两个原始边缘之间的角度的正弦成比例,因此当它们垂直时达到最大值,并且当边缘共线(平行)时逐渐减小以消失.

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

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和
edgeB之间point1,以point2
...
edgeE之间point4和point0.

然后Vertex A(point0)介于
edgeE[From point4to point0]
edgeA[From point0to`point1'之间

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

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

并且这两个邻接边缘的横产物用下面的矩阵,这是通过将代表这三个符号下方的两个向量的坐标的坐标轴(构成的行列式计算i,j,及k).第三个(零)值坐标是因为交叉积概念是三维构造,因此我们将这些二维向量扩展为三维以应用交叉积:

 i    j    k 
-4    0    0
 1    4    0    

假设所有交叉乘积产生垂直于两个矢量平面的矢量,则上述矩阵的行列式仅具有k(或z轴)分量.
计算k或z轴分量的大小的公式是
a1*b2 - a2*b1 = -4* 4 - 0* 1 = -16

该值(-16)的大小是2个原始矢量之间的角度的正弦的乘积,乘以2个矢量的大小的乘积.
实际上,其价值的另一个公式是
A X B (Cross Product) = |A| * |B| * sin(AB).

因此,要回到角度的度量,您需要将此值(-16)除以两个向量的大小的乘积.

|A| * |B| = 4 * Sqrt(17) =16.4924...

所以罪的量度(AB)= -16 / 16.4924=-.97014...

这是衡量顶点向左或向右弯曲后的下一个段的度量,以及是多少.没有必要采用正弦波.我们所关心的只是它的大小,当然还有它的标志(正面或负面)!

对闭合路径周围的其他4个点中的每个点执行此操作,并在每个顶点处将此计算中的值相加.

如果最终总和为正,则顺时针方向,负方向,逆时针方向.

Answer 3

我想这是一个非常古老的问题,但无论如何我都会抛出另一个解决方案,因为它很简单,而且不是数学密集的 - 它只是使用基本代数.计算多边形的有符号区域.如果它是负数,则点是顺时针顺序,如果它是正数,则它们是逆时针.(这与Beta的解决方案非常相似.)

计算有符号面积:A = 1/2*(x ₁*y ₂ - x ₂*y ₁ + x ₂*y ₃ - x ₃*y ₂ + ... + x _n*y ₁ - x ₁*y _n)

或者在伪代码中:

signedArea = 0
for each point in points:
    x1 = point[0]
    y1 = point[1]
    if point is last point
        x2 = firstPoint[0]
        y2 = firstPoint[1]
    else
        x2 = nextPoint[0]
        y2 = nextPoint[1]
    end if

    signedArea += (x1 * y2 - x2 * y1)
end for
return signedArea / 2

请注意,如果您只是检查订购,则无需费力除以2.

资料来源:http://mathworld.wolfram.com/PolygonArea.html

Answer 4

找到y最小的顶点(如果有连接则找到最大的x).设顶点为A和列表中的前一个顶点,列表中B的下一个顶点为C.现在计算符号的叉积的AB和AC.

参考文献:

• 如何找到简单多边形的方向？在 常见问题中:comp.graphics.algorithms.

• 维基百科的曲线方向.

Answer 5

这是基于此答案的算法的简单C#实现.

假设我们有一个Vector类型X和Y属性类型double.

public bool IsClockwise(IList<Vector> vertices)
{
    double sum = 0.0;
    for (int i = 0; i < vertices.Count; i++) {
        Vector v1 = vertices[i];
        Vector v2 = vertices[(i + 1) % vertices.Count];
        sum += (v2.X - v1.X) * (v2.Y + v1.Y);
    }
    return sum > 0.0;
}

Answer 6

从其中一个顶点开始,计算每一侧所对的角度.

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

如果值的总和为正,则以逆时针方向绘制多边形.

Answer 7

用 JavaScript实现Sean 的回答：

function calcArea(poly) {
    if(!poly || poly.length < 3) return null;
    let end = poly.length - 1;
    let sum = poly[end][0]*poly[0][1] - poly[0][0]*poly[end][1];
    for(let i=0; i<end; ++i) {
        const n=i+1;
        sum += poly[i][0]*poly[n][1] - poly[n][0]*poly[i][1];
    }
    return sum;
}

function isClockwise(poly) {
    return calcArea(poly) > 0;
}

let poly = [[352,168],[305,208],[312,256],[366,287],[434,248],[416,186]];

console.log(isClockwise(poly));

let poly2 = [[618,186],[650,170],[701,179],[716,207],[708,247],[666,259],[637,246],[615,219]];

console.log(isClockwise(poly2));

很确定这是正确的。它似乎工作:-)

那些多边形看起来像这样，如果你想知道：