algorithm - 给定一组矩形，是否有重叠？

Question

给定一组表示为元组的矩形 (xmin, xmax, ymin, ymax)其中 xmin和 xmax是左右边缘，ymin和 ymax分别是底部和顶部边缘 - 集合中是否有任何一对重叠的矩形？

一种直接的方法是比较每对矩形的重叠，但这是 O(n^2) - 应该可以做得更好。

更新:xmin , xmax , ymin , ymax是整数。所以矩形 1 和矩形 2 重叠的条件是 xmin_2 <= xmax_1 AND xmax_2 >= xmin_1 ; Y 坐标也类似。

如果一个矩形包含另一个矩形，则认为这对矩形重叠。

Answer 1

您可以通过以下方式在 O(N log N) 方法中完成。

首先，“压缩”您的 y 坐标。也就是说，将所有 y 坐标(顶部和底部)一起排序在一个数组中，然后用排序数组中的索引替换矩形描述中的坐标。现在你的所有 y 都是从 0 到 2n-1 的整数，并且你的问题的答案没有改变(如果你有相等的 y，请参见下文)。

现在你可以将平面分成 2n-1 条，每个单位高度，每个矩形完全跨越其中的几个。为这些条纹准备一个线段树。 (有关线段树概述，请参阅 this link。)

然后，在同一个数组中对所有有问题的 x 坐标(包括左边界和右边界)进行排序，为每个坐标保留它来自哪个矩形以及这是左边界还是右边界的信息。

然后遍历此列表，并在进行时维护当前“事件”的所有矩形的列表，也就是说，您已经看到了左边界但还没有看到右边界。

更准确地说，在您的线段树中，您需要为每个条纹保留多少个事件矩形覆盖它。当您遇到左边界时，您需要为相应矩形的底部和顶部之间的所有条纹加 1。遇到右边界时，需要减一。使用线段树的大规模更新(惰性传播)，加法和减法都可以在 O(log N) 中完成。

为了实际检查您需要什么，当您遇到左边界时，在加 1 之前，检查底部和顶部之间是否至少有一个具有非零覆盖率的条纹。这可以在 O(log N) 中通过对线段树中的区间查询求和来完成。如果此区间上的总和大于 0，则您有交集。

 squeeze y's
 sort all x's
 t = segment tree on 2n-1 cells
 for all x's
     r = rectangle for which this x is
     if this is left boundary
         if t.sum(r.bottom, r.top-1)>0   // O(log N) request
              you have occurence
         t.add(r.bottom, r.top-1, 1)  // O(log N) request
     else
         t.subtract(r.bottom, r.top-1)  // O(log N) request

你应该仔细实现它，考虑到你是否认为触摸是交叉点，这会影响你对相等数字的处理。如果你考虑触摸一个交叉点，那么你需要做的就是，在对 y 进行排序时，确保所有具有相同坐标的点的所有顶部都在所有底部之后，并且类似地当你对 x 进行排序时，确保所有相等的 x 的所有左先于右。