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

Question

因此，我正在尝试实现一种算法，该算法将多个矩形作为输入并尝试将它们打包成最小面积的矩形。矩形都可以旋转 90 度。

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

有什么建议吗？

-编辑-

我想我之前错误地陈述了这个问题。我们有许多矩形，每个矩形都可以旋转 90 度。我们需要找到一个适合所有给定矩形的矩形，使得没有两个矩形重叠，同时最小化封闭矩形的面积。

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

Answer 1

我使用这个算法得到了很好的结果:

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

编辑:

我提供的链接中描述的算法会给您一个"is"或“否”的答案，以确定一组给定的矩形是否可以打包到一个特定的封闭矩形中。要找到最小外接矩形，可以重复运行该算法。基本上，计算封闭矩形的下限和上限，然后进行二分搜索以找到落在这些边界内的最小解。我假设封闭矩形在一个维度上是固定大小的(即，宽度是恒定的，寻找最小长度，反之亦然)。如果封闭矩形的宽度和长度都允许变化，那么它就更难了，这可能行不通。

计算下限和上限的简单(但天真)方法如下:

Lower Bound - 最好的情况是所有矩形都可以完美地打包，而不会浪费任何空间。因此，将所有输入矩形的面积相加并计算该面积所需的外接矩形长度。

上限 - 最坏的情况是每个矩形必须打包在单独的“行”中，因此对于每个输入矩形，计算 min(width, height) 并对它们求和(即，假装输入矩形使用每个输入的最小宽度或高度相互堆叠，这样输入的另一维不超过封闭矩形的宽度。

如果你再努力一点，你可以显着提高下限和上限以减少搜索空间，但这应该给你一个起点。