如何二维装箱实现编程？ [英] How is 2D bin packing achieved programmatically?

问题描述

有计算器上几个类似的问题，但没有人似乎提供了一个实实在在的答案，有人没有NP难问题和算法的深刻理解可以理解的。

There are a few similar questions on stackoverflow, but none of them seem to provide a tangible answer that someone without a solid understanding of NP-hard problems and algorithms can understand.

一个人如何进行矩形物体的二维装箱？就我而言，我试图组装多个图像到一个单一的形象，用作spritesheet，使用的空间量最小。每幅图像可能有完全不同的界限，但没有设定界限的容器。

How does one perform 2D bin packing of rectangular objects? In my case, I'm trying to assemble several images into a single image, for use as a spritesheet, using the smallest amount of space. Each image possibly has wildly different bounds, but there is no set bounds to the container.

我希望有人与装箱算法的理解可以解释如何可以通过编程来实现，而不是提供的装箱方法的概述。

I was hoping someone with an understanding of bin packing algorithms could explain how this can be achieved programmatically, rather than providing a general overview of the bin packing method.

推荐答案

我用Google搜索装箱code，这是我第一次打：<一href="http://$c$cincomplete.com/posts/2011/5/7/bin_packing/">http://$c$cincomplete.com/posts/2011/5/7/bin_packing/

下面是一个总结：构建一个二叉树。树中的每个分支包含一个精灵。每个叶节点重新presents可用空间。最初，树具有刚根节点，从而重新presents所有可用的空间。为了一个精灵添加到树，搜索树未占用（叶）节点，大到足以容纳精灵。打开从叶节点到一个分支通过设置精灵作为节点的乘员，并给予该节点的两个孩子。一个孩子再presents剩余空间精灵的权利;另外再presents精灵下方的剩余空间和第一个孩子。

Here's a summary: build a binary tree. Each branch in the tree contains a sprite. Each leaf node represents available space. Initially the tree has just the root node, which represents all available space. To add a sprite to the tree, search the tree for an unoccupied (leaf) node big enough to hold the sprite. Turn that node from a leaf into a branch by setting the sprite as the node's occupant and giving the node two children. One child represents the remaining space to the right of the sprite; the other represents the remaining space below the sprite and the first child.

我上面链接的文章解释了这么多的更充分，以图表和JavaScript code。这也解释了如何动态比预先选择一个固定大小成长精灵表相当。

The article I linked above explains this much more fully, with diagrams and JavaScript code. It also explains how to dynamically grow the sprite sheet rather than choosing a fixed size in advance.

这篇关于如何二维装箱实现编程？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！