如何以编程方式实现二维装箱？

在stackoverflow上有一些类似的问题，但是没有一个似乎提供了一个实际的答案，即对NP-hard问题和algorithm没有深入理解的人能够理解。

如何执行矩形对象的二维装箱？ 在我的情况下，我试图将几个图像组装成一个单一的图像，用作一个spritesheet，使用最小的空间。 每个图像可能具有非常不同的边界，但是没有限定容器的边界。

我希望有一位了解bin包装algorithm的人可以解释如何以编程方式实现这一点，而不是提供bin包装方法的一般概述。

Answer 1

我谷歌search“bin包装代码” ，这是我第一次打： http : //codeincomplete.com/posts/2011/5/7/bin_packing/

这里有一个总结：构build一个二叉树。 树中的每个分支都包含一个精灵。 每个叶节点表示可用空间。 树最初只有根节点，它代表了所有可用的空间。 要将精灵添加到树中，请在树中search一个空间足够大的未占用（叶）节点来容纳精灵。 通过将精灵设置为节点的占有者并给节点两个子节点，将该节点从叶子转到分支。 一个孩子代表精灵右边的剩余空间; 另一个表示精灵和第一个孩子下面的剩余空间。

我上面链接的文章用图表和JavaScript代码解释了这一点。 它还解释了如何dynamic增长精灵表，而不是事先select一个固定的大小。

Answer 2

所有你需要的是在这里： https ： //github.com/juj/RectangleBinPack

有一篇论文和一个体面的C ++实现。

如果你需要一个更简单的伪代码，看看这个网站： http : //www.blackpawn.com/texts/lightmaps/

“断头台包”在那里被称为树形包装。