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

Question

我正在寻找一种算法来确定新矩形是否完全被一组现有矩形覆盖。另一种提出问题的方式是，新矩形是否完全存在于现有矩形覆盖的区域中？

似乎有很多算法可以确定矩形重叠等等，但我真的找不到任何解决这个确切问题的算法。

矩形将使用 x, y 坐标表示。本题涉及地理测绘。

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

The rectangles are aligned on the X/Y axis

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