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 困難ですが、一連の四角形を特定のバウンディング ボックスにパックできるかどうかを決定する問題は、ビン パッキング (Korf 2003) からの削減によるNP 完全です。

Optimal Rectangle Packing の新しい改善:

Korf [2003] は、四角形のパッキング問題を 2 つのサブ問題に分割しました: 最小バウンディング ボックス問題と包含問題です。前者は、指定された長方形のセットを含むことができる最小面積の境界ボックスを見つけますが、後者は、指定された長方形を指定された境界ボックスに詰め込もうとします。最小バウンディング ボックス問題を解決するアルゴリズムは、包含問題を解決するアルゴリズムをサブルーチンとして呼び出します。

最小バウンディング ボックスの問題

最小境界ボックスの問題を解決する簡単な方法は、実行可能で潜在的に最適な境界ボックスのセットを表す最小領域と最大領域を見つけることです。この範囲内の領域ですべての次元のバウンディング ボックスを生成し、最小領域のすべての実行可能なソリューションが見つかるまで、領域の減少しない順序でテストできます。最小面積は、与えられた長方形の面積の合計です。最大領域は、バウンディング ボックスの高さを最も高い四角形の高さに設定し、左から右にスキャンするときに最初に使用可能な位置に四角形を配置することによって検出された貪欲なソリューションのバウンディング ボックスによって決定されます。下から上へ。

最適な長方形パッキング: 新しい結果も参照してください。

于 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)。例として「Graham's Scan」: 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 に答える