Packing Rectangles Algorithm

5
votes

I need to solve the following problem: I have multiple rectangles of sizes: width height, width/2 height/2, width/4 height/4 , width/8 height/8 ... etc

I need to pack these rectangles in a big rectangle of size x*width y*height such that no rectangles overlap, the rectangles are distributed randomly in the packing and any rectangle should at least touch another rectangle. I tried a fairly basic greedy algorithm but it fails.

Can you give me some suggestions on how to solve the problem?

Thanks!

EDIT: You can have more than one rectangle of each size

This is not homework. I'm trying to create an effect similar to the effect on ted.com

By random I mean that there might exist more than one packing of the rectangles that satisfies the constraints. The algorithm should not produce the same packing at each run.

5
algorithmmathpacking
Is this homework? If so tag it as homework. – Ed Heal
You need to give more specifics. Do you have one of each of the rectangle sizes (eg 1 of unit side, 1 of 0.5 unit sides etc...) or do you have as many at your disposal as you wish? Also, define randomly.. – El Ronnoco
You could steal the Window 8 "metro" code :-) – spraff
Sounds very similar to a question I answered earlier: stackoverflow.com/questions/7439560/… – Merlyn Morgan-Graham

5 Answers

4
votes

This sounds like a rectangle packing problem. There is a link there to an algorithm. That code packs the rectangles as tightly as possible. You said you want the rectangles to be distributed randomly, which I'm guessing means not all rectangles of one size next to each other and all rectangles spread out to fill the big rectangle. Maybe the code at the link above would be a good starting point to get some ideas.

2
votes

You can use a spatial index or a quadtree to subdivide the 2d-plane. The idea is to reduce the 2d problem to a 1d-problem. Once you got the spatial index (or space-filling-curve) and you can discretize the 2d into 1d you can use the 1d to search for similarity or to sort from low to high or the reverse for example by the length. If you got this order you can then compute the index back to a 2d represenation and to pack them in most efficent way in your container. There are many ways to make a spatial index. Some of the best but difficult to make is the hilbert curve. Another one is the z-curve or morton-curve. It's different from zizag-curve because it's subdivide the plane into 4 squares (not rectangles).

EDIT: Here is a link for an Jquery-Plugin: http://www.fbtools.com/jquery/treemap/ Here with world poplulation: http://www.fbtools.com/jquery/treemap/population.html

EDIT: http://people.csail.mit.edu/konak/papers/socg_2008-circular_partitions_with_applications_to_visualization_and_embeddings.html

EDIT: http://lip.sourceforge.net/ctreemap.html

1
votes

At each step you divide the surface of your new rectange by 4.

SUM(1/4n for n in [0,inf]) = 4/3**

So the best you can do is fit your rectangle in a rectangle of surface 4/3 (height*width)

(that's a lower bound)

@mloskot algorithm gives a possible solution that will be in a rectangle of surface 3/2*(height*width) : Here is an illustration:

enter image description here

I don't see how you can do better.

0
votes

Assuming you have only one rectangle of each size, you can try to replicate the arrangement of paper sizes. Sort the rectangles by size from the biggest to the smallest, then

  1. Take first rectangle and place it at the corner of the target plane.
  2. Take next rectangle (assert it's smaller than the previous rectangle)
  3. Rotate about 90 degrees
  4. Place so
    • its shorter size is adjacent to the longer size of the last bigger neighbour
    • and its longer side is adjacent to the edge of the target plane or edge of neighbour of the same size
  5. Repeat 2 - 4

I realise the description might be unclear, so here is picture presenting the solution - it should help to grasp it:

enter image description here

0
votes

This is a lot like MIP-mapping