给定一组矩形,是否有任何重叠？

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个条纹,每个单位高度,每个矩形完全跨越几个.为这些条纹准备分段树.(有关分段树概述,请参阅此链接.)

然后,对相同数组中的所有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都是左派在所有权利之前.

Answer 2

你为什么不尝试平面扫描算法？平面扫描是一种广泛用于计算几何的设计范例,因此它具有经过充分研究并且可以在线获得大量文档的优点.看看这个.线段交叉问题应该给你一些想法,也就是矩形联合的区域.

阅读有关线段交叉的Bentley-Ottman算法,问题与你的问题非常相似,它有O((n + k)logn),其中k是交点的数量,不过,因为你的矩形边平行于x和y轴,它更简单,因此您可以修改Bentley-Ottman以在O(nlogn + k)中运行,因为您不需要更新事件堆,因为一旦访问了矩形并且赢得了所有交叉点,就可以检测到t修改扫描线顺序,因此无需保留事件.要使用新矩形检索所有交叉矩形,我建议在每个矩形的ymin和ymax上使用范围树,它将为您提供位于由新矩形的ymin和ymax定义的区间中的所有点,从而与它相交的矩形.

如果您需要更多细节,请查看M. de Berg等的第二章.al 计算几何书.另外看看这篇论文,他们展示了如何在O(nlogn + k)中找到凸多边形之间的所有交点,它可能比我的上述建议更简单,因为所有数据条纹都在那里解释,你的矩形是凸的,非常好在这种情况下的事情.