Calculate the border around multiple connected rectangles
I am working on a project where I need to create a border around a group of rectangles.
Let's use this image as an example of what I want to accomplish.
EDIT: Couldn't get the image tag to work correctly, so here is the full link: http://www.flickr.com/photos/ 21093416 @ N04 / 3029621742 /
We have rectangles A and C, which are connected by a special reference rectangle B. You can think of this as two nodes in the graphic (A, C) and the edge between them (B). This means that the rectangles have pointers to each other like this: A-> B, A <-B-> C, C-> B
Each rectangle has four vertices stored in an array, with index 0 at the bottom left and index 3 at the bottom right.
I want to "traverse" this linked structure and calculate the vertices that make up the border (red line) around it. I already have some small ideas on how to do this, but want to know if some of you are more mathematically inclined with some neat tricks up your sleeves.
The reason I am posting this is because someone might have solved a similar problem before, and there are some ideas I could use. I did not expect anyone to sit down and think long and hard. I will work on the solution in parallel while awaiting answers.
Any input is greatly appreciated.
source to share
Using an example where the rectangles are perpendicular to each other and therefore can be represented 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 x coordinates (both left and right) into a list, then sort it and remove duplicates
1 3 4 5 6
2) collect all 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 the number of gaps between unique x coordinates * by the number of spaces between unique y coordinates. It only needs to be one bit per cell, so in C ++ the vector <bool> will probably give you a very economical 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 mesh cell for each edge, if the cell next to it in that cardinal direction is not colored, draw a line border for that edge
In this question, rectangles are described as four vectors, each representing an angle. If each rectangle can be arbitrary and different rotation from the others, then the above approach won't work. The problem of finding a path around a complex polygon is regularly tackled with vector graphics rasterizers, and a good approach to solving the problem is to use a library like Cairo to get your job done!
source to share
A generalized solution to this problem is to implement Boolean operations in terms of a scan line. You can find a short discussion here to get you started. From the text:
"Boolean algorithms are based on scan lines. For the fundamentals, the book: Computational Geometry Introduction by Franco P. Preparations and Michael Ian Chamos is very good."
I have this book, even though it's in the office right now, so I can't seem to find the page numbers you should read, although Chapter 8 on the geometry of rectangles is probably the best starting point.
source to share
- Calculate the sum of the boundaries of all three rectangles separately
- calculate the overlapping rectangle A and B and subtract it from the sum
- Do the same for overlapping rectangle B and C
(to get an overlapping rectangle from A and B, take the middle 2 X positions along 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:
- 10 + 8 + 10 = 28
- X coordinates ordered = 1,3,3,5, middle two - 3 and 3
Y ordered orders = 1,2,4,4 middle two - 2 and 4
like this: (3,2) - (3,4): boundery = 4 - X orders ordered = 3,4,5,6, middle two - 4 and 5
Y ordered orders = 2,3,4,6 Middle two - 3 and 4
like this: (4,3) - (5,4): boundery = 4 - 28 - 4 - 4 = 20
This is my example:
1 2 3 4 5 6
1 +---+---+
| |
2 + A +---+---+
| | B |
3 + + +---+---+
| | | | |
4 +---+---+---+---+ +
| |
5 + C +
| |
6 +---+---+
source to share
After some thought, I could do something like this:
Pseudocode:
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 pseudocode needs to be a bit refined and may not cover all cases, but I think I could solve my own problem.
source to share
I didn't think about it completely, but I'm wondering if you could do something like:
- List all the ribs.
- Get all edges where P1.X = P2.X
- In this list, get pairs where X is
- For each pair, replace with one or two edges for parts where they do NOT overlap.
- Do something smart to get the ribs in the right order
Will your rectangles always be horizontally aligned unless you need to do the same, but for Y too? And are they always guaranteed to touch? If the algorithm hadn't been broken, the "correct order" would not have been determinable.
source to share