Expand rectangles as much as possible to cover another rectangle, minimizing overlap

Question

Given a tiled, x- and y-aligned rectangle and (potentially) a starting set of other rectangles which may overlap, I'd like to find a set of rectangles so that:

if no starting rectangle exists, one might be created; otherwise do not create additional rectangles
each of the rectangles in the starting set are expanded as much as possible
the overlap is minimal
the whole tiled rectangle's area is covered.

This smells a lot like a set cover problem, but it still is... different.

The key is that each starting rectangle's area has to be maximized while still minimizing general overlap. A good solution keeps a balance between necessary overlaps and high initial rectangles sizes.

I'd propose a rating function such as that: $\left( \left( \sum\limits_{n=0}^{initial_boxes_count-1}{{box_area}_n} \right) \times extended_initial_rectangles_count \right) - \left( \sum\limits_{n=0}^{{overlapping_boxes_count}-1}{number_of_overlaps} \right)$

Higher is better.

Examples (assumes a rectangle tiled into a 4x4 grid; numbers in tiles denote starting rectangle "ID"):

easiest case: no starting rectangles provided, can just create one and expand it fully:

.---------------.      .---------------.
|   |   |   |   |      | 1 | 1 | 1 | 1 |
|---|---|---|---|      |---|---|---|---|
|   |   |   |   |      | 1 | 1 | 1 | 1 |
|---|---|---|---|  =>  |---|---|---|---|
|   |   |   |   |      | 1 | 1 | 1 | 1 |
|---|---|---|---|      |---|---|---|---|
|   |   |   |   |      | 1 | 1 | 1 | 1 |
·---------------·      ·---------------·
                       rating: 16 * 1 - 0 = 16

more sophisticated:

.---------------.      .---------------.      .---------------.
| 1 | 1 |   |   |      | 1 | 1 | 1 | 1 |      | 1 | 1 | 2 | 2 |
|---|---|---|---|      |---|---|---|---|      |---|---|---|---|
| 1 | 1 |   |   |      | 1 | 1 | 1 | 1 |      | 1 | 1 | 2 | 2 |
|---|---|---|---|  =>  |---|---|---|---|  or  |---|---|---|---|
|   |   | 2 | 2 |      | 2 | 2 | 2 | 2 |      | 1 | 1 | 2 | 2 |
|---|---|---|---|      |---|---|---|---|      |---|---|---|---|
|   |   | 2 | 2 |      | 2 | 2 | 2 | 2 |      | 1 | 1 | 2 | 2 |
·---------------·      ·---------------·      ·---------------·
         ratings:     (4 + 4) * 2 - 0 = 16   (4 + 4) * 2 - 0 = 16

pretty bad situation, with initial overlap:

.-----------------.      .-----------------------.
| 1   |   |   |   |      |  1  |  1  |  1  |  1  |
|-----|---|---|---|      |-----|-----|-----|-----|
| 1,2 | 2 |   |   |      | 1,2 | 1,2 | 1,2 | 1,2 |
|-----|---|---|---|  =>  |-----|-----|-----|-----|
|     |   |   |   |      |  2  |  2  |  2  |  2  |
|-----|---|---|---|      |-----|-----|-----|-----|
|     |   |   |   |      |  2  |  2  |  2  |  2  |
·-----------------·      ·-----------------------·
    rating: (8 + 12) * 2 - (2 + 2 + 2 + 2) = 40 - 8 = 36

    covering with 1 only:
                         .-----------------------.
                         |  1  |  1  |  1  |  1  |
                         |-----|-----|-----|-----|
                         | 1,2 | 1,2 |  1  |  1  |
                     =>  |-----|-----|-----|-----|
                         |  1  |  1  |  1  |  1  |
                         |-----|-----|-----|-----|
                         |  1  |  1  |  1  |  1  |
                         ·-----------------------·
    rating: (16 + 2) * 1 - (2 + 2) = 18 - 4 = 16

more starting rectangles, also overlap:

.-----------------.      .---------------------.
| 1 | 1,2 | 2 |   |      | 1 | 1,2 | 1,2 | 1,2 |
|---|-----|---|---|      |---|-----|-----|-----|
| 1 |  1  |   |   |      | 1 |  1  |  1  |  1  |
|---|-----|---|---|  =>  |---|-----|-----|-----|
| 3 |     |   |   |      | 3 |  3  |  3  |  3  |
|---|-----|---|---|      |---|-----|-----|-----|
|   |     |   |   |      | 3 |  3  |  3  |  3  |
·-----------------·      ·---------------------·
    rating: (8 + 3 + 8) * 3 - (2 + 2 + 2) = 57 - 6 = 51

The starting rectangles may be located anywhere in the tiled rectangle and have any size (minimum bound 1 tile).

The starting grid might be as big as 33x33 currently, though potentially bigger in the future.

I haven't been able to reduce this problem instantiation to a well-problem, but this may only be my own inability.

My current approach to solve this in an efficient way would go like this:

if list of starting rects empty:
  create starting rect in tile (0,0)
for each starting rect:
  calculate the distances in x and y direction to the next object (or wall)
sort distances in ascending order
while free space:
  pick rect with lowest distance
  expand it in lowest distance direction

I'm unsure if this gives the optimal solution or really is the most efficient one... and naturally if there are edge cases this approach would fail on.

I'm not sure I follow the requirements fully. You have to minimize the overlap and also cover the whole area, right? But you also mention maximizing the rectangle areas, is that the same as covering the whole area, or something else? In example 3, isn't it better to just cover everything with 1 (or 2)? Similar for upper half of example 4. — jdehesa
Yes, that's the added spice. Minimizing overlap but maximizing starting rectangle size is normally a contradiction, but a requirement here. You are right that covering example 3 with all 1 or 2 would satisfy the minimum overlap requirement, but not the "maximize all starting rects" one. A balance of these two is the optimal solution. — Ionic
But do you have some policy to decide which solution is best? E.g. in example 3, you can have: a) your solution, overlap 4, sizes 8 and 12 b) cover everything with 1, overlap 2, sizes 16 and 2 c) cover everything with 1 and 2, overlap 16, sizes 16 and 16. Is there anyway to tell which one is the best trade-off, like a weighting or some additional rule? — jdehesa
"Is there anyway to tell which one is the best trade-off, like a weighting or some additional rule?" Good question. I haven't been able to come up with a good, mathematical weighting function. "Intuitively" (which is a great description for a mathematical problem...) I would say that overlap should be kept low while allowing individual starting rects to grow as much as possible without sacrificing high overlap values. I have been thinking about how to define this before, but was unable to express a balance function. — Ionic
How do you evaluate tile expansion? For instance, is it more valuable to expand a 2x1 tile into a 2x2, or a 10x20 into an 11x20 (more 1x1 tiles, but less percentage increase)? — Prune

Prune Prune · Accepted Answer · 2018-03-22T19:30:55

Proposed attack. Your mileage may vary. Shipping costs higher outside the EU.

Make a list of open tiles
Make a list of rectangles (dimension & corners)

We're going to try making +1 growth steps: expand some rectangle one unit in a chosen direction. In each iteration, find the +1 with the highest score. Iterate until the entire room (large rectangle) is covered.

Scoring suggestions:

Count the squares added by the extension: open squares are +1; occupied squares are -1 for each other rectangle overlapped.

For instance, in this starting position:

-  -  3  3
1  1 12  -
-  -  2  -

...if we try to extend rectangle 3 down one row, we get +1 for the empty square on the right, but -2 for overlapping both 1 and 2.

Divide this score by the current rectangle area. In the example above, we would have (+1 - 2) / (1*2), or -1/2 as the score for that move ... not a good idea, probably.

The entire first iteration would consider the moves below; directions are Up-Down-Left-Right

rect  dir  score
  1    U   0.33 = (2-1)/3
  1    D   0.33 = (2-1)/3
  1    R   0.33 = (1-0)/3
  2    U  -0.00 = (0-1)/2
  2    L   0.00 = (1-1)/2
  2    R   0.50 = (2-1)/2
  3    D   0.00 = (1-1)/2
  3    L   0.50 = (1-0)/2

We have a tie for best score: 2 R and 3 L. I'll add a minor criterion of taking the greater expansion, 2 tiles over 1. This gives:

-  -  3  3
1  1 12  2
-  -  2  2

For the second iteration:

rect  dir  score
  1    U   0.33 = (2-1)/3
  1    D   0.33 = (2-1)/3
  1    R   0.00 = (0-1)/3
  2    U  -0.50 = (0-2)/4
  2    L   0.00 = (1-1)/4
  3    D  -1.00 = (0-2)/2
  3    L   0.50 = (1-0)/2

Naturally, the tie from last time is now the sole top choice, since the two did not conflict:

-  3  3  3
1  1 12  2
-  -  2  2

Possible optimization: If a +1 has no overlap, extend it as far as you can (avoiding overlap) before computing scores.

In the final two iterations, we will similarly get 3 L and 1 D as our choices, finishing with

3  3  3  3
1  1 12  2
1  1  2  2

Note that this algorithm will not get the same answer for your "pretty bad example": this one will cover the entire room with 2, reducing to only 2 overlap squares. If you'd rather have 1 expand in that case, we'll need a factor for the proportion of another rectangle that you're covering, instead of my constant value of 1.

Does that look like a tractable starting point for you?

Expand rectangles as much as possible to cover another rectangle, minimizing overlap

1 Answers