對多邊形的操作 - 如何對找到的頂點進行排序

Question

我在輸入上有兩個表示爲兩個向量點的凹多邊形。我想對它做一些多邊形操作 - 聯合，相交和差異。我發現這些多邊形之間的交點並將它們插入每個多邊形的正確位置。然後我給出關於它的位置的信息（內部 - 它在另一個多邊形內，外部 - 它在另一個多邊形之外，交點 - 多邊形的兩條邊相交）到每個頂點。現在我知道哪些點創建了這些多邊形（外部和交叉點）的聯合等，但我需要知道如何將它們排序到正確的順序。在相交運算的情況下，我需要將這些已排序的點分爲正確的集合數，因爲相交的結果可能不止一個多邊形。

我使用C++，但我不一定需要代碼，我只想要如何排序這些最終的多邊形點。而且我不想爲這些操作使用任何庫，因爲我已經有了自己的功能並且想要使用它們。

我看了一下這個問題How to intersect two polygons?還有其他一些問題，但是他們都沒有解決最終的點排序問題。 我也讀過這篇文章http://www.gvu.gatech.edu/~jarek/graphics/papers/04PolygonBooleansMargalit.pdf，但我可能不明白。

任何幫助，將不勝感激。

Answer 1

如果你遵循我的意見我所有的建議：

• 交集和接觸點之間的區別
• 請兩個多邊形交點的兩個當量之間的聯繫

聯合的解決方案將爲：

1. 只考慮外，觸摸並交點
2. 確保在兩個多邊形點在不同方向（集之一是在順時針方向，另一個逆時針）
是有序
3. 從任意兩個多邊形中的隨機點開始。
4. 對於任何兩個多邊形的每個頂點保持如果你訪問它
5. 你遇到一個交點每次繼續從下一個遍歷交點相當於後跟隨其他多邊形點。
6. 如果您回到從此處開始的位置，則會關閉兩個多邊形連接的其中一個組件。如果不是所有頂點都被遍歷，則從任何未訪問的頂點重複它的全部。
7. 最後計算你找到的所有多邊形的面積。面積最大的將是真正的聯盟。其餘的將是工會的漏洞。

爲解決方案加入將是：

1. 只考慮內部和交叉點
2. 確保在兩個多邊形的點相同方向有序
3. 從任意兩個多邊形中的隨機點開始。
4. 對於任何兩個多邊形的每個頂點保持如果你訪問它
5. 你遇到一個交點每次繼續從下一個遍歷交點相當於後跟隨其他多邊形點。
6. 如果您回到從此處開始的位置，則會關閉兩個多邊形連接的其中一個組件。如果不是所有頂點都被遍歷，則從任何未訪問的頂點重複它的全部。

編輯：正如我已經提到，我有上帝的感覺我與多邊形方向辦法需要修改。然而，通過網絡搜索時，我發現算法的描述，可能爲你做的工作：The Vatti clipping algorithm

EDIT2One more article描述這樣的裁剪算法。