algorithm - 文字 - 最長回文 アルゴリズム




2Dビンパッキングはプログラムによってどのように達成されますか? (2)

stackoverflowに関するいくつかの同様の質問がありますが、それらのどれもが、NP困難な問題やアルゴリズムをしっかりと理解していない人が理解できるという明確な答えを提供しているようです。

長方形オブジェクトの2Dビンパッキングはどのように行いますか? 私の場合は、スペースの最小量を使用して、スプライトシートとして使用するために、複数のイメージを単一のイメージにアセンブルしようとしています。 各イメージには多分異なる境界がありますが、コンテナには境界が設定されていません。

私はビンパッキングアルゴリズムの理解を持っている人がビンパッキング方法の一般的な概要を提供するのではなく、これをプログラム的に達成する方法を説明できることを期待していました。


私は "ビンの梱包コード"をGoogle検索し 、これは私の最初のヒットでした: http://codeincomplete.com/posts/2011/5/7/bin_packing/ : http://codeincomplete.com/posts/2011/5/7/bin_packing/

要約は次のとおりです。バイナリツリーを構築します。 ツリーの各ブランチにはスプライトが含まれています。 各リーフノードは使用可能なスペースを表します。 最初、ツリーには利用可能なすべてのスペースを表すルートノードだけがあります。 ツリーにスプライトを追加するには、スプライトを保持するのに十分な大きさの非占有(リーフ)ノードをツリーで検索します。 スプライトをノードの占有者として設定し、ノードに2つの子を与えることによって、そのノードをリーフから枝に変換します。 1つの子は、スプライトの右側の残りのスペースを表します。 もう一方はスプライトと最初の子の下の残りのスペースを表します。

上にリンクした記事では、ダイアグラムとJavaScriptコードを使ってこれをさらに詳しく説明しています。 また、事前に固定サイズを選択するのではなく、スプライトシートを動的に拡大する方法についても説明します。






bin-packing