找到包含所有矩形的最小区域

Question

这是一个面试问题。
我们被赋予各种矩形的尺寸，我们必须找出可以包围所有矩形的矩形面积（最小值）？矩形也可以旋转。

test case:-
input:
3   //number of rectangles
8 8
4 3
3 4

output:
88

11x8:
+ - - - - - - + + - +
|             | |   |
|             | |   |
|             | + - +
|             | + - +
|             | |   |
|             | |   |
+ - - - - - - + + - +

在将矩形拟合到最小可能区域之前，我曾问过一个类似的问题。
上述方法考虑了所有可能性、旋转，并在所有布局情况下确定了所有此类可能性的最小值<我们不能先求矩形面积之和，然后再求最大长度、最大宽度吗？

Answer 1

首先你应该检查，外接矩形是否可以旋转？无论如何，你可以忽略“矩形”的情况，并解决点的任务。你有一系列的点(矩形的顶点)。你的任务是找到面积最小的编码矩形。如果包围矩形不能旋转，那么解是愚蠢的，复杂度为O(n)。

生成矩形数组并生成点数组，这些点是矩形的顶点。接下来很简单:

long n; // Number of vertexes
point arr[SIZE]; //Array of vertexes
long minX = MAXNUMBER, minY = MAXNUMBER, maxX = -MAXNUMER, maxY = -MAXNUMBER;
for (long i = 0; i < 4 * n; i++)
{
    minX = MIN(minX, arr[i].x);
    minY = MIN(minY, arr[i].y);
    maxX = MIN(maxX, arr[i].x);
    maxY = MIN(maxY, arr[i].y);
}
long width = maxX - minX, height = maxY - minY;
printf("%ddX%ld", width, height);

如果矩形可以旋转，则是另一个任务。那么你应该首先：

< li >构建矩形中所有点的最小凸多边形。你可以使用任何现有的算法。复杂度O(n log n)。比如“格拉汉姆的扫描”:http://en.wikipedia.org/wiki/Graham's_scan < li >对凸多边形使用简单算法。链接:http://cgm.cs.mcgill.ca/~orm/maer.html

维基中任务的链接：http://en.wikipedia.org/wiki/Minimum_bounding_rectangle

Answer 2

非正方形基准上的最佳矩形包装：

给定一组矩形，我们的问题是找到所有最小面积的封闭矩形，这些矩形将包含它们而不重叠。我们将封闭矩形称为包围盒。优化问题是NP难的，而通过装箱的简化，确定一组矩形是否可以在给定的边界框中装箱的问题是NP完全的（Korf 2003）。

最佳矩形填料的新改进：

Korf[2003]将矩形布局问题分为两个子问题：最小包围盒问题和包含问题。前者找到一个最小面积的边界框，该边界框可以包含一组给定的矩形，而后者则试图将给定的矩形封装在一个给定的边界框中。求解最小边界盒问题的算法将求解包含问题的算法作为子程序调用。

解决最小边界盒问题的一种简单方法是找到描述可行和潜在最优边界盒集的最小和最大区域。可以使用该范围内的面积生成所有维度的边界框，然后按面积的非递减顺序进行测试，直到找到最小面积的所有可行解。最小面积是给定矩形的面积之和。最大面积由贪婪解决方案的边界框确定，通过将边界框高度设置为最高矩形的高度，然后在从左到右扫描时将矩形放置在第一个可用位置，并对每列从下到上扫描来确定。

另请参见最佳矩形布局:新结果。

Answer 3

这个问题没有绝对的解决方案，但有几种近似的解决方案。你可以在这里阅读其中的一些。