許多（多於兩個）無孔多邊形的聯合

Question

即時創建沒有孔的多邊形的聯合。輸入多邊形是沒有孔，也應該是輸出。我已經有了用於找到兩個多邊形的工作算法。但是如果有兩個以上的話就有問題了。作爲工會不應該是不相交的多邊形，當我試圖通過一個計算它們的總和我有在這種情況下一個問題：

然後多邊形1符合多邊形2的工會脫節（所以我的算法呢不計算總和）。在第二個循環中，它與第3個和第4個多邊形結合，但輸出不是第2個多邊形。 那麼是否有人知道這樣做的快速和準確的算法呢？ 可能一個好主意是首先通過交叉排序多邊形，但我不能想到任何快速算法，也不是很不知道如何排序。

Answer 1

你不應該一個一個地看多邊形。

您可以直接使用n個多邊形從這個問題polygon union without holes中直接應用2種算法中的任何一種。

希望它有助於

Answer 2

你可以反覆地做到這一點，產生一組連接組件（而不是永遠只是一個單一的連接組件）：

1. 將所有多邊形在「開放」之列。初始化一個組件列表爲空。
2. 雖然開放不爲空：
   • 從開放刪除多邊形p並設置標誌改變爲true。
   • 重複而改變是真實的：
     • 設置在開放改變假
     • 爲每個多邊形q：
       • 如果q相交p，刪除q from open，將集合更改爲爲真，並將集合p設爲p和,的並集。
   • 添加p到部件。

在結束時，部件將包括能夠由輸入多邊形的並集來形成所有的非交叉，連接的組件。在您發佈的示例中，它應該生成一個多邊形。

這不是最有效的方法（請參閱由Ricky Bobby發佈的鏈接中的算法），但它具有簡單性的優點。如果你沒有處理數百個多邊形，它應該表現得很好。

P.S.正如@japreiss指出的那樣，即使所有輸入多邊形都沒有孔，即使輸入都是凸多邊形，聯合也可以有孔。如果輸入可以凹入，那麼即使是2個多邊形的聯合也可以有一個孔。你的2多邊形算法是否已經處理了？

Answer 3

我將使用掃描線算法來查找所有邊界相交點，在交點處斷開輪廓，然後從沿着邊緣的（例如）最低x座標頂點步行開始，始終選擇最外面的一個。有了更多的工作，可以擺脫無孔狀況（孔只是不同方向的輪廓）。