sankantsuのブログ

技術メモ・競プロなど

TeXでドラゴン曲線を描く

概要

ドラゴン曲線というフラクタル曲線の一種をTeXを使って描いてみる. この題材はTeXブックに載っている有名(?)なもので,今回は元のプログラムを参考にしつつ簡易的なバージョンに書き直した.

出力結果を画像にすると以下のような感じ.

ドラゴン曲線

コード

github.com

pdftexコンパイルできるサンプルを用意した. 以下,実装について説明する.

解説

全体の流れ

まず,線の構成要素をボックスとして用意しておく. ここでは縦/横方向の線を構成要素として使った(線は\vruleを使って描ける). 基本的にはこの縦線または横線を\kern, \raiseといったTeXのプリミティブを使って位置を調整しながら並べることで任意の線を描く.

毎回プリミティブを使って位置制御をするのは大変なので,現在の位置から紙面の上下左右に向かって線を伸ばすという操作をするマクロを定義する (\goEast, \goNorth, \goWest, \goSouth).

また,現在の進行方向に対して相対的に直進,後退,左折,右折ができるようなマクロも用意する (\S,\B,\L,\R). さらに,\S,\B,\L,\Rを並べた命令列を受け取って連続した線を描くようなマクロpathを用意する.

最後に,ドラゴン曲線の再帰的な定義を使って\pathコマンドを使ってドラゴン曲線を描く.

縦線と横線の用意

\newdimen\lineLength
\newdimen\lineWidth
\newbox\vLine
\newbox\hLine

\lineLength=5pt
\lineWidth=0.3pt

\setbox\vLine=\hbox{\vrule height\lineLength width\lineWidth}
\setbox\hLine=\hbox{\vrule height\lineWidth width\lineLength}

\newdimen, \newboxというのはそれぞれレジスタを確保するための命令で,それぞれ寸法 (pt とか cm とか) を保存するレジスタ,ボックス (文字列を組版したまとまりを入れておく箱) を保存するレジスタを確保する.

線の長さ, 幅の適切な寸法をそれぞれ \lineLength, \lineWidth という名前で設定しておく.

設定した寸法を使って \vrule を使って線を描き,縦の線を \vLine, 横の線を \hLine というボックスに入れておく.

上下左右の移動

\newcount\dir
\newdimen\y

\def\goEast{\raise\y\copy\hLine \global\dir=0\relax}
\def\goNorth{\raise\y\copy\vLine \kern-\lineWidth \global\advance\y\lineLength \global\dir=1\relax}
\def\goWest{\kern-\lineLength \raise\y\copy\hLine \kern-\lineLength \global\dir=2\relax}
\def\goSouth{\global\advance\y-\lineLength \raise\y\copy\vLine \kern-\lineWidth \global\dir=3\relax}

\yというのは,現在のy座標を覚えておくためのレジスタである. 線を描く前に \raise\y として \y に入っている値ぶんだけ組版位置を上方向に上げておくことで上下位置の調整を行う.

x方向の調整は,文字の組版によって自動的にx座標が右に文字幅ぶんだけ動くことと,\kern という命令によって明示的に左右方向の位置を動かすことによって行う.

\dir はここまでの分ではなくてもかまわないのだが,現在の進行方向を入れておくためのレジスタで,次に進行方向に対する相対的な移動を実装するために使う.

進行方向に対する相対的な移動

\def\S{\ifcase\dir \goEast \or\goNorth \or\goWest \or\goSouth \fi} % move straight
\def\B{\ifcase\dir \goWest \or\goSouth \or\goEast \or\goNorth \fi} % move back
\def\L{\ifcase\dir \goNorth \or\goWest \or\goSouth \or\goEast \fi} % move left
\def\R{\ifcase\dir \goSouth \or\goEast \or\goNorth \or\goWest \fi} % move right

\def\path#1{\hbox{\dir=0\y=0pt#1}}

このステップは比較的単純で\ifcaseという命令を使って現在の進行方向\dirを参照して紙面での上下左右移動を選択するだけである.

\ifcaseについて簡単に説明しておくと,

\ifcase<number> <case0> \or<case1> \or<case2>... \else<other cases>\fi

という書式で,<number>の値が0なら<case0>を展開,1なら<case1>を展開... という具合に分岐し,どれにも当てはまらなければ <other cases> を展開する.

\pathは単にy座標と向きを初期化したあと渡された命令列を展開してできた組版結果をまとめるだけである.

ドラゴン曲線を描く

\newcount\n
\def\dragon{\ifnum\n>0{\advance\n-1 \dragon\L\nogard}\fi}
\def\nogard{\ifnum\n>0{\advance\n-1 \dragon\R\nogard}\fi}

\centerline{\path{\n=13 \dragon}}

いよいよ最後のステップであるドラゴン曲線の描画である. ドラゴン曲線は次数によって再帰的に定義されていて,

  • 最初 (n=1) はただの直線
  • n=k+1 の曲線は,n=k の曲線を描いたあと左に曲がり,逆向きに n=k の曲線を描いたもの

という手順で構成できる.

Wikipedia にアニメーションが置いてあって,とてもわかりやすい.

Dragon curve - Wikipedia

実装は素直に再帰的定義をなぞったものになっていて,\nを1減らして\dragonを描き,左に曲がって\nogard(\dragonの逆)を描く. ポイントとしては,\n を1減らす \advance\n-1 という命令の効果が {...} で囲んだグループに対してローカルになるところで,\dragonが展開されるたびにローカルに \n を更新することで再帰的な定義を再現できるようになっている.