猿问
下载APP

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

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

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


例如:


point[0] = (5,0)

point[1] = (6,4)

point[2] = (4,5)

point[3] = (1,5)

point[4] = (1,0)

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


呼啦一阵风
浏览 69回答 2
2回答

万千封印

在非凸多边形(例如新月形)的情况下,一些建议的方法将失败。这是一个非常简单的非凸多边形(它甚至可以使用自相交的多边形,如图8,告诉你它是否主要是顺时针方向)。边上的和,(x 2 - x 1)(y 2 + y 1)。如果结果为正,则曲线为顺时针,如果为负,则曲线为逆时针。(结果是封闭区域的两倍,带有+/-约定。)point[0] = (5,0)   edge[0]: (6-5)(4+0) =   4point[1] = (6,4)   edge[1]: (4-6)(5+4) = -18point[2] = (4,5)   edge[2]: (1-4)(5+5) = -30point[3] = (1,5)   edge[3]: (1-1)(0+5) =   0point[4] = (1,0)   edge[4]: (5-1)(0+0) =   0                                         ---                                         -44  counter-clockwise

白衣染霜花

所述叉积测量两个向量的垂直岬的程度。想象一下,多边形的每个边都是三维(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个点中的每个点执行此操作,并在每个顶点处将此计算中的值相加。如果最终总和为正,则顺时针方向,负方向,逆时针方向。
打开App,查看更多内容
随时随地看视频慕课网APP
我要回答