3

Possible Duplicate:
Algorithm for finding the fewest rectangles to cover a set of rectangles

I need some help figuring out an algorithm. I have a shape laid out on a grid as shown below.

Shape on Grid http://www.benfillmore.com/shape.png

The goal is combine the squares into larger rectangles like so:

Larger Rectangles http://www.benfillmore.com/boxes.png

I'm trying to cover every square in the shape with as few rectangles as possible. It's okay if the rectangles overlap each other:

Overlap http://www.benfillmore.com/overlap.png

I'm not looking for full solutions, just ideas, or someone pointing me in the right direction. I've implemented a couple ideas, but they don't even come close to optimal. I'm not worried about processing time, that's only done once at shape creation. I just need as few rectangles as possible.

Thanks a million

Community
  • 1
  • 1
Fillmore
  • 131
  • 4
  • Bingo! Thanks a million, that should work great. At first glance it looks perfect. Now I need to spend a few minutes wrapping my head around it. – Fillmore Nov 28 '12 at 18:56

0 Answers0