可以使用按矩形最小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树（一种空间泛化的B树）是存储地理空间数据最好的方法之一，对于这个问题非常有用。只需将矩形存储在R树中，您就可以使用简单的O(n log n)复杂度找到交集。（每次搜索n个，每个需要log n时间）。
{ [k, 2n-k]×[0, 1] | k ∈ {0, ..., n-1} }。 - Yakov Galka[k, 2n-k]×[k, 2n-k]仅仅是点矩形吗？ - Adam Matan由于矩形不能平行于坐标轴，将问题转化为已经解决的问题：计算矩形边界的交点。
扫描线在S中的每个x坐标处停止，即所有起始值和所有结束值。对于每个新的起始坐标，将相应的线放入临时集合I中。对于每个新的结束坐标，从I中删除相应的线。
除了向I添加新线之外，还可以检查每条新线是否与当前在I中的某条线相交。如果它们相交，则相应的矩形也会相交。
您可以在此处找到有关此算法的详细说明。
运行时间为O(n*log(n) + c*log(n))，其中c是I中线的交点数。
从集合中选择最小的矩形（或任何矩形），并遍历它内部的每个点。如果其中一个点也存在于所有其他矩形中，则交集不为空。如果所有点都没有被其他矩形占据，则交集为空。