N个矩形的交点

Question

我正在寻找一种算法来解决这个问题:

给定笛卡尔坐标上的N个矩形,找出这些矩形的交集是否为空.每个矩形可以位于任何方向(不必使其边缘平行于Ox和Oy)

你有什么建议可以解决这个问题吗？:)我可以考虑测试每个矩形对的交集.但是,它是O(N*N)并且非常慢:(

Answer 1

抽象

根据矩形的最小X值使用排序算法,或将矩形存储在R树中并进行搜索.

直接进场(带分拣)

让我们表示low_x()- 矩形的最小(最左边)X值,以及high_x()- 矩形的最高(最右边)X值.

算法:

Sort the rectangles according to low_x().                   # O(n log n)

For each rectangle in sorted array:                         # O(n)
    Finds its highest X point.                              # O(1)
    Compare it with all rectangles whose low_x() is smaller # O(log n)
        than this.high(x)

复杂性分析

这应该适用于O(n log n)均匀分布的矩形.

最糟糕的情况是O(n^2),例如当矩形不重叠但是一个在另一个之上时.在这种情况下,推广的算法有low_y()和high_y()太.

数据结构方法:R树

R树(B树的空间概括)是存储地理空间数据的最佳方式之一,并且可以在这个问题中有用.只需将矩形存储在R树中,您就可以通过简单的O(n log n)复杂性来发现交叉点.(n搜索,log n每个时间).

Answer 2

观察 1：给定一个多边形 A 和一个矩形 B，交集 A \xe2\x88\xa9 B 可以通过与 B 的每条边对应的半平面的 4 个交集来计算。

\n\n

观察 2：从凸多边形切割半平面得到凸多边形。第一个矩形是凸多边形。此操作最多每增加 1 个顶点数。

\n\n

观察3：凸多边形顶点到直线的有符号距离是单峰函数。

\n\n

这是算法的草图：

\n\n

按 CCW 顺序维护平衡二叉树中当前的部分交集 D。

\n\n

当切割由线 L 定义的半平面时，找到 D 中与 L 相交的两条边。这可以通过利用到 L 的有符号距离的单峰性进行一些巧妙的二元或三元搜索，在对数时间内完成。部分我不太记得了。）从D中删除L一侧的所有顶点，并将交点插入到D中。

\n\n

对所有矩形的所有边 L 重复此操作。

\n