<p>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 <a href="http://www.aaai.org/Papers/ICAPS/2003/ICAPS03-029.pdf" rel="nofollow">Richard E. Korf: Optimal Rectangle Packing: Initial Results</a>. Here's a <a href="http://www.codeproject.com/Articles/210979/Fast-optimizing-rectangle-packing-algorithm-for-bu" rel="nofollow">link</a> 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 <a href="http://minion.sourceforge.net/" rel="nofollow">MINION</a>.</p>

CC BY-SA 3.0
2012-03-14T18:33:45.400Z
2012-03-14T18:33:45.400Z
Juho
<p>I'm trying to find a solution for the following problem. 
You have a set of pictures or let us assume they are just <strong>boxes</strong> with a given <strong>aspect ratio</strong>. And you have a two-dimensional <strong>area</strong> 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). </p>

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

<p>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)</p>

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

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

<pre><code>x1+...+xn &lt;= x_dimension            | x1..xn (box width)
a1*x1+...+an*xn &lt;= y_dimension      | a1..an (aspect ratio)
</code></pre>

<p>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:</p>

<pre><code>min(x_remainder*y_remainder)
</code></pre>

<p>whereas</p>

<pre><code>(x1+...+xn) - x_dimension = x_remainder 
(a1*x1+...+an*xn) - y_dimension  = y_remainder
</code></pre>

<p>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.</p>

CC BY-SA 3.0
2012-03-14T11:54:07.067Z
In general, this is called packing. To get you going, check the [Wikipedia article on packing](http://en.wikipedia.org/wiki/Packing_problem).
Juho
CC BY-SA 3.0
2012-03-14T15:28:48.090Z
And this particular version of the problem is called 2-dimensional packing.
Suresh Venkat
<cg.comp-geom><optimization><packing>
Distribution of variable sized images/boxes(only aspect ratio given) on a 2D area
JustGoscha
# Distribution of variable sized images/boxes(only aspect ratio given) on a 2D area

(Asked by: username_0 on 2012-03-14)

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.

**Tags:** cg.comp-geom, optimization, packing

> **Comments:**
> **username_1**: In general, this is called packing. To get you going, check the [Wikipedia article on packing](http://en.wikipedia.org/wiki/Packing_problem).  
> **username_2**: And this particular version of the problem is called 2-dimensional packing.  

---

## 1 answers

### Answer by username_1 on 2012-03-14. Score: 4 | Accepted answer

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](http://www.aaai.org/Papers/ICAPS/2003/ICAPS03-029.pdf). Here's a [link](http://www.codeproject.com/Articles/210979/Fast-optimizing-rectangle-packing-algorithm-for-bu) 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](http://minion.sourceforge.net/).


---

