10

这是一道面试题。
我们得到了各种矩形的尺寸，我们必须找出可以包围所有矩形的面积（最小）？矩形也可以旋转。

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

output:
88

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

在将矩形拟合到最小可能区域 之前，我查看了一个类似的问题
，上述方法着眼于所有可能性、旋转，并确定所有布局案例中所有此类可能性的最小值。
难道我们不能建立一个算法，首先找到矩形面积的总和，然后寻找最大长度，宽度？

4

3 回答 3

7

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

于 2012-09-17T09:23:03.757 回答
7

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

给定一组矩形，我们的问题是找到所有最小面积的封闭矩形，这些矩形将包含它们而不重叠。我们将封闭矩形称为边界框。优化问题是NP-hard，而决定一组矩形是否可以打包在给定边界框中的问题是NP-complete，通过减少 bin-packing (Korf 2003)。

最佳矩形包装的新改进：

Korf [2003] 将矩形打包问题分为两个子问题：最小边界框问题和包含问题。前者找到一个面积最小的边界框，可以包含给定的一组矩形，而后者试图将给定的矩形打包在给定的边界框中。解决最小边界框问题的算法将解决包含问题的算法称为子程序。

最小边界框问题

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

另请参见最佳矩形包装：新结果。

于 2012-09-17T19:55:42.030 回答
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);

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

  1. 构建矩形中所有点的最小凸多边形。您可以使用任何现有的算法。复杂度 O(n log n)。例如“格雷厄姆的扫描”：http ://en.wikipedia.org/wiki/Graham%27s_scan
  2. 对凸多边形使用简单的算法。链接：http ://cgm.cs.mcgill.ca/~orm/maer.html

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

于 2012-09-17T09:03:02.987 回答