矩形多邊形上的布爾操作

Question

Avast在那裏的程序員！

我有以下問題：

我有兩個矩形重疊的像顯示在下面的圖片。

我想弄清楚由點ABCDEF的多邊形。

備用聖誕節描述：紅色的餅乾切割了一些黑色的餅乾。我想計算黑色的餅乾。

每個矩形是具有4個2d頂點的數據結構。

什麼是實現這一目標的最佳算法？

Answer 1

這是一般的2D多邊形裁剪的一種特殊情況。 Weiler-Atherton算法是一個很好的開始。 Wikipedia has a summary和links to the original paper。該算法似乎與您描述的數據結構非常吻合。

請注意，很有可能你會得到一個帶有洞的矩形（如果紅色的是完全在黑色的裏面）或者甚至是兩個矩形（例如，如果紅色比黑色更高，更瘦）。如果你確定在黑色矩形內只有一個紅色矩形的一個角落，那麼解決方案應該更簡單。

Answer 2

constructive solid geometry

Answer 3

我發現了一些東西在這裏我可以使用：

http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Boolean_set_operations_2/Chapter_main.html

其實我下載了CGAL源之前，我甚至張貼了這個問題，但我想我會仔細看進去。

Answer 4

座標有多精確？如果矩形非常小，最簡單的方法可能是將它們繪製在畫布上，先是黑色矩形，然後是紅色。畫布上剩餘的黑色像素是剩餘的多邊形。

另一種方法是將座標網格劃分爲基於矩形所有邊的一組矩形（不包括無限長矩形，如果有兩個原始矩形，則最多可生成9個矩形）。然後，只需測試這些矩形中每個矩形的代表點，以獲得特定多邊形中的成員資格，以確定哪些矩形位於哪個矩形中，哪些矩形位於外面。