在 stackoverflow 上有一些类似的问题，但似乎没有一个提供一个对 NP-hard 问题和算法没有扎实理解的人可以理解的切实答案。
如何对矩形对象执行二维装箱？在我的情况下，我试图将几个图像组合成一个图像，用作精灵表，使用最少的空间。每个图像可能有非常不同的边界，但容器没有设置边界。
我希望了解装箱算法的人可以解释如何以编程方式实现这一点，而不是提供装箱方法的一般概述。
问问题
45440 次
1 回答
31
我在 Google 上搜索了“bin 包装代码”，这是我的第一次点击：http ://codeincomplete.com/posts/2011/5/7/bin_packing/
这里有一个总结：构建一棵二叉树。树中的每个分支都包含一个精灵。每个叶节点代表可用空间。最初，树只有根节点，它代表所有可用空间。要将精灵添加到树中，请在树中搜索一个足够大以容纳精灵的未占用（叶）节点。通过将精灵设置为节点的占用者并为节点提供两个子节点，将该节点从叶子变为分支。一个孩子代表精灵右侧的剩余空间；另一个代表精灵和第一个孩子下方的剩余空间。
我在上面链接的文章用图表和 JavaScript 代码更全面地解释了这一点。它还解释了如何动态增长精灵表，而不是预先选择固定大小。
于 2012-01-06T21:53:19.647 回答