How to fill a square with smaller squares/rectangl

Question

In my office at work, we are not allowed to paint the walls, so I have decided to frame out squares and rectangles, attach some nice fabric to them, and arrange them on the wall.

I am trying to write a method which will take my input dimensions (9' x 8' 8") and min/max size (1' x 3', 2', 4', etc..) and generate a random pattern of squares and rectangles to fill the wall. I tried doing this by hand, but I'm just not happy with the layout that I got, and it takes about 35 minutes each time I want to 'randomize' the layout.

Answer 1

Sounds like a Treemap

Answer 2

Bin packing or square packing?

Bin packing: http://www.cs.sunysb.edu/~algorith/files/bin-packing.shtml

Square packing: http://www.maa.org/editorial/mathgames/mathgames_12_01_03.html

This actually sounds more like an old school random square painting demo, circa 8-bit computing days, especially if you don't mind overlaps. But if you want to be especially geeky, create random squares and solve for the packing problem.

Answer 3

If you're talking on a pure programing problem ;) There is a technique called Bin Packing that tries to pack a number of bins into the smallest area possible. There's loads of material out there:

http://en.wikipedia.org/wiki/Bin_packing_problem

http://mathworld.wolfram.com/Bin-PackingProblem.html

http://www.cs.sunysb.edu/~algorith/files/bin-packing.shtml

So you 'could' create a load of random squares and run it through a bin packer to generate your pattern.

I've not implemented a bin packing algorithm myself but I've seen it done by a colleague for a Nike website. Best of luck

Answer 4

1. Define input area;
2. Draw vertical lines at several random horizontal locations through the entire height;
3. Draw horizontal lines at several vertical positions through the entire width;
4. Shift some "columns" up or down by arbitrary amounts;
5. Shift some "rows" left or right by arbitrary amounts (it may be required to subdivide some cells to obtain full horizontal seams;
6. Remove seams as aesthetically required.

This graphical method has similarities to Brian's answer.