如何通过编程实现二维装箱？

Question

如何通过编程实现二维装箱？

algorithmbin-packing

45

stackoverflow上有几个类似的问题，但它们似乎没有提供一个具体的答案，让那些没有坚实的NP-hard问题和算法理解的人能够理解。

如何对矩形对象进行2D装箱？在我的情况下，我试图将几个图像组合成一幅图像（用作精灵表），并使用尽可能少的空间。每个图像可能具有极不同的边界，但容器没有固定的边界。

我希望理解装箱算法的人能够解释如何以编程方式实现这一点，而不是提供装箱方法的概述。

- FrozenFire

2

http://www.codeproject.com/KB/web-image/rectanglepacker.aspx - user97370

1

我实际上非常仔细地阅读了那篇文章，虽然它确实提高了我的装箱理解，但其示例实现严重依赖于仅在C#中可用的结构。即使在阅读所提供的源代码后，我也不知道他是如何完成一些必要的步骤的。 - FrozenFire

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rob mayoff · Accepted Answer

我在谷歌上搜索了“bin packing code”，这是我找到的第一个结果：http://codeincomplete.com/posts/2011/5/7/bin_packing/

这里是总结：建立二叉树。每个分支都包含一个精灵。每个叶节点表示可用空间。最初，树只有根节点，表示所有可用空间。要向树中添加精灵，请搜索树以找到足够大以容纳精灵的未占用（叶）节点。通过将精灵设置为节点的占用者并赋予节点两个子节点，将该节点从叶变为分支。一个子节点表示精灵右侧的剩余空间；另一个子节点表示精灵下方和第一个子节点的剩余空间。

上面链接的文章使用JavaScript代码和图示更详细地解释了这一点。它还解释了如何动态增长精灵表而不是提前选择固定大小。