如何以编程方式实现2D装箱？

Question

关于stackoverflow也有一些类似的问题，但是似乎都没有一个切实的答案，即使对NP难题和算法没有扎实的理解的人也可以理解。

如何执行矩形对象的2D装箱？以我为例，我试图使用最小的空间将几张图像组合成一个图像，用作电子表格。每个图像可能具有截然不同的边界，但是容器没有设置边界。

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

Answer 1

我用Google搜索了“装箱码”，这是我的第一个热门商品：http
:
//codeincomplete.com/posts/2011/5/7/bin_packing/

总结：构建一个二叉树。树中的每个分支都包含一个精灵。每个叶节点代表可用空间。最初，树只有一个根节点，它代表所有可用空间。要将精灵添加到树中，请在树上搜索一个足够大以容纳精灵的未占用（叶子）节点。通过将精灵设置为节点的占用者并给该节点两个孩子，将该节点从叶子变成分支。一个孩子代表小精灵右边的剩余空间；另一个代表精灵和第一个子对象下方的剩余空间。

我上面链接的文章通过图表和JavaScript代码更全面地解释了这一点。它还说明了如何动态增长Sprite表，而不是预先选择固定大小。