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

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

如果矩形都有相同的角度，那么下面的操作可能会更高效、更容易编程：

为每个y坐标确定哪个矩形覆盖那个y坐标(您只需对覆盖变化的y坐标进行此操作，即对应于矩形的上限或下限)。一旦您知道了这一点，就解决每个这样的y坐标的问题(即检查所有x值是否都由该Y坐标的“活动”矩形覆盖)。

编辑:我认为这是O(n^2 log(n)^2)的复杂性，因为两类都是您必须做的艰苦工作。

Answer 3

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

如果有一个交集，则丢弃它(相交部分)，并将未覆盖的段添加到矩形数组中。

接下来，搜索新段和其他现有(仍未检查的)矩形之间的交集。

该算法递归地丢弃交叉口，只留下未发现的部分。

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

如果数组中仍然有一些矩形，则重叠不是满的，因为仍然有一些部分剩余。

希望这能帮上忙

我可以尝试找到我的代码，如果这是你要找的。我想是在C#

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