我正在寻找解决这个问题的算法:
给定笛卡尔坐标上的 N 个矩形,找出这些矩形的交点是否为空。每个矩形可以位于任何方向(不必使其边缘平行于 Ox 和 Oy)
你对解决这个问题有什么建议吗? :) 我可以考虑测试每个矩形对的交集。然而,它是 O(N*N) 并且相当慢 :(
最佳答案
摘要
根据矩形的最小 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
次)。
关于algorithm - N个矩形的交集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5880558/