3
$\begingroup$

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.

enter image description here

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)
$\endgroup$
  • $\begingroup$ Are two rectangles adjacent if they touch in only one point? $\endgroup$ – adrianN Jan 25 '17 at 16:03
  • $\begingroup$ It'd be nice to see a picture of what you want... And "the entire space" means (part of) plane, right? $\endgroup$ – HEKTO Jan 25 '17 at 21:11
  • $\begingroup$ The rectangle are axis-parallel and are not considered adjacent if they touch only one point but they have to share a finite length segment. @HEKTO You are right, I added the picture to better explain :) $\endgroup$ – Enialis Jan 25 '17 at 22:53
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for the detailed answer! Just two comments. Step 2 I guess can be optimized because the two maps share the same key (for each right key there is a left one in this problem with 'no holes', apart from the first and last element). Instead of Active sets, I can update a BST. So A0 is the status of the tree after the first step, I can extract the tuples I am interested and update it to A1, I extract again the tuples filtering what was already extracted. Is this a good approach? $\endgroup$ – Enialis Jan 26 '17 at 11:52
  • $\begingroup$ Yes, I agree. There is a number of "switch points" on $OX$ axis, and for each of them you need two sets of rectangles, "touching" the point from the left and from the right. The BST is OK, any good ordered set implementation will work $\endgroup$ – HEKTO Jan 26 '17 at 15:06
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for the insight :) I didn't know this algorithm. So if I correctly understood I can load the rectangles in whatever data-structure (let's say a linked list), this is not used for the solution. Then I have to take all the endpoints and create a sorted list in x-direction. I sweep along this 'events' list detecting the horizontal paths. I repeat the scan/procedure for y direction. Is this correct? Do you have a pseudo-code or suggestions for an efficient (less than O(n^2) ) sweep scan? Thanks!! $\endgroup$ – Enialis Jan 25 '17 at 23:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.