そのため、いくつかの長方形を入力として取り、それらを最小面積の長方形に詰め込もうとするアルゴリズムを実装しようとしています。長方形はすべて 90 度回転できます。
これはビン パッキングの問題に似ていることはわかっていますが、回転を説明する適切なアルゴリズムを見つけることができません。ここでこれについて詳しく説明している論文を見つけました。記事自体は理解していますが、もっと簡単なものを見つけたいと思っていました。
助言がありますか？
-編集-
私は以前の問題を誤って述べたと思います。それぞれが 90 度回転できるように、多数の長方形が与えられます。囲まれている長方形の面積を最小限に抑えながら、2 つの長方形が重ならないように、指定されたすべての長方形に適合する長方形を見つける必要があります。
ここで私が直面する問題は、囲みの四角形が与えられ、与えられた四角形が収まるかどうかをチェックするのではなく、最小値を見つけるように求められることです。
このアルゴリズムを使用して良い結果が得られました。
http://www.intechopen.com/articles/show/title/a_greedy_algorithm_with_forward-looking_strategy
編集：
私が提供したリンクで説明されているアルゴリズムは、特定の長方形のセットを特定の囲み長方形にパックできるかどうかについて、「はい」または「いいえ」の答えを提供します。最小の囲み四角形を見つけるために、アルゴリズムを繰り返し実行できます。基本的に、囲んでいる四角形の下限と上限を計算し、バイナリ検索を実行して、それらの境界内に収まる最小の解を見つけます。囲んでいる四角形は 1 次元で固定サイズであると想定しています (つまり、幅は一定で、最小の長さを探しているか、またはその逆です)。囲んでいる四角形の幅と長さの両方を変更できる場合は、より困難になり、うまくいかない可能性があります。
下限と上限を計算するための単純な (しかし素朴な) アプローチは、次のようになります。
下限 - 最良のケースは、すべての四角形を無駄なスペースなしで完全にパックできることです。したがって、すべての入力長方形の面積を合計し、その面積に必要な囲み長方形の長さを計算します。
上限 - 最悪の場合、各四角形を個別の「行」にパックする必要があるため、入力四角形ごとにmin(width, height)それらを計算して合計します (つまり、各入力の最小幅または高さを使用して、入力四角形を互いに積み重ねるふりをします)入力の他の次元が囲む長方形の幅を超えないようにします)。
もう少し頑張れば、下限と上限を大幅に改善して検索スペースを削減できますが、これが出発点になります。