最初に、決定論的なベスト フィット減少アルゴリズムから始めます。
サイズに基づいて、大きい方から小さい方へ長方形を並べます
最初の長方形を取り、収まる場合はコンテナに入れます
次の長方形を取り、切り取らずにコンテナー内の残りの最適な場所に配置します (コンテナーに収まる場合)。複数のオプションがある場合は、葉の残りの領域が最も少ないオプションを選択します。コンテナがいっぱいになるか、すべての長方形が使用されるまで、この手順を繰り返します。
コンテナーがまだいっぱいでない場合は、同じ順序で使用されていない四角形を通過しますが、今回はトリミングを試みます。
さて、それは完璧ではありません。この画像の左の 2 つのソリューションと同様の状況に陥る可能性があります。ここでは、「スペースがない」アイテムが必要ない場合でも切り取ってしまいます。
そのため、2 番目に、最初の結果にメタヒューリスティック アルゴリズムをスローします。たとえば、タブー検索やシミュレーテッド アニーリングなどです。それを行うためのオープンソース ライブラリを探している場合は、こちらをご覧ください。
これを書いている時点では、最適化しようとしている正確な基準は決まっていません。しかし、最終的に決定される基準が何であれ、次のヒューリスティック (つまり、一般的に最適ではない) アプローチが役立つ場合があります。
少数の長方形を 1 つの大きな長方形に結合するには、少数の「レイアウト」のみを検討してください。 次に、同じいくつかのレイアウトを使用して、これらの新しい長方形をさらに大きな長方形に結合する方法を再帰的に調べ、長方形が 1 つだけ残るようにします。
これは、最適なソリューションを保証するものではありません。写真の一部のサブセットは、最終的なソリューション内でサブ長方形を形成するように制限されているためです。しかし、妥当な品質のソリューションが得られる可能性が高いようです。
たとえば、3 つの長方形 A、B、C の場合、次の 4 つのレイアウトを検討してください。
A
B
C
ABC
AB (i.e. A appears on the left)
AC
AA (i.e. A appears on the top)
BC
トリミングは、3 枚の写真のグループを結合する最初のラウンドでのみ発生します。この手順では、上記の 4 つのレイアウトのそれぞれで 3 枚の写真のすべてのサブセットを検討し、それぞれに最適なスケーリングとトリミングを決定する必要があります。ただし、結果の長方形は後の手順で拡大または縮小できることに注意してください。(最適性基準の適切な選択には、特定のレイアウトの下での A、B、および C のそれぞれのスケーリングとトリミングの理想的な量が、結果の四角形がどれだけスケーリングされるかに影響されないというプロパティが必要です。問題。）
後続の結合ラウンドは同様に動作しますが、クロッピングは考慮されません。完全な解決策として、ラウンド 2 では、ラウンド 1 で生成された 3 つの長方形のすべてのセットを結合しようとしますが、このアプローチに従うと、指数関数的な爆発が発生します。写真のサブセットごとに最適な配置をいくつか保持するだけで十分です。各写真が、各ラウンドで生成される長方形の少なくとも 1 つに表示されることが重要であることに注意してください。
これが最適であると主張するつもりはまったくありませんが、試してみるのに役立ついくつかのアイデアがあります。
コメントに基づいて問題を再定義します。v x t サイズの長方形 X と、さまざまなサイズの N 個の長方形が与えられます。長方形 X を N 個の長方形で完全に覆いたいとします。元の寸法に比例して画像のサイズを変更できます。長方形 X の領域もカバーしないN 個の長方形によってカバーされる領域の量を最小限に抑えたいと考えています。
ここに1つのアイデアがあります：
それがどうなるかはわかりませんが、試してみてください。