Search code examples
algorithmrectangles

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

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:

programmer art

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?

Solution

  • 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.