How to fill a square with smaller squares/rectangles?

Question

This is not a homework or interview 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.

Here is sort of what I am looking for if it helps

Answer 1

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%5Fpacking%5Fproblem

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 2

Since you can pick the size of the rectangles, this is not a hard problem.

I'd say you can do something as simple as:

   Pick an (x,y) coordinate that is not currently inside a rectangle.
   Pick a second (x,y) coordinate so that when you draw a rectangle between
      the two coordinates, it won't overlap anything. The bounding box of
      valid points is just bounded by the nearest rectangles' walls.
   Draw that rectangle.
   Repeat until, say, you have 90% of the area covered. At that point you
      can either stop, or fill in the remaining holes with as big rectangles
      as possible.

It might be interesting to parametrize the generation of points, and then make a genetic algorithm. The fitness function will be how much you like the arrangement - it would draw hundreds of arrangements for you, and you would rate them on a scale of 1-10. It would then take the best ones and tweak those, and repeat until you get an arrangement you really like.

Answer 3

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%5F12%5F01%5F03.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 4

Sounds like a Treemap

Answer 5

I would generate everything in a spiral slowly going in. If at any point you reach a point where your solution is proven to be 'unsolvable' (IE, can't put any squares in the remaining middle to satisfy the constraints), go to an earlier draft and change some square until you find a happy solution.

Pseudocode would look something like:

public Board GenerateSquares(direction, board, prevSquare)
{
   Rectangle[] rs = generateAllPossibleNextRectangles(direction, prevSquare, board);
   for(/*all possible next rectangles in some random order*/)){
      if(board.add(rs[x]){
           //see if you need to change direction)
           Board nBoard = GenerateSquares(direction, board, rs[x]);
           if(nBoard != null) return nBoard; //done
           else board.remove(rs[x]);
      }
  }
  //all possibilities tried, none worked
  return null;
}

}

Answer 6

One solution is to start with x*y squares and randomly merge squares together to form rectangles. You'll want to give differing weights to different size squares to keep the algorithm from just ending up with loads of tiny rectangles (i.e. large rectangles should probably have a higher change of being picked for merging until they get too big).

Answer 7

I suggest:

Start by setting up a polygon with four vertices to be eaten in varying size (up to maxside) rectangle lumps:

public double[] fillBoard(double width, double height, double maxside) {
  double[] dest = new int[0];
  double[] poly = new int[10];
  poly[0] = 0; poly[1] = 0; poly[2] = width; poly[3] = 0;
  poly[4] = width; poly[5] = height; poly[6] = 0; poly[7] = height;
  poly[8] = 0; poly[9] = 0;
  ...
  return dest; /* x,y pairs */
}

Then choose a random vertex, find polygon lines within (inclusive) 2 X maxside of the line. Find x values of all vertical lines and y values of all horizontal lines. Create ratings for the "goodness" of choosing each x and y value, and equations to generate ratings for values in between the values. Goodness is measured as reducing number of lines in remaining polygon. Generate three options for each range of values between two x coordinates or two y coordinates, using pseudo-random generator. Rate and choose pairs of x and pair of y values on weighted average basis leaning towards good options. Apply new rectangle to list by cutting its shape from the poly array and adding rectangle coordinates to the dest array.

Question does not state a minimum side parameter. But if one is needed, algorithm should (upon hitting a hitch with a gap being too small) not include too small candidates in selection lists (whic will occasionally make them empty) and deselect a number of the surrounding rectangles in a certain radius of the problem with size and perform new regeneration attempts of that area, and hopefully the problem area, until the criteria are met. Recursion can remove progressively larger areas if a smaller relaying of tiles fails.

EDIT

Do some hit testing to eliminate potential overlaps. And eat some spinach before starting the typing. ;)

Answer 8

Another idea:

1. Randomly generate points on the wall
    Use as many points as the number of rectangles you want
    Introduce sampling bias to get cooler patterns
2. Build the kd-tree of these points

The kd-tree will split the space in a number of rectangles. There might be too much structure for what you want, but its still a neat geeky algorithm.

(see: http://en.wikipedia.org/wiki/Kd-tree)

Edit: Just looked at JTreeMap, looks a bit like this is what its doing.

Answer 9

Building off Philippe Beaudoin answer.

There are treemap implementations in other languages that you can also use. In Ruby with RubyTreeMap you could do

require 'Treemap' 
require 'Treemap/image_output.rb'

root = Treemap::Node.new 0.upto(100){|i| root.new_child(:size => rand) } 

output = Treemap::ImageOutput.new do |o| 
   o.width = 800 
   o.height = 600 
end 

output.to_png(root, "C:/output/test.png")

However it sorts the rectangles, so it doesn't look very random, but it could be a start. See rubytreemap.rubyforge.org/docs/index.html for more info

Answer 10

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.