algorithm - 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-Trees

R 树(B-trees 的空间推广)是存储地理空间数据的最佳方式之一，可用于解决此问题。只需将您的矩形存储在 R 树中，您就可以通过简单的 O(n log n) 复杂度来发现交叉点。 (n 次搜索，每次搜索 log n 次)。