1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ In general, this is called packing. To get you going, check the Wikipedia article on packing. $\endgroup$
    – Juho
    Commented Mar 14, 2012 at 11:54
  • $\begingroup$ And this particular version of the problem is called 2-dimensional packing. $\endgroup$
    – Suresh Venkat
    Commented Mar 14, 2012 at 15:28

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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