Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
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
add comment

2 Answers

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|improve this answer
add comment

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|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
add comment

Your Answer

 
discard

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.