12

我需要将静态大小的大矩形分割成小矩形的算法。对我来说完美的实现如下所示：

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方法。任何想法和链接将不胜感激。

4

1 回答 1

7

您要做的是在线 2D 装箱。它之所以在线，是因为在您尝试将所有小图片打包成大图片之前，您并没有掌握所有的小图片。此外，一些小图片将被“释放”并释放它们的空间。另一方面，离线算法允许您在打包之前对小图片从大到小进行排序。

这里有一篇文章调查了 2D 包装的最新技术： 二维包装调查。很有理论意义。

这篇文章A New Upper Bound on 2D Online Bin Packing引用了其他描述在线 2D 打包算法的文章。

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

John Ratcliff 发布了一篇关于纹理打包的博客文章。

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

于 2011-05-23T15:52:46.053 回答