algorithm - 求大于 180º 的多边形的内角数

Question

如何找到大于 180º 的多边形的内角数，只有多边形的顶点？

对于每个顶点，我总是想要内角，而不是外角。

来自巴西的感谢。

Answer 1

您可以简单地通过标量积(点积)确定两个向量的角度。一个有用的属性是，如果向量是正交的，则它们的标量积为零；否则如果它们的角度是钝角，则乘积为负，否则为正。因此，要采取的步骤是:

• 找到从 V0 到 V1 的第一条边(作为向量，您可以通过减去坐标得到它)，然后将它向左旋转 90 度(这只是将 (x y) 转换为(-y x))
• 找到从V1到V2的第二条边(不旋转)
• 取标量积(这只是(x1 * x2) + (y1 * y2))
• 如果标量积为负，则为右转，否则为左转
• 下一个边缘...
• 如果逆时针穿过顶点，计算右转的次数，否则计算左转的次数
• 对于最后一个顶点，您必须返回到第一个顶点(即使用边 Vn 到 V0 和 V0 到 V1)

编辑:您可以通过使用以下公式计算多边形的面积来确定顶点是逆时针还是顺时针排序:

     1  n-1A = --- SUM( x(i)*y(i+1) - x(i+1)*y(i) )     2  i=0

其中 n 是顶点数。 x(n) 和y(n) 与x(0) 和y(0) 相同(关闭多边形)。

如果为正，则顶点按逆时针顺序排列，否则按顺时针顺序排列。

编辑:当您简化旋转和标量积的步骤时，您会得到二维叉积的公式，x1*y2 - x2*y1 .这简化了上面的第一步:

• 找到从 V0 到 V1 的第一条边(作为向量，通过减去坐标)
• dito 从 V1 到 V2 的第二条边
• 取叉积((x1 * y2) - (x2 * y1))
• 如果叉积为正，则为左转

抱歉第一种方法比较复杂。