二分木画像化レシピ
作り方について質問が出たので、一応参考までに簡単に説明。
- 好きな言語で、二分探索木のプログラムを書く
- 二分探索木をトラバースしながら、PostScriptを出力する
以上。PostScriptについては、A First Guide to PostScript(英語)がわかりやすい。PostScriptで作った画像をpngとかgifに変換したい場合は、ImageMagickを使いました。
PostScript自体はとても簡単で、上の画像のソースはこんな感じ。
1.000000 setlinewidth newpath 400.000000 580.000000 moveto 590.000000 568.085106 lineto stroke newpath 400.000000 580.000000 moveto 210.000000 568.085106 lineto stroke 0.550000 setlinewidth newpath 590.000000 568.085106 moveto 685.000000 556.170213 lineto stroke newpath 590.000000 568.085106 moveto 495.000000 556.170213 lineto stroke 0.325000 setlinewidth newpath 685.000000 556.170213 moveto 732.500000 544.255319 lineto stroke newpath 685.000000 556.170213 moveto 637.500000 544.255319 lineto stroke (以下同様に続く)
ちなみに、アニメーションを作るときは、上に書いたPostScriptを出力するプログラムに流しこむデータの量を変化させながら、何枚も画像を出力していった後に、全部gifに変換してgifアニメーションにまとめただけ。これもImageMagickでやった。
ちなみに、データ数が10000あって、100枚の画像でアニメーションさせるときに流しこむデータ量は、100, 200, 300, ... としていくと綺麗なアニメーションにはならないので注意。木の高さはデータ数の対数に比例してゆくので、流しこむデータ量は指数的に変化させたほうが同じ速度で木が成長しておもしろい。
uimでKDE向けのアプリケーションで日本語入力でけねーと思ってたら
apt-get install uim-qt で解決した。