如何用線切割簡單多邊形

Question

我有一個簡單的多邊形（凸或凹，但沒有孔），我需要用線段切片成部分。我不確定如何實際確定在切片之後產生多少個多邊形，或者如何對頂點進行分組。

基本的凸形案例總是會導致2個子多邊形很容易，但是如何處理複雜的凹形？以「E」形多邊形爲例。垂直切片可以產生4個多邊形。我怎樣才能確定哪些頂點組成了每個子多邊形？

定義多邊形：我在這裏有兩個選項。我的多邊形可以是頂點的有序列表，也可以是三角形的數組。我更喜歡使用三角形陣列的解決方案。如果它們相交，應該很容易遍歷每個三角形並將它與線條分開。但是，我不知道如何將這些三角形分組爲這些結果的子多邊形。

僞代碼甚至一般的建議是好的;一個C＃實現是理想的。

Answer 1

後來我給了this answer一個有點不同的問題。

這個答案給出了一種建立形狀輪廓的方法，給定了該形狀的三角形分解。

其基本思想是將所有三角形的邊緣視爲有向矢量，然後抵消相等但相反的邊緣。

就你而言，你會有一堆代表原始形狀的三角形。你會用線條分割各個三角形。然後，您將使用上述方法將三角形重新組合爲幾何形狀，但條件是切片邊不會取消。

上面提到的答案中有細節和圖片。但是總結的步驟將是

1. 執行三角形分割

2. 對於每個得到的三角形，三個向邊添加到一組。要確定順時針順序，請查看the the answers to this question。

3. 經過邊緣設置除去邊緣的對是相等但相反的（除非它們是切片邊緣）

4. 接在該組的邊緣，然後查找其尾部的頭部相匹配的邊緣第一個邊緣。然後重複該邊緣，直到到達開始邊緣。按照您的要求從邊緣設置中移除每個邊緣。每當你到達開始邊時，你都有一個閉合的循環來表示結果多邊形之一。

5. 執行步驟4，直到沒有剩下的邊。

所有這些都適合您希望從多邊形的三角測量開始。但正如您原始問題的評論者之一所指出的那樣，您可能需要考慮在Generate new polygons from a cut polygon (2D)處給出的替代方案。

Answer 2

我在我的庫PolyK中有這個算法。這裏是the demo。如果你理解Javascript，我相信很容易將它重寫成你的編程語言。