Packing Rectangles Algorithm

Question

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.

Crosscheck

Is this homework? If so tag it as homework. – Hebe

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.. – Jessalin

You could steal the Window 8 "metro" code :-) – Modlin

Sounds very similar to a question I answered earlier: #7440060 – Deltadeltaic

Answer 1

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

Lunn

Answer 2

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.

Trembles

Answer 3

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:

I don't see how you can do better.

Linnlinnaeus

Answer 4

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:

Bewray

In your example, you divide the surface by 2 at each step (A1,A2 ...), But in the desired algorithm it's by 4 ... So something is wrong here – Linnlinnaeus

The A-series paper works this way because the edge length ration is 1:sqrt(2), other paper sizes don't pack this way. (I often wonder why A-series isn't more common internationally...) – Modlin

@Ricky Bobby good point, I missed that details while reading the question. – Bewray

@Modlin I didn't mean to give the example as 1:1 corresponding to the problem in question. I rather meant to give some idea to follow. – Bewray

Answer 5

This is a lot like MIP-mapping

Modlin

You can have more than one rectangle of each size. – Crosscheck