Data structure for adjacent rectangles

Question

I have a file with a list of non-overlapping rectangles covering the entire space (they are adjacent). I would like to plot efficiently the graph edges that connect each rectangle center point with the adjacents rectangle center points. Which is the best data structure to use to load the rectangle list? Which is the best algorithm to find all the adjacent rectangles in x and y directions?

Thank you.

More details: In the picture below a visual example with 12 axis-aligned rectangles. The red paths are the desired output.

The numbering is from the random order in the input file:

rect1   (19,0)  (23,19)
rect2   (0,3)   (4,16)
rect3   (8,17)  (11,19)
rect4   (8,6)   (19,17)
rect5   (0,0)   (11,3)
rect6   (4,3)   (15,6)
rect7   (4,6)   (8,8)
rect8   (15,3)  (19,6)
rect9   (11,0)  (19,3)
rect10  (0,16)  (4,19)
rect11  (4,8)   (8,19)
rect12  (11,17) (19,19)

The desired output is the adjacent combinations of rectangles and their length:

(1,4) (1,12) (1,8) (1,9) (2,5) (2,10) (2,11) (2,7) 
(2,6) (3,4) (3,12) (3,11) (4,6) (4,7) (4,8) (4,11) 
(4,12) (5,6) (5,9) (6,7) (6,8) (6,9) (7,11) (8,9) (10,11)

Answer 1

The sweeping algorithm, suggested by @adrianN, can be elaborated this way.

Step 1. Put all your rectangles in a map of sets in such way, that:

• the map key is left boundary of rectangle
• the map value is ordered by lower boundary set of rectangles, having this left boundary

For your example, this map will be:

0 => (2, 5, 10)
4 => (6, 7, 11)
8 => (3, 4)
11 => (9, 12)
15 => (8)
19 => (1)

Step 2. Create a similar map of rectangle sets, having the same right boundary.

Step 3. Define active rectangle set, which will "sweep" the data structure above, from left to right, generating pairs of adjacent rectangles.

At first assign to the active set the rectangle set with minimal left boundary $x_0$. You can immediately generate a number of pairs of adjacent rectangles from the active set (because it's ordered and there are no "holes" in it).

Then move the active set to the next position of the left boundary, let's say $x_1$. You will need to update the active set, removing rectangles with right boundary $x_1$, and adding rectangles with left boundary $x_1$. You already have these rectangle sets in data structures, created earlier. The active set will be ordered after this update - generate pairs from it.

And so on...

For your example - active sets A0, A1 etc. will be:

A0 = (2, 5, 10)
A1 = (5, 6, 7, 11)
A2 = (5, 6, 4, 3)
A3 = (9, 6, 4, 12)
A4 = (9, 8, 4, 12)
A5 = (1)

This algorithm will generate all pairs of rectangles, adjacent in vertical direction only. Some of pairs will be generated more than once - you'll need to filter repetitions out.

In order to get all pairs of rectangles, adjacent in horizontal direction, you'll need to "rotate the picture" by 90 grades and repeat the algorithm. Another option - much more complex processing of rectangles during the active set update.

Time complexity of this algorithm depends on complexity of set operations union and minus.

Answer 2

I assume your rectangles are axis-parallel.

You can use a sweep-line approach. Sweep over the rectangles once in (say) x-direction. Add a path for all rectangles that intersect your sweep-line to your graph. The interesting points for the sweep line are the ends of your rectangles. If you sort them by their left border you can sweep easily. To construct the path to add to your graph you need to know the y-order of the rectangles that are currently intersecting the sweep-line. Here you can use a list sorted by y-coordinates.