# Algorithm to reduce a bitmap mask to a list of rectangles?

Before I go spend an afternoon writing this myself, I thought I'd ask if there was an implementation already available --even just as a reference. The first image is an example of a bitmap mask that I would like to turn into a list of rectangles. A bad algorithm would return every set pixel as a 1x1 rectangle. A good algorithm would look like the second image, where it returns the coordinates of the orange and red rectangles. The fact that the rectangles overlap don't matter, just that there are only two returned.

To summarize, the ideal result would be these two rectangles (x, y, w, h): `[ { 3, 1, 2, 6 }, { 1, 3, 6, 2 } ]`

-

I don't know any algorithm for that specific problem, but here's an idea how you could tackle this:

1. Let `X` and `Y` be `0`
2. Search and increment `(X, Y)` in your bitmap and visit each pixel from left to right, from top to bottom until you hit an unvisited foreground pixel.
3. Search from `(X, Y)` to the right, until you hit a background pixel or an already visited pixel. Keep the amount of found pixels as `WIDTH`. Set `HEIGHT` to `1`.
4. Start another search at (`X, Y + HEIGHT)` and search `WIDTH` pixels. If all these pixels belong to the foreground, increase `HEIGHT` by `1`.
5. Repeat step 3 until you hit a background pixel in the search. Then you add the rectangle (formed by `X, Y` and `WIDTH`, `HEIGHT`) to the list of found rectangles and mark all the pixels it encloses as visited.
6. Increment `X` by `WIDTH` and continue your search (go to step 2). Your search ends when you reached the bottom right pixel of your bitmap.

The algorithm would produce 3 rectangles for your specific example. To get a result with only 2 rectangles, you would have to alter step 3 so that it only stops at a background pixel and ignores already visited pixels. This however would potentially result in a lot of overlapping rectangles. So step 3 could be optimized further by keeping track of unvisited and visited foreground pixels. If the last pixel (before the background pixel) is a visited pixel, use the last unvisited foreground pixel to get the `WIDTH`.

Update: I went ahead and implemented the algorithm I proposed. Here's an interactive demo where you can try it yourself (click "Play flash full screen", if the display is too small).

Controls: Click and drag in the black area to draw pixels. Hold Shift and draw to erase. Double-click to clear the canvas.

Here's the full source of the flash demo.

-
This question recently got bumped in my SO history, but I honestly have no recollection of even asking this question, let alone why I needed it in the first place. :) That said, your algorithm and source looks like it fits the bill for ...whatever it was I wanted. Thanks. – moswald Sep 25 '15 at 13:51

This problem is underspecified. Because you've provided a single, simplistic example, you have missed some of the important logical possibilities and corner cases here (or, you just haven't explicitly excluded them). For instance, since you don't mention the proposed application for this, you haven't specified what is more important: Breaking up the entire map into exclusive rectangles that have as large an area as possible (the Packing Problem, which has an arbitrary number of solutions), or simply getting edge-matched rectangles in each of x and y, as you seem to imply above. I assume the latter.

Consider the case where you fill in each of the 4 tiles that sit immediately in the corners of the "plus-sign"-shaped bitmask you've drawn above ([2, 2] being the topmost). Now what are the optimal rectangles? Considering just columns, Would you prefer narrower, longer rects with slimmer ones to the sides, or the large, broader square which could now be found in the middle of the image, with squat squares above and below?

Anyway, assuming longest-possible edge-matched rects, take this as a first-attempt solution:

• Break the bitmask down into columns. Each column starts at some value y0 and ends at some other value y1. Store each column as a (y0, y1) tuple in a list.
• Columns: Evaluate the list. Find where adjacent tuples have the same y0 AND y1 between them (eg. column A starts at y0=1 and ends at y1=4; so does column B). For as long as each consecutive column DOES have these the same, increment the width of a rectangle you have created to represent these, by one. As soon as they DO NOT, end this rectangle and store it, and create a new one for any subsequent column groups.

Repeat both of the above steps for rows, exactly as for columns (using x0 and x1 instead, and a separate list, of course).

You should now have some lists of cleanly-edged rectangles. They may however not be optimal for your application; if this is the case, you will need a system of heuristics that enables more efficient packing. See the Packing Problem for more.

-