7

重複の可能性:
かなり最適な方法で長方形をパッキングするために必要なアルゴリズム

それぞれランダムなサイズ (ランダムな幅と高さ) のN 個の長方形があります。すべての長方形は、X 軸と Y 軸に平行です。結果の境界長方形の面積が最小になり、入力長方形の周囲/間の潜在的なギャップができるだけ小さくなるように、これらの長方形を並べて配置するのに役立つアルゴリズムを探しています。長方形は回転できず、互いに重なり合うことはできません。

(スプライト シートを作成し、アニメーターから取得したさまざまな画像からスプライトの位置を保存できるように、ゲーム スプライトの配置を自動化するためにこれらが必要です。)

例えば：

+---+   +----------+
| 1 |   |    2     |
+---+   +----------+                 +----------+..           +---+----------+
                                     |    2     |..           | 1 |    2     |
+--------+                ===>       +--------+-+-+    vs     +---+----+-----+
|        |                           |        | 1 |           |        |......
|    3   |                           |    3   +---+           |    3   |......
+--------+                           +--------+....           +--------+......

                                       Unused: 8                 Unused: 18

未使用のスペースは、図面内のドット (.) でマークされています。最初の結果には、未使用のスペースが小さい境界四角形があるため、入力四角形のこの配置を見つけることが望ましいでしょう。

これに役立つアルゴリズムはすでにありますか？私は多くのグーグルを行いましたが、ほとんどの結果は、最小の境界長方形を見つけること、または N 個の長方形が事前に定義された領域をカバーしているかどうかを見つけることに関連しています。

4

1 に答える 1

3

で提案されている解決策は、さまざまなサイズの四角形を可能な限り最適な方法で最小の四角形にパックするために使用できるアルゴリズムは何ですか? 見栄えは良いですが、少し変更します。境界ボックスを最小領域で貪欲に拡張するのではなく、最小領域まで貪欲に拡張し、残りの四角形で使用される領域よりも大きなスペースを残します。また、最大面積ではなく最大寸法で次の長方形を選択します。

これにより、早い段階でより多くのスペースが確保され、最後の最後にスペースが常に不足してほとんど空のマージンが残ることを防ぐことができます。

于 2013-01-11T03:44:11.597 に答える