How to find free area rectangles?

Question

Can anyone help me on how to draw rectangles for space in a bounding box region with n rectangular obstacles? There could be any number of axis parallel rectangular obstacles, this is not a unique case, thus different corner cases needs to be taken into consideration. Is it best to use maximal horizontal strip algorithm? And how?

Problem Description:

1.SUB1 and SUB2 are the obstacles and you will not touch the internal of SUB1 and SUB2, you need to find all the free areas externally to all SUBs and create rectangles out of them.

2.You will need to find all the possible rectangles on the free areas rectangles accordingly with its sweep through from left to right without intersecting the SUBs;

The total number of maximal horizontal space rectangles in this case should be 7 or in general, 3n+2 (where n being the number of obstacles):

Click to view images: http://img25.imageshack.us/img25/452/pic1gts.png http://img22.imageshack.us/img22/3417/pic2h.png http://img16.imageshack.us/img16/5818/pic3h.png http://img13.imageshack.us/img13/2151/pic4.png

Answer 1

Are you looking for the simplest algorithm, or the one that finds the optimally fewest split rectangles?

Start with the easiest-to-code algorithm as a baseline, which is likely good enough for many applications by itself. This is easy to write and understand.

Initialize your list of rectangles to include just one, the screen rectangle.

Now, for each obstacle, iterate through the rectangle list. If the rectangle intersects with the obstacle, remove the rectangle from the list and insert new, smaller rectangles that avoid the obstacle. This is a small subproblem, easy to solve by just looking at what part of the obstacle intersects the rectangle. You may end up with 0, 1, 2, 3, or 4 new subrectangles. (consider the six cases where the obstacle intersects one corner, two corners, all corners, no corners and no edge, no corners and 1 edge, no corners and 2 edges.)

Repeat for all obstacles, and you're left with a list of split rectangles that cover your area without hitting the obstacles. It's not optimally few, but it's a good place to start and 10 minutes to code.

Answer 2

Yes, I am looking to find the optimally fewest split rectangles.

I would like to get a little bit of clarification on your suggestion. "Initialize your list of rectangles to include just one, the screen rectangle".

By screen rectangle, do you mean the outer bounding canvas? Then, I would only have a single rectangle in the Rectangle List.

"Now, for each obstacle, iterate through the rectangle list. If the rectangle intersects with the obstacle, remove the rectangle from the list and insert new, smaller rectangles that avoid the obstacle."

To proceed with above, should I make comparison based on each collinear edges of the obstacles (4 edges - left, right, top, bottom)? Meaning each SUB1 and SUB2 edges at 4 corner points are examine to see whether it intersects with each other or the canvas bounding box. Is this right?

Answer 3

The corner-stitching data structure can do this for you. I don't know of any open-source implementations though. The original, or at least canonical, paper for this is Ousterhout (of Tcl fame): http://www.eecs.berkeley.edu/Pubs/TechRpts/1983/6352.html