12

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.

rectangles

Geobits
  • 22,218
  • 6
  • 59
  • 103
James RedEyes
  • 145
  • 1
  • 6
  • Are rectangles allowed to overlap? – Sneftel Nov 26 '13 at 14:48
  • Assuming you have a fixed area it doesn't matter they way you fill that area as long as you take up 100% of the area – dbarnes Nov 26 '13 at 14:48
  • They can't overlap @Sneftel – James RedEyes Nov 26 '13 at 14:58
  • @dbarnes Yeah , but what is the smallest amount of rectangles I could use? Technically i could just use 1x1 rectangles to fill it but I want to minimize the amount of rectangles if possible. – James RedEyes Nov 26 '13 at 15:04
  • Can you create an image that shows what you mean? It seems to me we are guessing how the shape may look like. – ojdo Nov 26 '13 at 15:10
  • possible duplicate of [Algorithm for finding the fewest rectangles to cover a set of rectangles](http://stackoverflow.com/questions/5919298/algorithm-for-finding-the-fewest-rectangles-to-cover-a-set-of-rectangles) – finnw Nov 26 '13 at 16:28
  • 1
    @finnw That question has some differences. Mainly that the rectangles may not be base-aligned or even connected, according to that OP's edit. – Geobits Nov 26 '13 at 16:45
  • OP: If you have a new question, please ask that separately. Don't just edit over your old one. – Geobits Nov 27 '13 at 17:39
  • subset: squares of identical size: http://stackoverflow.com/questions/8639154/algorithm-to-find-the-minimum-number-of-rectangles-covering-certain-elements-in – Ciro Santilli OurBigBook.com Feb 19 '17 at 15:08

2 Answers2

8

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(n2).

For example:

reducing rectangles

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.

Community
  • 1
  • 1
Geobits
  • 22,218
  • 6
  • 59
  • 103
  • 1
    This will work because at any step we can only optimize by combining the widths. The number of rectangles shall be at least equal to the number of steps in the staircase. – Abhishek Bansal Nov 26 '13 at 16:09
7

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.

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

ojdo
  • 8,280
  • 5
  • 37
  • 60
  • For arbitrarily placed rectangles, this makes sense. Isn't it a bit overkill for non-overlapping, base-aligned groups? – Geobits Nov 26 '13 at 15:52
  • @Geobits - It looks like this solution also assumes non-overlapping. Otherwise, it could have been further reduced by extending the green rectangle up, and the orange rectangle down, thus eliminating the purple rectangle. – mbeckish Nov 26 '13 at 15:59
  • I meant the *source* is non-overlapping rectangles, rather than a simple binary image composed of overlapping rectangles with no given alignment, etc. The problem as given is just simpler, since there are constraints on how they are placed. I'm sure the algorithms in the paper would still work for this, they're just more complicated than necessary. – Geobits Nov 26 '13 at 16:02