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

Question

我试图让单调的多边形，所以我可以三角测量它，但我有正规顶点的问题（一个顶点有一个邻居在它上面，一个邻居在它下面：

的算法手柄定期顶点是混淆了我，因为我不知道该多边形是否是在右边或左边：

的算法是书中计算几何算法和应用第三版

Answer 1

建立从普通的光线指向右侧，查找是否相交与边缘的cts并且得到这些交叉点的​​数量。如果很奇怪，多边形位于右侧。

这种做法是接近点在多边形算法{} example, discussing non-trivial cases

也许，在书的算法，你得与其他方式提供这些信息。例如，您可能知道步行顺序是顺时针还是逆时针。

Answer 2

首先你计算整个多边形的签署AERA。 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 

所以没必要做任何昂贵的线的交点或点在多边形测试。

，我实现了算法几年前，这是一个很大的帮助，分析多边形的在开始缠绕顺序和 - 如果逆时针 - 做任何进一步处理之前扭转缠绕顺序。

这消除了很多，其中控制流依赖于缠绕顺序上箱子。你会以更简洁，更简单的方式跟随代码。