Creating a Tree from a List of Rectangles

Question

This may be a silly question, but nothing comes to mind straight away. Given a list R of 2D rectangles (x, y, w, h) arranged so that any given rectangle is either fully inside or fully outside any other, what's the most efficient way to determine the immediately enclosing rectangle p of each rectangle in R? Currently I sort R by y then x, then go through every pair (a, b) and test whether a is a child of b. Not only is this not very efficient, but it also doesn't work correctly: I figured that since R is already sorted, the last parent found should be the immediately enclosing one, but this doesn't seem to hold. Is there something wrong with my reasoning? If not, I'll post code.

Answer 1

1. Sort by (x+y).
2. Starting at the beginning of the sorted list, grab a rectangle Q.
3. Compute (x+y+w+h) for that rectangle.
4. For each rectangle R in part of the list that follows rectangle Q, and has x+y for R <= (x+y+w+h) of Q, check to see if R is within the bounds of Q. If it is, set Q as the parent of R, overwriting any previously set parent.
5. Repeat for the list.