如何將自相交多邊形劃分爲簡單的多邊形？

Question

我有一個由點列表定義的多邊形。該多邊形可以與多個交點交叉。我用蠻力找到了所有的點。 （尚未實施Bentley-Ottmann掃描方法）。例如， http://i.imgur.com/3F3LbfB.png 我有4個頂點，邊1-2與邊4-0（點A）相交，邊2-3與邊4-0（點B）相交。我簡單的多邊形0-1-A-0和休息，這休息也分爲兩個多邊形：A-B-2-A 和B-3-4-B 一般algortithm是如何？

Answer 1

一個簡單的方法是通過細分交叉點處的多邊形線段（Bentley - Ottmann自然延伸以同時執行此操作）來計算planar straight-line graph (PSLG)，然後枚舉其有限面。後者可以通過準備組合嵌入然後traversing it as described in this previous answer of mine來完成。