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