確定一個矩形是否被另一組矩形完全覆蓋所需的算法

Question

我正在尋找一種算法來確定一個新矩形是否被一組現有矩形完全覆蓋。提出問題的另一種方式是，新矩形是否與現有矩形覆蓋的區域完全一樣存在？

似乎有很多算法來確定矩形重疊等，但我真的找不到解決這個確切問題的任何東西。

矩形將使用x，y座標表示。這個問題涉及地理製圖。

編輯 - 從發佈註釋由OP：

的矩形在X對齊/ Y軸

Answer 1

我已經做了，在過去類似的東西。 想法是新的矩形與每個比較現有的（一個接一個）

如果有交叉點丟棄它（相交的部分），和未覆蓋段添加到一個矩形陣列

下，搜索新分段和其他現有（仍未選中）矩形之間的交集。

做算法遞歸地丟棄交集，只留下未覆蓋的部分。

到底

，如果數組中沒有矩形，你有一個完整的重疊

是否還有數組中的某些矩形，重疊並不完全，因爲還留有一些部分。

希望這有助於

我可以嘗試找到我的代碼，如果這是你在找什麼。我認爲它在C＃

另一個想法是將所有現有的矩形轉換成多邊形，然後檢查新的矩形是否在多邊形內，但如果你不使用語言（或框架），我不會推薦這個，它知道如何使用多邊形。

Answer 2

如果矩形都具有相同的角度;那麼下面的程序可能會更有效，更容易編程：

確定每個y座標是哪個矩形覆蓋了y座標（您只需對覆蓋更改的y座標執行此操作;即對應於上部或矩形的下限）。一旦你知道了，爲每個這樣的y座標解決問題（即檢查所有的x值是否被該Y座標的「有效」矩形覆蓋）。

編輯：我覺得這是O​​（n^2的log（n）^ 2）複雜性，兩類都是你所要做的

Answer 3

如果矩形排列的辛勤工作，很容易：

假設你有矩形A0並想知道它是否完全被（B1，B2，B3 ......）= B

A := (A0) 
while P := pop B 
    for R in A 
    if P fully covers R: 
     remove R from A 
    else if P and R does overlap: 
     remove R from A 
     break R in subrentangles S := (S1, S2, S3,...) following the intersections \ 
                with P edges 
     push S into A 
if A is empty: 
    say B covers A0 
else: 
    say B does not fully cover A0 

Answer 4

R-tree可能是有用的。 如果可能存在旋轉的矩形，可以將它們放在邊界矩形中。

Answer 5

嘗試此

源矩形：X0，Y0，寬，高

//基本上比較邊緣

如果（（（X0> =ⅹⅰ）& &（X0 +廣度< = Xi）的）& &（（Y0> =易）& &（Y0 +高度< =易））{// 考慮矩形 }否則{個矩形

第一種方法 「減去」（返回發現部分）：//丟棄 }

Answer 6

這裏是我的代碼，因爲你提出要求。

第二種方法是從基本矩形中減去矩形列表。

你的情況列表

包含現有的矩形，而新的一個是基礎

，以檢查是否有完整的交集列表從第二個方法返回應該沒有的元素。

public static List<Rectangle> SubtractRectangles(Rectangle baseRect, Rectangle splitterRect) 
    { 
     List<Rectangle> newRectaglesList = new List<Rectangle>(); 

     Rectangle intersection = Rectangle.Intersect(baseRect, splitterRect); 
     if (!intersection.IsEmpty) 
     { 
      Rectangle topRect = new Rectangle(baseRect.Left, baseRect.Top, baseRect.Width, (intersection.Top - baseRect.Top)); 
      Rectangle bottomRect = new Rectangle(baseRect.Left, intersection.Bottom, baseRect.Width, (baseRect.Bottom - intersection.Bottom)); 

      if ((topRect != intersection) && (topRect.Height != 0)) 
      { 
       newRectaglesList.Add(topRect); 
      } 

      if ((bottomRect != intersection) && (bottomRect.Height != 0)) 
      { 
       newRectaglesList.Add(bottomRect); 
      } 
     } 
     else 
     { 
      newRectaglesList.Add(baseRect); 
     } 

     return newRectaglesList; 
    } 

    public static List<Rectangle> SubtractRectangles(Rectangle baseRect, List<Rectangle> splitterRectList) 
    { 
     List<Rectangle> fragmentsList = new List<Rectangle>(); 
     fragmentsList.Add(baseRect); 

     foreach (Rectangle splitter in splitterRectList) 
     { 
      List<Rectangle> toAddList = new List<Rectangle>(); 

      foreach (Rectangle fragment in fragmentsList) 
      { 
       List<Rectangle> newFragmentsList = SubtractRectangles(fragment, splitter); 
       toAddList.AddRange(newFragmentsList); 
      } 

      if (toAddList.Count != 0) 
      { 
       fragmentsList.Clear(); 
       fragmentsList.AddRange(toAddList); 
      } 
     } 

     return fragmentsList; 
    } 

Answer 7

您可以使用用於計算矩形的聯合區域的算法。當你想檢查矩形a是否被矩形B = {b_1，b_2，...，}覆蓋時。

首先計算B中矩形的並集面積，我們得到area_1作爲值。

然後計算B + {a}中矩形的聯合區域，我們得到area_2作爲值。
因此，如果area_1 == area_2，那麼您確定矩形a被矩形B覆蓋。否則，答案是錯誤的。

所以主要問題是如何計算矩形的聯合面積。這個問題可以通過現有的優秀算法來解決。該算法可以簡單介紹爲首先離散矩形點的值，然後使用分割樹來加速計算每個塊的面積。