我如何知道多邊形的內部是否位於頂點的右側或左側？

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 

所以沒必要做任何昂貴的線的交點或點在多邊形測試。

，我實現了算法幾年前，這是一個很大的幫助，分析多邊形的在開始纏繞順序和 - 如果逆時針 - 做任何進一步處理之前扭轉纏繞順序。

這消除了很多，其中控制流依賴於纏繞順序上箱子。你會以更簡潔，更簡單的方式跟隨代碼。