Finding the smallest set of rectangles that covers the given rectilinear simple polygons

Question

For collision detection I'd like to turn a bitmap into a set of rectangles, using as few rectangles as possible. A more formal description of the problem is described in the title. An example:

For tie-breakers of multiple solutions I'd prefer it if the total area covered by all the rectangles combined was maximized. For example, the blue rectangle in the above picture could've been smaller, but that would've been a less optimal solution.

Is there a more common name for this problem? Any literature? Or a simple algorithm that gives an optimal solution?

Answer 1

I managed to solve the problem in a way that was good enough - it's probably not optimal though.

1. Make a 2D array with the dimensions of the bitmap. For every pixel in the bitmap that's black make the corresponding element WALL, otherwise EMPTY_SPACE.

2. Scan the array left-right, top to bottom for the first EMPTY_SPACE. Save this coordinate.

3. Create a rectangle of area 1 with the topleft coordinate set to the coordinate found at 2, extending 1 downwards and to the right.

4. Horizontally extend the rectangle to the left and to the right as long as it doesn't cover any WALL.

5. Vertically extend the rectangle up and down as long as it doesn't cover any WALL.

6. Mark any element covered by the rectangle as a COVERED_SPACE and add the rectangle to the set of rectangles.

7. If there is still an element containing EMPTY_SPACE left goto 2, otherwise you're done.

Answer 2

This problem may be NP-hard, but if you want the highest quality solutions for instances not created by an NP-hardness reduction, then running an integer programming solver is worth a try. Even if running time is a concern, it may be useful to have a gold standard to compare against.

In essence you're trying to solve a special case of a problem called set cover. This is how set cover can be formulated as an integer program.

minimize sum_{white rectangles R} x_R
subject to
for all white points p, sum_{white rectangles R such that p in R} x_R >= 1
for all white rectangles R, x_R in {0, 1}

All you have to do is write code to construct the specific instance of this integer program corresponding to its input, call the solver, get the results back, and then do one more optimization with the optimal number of rectangles (k) known.

maximize sum_{white rectangles R} area(R) x_R
subject to
for all white points p, sum_{white rectangles R such that p in R} x_R >= 1
for all white rectangles R, x_R in {0, 1}
sum_{white rectangles R} x_R <= k

If the instances are large, then you may need to do some preprocessing (the solvers typically can do this as well, but they have to use algorithms for a more general problem, which may not be as efficient). First, use only the white rectangles that are maximal, that is, are not contained in a larger white rectangle. There probably are clever algorithms for enumerating them, but you should implement the naive one and benchmark the whole system first. Second, use only some of the points. In particular, if p and q are distinct points, and p belongs to every maximal rectangle to which q belongs, then tracking p is superfluous.

Answer 3

I suggest simply starting at an external corner which is not yet covered by a rectangle, and greedily growing that rectangle. Repeat until everything's covered. I don't think this gives you the tie-breaker property you're looking for on a global basis (since you may have multiple options for how to greedily grow each rectangle), but it does on a local basis.