劃分自相交多邊形（C代碼）

Question

我想將自相交多邊形劃分爲簡單的多邊形。我將邊緣和交點保存在數據結構（連接列表）中。

所以這裏是一個例子。我有一個連接列表，包含邊的x，y座標和多邊形的交點。根據這個picture中的多邊形，它將是::（1） - >（2） - >（3）... - >（7）。我想要做的是獲取簡單多邊形的邊（這裏是三角形）。在這種情況下:: 1,2,7/3,4,5/5,6,7。

Answer 1

我認爲Bentley-Ottman將是你最好的選擇。有一個很好的交互式可視化here。另一個很好的描述here。