Algorithm for positioning rectangles of various size into a larger rectangle

Question

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.

Answer 1

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$.

Answer 2

I guess this should be exactly what you need. Basically it is an implementation of the approach presented in this paper by Richard E. Korf. To quote the introduction:

Given a set of rectangles with fixed orientations, we want to find an enclosing rectangle of minimum area that contains them all with no overlap. Many simple scheduling tasks can be modelled by this NP-complete problem. We use an anytime branch-and-bound algorithm to solve the problem optimally.