重複の可能性:
かなり最適な方法で長方形をパッキングするために必要なアルゴリズム
それぞれランダムなサイズ (ランダムな幅と高さ) のN 個の長方形があります。すべての長方形は、X 軸と Y 軸に平行です。結果の境界長方形の面積が最小になり、入力長方形の周囲/間の潜在的なギャップができるだけ小さくなるように、これらの長方形を並べて配置するのに役立つアルゴリズムを探しています。長方形は回転できず、互いに重なり合うことはできません。
(スプライト シートを作成し、アニメーターから取得したさまざまな画像からスプライトの位置を保存できるように、ゲーム スプライトの配置を自動化するためにこれらが必要です。)
例えば:
+---+ +----------+
| 1 | | 2 |
+---+ +----------+ +----------+.. +---+----------+
| 2 |.. | 1 | 2 |
+--------+ ===> +--------+-+-+ vs +---+----+-----+
| | | | 1 | | |......
| 3 | | 3 +---+ | 3 |......
+--------+ +--------+.... +--------+......
Unused: 8 Unused: 18
未使用のスペースは、図面内のドット (.) でマークされています。最初の結果には、未使用のスペースが小さい境界四角形があるため、入力四角形のこの配置を見つけることが望ましいでしょう。
これに役立つアルゴリズムはすでにありますか?私は多くのグーグルを行いましたが、ほとんどの結果は、最小の境界長方形を見つけること、または N 個の長方形が事前に定義された領域をカバーしているかどうかを見つけることに関連しています。