最適なレイアウトアルゴリズム

Question

私は「すでにSPRITEをゲット！」..セクションで

http://weblogs.asp.net/zowens/archive/2008/03/05/css-sprite-for-asp-net.aspx

をこの記事に基づいて、私のASP.NETアプリケーションでのCSSスプライトセットアップを実施しています ...著者は言う...

"これは本当に面白いのは、すべての画像が縦に並んでいるということだけですが、他のほとんどのジェネレータはどういうわけか、画像を縦横に並べます。

これは私の質問がであるため、以前に解決された問題であるに違いないと確信しています。「四角形のコレクションを考えると、効率的にこれらを最適な方法でレイアウトできますか？（私はそれが最適の定義に依存していると考えますが、開始点として正方形に最も近い可能性がありますが（実際にはそうではないかもしれませんが））また、すべての長方形が事前に必要ですか？漸進的に行われますか？

Answer 1

これは、長方形のパッキングの問題として知られています。非常に単純なケースでも、最適な解を見つけることはNPハードですが、しばしば良いヒューリスティックがあります。グーグル矩形のパッキングは、興味深いアルゴリズムとコードを提供します。