0
$\begingroup$

I've got 64 images of 96x192 pixels. I have to arrange them on a rectangle. I need the height and width of that rectangle to be powers of two. Given the dimensions of my images, they don't perfectly 'fit' on it (I can not rotate or cut the images into smaller ones); there is always some 'wasted space'.

  1. ¿What are the dimensions of the rectangle that minimizes that wasted space?
  2. ¿Can this problem be generalized to n images of w x h pixels?
  3. ¿Does this problem have a name?

Context: This is not a class exercise. I'm trying to arrange sprites into a image for using them on hobby videogames. The requirement of power-of-two comes from the fact that some old video-cards don't handle non-po2 images very well. I've been thinking about this for 24 hours and couldn't arrive to any satisfying solution.

1 Answers 1

2

You need at least $96 \times 192 \times 64 = 1179648$ pixels. This is slightly more than $2^{20} = 1048576$ but fewer than $2^{21} = 2097152$. So you just need to check that you can fit them into $2^{21}$. One of many possibilities would be a rectangle $2^{9} \times 2^{12} = 512 \times 4096$, you could have 4 images across (since $ 4 \times 96 = 384$ ) and 16 images down (since $16 \times 192 = 3072$ ) and so the 64 images would fit.

This is a packing problem

  • 0
    Thanks for your answer. I've re-tagged my problem as a packing problem. However, I don't think you have answered the question; you have narrowed the search (I didn't think about multiplying height and width... ) but I was looking for the minimal solution not one randomly chosen from the "many possibilities"... choosing the minimal one was kind of the point of my question. Also, you didn't say anything about generalizing. Nevertheless, your answer has been useful to me, so +1.2011-03-02
  • 0
    @Henry: I think you need to wrap your exponents in curly braces: `2^{20}` becomes $2^{20}$ but `2^20` becomes $2^20$.2011-03-02
  • 0
    In this case, the minimal solution must involve $2^{21}$ pixels as $2^{20}$ is too few. So $2^{21}$ is a lower bound, and it turns out to be achievable. To generalise, do the same thing: find a lower bound of the smallest power of 2 which is at least $n \times w \times h$, see if it possible to fit your small rectangles in it, and if not try the next larger power of 2 until you do find a solution.2011-03-02
  • 0
    @Rahul Narain: Thank you, you are of course correct. My problem is that I often cannot see the TeX output (old system).2011-03-02
  • 0
    @Henry: I understand what you are saying - the solution has boundaries. I'd even go further and say that there's probably an *upper* bound (the first po2 greater than 2*n pixels). My problem is that, even within that boundary, there are lots of possible combinations of dimensions. I'm looking for a formula or algorithm that finds the optimal one, without manually calculating all the possible ones; or else, some proof that such thing doesn't exist.2011-03-02
  • 0
    If optimal is not using the smallest number of pixels which fits the constraints [which seem to be having a power of 2 as a rectangle, i.e with power of 2 sides, and with the small rectangles fitting inside], then what is optimal?2011-03-02