将大矩形分区为小矩形(2D Packing)

Question

我需要算法将大的静态大小的矩形分成小的矩形.对我来说完美的实现看起来像这样:

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

所以我需要算法GetRect和FreeRect方法.任何想法和链接将不胜感激.

Answer 1

你要做的是在线二维包装.它是在线的,因为在您尝试将它们打包成大图之前,您手边没有所有小图片.此外,一些小图片将被"解除分配",他们的空间将被释放.另一方面,离线算法允许您在打包之前对小图片进行从最大到最小的排序.

这篇文章调查了2D包装的最新技术:二维包装调查.这是理论上的.

本文2D在线装箱的新上界引用了描述在线二维装箱算法的其他文章.

游戏世界中的人们也有类似的问题; 他们称之为纹理包装或纹理图集.但是,他们使用离线算法.

John Ratcliff发表了一篇关于纹理包装的博客文章.

另请参阅gamedev上的相关问题:https://gamedev.stackexchange.com/questions/2829/texture-packing-algorithm