GC友好的凸裁剪（聯合和差異）算法

Question

我正在尋找將基於另一個凸多邊形切割我的凸多邊形的算法。它將用於可破壞的地形（差異）和用於在2D地圖中創建地形（聯合）。

算法必須是垃圾收集器友好的，唯一需要的布爾操作是Union &差異。

我已經做了一些研究，並且有一些github項目，但它們都會或多或少產生一些垃圾。

https://github.com/tmpvar/2d-polygon-boolean

https://github.com/w8r/GreinerHormann

我想最好的解決辦法是學習的其中一個，並重新讓自己的路。但也許你聽說過一些適合我的需求？

謝謝。

Answer 1

這個問題涉及到兩個子問題

1. 找到兩個輪廓

2. 加入該每畝要連接的頂點之間的交叉點。

對於1.您可以利用凸性：將兩個多邊形看作兩個單調鏈。當你同時通過兩個雙鏈的鏈條時，比如說增加x，當縱座標在兩個橫座標之間相交時，就可以檢測到交叉點。

對於2.注意到聯合或差異是由輪廓的一部分在一個多邊形和另一個多邊形之間交替的部分組成，在每個間隔點處。

請注意，在差異的情況下，可能有幾個斷開連接件。

我想，你可以在所有（但對於輸出多邊形）實現這一點沒有任何分配/釋放。