确定一个矩形是否被另一组矩形完全覆盖所需的算法

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覆盖。否则，答案是错误的。

所以主要问题是如何计算矩形的联合面积。这个问题可以通过现有的优秀算法来解决。该算法可以简单介绍为首先离散矩形点的值，然后使用分割树来加速计算每个块的面积。