algorithm - 测试轴对齐矩形是否覆盖另一个矩形的快速算法

Question

我们有轴对齐的矩形：{ top, left, width, height: number}
我们要测试给定：

• 轴对齐的矩形列表rs
• 轴对齐的矩形：r

ifr完全被 的并集覆盖rs。

最快的方法是什么？

我发现有快速的数据结构来测试rs和的交集r（例如https://github.com/mourner/rbush），所以我可以先找到rs相交的矩形，r然后从r所有这些矩形中减去，然后看看如果您有任何剩余区域。rs如果没有太多重叠，这似乎效果很好，因为你最终不会有很多相交的矩形。

有更好的解决方案吗？

标签： algorithmspatialcomputational-geometry

Answer 1

你可以想到一个扫描线过程。

按顶部边缘的纵坐标对所有矩形进行排序。然后从顶部边缘移动到顶部边缘，保持更新“活动矩形”列表（即跨越当前水平的所有矩形）。

考虑两个连续水平线之间这些矩形覆盖的水平范围，并检查它们是否完全覆盖了目标矩形的相应切片。