通過添加對角線來分解簡單多邊形

Question

我面臨的問題是通過在初始多邊形中添加對角線（它們本身並不相交），將簡單多邊形（即沒有孔的多邊形）有效地分解爲較小的簡單多邊形。 在其它方面，這裏是函數的Java的簽名，我想有效地實現（線性時間或的n * log（n））的：

public static List<SimplePolygon> addDiagonals(SimplePolygon polygon, List<Edge> diagonals); 

其中多邊形是由表示初期多邊形雙連接邊列表和對角線是邊的列表，其中邊只由開始和結束節點組成。該函數必須返回多邊形中添加對角線所產生的子多邊形列表。這裏是一個圖像顯示我想要的東西：

起始多邊形是在左上角，和另外5人是通過添加對角線產生的子多邊形。 我很難找到如何有效地實現這種分解，因爲它很容易重複節點事件對角線，但如果大量的對角線是從同一個節點出去，我總是要檢查與節點相鄰的頂點是否重複如果是這種情況，那麼我將對角線添加到副本（假設原始屬於另一個子多邊形），那麼我必須再次檢查這個重複節點是否也沒有重複（如果已經有一個對角線與此節點相鄰）等。 您有關於如何有效地進行這種分解的想法嗎？對不起，如果解釋不夠清楚。 謝謝！

Answer 1

如果對角線被索引，則可以使用矢量輔助程序，該矢量輔助程序計算爲每個對角線生成的sp（子多邊形）的數量。每個對角線必須產生2個多邊形...

1. 大小爲啓動這個輔助（每個對角線的SP）=對角線的數量和零填充。
2. 選取下一個對角線：如果sp == 2的數目，移動到下一個對角線。如果不是：
3. 增加sp（在助手向量中）的數量，並生成第一個多邊形，它以對角線開始，並訪問相鄰邊和對角線，直到它再次到達第一個對角線，如果在此過程中sp生成器訪問另一個對角線，增加爲該對角線生成的sp的數量。
4. 如果第一個對角線的sp數爲1，則再次運行第3步。
5. 如果還有未訪問的對角線，回到步驟2

這樣你保證生成每個子多邊形只有一次，不重複。 最好。