块状布局算法 [英] Block layout algorithm

问题描述

我在寻找帮助改进算法用于放置奇怪形状的块。我的问题域是奇数，但我的块最好的比喻是俄罗斯方块片，但他们可以有超过四件。该块仍然是由只有直角，但也可以是漫长而曲折的，他们可以转向，等等。

I'm looking for help with improving an algorithm for placing blocks of odd shapes. My problem domain is odd, but the best analogy for my blocks is Tetris pieces, except that they can have more than four pieces. The blocks still are composed of only right angles, but they can be long and winding, they can branch, etc.

我想安排多个大型任意形状的块在最小的空间（我知道，一个装箱问题），但我目前的解决方案看起来丑陋。我基本上放置一个，那么穷举通过尝试将它们放置在我的网格的原点，然后慢慢地推动它们在不同的方向，直到它们不碰撞再迫使其余部分。它不慢，但它没有适应件很好所以他们不浪费整体空间的任何企图。

I'm trying to arrange multiple large arbitrarily shaped blocks in minimal space (I know, a bin-packing problem) but my current solution looks ugly. I'm basically placing one, then brute forcing the rest by trying to place them at the origin of my grid and then slowly pushing them in different directions until they don't collide anymore. It's not slow, but it doesn't make any attempt to fit pieces nicely so they don't waste overall space.

我唯一能想到的尝试是订购块按大小，将首先最大的，再恰当不过了最小的一端插入剩余的任何漏洞。但也有一定的方式，可能会适得其反。

The only thing I can think of trying is ordering the blocks by size, placing the largest first, then fitting the smallest in at the end into any holes remaining. But there are certainly ways that can backfire.

是否有任何启发式或近似算法，可以帮助我在这里？

Are there any heuristics or approximation algorithms that can help me here?

结果将类似于以下内容：

The results would look something like the following:

此外，也许是我的gravatar赠送，这是洛克人相关...

Also, perhaps my gravatar gives away that this is Mega Man related...

推荐答案

这（四角形状包装）通常似乎是一个平凡的数学题，我会点你一些其他人谁已经在它的工作的专业知识。这家伙有一堆关于他的网站，其他人可以提交解决方案四角的例子。他还解算器软件Java的：

This (polyomino shape-packing) generally seems to be a nontrivial math problem, and I'll point you to the expertise of some others who have worked on it. This guy has a bunch of polyomino examples on his website where others can submit solutions. He also has solver software in Java:

http://gp.home.xs4all.nl/Site/Polyomino_Solver.html 。

http://gp.home.xs4all.nl/PolyominoSolver/downloadsolver.htm

也有一些算法，该由斯蒂芬·蒙哥马利 - 史密斯，写这似乎是多个COM prehensive除上述（它解决了一些问题，没有解决的与），最终把它做成一个xscreensaver的（解决了实时和酷看！）。下面的截图，从屏幕保护程序，只显示形状高达pentominoes，但它的工作原理与普通的容器一般的形状。

There are also some algorithms written for this by Stephen Montgomery-Smith, which seem to be more comprehensive than the above (it solved some problems that weren't solvable with that) eventually made it into an xscreensaver (solves in real-time and cool to watch!). The following screenshot, from the screensaver, only shows shapes up to pentominoes, but it works on general shapes with general containers.

http://www.math.missouri.edu/~stephen/software/

我不确定如果这些软件近似于四角系统允许孔的最佳选择。但是，这绝对是可判定的这样一来，你当然可以插入额外的1x1的四角系统到您的解决方案，看看它是否能找到一个适合，然后取出1x1的作品得到结果的特定结果的意义。

I am unsure if either of these software approximates the best fit of polyominoes allowing for holes. But it's definitely 'decidable' this way, in the sense that you could certainly insert extra 1x1 polyominoes into your solution and see if it can find a particular result that fits, then remove the 1x1 pieces to get the result.

有关您的应用程序，它可能是更有效的工作倒退。所有这些算法有复杂性在单元电池的各块的数目。一个好的方法来布置你的块将是认为它们是在较大的细胞细分，从而使你的格挡一个3x3正方形对应于一个重新调整的版本一个1x1正方形。然后，垫空的空间，所以它们都构成较大块的块，运行算法，并夺走了额外的空间。这不仅会快得多来执行，但它也将生成您所需要的块之间的空间中。

For your application, it might be more efficient to work backwards. All of these algorithms have complexity in the number of unit cells in each block. A good way to lay out your blocks would be to think of them as "subdivisions" in larger cells, so that a 3x3 square in your block corresponds to a 1x1 square in a rescaled version. Then, pad the blocks with empty space so they all consist of the larger blocks, run the algorithm, and strip away the extra space. Not only will this be much faster to execute, but it will also generate the space between blocks that you require.

这篇关于块状布局算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！