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

Question

在stackoverflow上有几个类似的问题，但没有一个似乎提供了一个明确的答案，即对NP-hard问题和算法没有深入理解的人可以理解。

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

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

Answer 1

I Googled "bin packing code"，这是我的第一次打击：http://codeincomplete.com/posts/2011/5/7/bin_packing/

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

上面链接的文章更全面地解释了这一点，其中包含图表和JavaScript代码。它还解释了如何动态生成精灵表，而不是事先选择一个固定的大小。

Answer 2

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

有一张纸，一个体面的C++实现。

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

的“铡包”被称为基于树的包装出现。