![見出し画像](https://assets.st-note.com/production/uploads/images/76081620/rectangle_large_type_2_258325fb169975d28de73674854f5473.png?width=800)
再帰図形 (1)
この節は,かなりプログラミング寄りな内容になっています。
「自己相似形」はフラクタルの重要なキーワードです。
フラクタルCGコレクション(渕上季代絵著:サイエンス社) (以下,「この本) では,まず再帰図形について説明とプログラムが示されています。再帰図形とは,「再帰的( Recursive ) な規則に基づいて無限に繰り返される図形」です。はじめに次のような図が例として載っています。
![画像3](https://assets.st-note.com/production/uploads/images/76022437/picture_pc_e255318ebcf379fc14e70a4d00b219e8.png?width=800)
円の中に2つの円が並んでいます。(左) そのそれぞれの円の中に2つの円が並んでいます。(中央) これを繰り返していくと右の図になります。これが自己相似形です。
中に描く円は3つ以上でも構いません。次のページにインタラクティブに動かせるものを載せました。
右上にスライダがあり,中に描く円の数と,反復の回数を選ぶことができます。たとえば,中の円が3つで,4回繰り返した場合が次の図です。
![画像4](https://assets.st-note.com/production/uploads/images/76045455/picture_pc_b9f1ba982aa578a2156303bff75c69c4.png?width=800)
2つの場合に戻りましょう。この図を描く方法として,この本では次のアルゴリズムを示しています。
・2つの円のうち,右側の円だけを最終レベルNまで描く。下図 a
・N-1 レベルの値を使って,最終レベルの左側の円を描く。下図b
・N-2 レベルの値を使って,N-1 レベルの左側の円を描き,その中に右側の円を描く。
・レベルを順に下げながら同様にして描いていく。少し進んだのが下図cとその右
![画像2](https://assets.st-note.com/production/uploads/images/76016051/picture_pc_67d8eb7aa5f82f18cbcc5853a805bc29.png?width=800)
次がそのプログラムです。言語はN88BASIC。
![画像1](https://assets.st-note.com/production/uploads/images/76015378/picture_pc_6c97589a600ef94c8df2d02bbfa56cf2.png?width=800)
上から順に読んでいくと100 行目(行番号の100) に GOTO が出てきます。 G3 というラベルのついたところに飛びます。200行目から進みますと220行目で GOTO で 260行 に飛びますが,これで実行は終わります。いずれも IF ですから,条件が成り立てば飛び,成り立たなければそのまま進むわけです。
では,成り立たないとして進んでみましょう。順に180行目まで行きますが,ここは IF ではないので,無条件で G1 に飛びます。ということは,80行目のG1 からここまでがループのように思えますが,G3はこのループの外にあるので,100行目の IF I>N が成り立つとループの外に出ることになります。
ここまでならよいのですが,250 行で GOTO G2 ということは,ループの中の途中に飛ぶことになるのです。
さあ,実行手順を追えたでしょうか。
これが,この本が出版された1997年(昭和62年)のころの標準的なプログラムだったのです。
これをこのままCindyScriptに移植することはできません。CindyScriptではループの途中で抜ける break は用意されていないのです。Pythonなどでも無理でしょう。 break はありますが,ループの外からループの中に飛ぶということは通常はしません(多分できないでしょう)。
そこで,次のようにアルゴリズムを変えます。
(1) 円の中に2つの円を描く。描いた円の中心と半径を記録する。(下図左)
(2) 記録された中心と半径を用いて,その円の中に2つの円を描いて,描いた円の中心と半径を記録する。(下図2番目以降)
![画像5](https://assets.st-note.com/production/uploads/images/76045585/picture_pc_6cebee6d512168f0f6654ede0b7bad46.png?width=800)
どうでしょうか。こちらの方が,自己相似形をそのままプログラムしたものといえるのではないでしょうか。これがこれまでに出てきている「反復関数系」です。つまり,(1) の手続きを関数として定義し,この関数を反復して使うのです。 次に示すのがCindyScriptで書いたコードです。
// [中心,半径]のリストを引数として中の円を描く
// 戻り値は中に描いた円の[中心,半径]のリスト
drawfig(list):=(
ret=[];
c=list_1;
r=list_2;
rd=r/2;
repeat(2,s,
center=c+r/2*[cos(s*pi),sin(s*pi)];
drawcircle(center,rd);
ret=append(ret,[center,rd]);
);
ret;
);
Loop=1; // 繰り返し数
clist=[[[0,0],6]]; // 最初の円
drawcircle(clist_1_1,clist_1_2);
repeat(Loop,
newlist=[];
forall(clist,
newlist=newlist++drawfig(#);
);
clist=newlist;
);
コードの内容を細かく説明すると長くなりますので要点だけ。
// で始まるのはコメント文です。
はじめに,中の円を描いて,その中心と半径をリストにして返す関数 drawfig() を定義しています。
repeat は繰り返し。Python 等では for 文です。
drawcircle() は中心と半径を与えて円を描く組み込み関数。
forall(clist,
newlist=newlist++drawfig(#);
);
ここはCindyScript独特の組み込み関数を使っています。
forall は,リストの各要素に対して,そのあとに示す操作を行うものです。各要素は#で表されます。Pythonなら for文で繰り返せばよいでしょう。違いは,リストの長さを求める必要がないということです。
++ はリストを連結する演算子です。
したがって,やっていることは,clist のすべての要素に対し,drawfig() を実行して円を描き,戻り値のリストを newlist に追加(連結)することです。drawfig() の戻り値はリストなので,append で追加するのではなく,連結します。
これで,中の円を描いたあとの,各円の中心と半径のリストが得られます。このリストで clist を更新して繰り返すわけです。
drawfig() の中の rd=r/2 で,中に描く円の半径を半分にしています。また,center=c+r/2*[cos(s*pi),sin(s*pi)] で,中に描く円の中心を決めています。s は繰り返しの変数なので,1回目は左側(角度πの位置),2回目は右側に描かれます。
ここを,次のように変えると,中の円は半径が3分の1で,中心が半径の3分の2のところになります。
rd=r/3;
center=c+2*r/3*[cos(s*pi),sin(s*pi)];
![画像6](https://assets.st-note.com/production/uploads/images/76080975/picture_pc_50326350e0d6ab2006ba0fc03e272ae3.png?width=800)
このプログラムでは,複素数は使っていません。複素数平面で考えることもできますが大差ないでしょう。Python などでも簡単に移植できるでしょうからやってみてください。
なお,はじめに示したリンク先のものは,Web上で動かすために,中の円の個数や半径の比率なども変数にして,スライダを使って値を取得して計算するようになっています。そのため,プログラム全体は30行ほどになっています。
→複素数平面とフラクタル+目次 に戻る