minimizing overlap in random rectangles

Question

Hi,

I have a number of possibly overlapping rectangles, of random size and position within a fixed plane. Since these rectangles are random, some may not overlap:

|-----
|    |    |----|
|----|    |    |
          |----|

Some may overlap by just one corner:

|-----|
|  |--|--|
|--|--|  |
   |-----|

Some may be contained inside another rectangle:

|----------------|
|                |
|   |-----|      |
|   |     |      |
|   |-----|      |
|----------------|

Some may pass through another rectangle:

   |----------------|
   |                |
|--|-------------------|
|  |                |  |
|--|-------------------|
   |----------------|

etc.

I'm trying to find an algorithm that gives me a set of rectangles that represent the same area as the input set, but without overlapping. Some cases are obvious - rectangles contained within a larger rectangle can be discarded, and rectangles that overlap on a corner can be split into three rectangles, as can rectangles that pass through another rectangle. What I'm looking for, is a generic algorithm that deals with all these cases. I don't care much if it's not brilliantly efficient - the input set is rather small (25 rectangles at most)

Finding rectangles that overlap is easy, but it quickly gets harder from there, especially when you consider that one rectangle may overlap with multiple other rectangles.

This is doing my head in. Any suggestions?

Update:

I just realised one more thing:

I can either run this algorithm at the time that the rectangles are added tot he set, one by one, or after all the rectangles have been added. It may be easier to do it as the rectangles are being added, since you only have one rectangle to consider, but you still need to account for the situation where a single rectangle overlaps multiple other rectangles.

Answer 1

First create the set of all "atomic" rectangles in the composition, i.e. areas formed by the rectangle intersections and not being subdivided themselves. Every actual rectangle covers 1 or more atomic rectangles. Then run a combinatorial optimization algorithm e.g. SETCOVER to calculate the minimum number of rectangles you need to cover them all.

Here an illustration of the approach. You have three rectangles (A,B,C). They create 5 atomic regions (1-5):

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

The rectangles cover the atomic regions according to this table:

 A  {1,2,4}
 B  {2,3,4,5}
 C  {4,5}

The SETCOVER problem is now to select a minimal subset of the rectangles {A,B,C} so that all the atomic regions are covered when you put together the atomic regions covered by the rectangles. The minimal solution is (obviously)

 A {1,2,4} + B {2,3,4,5} = {1,2,3,4,5}

Note that here the areas are non-rectangular, e.g. area 3 has a complex shape. You can get rid of this problem by the following approach: take all the distinct X-coordinates of the corner points of the original rectangles and consider them as X-coordinates of a grid and do the same thing for the Y-coordinates; then every rectangle covers a set of grid squares which are never subdivided, i.e.:

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

 |    |  | |   | |

Which gives you the following 5x5 grid:

 AAA      A = rectangle A only
 A**BB    B = rectangle B only
 A*#CB    * = A and B
  BCCB    C = rectangles C and B
  BBBB    # = All

From this you can easily extract the 5 regions; as a matter of fact, they have been already marked :) (A,B,C,*,#)

Answer 2

If you don't already have a set of rectangles, you could approach it from the other way - start with a large rectangle and subdivide it until you have a set that you can work with - that will ensure that you have no overlaps.

Start with a whole rectangle

--------
|      |
|      |
|      |
|      |
|      |
--------

Split at a random point and store the two rectangles.

--------
|      |
|------|
|      |
|      |
|      |
--------

Split a random rectangle at a random point

--------
|      |
|------|
| |    |
| |    |
| |    |
--------

repeat . . .

--------
|      |
|------|
| |    |
| |----|
| |    |
--------

Stop when you have the required number of rectangles.

You could make this produce the kind of 'randomness' that you want by choosing more carefully the rectangle that you are going to split each time etcc

Answer 3

Are the rectangles parallel to the x&y axes? I suppose they are.

You can try using KD-Trees.

Or if you want something homegrown and not necessarily efficient you could 'rectangulate' and then if needed merge rectangles back.

By 'rectangulation' I mean you first find a bigger rectangle in which all rectangles fit (basically the rectangle formed by least left edge, greated right edge, least bottom edge, greatest top edge).

Now extend out all the edges of the rectangles to cut across the big rectangle. You now have a 'rectangulation'. Basically all this means is that you sort the vertical edges and the horizontal edges and pick adjacent pairs to form a small rectangle. For each small rectangle, you can now check if this is part of the interesting area or not and reject it if it is not (It is either full within or fully outside).

Now you have a list of small rectangles (possibly O(n^2), in your case perhaps ~2500) which make up the area of your interest. If the number is sufficiently small enough for your future processing, you could just use these, or you could merge them together to reduce the number of rectangles.

To merge you could consider a rectangle and consider 4 possiblitlies for a merge (adjacent rectangle of same height to right or left, or adjacent rectangle of same width to top or bottom).

You could speed up some processing (not just during merge) by maintaining a sorted list of edges (both horizontal and parallel) and maybe some hashtables.

Answer 4

Very interesting question - I think it's best to solve the problem a pair of rectangles at a time rather than looking at 3 or more at one time. Start by discarding those within other rectangles. Now you only have 3 kinds of intersections - corner overlap and pass through overlap and partial overlap (where the rectangle doesn't pass all the way through). These each create a new set of rectangles, right?

Number your starting rectangles from 1 to N. Starting with rectangle 1 cycle through until you find an intersecting rectangle. Create new rectangles. Delete the two intersecting rectangles and add the 3 or more newly created rectangles to your set and start again.

The result will be a whole bunch of non-overlapping rectangles. Does this create the fewest rectangles? Probably not, but you didn't specify that minimizing the number of rectangles was important. Does it take over o(n^2) time? Probably.

Answer 5

If you don't have any constraint on the number of rectangles that your algorithm should produce, you can definitely be rash in your treatment!

1. Easiest solution ever

Create a set of all the squares (of area 1) that are covered by the rectangles of the input set. A square being a rectangle... there you are!

2. Minimalist solution ?

Okay, that was rash, however I don't think you should worry about the input set. You problem is in fact different:

Pick up a contiguous area with a complex shape and try and cover it exactly with rectangles, minimizing their number and so that they do not overlap.

Of course, your area may not be contiguous, but it just means you have several contiguous areas you can work on independently.

Now, I freely admit I do not know the best solution for this problem, there are various approaches I can envision and I don't know their performances or result. KD-Tree should yield a solution, don't know if it's the minimalist one though!