Minimum number of rectangles in shape made from rectangles?

Question

I'm not sure if there's an algorithm that can solve this.

A given number of rectangles are placed side by side horizontally from left to right to form a shape. You are given the width and height of each.

How would you determine the minimum number of rectangles needed to cover the whole shape? i.e How would you redraw this shape using as few rectangles as possible?

I've can only think about trying to squeeze as many big rectangles as i can but that seems inefficient. Any ideas?

Edit: You are given a number n , and then n sizes: 2 1 3 2 5

The above would have two rectangles of sizes 1x3 and 2x5 next to each other. I'm wondering how many rectangles would i least need to recreate that shape given rectangles cannot overlap.

Answer 1

Since your rectangles are well aligned, it makes the problem easier. You can simply create rectangles from the bottom up. Each time you do that, it creates new shapes to check. The good thing is, all your new shapes will also be base-aligned, and you can just repeat as necessary.

---

First, you want to find the minimum height rectangle. Make a rectangle that height, with the width as total width for the shape. Cut that much off the bottom of the shape.

You'll be left with multiple shapes. For each one, do the same thing.

Finding the minimum height rectangle should be O(n). Since you do that for each group, worst case is all different heights. Totals out to O(n²).

For example:

In the image, the minimum for each shape is highlighted green. The resulting rectangle is blue, to the right. The total number of rectangles needed is the total number of blue ones in the image, 7.

---

Note that I'm explaining this as if these were physical rectangles. In code, you can completely do away with the width, since it doesn't matter in the least unless you want to output the rectangles rather than just counting how many it takes.

You can also reduce the "make a rectangle and cut it from the shape" to simply subtracting the height from each rectangle that makes up that shape/subshape. Each contiguous section of shapes with +ve height after doing so will make up a new subshape.

Answer 2

If you look for an overview on algorithms for the general problem, Rectangular Decomposition of Binary Images (article by Tomas Suk, Cyril Höschl, and Jan Flusser) might be helpful. It compares different approaches: row methods, quadtree, largest inscribed block, transformation- and graph-based methods.

A juicy figure (from page 11) as an appetizer:

Figure 5: (a) The binary convolution kernel used in the experiment. (b) Its 10 blocks of GBD decomposition.