再帰曲線

東京大学新聞に2012年度後期日程入試問題が掲載されていた. その総合科目IIにフラクタルの絵があった. 問題はフラクタル次元を計算するものだが, 私としてはその絵を描くプログラムに関心があった.

まず図はこういうものだ.


左からF₁, F₂, F₃

左からG₁, G₂, G₃
問題に記述はこうだ.

はじめに, 1辺の長さ1の正方形をF₀とする. F₀を, 1辺の長さ1/3の9個の小正方形に分割し, 中央の小正方形を取り去ったものをF₁とする.  また, それぞれの小正方形を1辺の長さ1/3のユニットと呼ぶ. 次に, F₁ を構成する8個のユニットのそれぞれについて, これを9個の小正方形に分割し, そこから中央の小正方形を取り去ったものをF₂とする.  また, この分割で得られたそれぞれの小正方形を1辺の長さ1/9のユニットと呼ぶ. 以下, 同様の操作を繰り返して得られる図形をF₃, F₄, ...とする.

PostScriptのこのプログラムは次のようだ.

/n 5 def
/l 540 def
/xs [0 1 2 0 2 0 1 2] def
/ys [0 0 0 1 1 2 2 2] def
/a {n 0 eq {0 0 moveto l 0 rlineto 0 l rlineto l neg 0 rlineto
 closepath fill}
 {/n n 1 sub def
 gsave 1 3 div dup scale
 0 1 7 {/i exch def
 xs i get l mul ys i get l mul gsave translate a grestore} for
 grestore
 /n n 1 add def} ifelse} def
 40 40 translate a

まず全体の次数nを決める. この例では5. 1辺の長さlも決める. 次に8個の正方形を描くので, その順に左下のxとy座標のリストxs, ysを書く. そしてユニットを描く手続きaの定義だ.



n=0なら, 長さlの正方形を書く. そうでないならnを1減らし, スケールを1/3にする. dupはx座標とy座標の両方を1/3にするためのもの. gsaveとそれに見合うgrestoreは, スケールや原点を変えるとき, 以前の環境をスタックするものである. xsとysから各小正方形の原点の座標をとり, 図を各手続きaを呼ぶ.

こうしてn=5を描いたのがこれだ.



次のは少し手ごわい.

はじめに, 1辺の長さ1の正方形G₀を, 1辺の長さ1/2の正方形ユニット4個に分け, 右上のユニットについては, 左下の1辺1/4の正方形を取り去る. こうして得られた図形をG₁とする. 次に, 残った3個の, 欠陥のないユニットのそれぞれについて, 同様の操作を行なう. すなわち, それぞれを4個の1辺の長さ1/4のユニットに分け, 右上にユニットについては左下の1辺の長さ1/8の正方形を取り去る. 得られた図形G₂とする. 続いて, G₂に含まれる1辺の長さ1/4の, 欠陥のない各正方形ユニットについて, 同様の操作を行なう. 得られた図形をG₃とする. これを繰り返して得られる図形の列をG₁, G₂, G₃, ...とする.

目で見ると簡単だが, 欠陥のない正方形をどう判定するか.

私の考え方はこうだ.

各正方形を4区画に分け, 左下, 右下, 左上, 右上の順に下請けに渡すとする. G₀を描く手続きをaとすると, 1/2のサイズで, a,a,aと3回呼び, 最後に左下を取り除いた正方形を描く手続きbを呼ぶ.

aはnを1減らして, a,a,a,bと呼べば良い. bはnを1減らし, 左下を除いて, a,a,aと呼べば良い. そう考えて書いたのが, このプログラムだ. 上のプログラムが理解出来れば, こちらも分かるだろう.

/n 7 def
/l 540 def /l2 l 2 div def
/a {n 0 eq{0 0 moveto l 0 rlineto 0 l rlineto l neg 0 rlineto
 closepath fill}
 {/n n 1 sub def
 gsave
 0.5 dup scale
 gsave 0 0 translate a grestore
 gsave l 0 translate a grestore
 gsave 0 l translate a grestore
 gsave l l translate b grestore
 grestore
 /n n 1 add def} ifelse} def
/b {n 0 eq{
 l2 0 moveto l2 0 rlineto 0 l rlineto l neg 0 rlineto
 0 l2 neg rlineto l2 0 rlineto closepath fill}
 {/n n 1 sub def
 gsave 0.5 dup scale
 gsave l 0 translate a grestore
 gsave 0 l translate a grestore
 gsave l l translate a grestore
 grestore
 /n n 1 add def} ifelse} def
 40 40 translate a

この結果, n=7で描いたのが, 下の図である.



PostScripでこういう図を描くのは思ったより易しい.