c++ - 回転せずに長方形をパッキングしますか?

Question

回転せずに四角形をパッキングするアルゴリズムはありますか?

おそらくC++での実装ですか？

私はこれを見つけました

と

• ギロチンビンパック
• シェルフビンパック
• SkylineBinPack

しかし、それらは長方形を回転させます。

Answer 1

ボックスを幅で並べ替えて、ツリーのノードに配置できます。次に、ツリーを 2 軸に沿って分割します。次のボックスでは、最も適合するもの、つまり無駄が最も少ないものを探し、そのボックスを空きノードに配置します。ボックスまたはノードが残らなくなるまで、すすぎ、繰り返します。blackpawn による kd-tree を使用してライトマップをパッキングすることを検討できます。

Answer 2

この小さなコードを使用して、長方形をパックできます。

http://www.flipcode.com/archives/Rectangle_Placement.shtml

Answer 3

ボックスを正方形にして、梱包後の回転を無視することができます。これはいくらかのスペースを浪費しますが、ギロチン ライブラリを変更する必要はありません。