將圓加入多邊形的算法

Question

將重疊的圓組合成多邊形的最佳方法是什麼？

我給出了一個具有固定直徑的圓的中心點列表。

我需要加入任何重疊的圓圈一起和輸出點的列表中所產生的多邊形。

這似乎是一個相當普遍的問題（GIS系統，矢量等）。這可以通過Google Maps API完成，但我正在尋找實際的算法。

我試圖通過計算每個圓周圍的點來解決這個問題。

然後刪除位於任何圓圈內的任何點。

這給了我想要的多邊形中正確的點列表。

但是，點的順序是這個解決方案的問題。每個圓都將其點存儲在一個數組中。將它們與2個重疊圓圈正確合併是相對直接的。但是，當處理多個重疊的圓時，它變得複雜。

希望你有一些想法，使這個解決方案的工作或其他算法，將達到預期的結果。

在此先感謝！

Answer 1

您應該能夠使用appraoch類似如下：

1. 首先，確定屬於同一組重疊圓圈圈。顯然，如果兩個圓的中心的絕對距離小於它們的組合半徑，則兩個圓重疊。對於每個圈子，將圈出的圈子存儲在hashmap/dictionary中。 （您可以使用union-find algorithm, or disjoint sets將它擴展到整個圓圈組，但這不是真的需要。）
2. 創建屬於一個圓的點時，請記住每個點的左右鄰居。您只需將它們存儲在有序數組中即可免費獲得此內容。
3. 刪除「內」點，即那些比一個半徑更接近與第一個圓相交的圓的任何中心的點。
4. 將鄰居標記爲那些沒有去除圈子「鬆散結尾」的內點。
5. 將未移除的點（包括鬆散結束點）連接到其原始左側和右側鄰居。
6. 對於每個鬆散的終點，找到同一組中最近的另一個圓的鬆散端並將它們連接起來。

下面是一張照片來說明方法。

• 紅點是被除去
• 藍點是「鬆散端」通過被鄰居「內」點「內」點;每個「鬆散的末端」具有另一個「鬆散的末端」，其距離小於兩個「點距離」
• 綠點可以容易地通過其順序與其鄰居（包括「鬆散的末端」他們被安排在圓周圍。

可以進一步通過區分左和右鬆散端部，並使用該一個圓的每個左鬆散端部具有將被連接到的另一個右鬆動端的事實降低的可能組合的數量圈。對於組中的n圈，僅留下(n-1)!方式來連接這些圈，而不考慮每圈的點數。

即使只考慮組中實際上與鬆散結束的圓相交的那些圓（只是將它們存儲在散列表/字典中），也可以進一步降低這一點。所以如果你有n的圈子平均與k其他圈子相交，那麼只有n*k可能的組合。

您也可以使用這樣的事實，即其他鬆散端不能比圓上兩點之間距離的兩倍更遠。我們稱這個距離爲d，然後您可以創建一個分辨率爲d的空間圖（例如一個散列圖或二維數組），並將每個鬆散端分配給該地圖中的單元格，然後另一個鬆散端必須與另一個相同的第一個鬆散的末端周圍的細胞。

因此，點之間可以相互連接的方式的數量大大減少了（特別是，它們在最終圖像中的連接方式不允許從頭開始）：這應該是可行的即使有蠻力，除非您在同一組中有批次重疊的圓圈，並且您可以使用更智能的nearest-neighbor search算法。

---

更新：回顧一段時間後這個答案，似乎就可以比較容易地確定的「寬鬆結束」點匹配對：假設你有在圈A中的「右」寬鬆結束，則匹配「左」鬆散的末端必須屬於其半徑重疊下一個「內」點到第一個「鬆散末端」的圓。因此，如果您將該關係存儲在另一張地圖中，則可以立即確定匹配的鬆散結束。 （如果內點與其他多個圓重疊，則該圖應該包含與其重疊的圓）。

Answer 2

下面是O（n log n）時間算法的草圖。

1. 使用您最喜歡的算法/庫來計算圓心上的Delaunay triangulation。

2. 刪除不重疊的圓之間的邊。

3. 漫步每個連接組件的無限面。用doubly connected edge list表示法很容易實現，其中邊緣列表的排序用於指示平面圖的拓撲。在這個邊界上的每個半邊都變成了一個頂點，其中屬於它的尾點的弧段終止並且屬於它的頭點的弧段開始。

4. （可選）用折線近似每個弧段。

_{如果有人來自谷歌正在閱讀本文，請注意，我沒有看過相關的代碼。}