本体資料

メディアプログラミング演習―第９回（第３テーマ３日目）―
再帰的アルゴリズム：再帰図形とフラクタル図形
再帰関数を用いて，繰り返しのある平面図形を描く．
最初の簡単な例を示す．図１は，円の中に，半径が半分の円を繰り返し描いた図形であ
る．これを実現する再帰プログラムは，図２となる（maru-pro）．
void draw(){
Maru(5,250, 250, 200);
}
void Maru(int n, float x, float y, float r) {
ellipse(x, y, r*2, r*2);
if (n>1) {
float R = r/2;
Maru(n-1, x+R, y, R); //右側の円
Maru(n-1, x-R, y, R); //左側の円
}
}
図１円の繰り返し
図２．図１を描くプログラム
図形例１：次いで，図３の図形を「再帰的に」描くことを考える．
図３最初の図形
図４．基本図形
この図形は，図４のような Y 字図形を描く手続きを再帰的に①～③に適用すること
で描ける．プログラムは，以下の通りである．
void draw(){
drawfig1(5, 200.0, 500.0,500.0);
｝
void drawfig1(int n, float leng,float XO,float YO) {
float x, y, ang;
if (n == 0) {return;};
float[] rx,ry;
rx=new float[3]; ry=new float[3];
drawfig1(n - 1, leng, rx[0], ry[0]);
for(int k=0;k<3;k++)
drawfig1(n - 1, leng, rx[1], ry[1]);
drawfig1(n - 1, leng, rx[2], ry[2]);
{ ang=3.141592/180*k*120;
rx[k] = leng*sin(ang) + XO;
(A)
}
ry[k] = leng*cos(ang) + YO;
line(XO,YO,rx[k],ry[k]);
};
図５．図３を描くプログラム
上図（A）は，図４の周囲３点の座標を求めるとともに，中心から各点への線分を描
いている．繰り返し数ｎが０でなければ，①～③の各頂点にて同じことを繰り返す（
（B）
の部分）
（lattice-pro）．
図形例２：例１を発展させると，次のような図６も描ける．図６は，図７のような５分
木線分の各頂点で，長さを変えて再帰的に描いた図形である(penta-pro)．
図６
繰り返し図形２
図７
図６の基本図形
応用図形（宿題，レポート）：図８および図９を描きなさい
図８
図１の応用
図９
図６の応用
(B)
フラクタル図形
フラクタル（フランス語: fractale）は、フランスの数学者ブノワ・マンデルブロが
導入した幾何学の概念である．フラクタル（Fractal）図形とは、自己相似性を持つ形
状でどの一部分を取り出しても全体と相似の関係をもち，有名な例では，マンデルブロ
ウ集合，ジュリア集合，コッホ曲線，シェルピンスキー曲線などがある．フラクタル図
形のなかには，再帰図形が多く含まれている．以下では，それらを作成する．
① コッホ曲線は，有名でありここでは，プログラムの添付する(koch-pro).
② 樹木曲線もほぼ同様の方法で描くことができる(tree-pro).
添付付プログラムは，
Processing の座標系で描いているので，「木」が横になっている，
これら２つのプログラムの構造や流れは，ほぼ同じである．これらを理解した上で，次
は，自作することにする．
③ シェルピンスキーのギャスケット（英: Sierpinski gasket）はフラクタル図形の 1
種であり、自己相似的な無数の三角形からなる図形である。その名前は，ポーラン
ドの数学者ヴァツワフ・シェルピンスキに由来する。
シェルピンスキーのギャスケットはフラクタル図形であり、以下の手順を繰り返すこ
とで、近似的に作図できる。
A) 1 辺の長さが 1 の正三角形の各辺の中点を互いに結ぶと、中心部に 1 辺の長さ
が 1/2 の正三角形ができる。
B) この 1 辺の長さが 1/2 の正三角形を切り取る。
C) これによって、1 辺の長さが 1/2 の正三角形が 3 個残る。
D) さらに、これら 3 つの正三角形の各辺の中点を互いに結んで出来た長さが 1/4
の正三角形を切り取る。
「切り取る」のではなく「その三角形を描く」として７回繰り返すと図１０となる．
図１０
シェルピンスキーのギャスケット
図１１
その基本手順
さて，これを再帰的に描く方法は以下の通りである．描く関数を
void triangle(int lev, float r, float x, float y)
とする．
構造や流れは，前述の例と同じであるが，変数 lev は，繰り返しの上限とする．
＊これが０である場合は，それ以上繰り返さないので，
―＞
(x,y)を上頂点として，長さｒの正三角形を描く．
＊そうでない場合，
―＞
図９の①～③を頂点とし，辺の長さを半分にし，この関数を再帰的の呼
び出す
このプログラムの雛形は以下の通りであり，sierpin-pro にある．
void triangle(int lev,float r, float x,float y)
{
if( lev==0){
：：：：：：
＜＝
頂点(x,y) 一辺がｒの正三角形を描く
}
else
{
：：：：：
＜＝図９の①～③を頂点とし長さ r/2 で再帰する
}
}
ヒント：
（A）三角形の３点は，(x,y) ,( x-r*sth,y+r*cth), (x+r*sth,y+r*cth)である．
(B)
②，③の座標は，各々(x-r/2*sth,y+r/2*cth )，(x+r/2*sth,y+r/2*cth )
である．
Ｅｘ．完成させ，レポートとして提出しなさい．

Download Report