关于stackoverflow也有一些类似的问题,但是似乎都没有一个切实的答案,即使对NP难题和算法没有扎实的理解的人也可以理解。
如何执行矩形对象的2D装箱?以我为例,我试图使用最小的空间将几张图像组合成一个图像,用作电子表格。每个图像可能具有截然不同的边界,但是容器没有设置边界。
我希望了解bin装箱算法的人可以解释如何以编程方式实现此目的,而不是提供bin装箱方法的一般概述。
我用Google搜索了“装箱码”,这是我的第一个热门商品:http : //codeincomplete.com/posts/2011/5/7/bin_packing/
总结:构建一个二叉树。树中的每个分支都包含一个精灵。每个叶节点代表可用空间。最初,树只有一个根节点,它代表所有可用空间。要将精灵添加到树中,请在树上搜索一个足够大以容纳精灵的未占用(叶子)节点。通过将精灵设置为节点的占用者并给该节点两个孩子,将该节点从叶子变成分支。一个孩子代表小精灵右边的剩余空间;另一个代表精灵和第一个子对象下方的剩余空间。
我上面链接的文章通过图表和JavaScript代码更全面地解释了这一点。它还说明了如何动态增长Sprite表,而不是预先选择固定大小。