Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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. – Joseph O'Rourke Sep 28 '11 at 10:48

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.

share|cite|improve this answer

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

share|cite|improve this answer
Ah, my mistake - there are not identical. Each of them have wn x kn size where n = 1, 2, ..., k – PiotrK Sep 28 '11 at 10:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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