矩形のUIオブジェクトを隙間のない抽象的な方法で配置する

Question

さまざまな幅と高さを持つ50個の画像のコレクションを考えると、それらをプログラム的に面白い抽象的な方法でどのように並べるのですか？興味深いことで（下図参照）

• 私は、何の大きなギャップ、無容易に区別行または列を（負の空間がT状交点の多くを形成する）を意味しません。私の特定のケースでは

、すべての画像は、高さや幅が150ピクセルの最大（150ピクセルで450px、378pxかによって150ピクセルすることができる）であることを意味する可能性があり、150ピクセルの最大設定寸法を有します。

それは古典的なプログラミングの課題となる可能性がありますが、私はGoogleにハードな話題を見つけてるようこれは思える...

EDIT：全体的な配置でなければなりませんどのように制限がないことを示すために、画像に変更（セットエリア内に収まる必要はありません）

Answer 1

問題はNP-Hardです。

This threadは、1つのタイプのnXm四角形であっても、解決策があるかどうかを調べるのはNP-Hardであることを示しているため、NP-Hardも同様です。しかし、通常、非最適な結果を見つける - あなたは後の溶液、または速くなりますgenetic algorithmsまたはhill climbingようなヒューリスティックなアプローチを、最適化されている場合backtrackingソリューションを試みることができる

この問題のプライベートケース]。あなたはjQueryプラグインに反対されていない場合は

Answer 2

、あなたはこれをチェックアウトすることができます - （それはおそらく最も洗練されたソリューションではありませんが）私はこれに似た何かを構築していますhttp://masonry.desandro.com/

Answer 3

。私のアプローチは、quadtreeを使用してキャンバスに配置した矩形を整理することでした。私はちょうど基本的にスパイラルで中心点を回り、新しい四角形を配置しようとし、四分木を使って衝突を検出しました。私が衝突を検出した場合、私は矩形の中心に最も遠くに衝突した矩形の端に配置しようとしていた長方形を移動し、衝突チェックプロセスを繰り返します。

また、おそらく最も洗練された方法ではないかもしれませんし、長方形の間にいくつかの大きな隙間を残す傾向があります（それらの境界線は一様ではありません）。