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

Question

我正在寻找一种算法,该算法将确定一个新矩形是否被一组现有矩形完全覆盖.提出问题的另一种方法是,新矩形是否完全存在于现有矩形覆盖的区域？

似乎有很多算法来确定矩形重叠等等,但我找不到能解决这个问题的任何东西.

矩形将使用x,y坐标表示.该问题涉及地理绘图.

编辑 - 来自OP发布的评论:

矩形在X/Y轴上对齐

Answer 1

如果矩形对齐很容易:

假设您有矩形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 2

我过去也做过类似的事情。这个想法是将新的矩形与每个现有的矩形进行比较（一一比较）

如果存在交集，则丢弃它（相交的部分），并将未覆盖的线段添加到矩形数组中

接下来，搜索新线段与其他现有（仍未选中）矩形之间的交集。

算法递归地丢弃交叉点，只留下未覆盖的部分。

最后，如果数组中没有矩形，则完全重叠

如果数组中还有一些矩形，则重叠不完整，因为还剩下一些部分。

希望这可以帮助

如果这是您正在寻找的内容，我可以尝试找到我的代码。我认为它是在 C# 中

另一个想法是将所有现有矩形转换为多边形，然后检查新矩形是否在多边形内，但如果您不使用知道如何使用多边形的语言（或框架），我不建议这样做。