algorithm - 找出一个矩形是否被其上方的矩形遮挡？

Question

我有一组矩形和一个引用矩形。我想知道引用矩形是否被其上方的矩形(集合中的所有矩形)完全遮挡。例如:

显而易见的解决方案是创建一个 bool 矩阵或位图，然后简单地对所有矩形进行 blit，然后检查是否有任何内容未被覆盖，但这不是一种选择。这必须每秒执行很多次。

我想到了这个想法:对于每个矩形，将它与每个其他矩形相交(并将它们限制为引用矩形)，从而产生不相交的较小矩形的集合，如下所示:

然后只需将它们的所有面积相加并从引用矩形的面积中减去即可。但是我不确定如何最好地做到这一点。欢迎任何其他想法、建议或示例。

谢谢。

Answer 1

令 n 为覆盖矩形的数量。使用平面扫描 (http://en.wikipedia.org/wiki/Sweep_line_algorithm) 和增强的自下而上伸展树(Splay Tree) (http://en.wikipedia.org/wiki/Splay_tree) 可以在 O(n log n) 时间内解决此问题。

1. 将所有覆盖矩形裁剪到引用。

2. 通过排序，将问题简化为覆盖矩形的所有 x 坐标都是 [0, 2n) 中的整数的问题。类似地转换 y 坐标。

3. 创建一个 2n 节点的伸展树(Splay Tree)。节点j的值为开区间(j,j+1)内有多少个矩形与扫描线相交。对于 O(log n) 次更新，不要将 j 的值存储在 j 中，而是将 j 的值与 j 的父值之间的差值存储(根存储其真实值)。旋转稍微复杂一点:旋转

       y          x
      / \        / \
     x   c  ->  a   y
    / \            / \
   a   b          b   c
   

   涉及更新

   b.diff += x.diff;  // if b exists
   x.diff += y.diff;
   y.diff -= x.diff;
   

   每个节点还跟踪其子树的最小值。为了与前面描述的值表示兼容，节点 j 存储其子树最小值与其值的差值。在轮换期间:

   y.diffmin = min(0, b.diffmin + b.diff, c.diffmin + c.diff);
   

   在展开操作结束时，以相同的方式更新根。如果 b 或 c 不存在，则省略。

4. 扫一扫。对于 [0, 2n) 中的 x，找到左侧位于 x 的所有矩形，并按如下方式更新树。对于从 y0 到 y1 的矩形，展开 y1 并增加其左 child 的 diff(并重新计算 diffmin)，然后展开 y0 并减少其左 child 的 diff。

   处理完所有左侧后，检查树最小值。如果它为零，则该引用未被覆盖。

   以几乎相同的方式处理右侧(交换描述中的递增和递减)。