算法需要，以確定是否一個矩形完全被給定一組多邊形P和矩形區域A一組多邊形

的覆蓋，我需要驗證，如果A完全由P.算法需要，以確定是否一個矩形完全被給定一組多邊形P和矩形區域A一組多邊形

覆蓋

的數量和複雜性的多邊形和總面積A非常大，因此，基於多邊形聯合的方法可能無法及時發揮作用。爲了讓事情更簡單一些，我將A'定義爲A內最小區域的大小，A的覆蓋範圍是我關心的。我想到建立一個二維分段樹，就像在2D中重複劃分區域的結構一樣（每個區域的正方形分成4個子正方形，直到子正方形的大小爲A'），但由於我們在這裏處理多邊形，所以我不確定是否這將是有效的。

來源

2013-02-27 user1089464

是否是遊戲代碼？ – SparKot 2013-02-27 07:23:36

什麼是限制？多邊形數量，最小最大座標（目標多邊形和所有其他））。 – 2013-02-27 08:46:05

我認爲這可能有所幫助：http://stackoverflow.com/questions/2272179/a-simple-algorithm-for-polygon-intersection – 2013-02-27 15:55:35

您可以使用多邊形交集或差，而不是工會的：

考慮自己作爲一個多邊形，每次選擇一個多邊形P·和細化爲A - P'，並檢查，看看是否是空的。在檢查完所有多邊形之後，您可以確定A是否被P覆蓋。

來源

2013-02-28 02:55:03

我可以試試。螺紋 – user1089464 2013-02-28 03:08:06

在附註中，我們如何實際實現二維分段樹？與一維樹相比，我在這裏看到的問題是，在一維樹中，我們知道在遍歷深度並返回結果時，查詢範圍僅分裂兩次。但在2D中，似乎並非如此 – user1089464 2013-02-28 03:10:37

我認爲對於二維分段樹，您應該首先考慮導致一維分段樹的分段的x投影，那麼樹的每個節點也是一維分段樹在節點x範圍內的分段的y投影上。 – 2013-02-28 13:54:51

算法需要，以確定是否一個矩形完全被給定一組多邊形P和矩形區域A一組多邊形

回答

相關問題