如何判断一个矩形是否被其上方的矩形遮挡？

Question

如何判断一个矩形是否被其上方的矩形遮挡？

algorithmlanguage-agnostic

3

我有一个矩形集合和一个参考矩形。我想找出参考矩形是否被它上面的所有矩形（即集合中的所有矩形）完全遮挡。例如：

明显的解决方案是创建一个布尔矩阵或位图，然后简单地绘制所有矩形并检查是否有任何未覆盖的部分，但这不是一个选择。这将需要每秒执行很多次。

我想出了这个想法：对于每个矩形，将其与每个其他矩形相交（并将它们限制在参考矩形内），从而得到一组不相交的较小矩形，如下所示：

然后只需添加它们的所有区域并从参考矩形的区域中减去即可。然而，我不确定最佳方法是什么。欢迎提出其他想法、建议或示例。

谢谢。

- fingerprint211b

所有矩形都始终与x轴和y轴对齐吗？另请参阅 SO 上的此问答。 - Bart Kiers

是的，总是。 - fingerprint211b

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- a dabbler · Accepted Answer

假设有n个覆盖矩形，可以使用平面扫描（扫描线算法）和增强的自底向上splay树（伸展树）以O(n log n)的时间解决此问题。

Clip all covering rectangles to the reference.
By sorting, reduce the problem to one where all x-coordinates of the covering rectangles are integers in [0, 2n). Transform the y-coordinates similarly.
Create a 2n-node splay tree. The value of node j is how many rectangles intersect the sweep line in the open interval (j, j + 1). For O(log n)-time updates, don't store j's value in j but rather the difference between j's value and j's parent's value (the root stores its true value). Rotations are slightly more complicated: the rotation
```
    y          x
   / \        / \
  x   c  ->  a   y
 / \            / \
a   b          b   c
```
involves updating
```
b.diff += x.diff;  // if b exists
x.diff += y.diff;
y.diff -= x.diff;
```
Each node also tracks its subtree minimum. For compatibility with the value representation previously described, node j stores the difference of its subtree minimum and its value. During a rotation:
```
y.diffmin = min(0, b.diffmin + b.diff, c.diffmin + c.diff);
```
At the end of a splay operation, update the root the same way. Omit b or c if they don't exist.
Sweep the line. For x in [0, 2n), find all rectangles whose left-hand side is at x and update the tree as follows. For a rectangle from y0 to y1, splay y1 and increment the diff of its left child (and recompute diffmin), then splay y0 and decrement the diff of its left child.

After all left-hand sides have been processed, check the tree min. If it's zero, then the reference is not covered.

Process the right-hand sides in much the same way (swap increment and decrement in the description).