聯合許多凸多邊形的快速算法或庫

Question

我需要對許多凸多邊形（高達數萬個）應用布爾或運算（a.k.a聯合），每個多邊形的頂點少於100個。我嘗試了Boost.Geometry（boost :: geometry :: union_（）函數），它需要大約200ms來聯合1500多邊形。

我已經實現了一個簡單的優化：

1. 多邊形分成兩組，
2. 遞歸工會兩組分爲兩個多邊形集合，
3. 聯盟最後兩個多邊形集合。

這種優化比將多邊形逐個聯合起來要快10倍左右。

我需要一個算法或C/C++庫來在大約10ms內完成這些操作。

有什麼建議嗎？

==== ====編輯

我已經取代Boost.Geometry與快船（http://www.angusj.com/delphi/clipper.php），它滿足我的要求。 Clipper可以在一個操作中合併多個多邊形（Boost.Geometry一次只能合併兩個），這可能是它比Boost.Geometry快得多的原因。

Answer 1

您可以嘗試掃描線算法，該算法將一次處理所有多邊形。

從上到下將所有邊從上到下排列，並按照頂點的縱座標從上到下排列它們。

維護一個活動列表，即橫過當前頂點水平的所有邊的列表。對於該線的位置，可以確定與活動邊的所有交點。保持活動邊沿水平排列，以交叉點的橫座標爲基準。

當您從一個頂點移動到另一個頂點時，某些邊緣會進入該列表，而其他邊緣則會離開它。另外，在排序過程中，某些邊可以交換，這表明它們相交。

交叉點成對，跟蹤多邊形內的線段。沿着水平線合併所有分段是一個簡單的一維問題。

將所有這些成分放在一起，通過將合併輸出從掃描線的一個位置鏈接到下一個位置，您將形成對應於最終聯合的圖形。它不一定是連接的。

應該有可能將整個過程實現爲單個過程，並避免在不需要的邊緣進行分段。

並仔細考慮活動列表處理是如何組織的，算法應該在時間O（NLog（N）+ NK）中運行，其中K是側面交點的數量。