我希望我的标题有意义，但这是我想要做的：
我有n矩形，每个矩形的宽度为 W n和高度为 H n，我需要将它们排列在二维 (x,y) 平面上，它们都适合的矩形占用的面积最小。我还需要能够确定 (x,y) 对应于哪个矩形。
我更喜欢伪代码中的东西，但可以使用多种语言。
感谢您的帮助。
问问题
2223 次
4 回答
2
这是一个很难以最佳方式解决的问题，但是有一些解决方案并不难实现，并且代表了许多用途（例如纹理）的良好近似值。尝试用谷歌搜索“矩形（角度）包装”......你会发现很多解决问题的代码。
于 2010-12-25T23:18:23.970 回答
1
对我来说听起来 NP 完全。有点像背包问题。这意味着没有真正的解决方案。只有好的近似值。
于 2010-12-25T23:19:19.167 回答
1
它是 2D bin 打包的变体。您的容器是灵活的这一事实，允许进行更多优化，也使其更具挑战性（如困难）。Drools Planner（开源java）可以处理这个。至少存在一个使用 Drools Planner 的实现（参见用户邮件列表）（非开源）。如果您需要一个开源示例作为起点，那么 drools-planner-examples 中的云平衡可能是一个很好的起点。
有关您可以使用的算法的概述，请参阅我对类似问题的回答。
于 2010-12-26T12:33:40.153 回答
0
您的问题称为 2D 打包问题。甚至一维问题也是 NP 难的。有关某些方法的好文章以及示例 C# 代码，请参见此处。
另外，请参阅以下问题：
于 2010-12-25T23:20:40.837 回答