可变大小块的有效定位
可变大小块的有效定位
提问于 2011-06-21 06:16:37
我有一个矩形数组(长度和宽度)。不保证是平方，但总是保证是整数。我希望在坐标系中尽可能有效地定位块，以便包含所有元素的边界框尽可能小。我也想要朝向正方形。在大小方面的差异不会太大，但我想要一个通用算法。
我发现这个搜索有点困难，只是想找个人给我指明正确的方向。如果需要，只需要寻找伪代码(语言无关紧要)或可以用Java实现的库。性能是一个问题，所以我真的需要它在每个方面都尽可能高效。
注意:如果这在某种程度上变得更容易，如果我仅限于正方形，这可能是一种选择。
回答 2
Stack Overflow用户
回答已采纳
发布于 2011-06-21 06:21:30
维基百科上的Packing problem文章链接到this algorithm，this paper -“最佳矩形打包:初始结果”中描述了这一链接。
Stack Overflow用户
发布于 2011-06-21 20:42:08
我不确定它与E先生所指的算法相比如何，但一旦我构建了一个窗口系统，我需要在屏幕外存储矩形图像片段。我的方法是这样的：
想象一下存储空间向左倾斜了45度，这样你就有了一个V形的箱子。它有一个“谷点”，在最底部(原点)
\ /
\ /
\/将一个街区放入其中，这样街区的底部角落就在谷点。
现在，从左到右，你有两个谷点，你可以在那里放置更多的区块。每次将块放入谷点时，都会修改谷点列表。
\ /
\/\/这确实浪费了空间，如果你把一个大的积木放到一个由小的积木组成的谷点，所以如果可能的话，最好先放大的积木。当您放置一个块时，您可以选择浪费空间最少的谷点。
正如我所说的，我不知道它与其他算法相比如何，但它很简单。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/6418224
复制相关文章
相似问题
腾讯云开发者
