長方形(矩形)詰込み問題の動作テスト

Next-Fit法(余白大): 左から右へ矩形を並べ、配置先の横幅を超えたら、縦にレベルを1段追加して配置を続ける。チェックに使う矩形は、未配置の矩形の1番最初のみ。
Next-Fit法(余白中): 右に並べられるかチェックする際、未配置の矩形を全て使って調べる。
空き領域管理: 矩形を配置するたびに、空き領域を登録する。(1つの空き領域に矩形を1つ置くと、元の空き領域は分割され、0～2個の空き領域ができる。)
総当たりで置いてみる版: 矩形を置くたびに、次に矩形を置けそうな座標をバッファに登録する。バッファの中から座標を取り出し、矩形を置いてみて、既に配置済みの矩形と重ならないなら、そのまま配置する。
BLF法(Bottom-Left-Fill): BL安定点(下にも左にも矩形をそれ以上動かせない点。このページの例では上下が逆で、上にも左も動かせない点)の候補を探し出し、それら一つ一つの座標で矩形が置けるか総当たりで調べる。

矢印の順番でボタンを押していけば、詰めていく様子が見られる。
えてして、Next-Fit法が無駄が多く、BLF法が一番無駄なく詰め込んでくれるはず。(「データ1」で矩形を生成すると分かりやすい。)
「ソート」を省略して詰めてみると、どの方法も無駄が多くなるのが確認できる。前処理としてソートはかなり重要。
処理が遅い時は以下を設定。
- 「空き領域・BL安定点の描画設定」の「描画しない」にチェックを入れる。
- 「アニメの時間間隔」を0にする。
- 「BL安定点候補を積極的に除去」にチェックを入れる。

Last Y =