algorithm - 我如何知道多边形的内部是位于顶点的右侧还是左侧？

Question

我正在尝试将单调的多边形设为多边形，以便对其进行三角剖分，但我在使用常规顶点时遇到了问题(一个顶点在其上方有一个邻居，在其下方有一个邻居:

处理规则顶点的算法让我感到困惑，因为我不知道多边形是在右边还是左边:

算法在《Computational Geometry Algorithms and Applications Third Edition》一书中

Answer 1

首先计算整个多边形的有符号区域。 aera 的符号会告诉您多边形顶点的缠绕顺序是顺时针还是逆时针。

您只需执行一次，而且操作成本低。

然后要确定您是否有左规则顶点或右规则顶点，您只需查看前一个顶点和下一个顶点的索引即可。有升序也有降序。

一个小表格现在会告诉你你是在左边还是右边:

Counter-Clockwise Polygon:
--------------------------
Ascending order: Regular vertex is on the left of the polygon
Descending order: Regular vertex is on the right of the polygon


Clockwise Polygon:
--------------------------
Ascending order: Regular vertex is on the right of the polygon
Descending order: Regular vertex is on the left of the polygon

因此无需进行任何昂贵的光线相交或多边形中的点测试。

几年前我已经实现了该算法，这对分析开始时多边形的缠绕顺序有很大帮助，如果是逆时针方向，则在进行任何进一步处理之前反转缠绕顺序。

这消除了很多控制流依赖于缠绕顺序的情况。这样，您最终会得到更清晰、更易于遵循的代码。