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.

Answer 1

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.