mieki256's diary

とりあえずプログラムを書いてみないとよくわからないなと思えてきたので、HTML5 の canvas と JavaScript を使って処理が確認できるページを作成。

_長方形詰込み問題のテスト (2013/10/06 リンク先をDropboxから自宅サーバ内ページに変更)

詰込む様子をアニメで確認できる。

自分の頭が悪過ぎて、Next-Fit法モドキしか書けない…。「ランダム」で作成した矩形(=長方形)なら、それらしく見えるけど。「データ」で作成した矩形でやると、ひどいことに。

人間の目なら、「おい！ その隙間に入りそうだろ！」と分かるのだけど。コンピュータに「ここに入るかチェックしてみろや」と伝えるにはどうすればいいのやら。

ちなみに、Texture Atlas用のアレコレで実験しているので、矩形数=画像数はそれほど多くならないはずで、そこは助かりそう。本当の長方形詰込み問題は、膨大な個数を詰め込まなければいけないから、各アルゴリズムの処理時間が重要になってくるだろうけど。今回、そのあたりは無視できる。

ただ、元画像の並びをまあまあ維持できたほうが、結果画像を見た時に混乱しない予感もあるので、そのへん困るところ。

• グチャグチャに詰め込めばサイズは小さくなる、けど、見た目で並びが分かりづらい。
• 並びを分かりやすくしようとすると、グチャグチャに詰め込めないから、サイズは大きくなる。

どっちを優先しますか、という問題がありそうな気もする。…まあ、どこに何が配置されているかはxmlで出力して、プログラムはその情報を使うわけだし、画像修正する際は、元画像の修正後にその手のツールで配置し直すのが常だろうし。画像の並びなんてどうでもいいやん、という気も。基板の配線パターンの見た目に拘ったジョブズじゃあるまいし。