Calculating a boundary around several linked rectangles.

Question

Hi,I am working on a project where I need to create a boundary around a group of rectangles.

Let's use this picture as an example of what I want to accomplish.

EDIT: Couldn't get the image tag to work properly, so here is the full link: http://www.flickr.com/photos/21093416@N04/3029621742/

We have rectangles A and C who are linked by a special link rectangle B. You could think of this as two nodes in a graph (A,C) and the edge between them (B). That means the rectangles have pointers to each other in the following manner: A->B, A<-B->C, C->B

Each rectangle has four vertices stored in an array where index 0 is bottom left, and index 3 is bottom right.

I want to "traverse" this linked structure and calculate the vertices making up the boundary (red line) around it. I already have some small ideas around how to accomplish this, but want to know if some of you more mathematically inclined have some neat tricks up your sleeves.

The reason I post this here is just that someone might have solved a similar problem before, and have some ideas I could use. I don't expect anyone to sit down and think this through long and hard. I'm going to work on a solution in parallell as I wait for answers.

Any input is greatly appreciated.

Answer 1

A simple trick should be:

1. Create a region from the first rectangle
2. Add the other rectangles to the region
3. Get the boundary of the region (somehow? :P)

Answer 2

After some thinking I might end up doing something like this:

Pseudo code:

 LinkRectsConnectedTo(Rectangle rectangle,Edge startEdge) // Edge can be West,North,East,South 
    for each edge in rectangle starting with the edge facing last rectangle
       add vertices in the edge to the final boundary polygon
       if edge is connected to another rectangle
          if edge not equals startEdge
             recursively call LinkRectsConnectedTo(rectangle,startEdge)

Obvisouly this pseudo code would have to be refined a bit and might not cover all cases, but I think I might have solved my own problem.

Answer 3

I haven't thought this out completely, but I wonder if you couldn't do something like:

• Make a list of all the edges.
• Get all the edges where P1.X = P2.X
• In that list, get the pairs where X are equal
• For each pair, replace with one or two edges for the parts where they DON'T overlap
• Do something clever to get the edges in the right order

Will your rectangles always be horizontally aligned, if not you'd need to do the same thing but for Y too? And are they always guaranteed to be touching? If not the algorithm wouldn't be broken, but the 'right order' wouldn't be definable.

Answer 4

1. Calculate the sum of the boundaries of all 3 rectangles seperately
2. calculate the overlapping rectangle of A and B, and subtract it from the sum
3. Do the same for the overlapping rectangle of B and C

(to get the overlapping rectangle from A and B take the middle 2 X positions, together with the middle 2 Y positions)

Example (x1,y1) - (x2,y2):

• Rectangle A: (1,1) - (3,4)
• Rectangle B: (3,2) - (5,4)
• Rectangle C: (4,3) - (6,6)

Calculation:

1. 10 + 8 + 10 = 28
2. X coords ordered = 1,3,3,5 middle two are 3 and 3
   Y coords ordered = 1,2,4,4 middle two are 2 and 4
   so: (3,2) - (3,4) : boundery = 4
3. X coords ordered = 3,4,5,6 middle two are 4 and 5
   Y coords ordered = 2,3,4,6 middle two are 3 and 4
   so: (4,3) - (5,4) : boundery = 4
4. 28 - 4 - 4 = 20

This is my example visualized:

   1   2   3   4   5   6

1  +---+---+
   |       |   
2  +   A   +---+---+
   |       | B     |
3  +       +   +---+---+
   |       |   |   |   |
4  +---+---+---+---+   +
               |       | 
5              +   C   +
               |       |
6              +---+---+

Answer 5

The generalized solution to this problem is to implement boolean operations in terms of a scanline. You can find a brief discussion here to get you started. From the text:

"The basis of the boolean algorithms is scanlines. For the basic principles the book: Computational Geometry an Introduction by Franco P. Preparata and Michael Ian Shamos is very good."

I own this book, though it's at the office now, so I can't look up the page numbers you should read, though chapter 8, on the geometry of rectangles is probably the best starting point.

Answer 6

Using the example, where rectangles are perpendicular to each other and can therefore be presented by four values (two x coordinates and two y coordinates):

   1   2   3   4   5   6

1  +---+---+
   |       |   
2  +   A   +---+---+
   |       | B     |
3  +       +   +---+---+
   |       |   |   |   |
4  +---+---+---+---+   +
               |       |
5              +   C   +
               |       |
6              +---+---+

1) collect all the x coordinates (both left and right) into a list, then sort it and remove duplicates

1 3 4 5 6

2) collect all the y coordinates (both top and bottom) into a list, then sort it and remove duplicates

1 2 3 4 6

3) create a 2D array by number of gaps between the unique x coordinates * number of gaps between the unique y coordinates. It only needs to be one bit per cell, so in c++ a vector<bool> with likely give you a very memory-efficient version of this

4 * 4

4) paint all the rectangles into this grid

   1   3   4   5   6

1  +---+
   | 1 | 0   0   0
2  +---+---+---+
   | 1 | 1 | 1 | 0
3  +---+---+---+---+
   | 1 | 1 | 1 | 1 |
4  +---+---+---+---+
     0   0 | 1 | 1 |
6          +---+---+

5) for each cell in the grid, for each edge, if the cell beside it in that cardinal direction is not painted, draw the boundary line for that edge

---

In the question, the rectangles are described as being four vectors where each represents a corner. If each rectangle can be at arbitrary and different rotation from others, then the approach I've outlined above won't work. The problem of finding the path around a complex polygon is regularly solved by vector graphics rasterizers, and a good approach to solving the problem is using a library such as Cairo to do the work for you!