Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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: http://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.

share|improve this question
1  
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. –  Suresh Venkat Mar 14 '12 at 15:28
add comment

1 Answer 1

up vote 3 down vote accepted

As mentioned in the comments, the problem is called the (2-dimensional) packing problem. Your problem (Rectangle packing) is NP-complete. It can be shown with a reduction from the Bin Packing problem. See for example this paper Richard E. Korf: Optimal Rectangle Packing: Initial Results. Here's a link that describes an algorithm (the same basic idea as in the paper) in quite a bit of detail. In addition, the paper mentions the problem can be modeled as a constraint satisfaction problem (CSP), so you might be interested in using a CSP-solver if you need to solve the problem in practice. One such solver I have used is MINION.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.