Minimize overlap in random rectangles

Question

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

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

Some can overlap with only one corner:

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

Some may be contained inside another rectangle:

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

Some may go through another rectangle:

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

and etc.

I am trying to find an algorithm that gives me a set of rectangles that represent the same area as a set of input data, but without overlapping. Some cases are obvious - the rectangles contained in the large rectangle can be discarded, and the rectangles that overlap at the corner can be divided into three rectangles, as well as the rectangles that pass through another rectangle. I'm looking for this is a general algorithm that applies to all of these cases. I don’t care if it is not brilliantly effective - the input set is quite small (maximum 25 rectangles)

Finding rectangles that overlap is easy, but it becomes more difficult from them, especially when you consider that one rectangle can overlap with several other rectangles.

It makes my head. Any suggestions?

Update:

I just realized one more thing:

I can either run this algorithm at a time when the rectangles are added, if it is installed one after the other, or after all the rectangles are added. This might be easier to do as the rectangles are added, since you only have one rectangle, but you still need to consider the situation where one rectangle overlaps several other rectangles.

Answer 1

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

You can use KD-Trees .

Or, if you want something homemade and not necessarily effective, you can "format" and then, if necessary, merge the rectangles back.

By “rectangularity” I mean that you first find a larger rectangle in which all the rectangles fit (basically a rectangle formed by the smallest left edge, the adjusted right edge, the smallest extreme edge, the largest upper edge).

Now align all the edges of the rectangles to cut a large rectangle. Now you have the "squareness". Basically, all of this means that you sort the vertical edges and the horizontal edges and select adjacent pairs to form a small rectangle. For each small rectangle, you can now check whether it is part of the area of ​​interest or not, and reject it if it is absent (it is completely filled or completely closed).

Now you have a list of small rectangles (maybe O (n ^ 2), in your case maybe ~ 2500) that make up your area of ​​interest. If the number is small enough for your future processing, you can simply use them or combine them together to reduce the number of rectangles.

To merge, you can consider a rectangle and consider 4 possibilities for merging (an adjacent rectangle of the same height to the right or left, or an adjacent rectangle of the same width from above or below).

You can speed up some processing (not only when merging) by maintaining a sorted list of edges (both horizontal and parallel) and possibly some hash tables.

Answer 2

First, create a set of all “atomic” rectangles in the composition, i.e. areas formed by the intersections of the rectangle and not separated by themselves. Each actual rectangle spans 1 or more atomic rectangles. Then follow a combinatorial optimization algorithm, for example. SETCOVER to calculate the minimum number of rectangles you need to cover.

Here is 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 | | | +-----+ | +--+-------+ 

Rectangles cover atomic regions according to this table:

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

Now the problem with SETCOVER is to select the smallest subset of rectangles {A, B, C} to cover all atomic regions when you assemble the atomic regions covered by rectangles. Minimal solution (obviously)

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

Note that here the areas are non-rectangular, for example. area 3 has a complex shape. You can get rid of this problem with the following approach: take all the clear X-coordinates of the corner points of the source rectangles and consider them as the X-coordinates of the grid and do the same for the Y-coordinates; then each rectangle covers a set of grid squares that are never subdivided, that is:

  +---------+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 5 regions; in fact, they are already marked :) (A, B, C, *, #)

Answer 3

A very interesting question - I think it’s best to solve the problem a couple of rectangles at a time, and not look at 3 or more at a time. Start by dropping those in the other rectangles. Now you have only 3 types of intersections - angular overlap and transition through overlap and partial overlap (where the rectangle does not go all the way). Each of them creates a new set of rectangles, right?

Enter the starting rectangles from 1 to N. Starting with the rectangle, 1 loop until you find the intersecting rectangle. Create new rectangles. Delete the two intersecting rectangles and add 3 or more newly created rectangles to your set and start over.

The result will be a whole bunch of non-overlapping rectangles. Does this create the smallest rectangles? Probably not, but you did not indicate that it is important to minimize the number of rectangles. Is this time o (n ^ 2)? Maybe.

Answer 4

Unless you have a limit on the number of rectangles your algorithm should produce, you can definitely be reckless in your treatment!

1. The easiest solution ever

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

2. Minimalist solution?

Well, that was reckless, but I don’t think you should worry about the input set. The problem is actually different:

Lift the adjacent 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 that means that you have several contiguous areas that you can work independently.

Now I freely admit that I do not know the best solution to this problem, there are various approaches that I can imagine, and I do not know their results or results. KD-Tree should give a decision, I don't know if this is minimalist though!

Answer 5

If you don’t have a set of rectangles yet, you can approach it from the other side - start with a large rectangle and divide it until you have a set with which you can work - this ensures that you do not overlap.

Start with a whole rectangle

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

Separate at a random point and save two rectangles.

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

Divide a random rectangle at a random point

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

repeat.,.

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

Stop when you have the required number of rectangles.

You can make it create the “randomness” you want by more carefully selecting the rectangle that you are going to split each time etcc