将大矩形划分为小矩形(2D 打包)

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包装技术水平的文章：二维包装调查。这是相当理论化的。

本文 2D 在线装箱的新上限引用了描述在线 2D 装箱算法的其他文章。

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

约翰·拉特克利夫（John Ratcliff）发表了一篇关于纹理包装的博客文章。

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