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

Question

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

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

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

Answer 1

I Googled "bin packing code"、これが私の最初のヒットだった：http://codeincomplete.com/posts/2011/5/7/bin_packing/

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

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

Answer 2

必要なのはここにある：https://github.com/juj/RectangleBinPack

紙とまともなC++実装があります。

あなたも、シンプルな擬似コードが必要な場合は、このサイトを見てみましょう：http://www.blackpawn.com/texts/lightmaps/

「ギロチンパックは、」そこツリーベースのパッキングと呼ばれています。