Finding Overlapping Rectangles in a given set of Axis aligned rectagles

Describe an algorithm that takes an unsorted array of axis-aligned rectangles and returns any pair of rectangles that overlaps, if there is such a pair. Axis-aligned means that all the rectangle sides are either parallel or perpendicular to the x- and y-axis. You can assume that each rectangle object has two variables in it: the x-y coordinates of the upper-left corner and the bottom-right corner.

Solution :

We can use Sweep Line algorithm for this. Create a sorted array of the x-coordinates of the left and the right edges of all the rectangles. The x-coordinates should be annotated with the rectangles they belong and whether they are the left or the right edge of the rectangle. Now, scan the sorted list from left to right, adding each rectangle to a balanced BST when you encounter the left edge of a rectangle and removing the rectangle from the balanced BST when you encounter the right edge of the rectangle. The solution requires the usage of one dimensional range search tree. A range search tree is a tree which is capable of performing range search queries efficiently. The time complexity of a range search query in a range search tree is O(R + logN), where N is the number of nodes in the tree and R is the number of elements in the result set.

First lets see how a search query works in a one dimensional range search tree:
1DRangeSearchTree(k1, k2, v):
    Input : Keys k1 and k2, and a node v of a binary search tree T
    Output : The elements whose keys are greater than or equal to k1 and less than or equal to k2.
    Algorithm :
        if key(v) >= k1 and key(v) <= k2
            ElementsInLeftSubTree = 1DRangeSearchTree(k1, k2, T.left(v))
            ElementsInRightSubTree = 1DRangeSearchTree(k1, k2, T.right(v))
            return ElementsInLeftSubTree U ElementsInRightSubTree  U {element(v)}
        else if key(v) < k1
            return 1DRangeSearchTree(k1, k2, T.right(v))
        else if key(v) > k2
            return 1DRangeSearchTree(k1, k2, T.left(v))

Now lets see the detailed algorithm of the original problem:

1) Sort all left and right rectange edges, according to their X value, into list L.

2) Create a new empty range search tree T, for Y ordering of rectangle tops/bottoms

3) Create a new empty result set RS of unique rectangle pairs

4) Traverse L in ascending order. For all V in L:

   If V.isRightEdge()

      T.remove(V.rectangle.top)

      T.remove(V.rectangle.bottom)

   else

       For all U in T.getRange(V.rectangle.top, V.rectangle.bottom)

         RS.add(<V.rectangle, U.rectangle>)

      T.add(V.rectangle.top)

      T.add(V.rectangle.bottom)

5) return RS

Time complexity is O(R + N log N) where R is the actual number of intersections.

Please note that this algorithm does not consider two rectangles as overlapping if one rectangle is completely within another rectangle. However this can be corrected with a minor tweek in the search algorithm for 1DRangeSearchTree.

Reference : http://stackoverflow.com/questions/3324880/axisaligned-rectangles-intersection