Intersection of N rectangles

Question

I'm looking for an algorithm to solve this problem:

Given N rectangles on the Cartesian coordinate, find out if the intersection of those rectangles is empty or not. Each rectangle can lie in any direction (not necessary to have its edges parallel to Ox and Oy)

Do you have any suggestion to solve this problem? :) I can think of testing the intersection of each rectangle pair. However, it's O(N*N) and quite slow :(

Answer 1

Abstract

Either use a sorting algorithm according to smallest X value of the rectangle, or store your rectangles in an R-tree and search it.

Straight-forward approach (with sorting)

Let us denote low_x() - the smallest (leftmost) X value of a rectangle, and high_x() - the highest (rightmost) X value of a rectangle.

Algorithm:

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)

Complexity analysis

This should work on O(n log n) on uniformly distributed rectangles.

The worst case would be O(n^2), for example when the rectangles don't overlap but are one above another. In this case, generalize the algorithm to have low_y() and high_y() too.

Data-structure approach: R-Trees

R-trees (a spatial generalization of B-trees) are one of the best ways to store geospatial data, and can be useful in this problem. Simply store your rectangles in an R-tree, and you can spot intersections with a straightforward O(n log n) complexity. (n searches, log n time for each).