I am writing a sprite sheet generator tool in adobe AIR, and I have to force with the question: How to pack a collection of 2D rectangles to smallest possible 2D rectangle with power of two. (like 1024x444).

I think that this question is NP-Hard. I found good answer for it here.

I thought about another option. What if I cut my rectangles to smaller rectangles. Will this make my life easier?

My XML data will be more complicated, and I am not sure how this will effect the performance of the application that will use the cut sprite sheet.

How ever the difficulty of such problem is probably belongs to P.

Do you think it's possible? What am I missing here?

  • 1
    $\begingroup$ Have you googled literature on tilings? $\endgroup$ – Raphael Jan 23 '14 at 18:12
  • $\begingroup$ How many rectangles are you thinking of? If there are only a few of them, then the problem could be amenable to some sort of brute force solution. $\endgroup$ – Yuval Filmus Jan 23 '14 at 19:14
  • $\begingroup$ @YuvalFilmus There might be 50 of theme, and may be more. I don't think that the brute will help me here. $\endgroup$ – Ilya Gazman Jan 23 '14 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.