# Distribution of variable sized images/boxes(only aspect ratio given) on a 2D area

I'm trying to find a solution for the following problem. You have a set of pictures or let us assume they are just boxes with a given aspect ratio. And you have a two-dimensional area with width and height. The boxes can vary in size only their aspect ratio is fixed, BUT they can have also have a max/min size (optional).

I'm looking for an optimal distribution of the boxes in this area, so that the remaining area is minimal.

Is there a solution to this problem, or a best practice to deal with it? Or are there any papers published on that topic? (some toolkit for javascript dealing with this problem would be brilliant)

What I already found during my short research? Similar problem: https://stackoverflow.com/questions/5129221/treemapping-with-a-given-aspect-ratio

I have also thought about a mathematical solution to this problem and what I came up with so far was:

x1+...+xn <= x_dimension            | x1..xn (box width)
a1*x1+...+an*xn <= y_dimension      | a1..an (aspect ratio)


of course there are multiple solution to this problem so what you then need to do is to find out which is the best. So you need to find:

min(x_remainder*y_remainder)


whereas

(x1+...+xn) - x_dimension = x_remainder
(a1*x1+...+an*xn) - y_dimension  = y_remainder


I'm not even sure if I'm on the right path with this approach, so I would also be grateful, if someone could provide me with some food for thought.

• In general, this is called packing. To get you going, check the Wikipedia article on packing.
– Juho
Mar 14 '12 at 11:54
• And this particular version of the problem is called 2-dimensional packing. Mar 14 '12 at 15:28