将大矩形划分为小矩形（2D Packing）

我需要将大的静态大小的矩形分割成小矩形的算法。我一个完美的实现是这样的：将大矩形划分为小矩形（2D Packing）

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

来源

2011-05-23 pure cuteness

这气味像功课。 – 2011-05-23 14:31:21

对子矩形的分配方式有任何限制吗？例如。有没有一个目标可以有效地包装矩形，或者你可以将它们粘在任何适合的地方？ – verdesmarald 2011-05-23 14:32:24

@ Jean-Paul Calderone。这不是功课。 @veredesmarald当然最好能有效地分配它们。 – 2011-05-23 14:34:58

你想要做的是在线2D装箱包装。它是在线的，因为在您试图将它们放入大图片之前，您手边没有全部小图片。此外，一些小图片将被“释放”，其空间将被释放。另一方面，离线算法允许您在打包之前将小图片从最大到最小排序。

这里是一篇文章，调查的2D包装的艺术状态：Survey on two-dimensional packing。这很理论。

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

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

John Ratcliff在纹理包装上发布了blog article。

另见gamedev此相关的问题：https://gamedev.stackexchange.com/questions/2829/texture-packing-algorithm

来源

2011-05-23 15:52:46

据我了解，在离线打包时，我不能将一些freespace添加回矩形（在我的示例中为'BigRect :: FreeRect'）？我现在很困惑。 – 2011-05-23 16:00:54

哎呀，它是在线包装。编辑答案。 – 2011-05-23 16:12:10

我刚刚读了你的答案。我在开始时没有全部图像。所以我认为我需要一些在线算法而不是离线。 – 2011-05-23 16:13:50

将大矩形划分为小矩形（2D Packing）

回答

相关问题