Partitioning big rectangle to small ones (2D Packing)

Question

I need algorithm which splits big static sized rectangle to small ones. A perfect implementation for me look like this:

struct RECT
{
  int l,t,r,b;
};

class BigRect
{
public:
  // width and height of big rect
  BigRect( unsigned width, unsigned height );

  // returns -1 if rect cannot be allocated, otherwise returns id of found rect
  int GetRect( unsigned width, unsigned height, RECT &out );

  // returns allocated rect to big rectangle
  void FreeRect( int id );
};

void test()
{
  BigRect r( 10, 10 );

  RECT out;
  r.GetRect( 4, 4, out ); // rect found ({0,0,4,4} for example), returns 1
  r.GetRect( 5, 5, out ); // rect found ({4,0,9,5} for example), returns 2

  r.GetRect( 6, 6, out ); // no place found for rect, returns -1
  r.FreeRect( 2 );        // add {4,0,9,5} back to rect

  r.GetRect( 6, 6, out ); // rect found (4,0,10,6)
}

So I need algorithm for GetRect and FreeRect methods. Any ideas and links would be appreciated.

Answer 1

What you're trying to do is online 2D bin packing. It's online because you don't have all your small pictures in hand before you attempt to pack them into the big picture. Furthermore some small pictures will be "deallocated" and their space will be freed up. On the other hand, an offline algorithm allows you to do things like sort your small pictures from largest to smallest before packing them.

Here's an article that surveys the state of the art in 2D packing: Survey on two-dimensional packing. It's quite theoretical.

This article A New Upper Bound on 2D Online Bin Packing cites other articles that describe online 2D packing algorithms.

People in the gaming world have a similar problem as you do; they call it texture packing or texture atlas. However, they use offline algorithms.

John Ratcliff posted a blog article on texture packing.

See also this related question on gamedev: https://gamedev.stackexchange.com/questions/2829/texture-packing-algorithm