给定一些可以旋转的矩形，找到一个最小面积的外接矩形。

Question

所以，我正在尝试实现一个算法，它以矩形的数量作为输入，并尝试将它们打包到最小面积的矩形中。所有矩形都可以旋转90度。

我意识到这与装箱问题类似，但我无法找到一个好的算法来考虑旋转。我找到了一篇详细讨论此问题的论文这里，虽然我理解了文章本身，但我希望能找到更简单的东西。

有什么建议吗？

-编辑-

我想我之前误述了问题。我们得到了一些矩形，每个矩形都可以旋转90度。我们需要找到一个矩形，使所有给定的矩形都适合其中，而不会重叠，同时最小化包围矩形的面积。

我在这里面临的问题是我们被要求找到最小值，而不是给出一个包围矩形并检查给定的矩形是否适合或类似的事情。

- efficiencyIsBliss

Answer 1

我使用这个算法得到了不错的结果：

http://www.intechopen.com/articles/show/title/a_greedy_algorithm_with_forward-looking_strategy

编辑：

我提供的链接中描述的算法将给出“是”或“否”的答案，以确定给定一组矩形是否可以放入特定的包围矩形中。要找到最小的包围矩形，您可以重复运行算法。基本上，计算包围矩形的下限和上限，然后进行二分查找，以找到在这些范围内的最小解决方案。我假设包围矩形在一个维度上是固定大小的（即宽度恒定，寻找最小长度或反之亦然）。如果包围矩形的宽度和长度都允许变化，则更加困难，可能无法使用此方法。

计算下限和上限的一种简单（但天真）方法如下：

下限 - 最好的情况是所有矩形都可以完美地放置而不会浪费任何空间。因此，求出所有输入矩形的面积总和，并计算所需的包围矩形长度。

上界 - 最坏情况是每个矩形必须被放置在单独的“行”上，因此对于每个输入矩形，计算min(width, height)并将它们相加（即假设输入矩形堆叠在一起，使用每个输入的最小宽度或高度，使得输入的另一个维度不超过包围矩形的宽度）。

如果您再努力一些，可以显著改善下限和上限，以减少搜索空间，但这应该为您提供了一个起点。

- cbranch