找出矩形是否被上面的矩形遮擋了？

我有一個矩形和一個參考矩形的集合。我想知道參考矩形是否被它上面的矩形（集合中的所有矩形）完全遮住了。例如：找出矩形是否被上面的矩形遮擋了？

http://i54.tinypic.com/246w57l.png

顯而易見的解決方案是創建的bool或位圖的矩陣和簡單的blit所有的矩形，並檢查是否有任何不是蓋的，但是這不是一個選項。這必須每秒完成很多次。

我想出了這個主意：爲每一個矩形，它相交與其他所有的矩形（和它們限制在參照矩形），從而產生更小的矩形不相交的集合，像這樣： http://i54.tinypic.com/s1j30h.png

然後簡單地增加他們的所有領域，並從基準矩形的面積中減去。不過，我不確定如何做到最好。歡迎任何其他想法，建議或例子。

謝謝。

2011-02-17 fingerprint211b

所有的矩形是否總是與x軸和y軸對齊？另請參閱SO上的[本問答]（http://stackoverflow.com/questions/4397226/algorithm-required-to-determine-if-a-rectangle-is-completely-covered-by-another-s）。 – 2011-02-17 11:31:28

是的，永遠。謝謝！請提交它作爲答案。 – fingerprint211b 2011-02-17 12:18:48

設n是覆蓋矩形的數目。這個問題可以通過平面掃描（http://en.wikipedia.org/wiki/Sweep_line_algorithm）和增強的自下而上的縱向樹（http://en.wikipedia.org/wiki/Splay_tree）在時間O（n log n）中解決。

將所有覆蓋矩形剪切爲參考。
通過排序，問題減少到一個，其中覆蓋矩形的所有的x座標是在[0，2N）的整數。相似地轉換y座標。
創建2n個節點伸展樹。節點j的值是開放區間（j，j + 1）中有多少個矩形與掃描線相交。對於O（log n）時間更新，不要將j的值存儲在j中，而是將j的值和j的父值之間的差值（根存儲它的真值）。旋轉是稍微複雜一些：旋轉
```
y   x 
/\  /\ 
    x c -> a y 
/\   /\ 
a b   b c 
```
涉及到更新
```
b.diff += x.diff; // if b exists 
x.diff += y.diff; 
y.diff -= x.diff; 
```
每個節點還跟蹤其子樹最小。爲了與前面描述的值表達兼容，節點j存儲其子樹最小值與其值的差值。旋轉期間：
```
y.diffmin = min(0, b.diffmin + b.diff, c.diffmin + c.diff); 
```
在展開操作結束時，以相同的方式更新根。如果不存在，則省略b或c。
掃線。對於[0，2n）中的x，找到所有左邊都在x處的矩形，並按如下方式更新樹。對於從y0到y1的矩形，展開y1並增加其左側子元素的diff（並重新計算diffmin），然後展開y0並遞減其左側子元素的差異。

在處理了所有左側之後，請檢查最小樹。如果它爲零，則不包括該參考。

以同樣的方式處理右側（描述中的交換增量和遞減）。

來源

2011-02-17 12:48:24

找出矩形是否被上面的矩形遮擋了？

回答

相關問題