# Algorithm for positioning rectangles of various size into a larger rectangle

I am working on tool for merging smaller textures into one larger for use on Android app.

I have $n$ rectangles of given size $(w_k, h_k)$, where $k=1,\ldots,n$ and I need to position them within master rectangle of size $2^l \times 2^m$, where $l, m \leq 9$ so none overlapping occur and $2^l \times 2^m$ has minimal possible value. The result should be $(x_k, y_k)$, a position of each of the $n$ base rectangles or information that such positioning is impossible.

• Minus the specific dimensions you list, your problem is known as "bin packing" in the literature. And the literature is vast. See the Wikipedia article for a start. Sep 28, 2011 at 10:48

We seem to have an number (I will use $k$) of identical $w \times h$ rectangles to fit inside a larger $2^n \times 2^m$ rectangles, and with a restrictions on $n$ and $m$.
For given $2^n$, we can fit $\lfloor 2^n / w \rfloor$ rectangles horizontally provided $w \le 2^n$. So we need at least $\lceil k / \lfloor 2^n / w \rfloor \rceil$ rows of rectangles and so a vertical height of at least $h \lceil k / \lfloor 2^n / w \rfloor \rceil$; if this is less than or equal to $2^m$ then there is a solution and the minimal value of $m$ is $\lceil \log_2 \left( h \lceil k / \lfloor 2^n / w \rfloor \rceil \right) \rceil$. The area of the master rectangle is then $2^{n+ \lceil \log_2 \left( h \lceil k / \lfloor 2^n / w \rfloor \rceil \right) \rceil}$. It is probably worth testing this for the ten(?) possible values of $n$ to see which produces the minimal master rectangle.
As for the coordinates (assuming these are one of the corners and $(0,0)$ is a possibility), this will be a matter of style. One way would be to use $(iw,jh)$ for nonengative integers $i$ and $j$ so long as $(i+1)w -1 \le 2^n$ and $(j+1)h -1 \le 2^m$.