algorithm - 如何找到覆盖另一个矩形的矩形区域

Question

我有一个点 [xmin,ymin,xmax,ymax] 的列表，每个点都用黑点显示

如何找出哪些矩形被另一个矩形覆盖以及覆盖了多少。该算法应该是高效的。一种解决方案是检查每个矩形与彼此的矩形，这将花费 O(n^2) 的时间复杂度，但我需要高效的算法。

请注意，图中有很多这样的矩形。应该检测到红色的移除，绿色的应该保留。

输入是n个矩形输出是覆盖区域和它覆盖的矩形 ID。最好给出一些算法和解释。

Answer 1

假设矩形列表是L，并且说只有绿色矩形的最终列表是G。矩形可以一个接一个地添加到 G 中。在每次添加之前，都会根据 G 中已有的列表进行检查。如果它与其中之一重叠，请比较它们的大小(面积)。如果它比列表中的大，则替换它，否则不添加到 G。

G 永远不会有两个重叠的矩形(即算法不变)。通过这种方式，您只检查那些最终进入最终名单的候选者。

如果矩形有随机重叠，这肯定比 O(n^2) 更好。但最坏的情况仍然是 O(n^2) - L 中的输入矩形都不重叠。在这种情况下，每个重叠检查都是 O(n) 操作。

但是可以优化重叠检查。通过维护基于 X 和 Y 的排序点列表，可以仅针对最接近矩形的 xmin、xmax、ymin 和 ymax 的点进行重叠检查。我认为这有点棘手，尤其是当新矩形仅部分重叠或与多个矩形重叠时。但这是可以做到的。

在任何情况下，重叠检查都可以在一定程度上加快，因为它不必针对 G 中的所有矩形。我无法量化它，但如果做得正确，我相信它可以在 O(nlogn) 中完成。