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


---

