Algorithm to find the optimal way of covering a plane with colored rectangles

Question

Suppose that I open up MS Paint, draw a bunch of solid rectangles, save it as a png, and give it to you:

Now you have to find out how I drew these rectangles. For this image, your algorithm would generate instructions like,

1. Draw the green rectangle (filling up the entire space)
2. Draw the pink rectangle
3. Draw the yellow rectangle
4. Draw the blue rectangle

Or in other words, given an image, I want to generate it using the fewest rectangle commands as possible. A rectangle command draws a solid rectangle given its position, length, width, and color. How can I approach this problem?

The algorithm should be robust enough to process images not only drawn by placing rectangles, but also complex images like photographs.

Answer 1

You would need to find the intersection of two figures, at any point where they intersect find which one is visible. For that point that will give you which one is on top.

Answer 2

You are probably well aware of this, but I'm pretty sure that even with 2 colors this problem is NP-complete. See the section on orthogonal polygons here. The covering problems that they look at are similar, but not exactly the same.

Heuristically I suspect that looking for large monochromatic rectangles will not get you too far from optimal. Once you have done that try to merge adjoining rectangles of the same color by moving a mutually adjacent different colored rectangle forward in the z order.

Answer 3

It's a multi-step process.

Start with these lists: R and S. R is the rectangles (the rectangle draws it uses to build the final image, in order). S is the section (each area of like-colored pixels).

1) Detect any "Perfect" shapes; any rectangle whose color is found NO WHERE EXCEPT that rectangle. There must be at least 1, since the last rectangle could not have been overlapped. Add it to the END of R.

2) Continue (1) until no perfect shapes are left.

3) The next part is tricky. For each section: if that section plus some collective part of all of the rectangles in R, forms a perfect rectangle, insert that rectangle to the beginning of the list, before all other existing rectangles in R.

4) Repeat (3) until there are no more.

Then you're done.