連載
» 2014年09月12日 11時00分 公開

無償ソフトで技術計算しよう【プログラミング処理編】(3):再帰アルゴリズムで「ハノイの塔」のプログラムを書く (2/2)

[伊藤孝宏,MONOist]
前のページへ 1|2       

再帰グラフィックスによるコッホ曲線

 再帰アルゴリズムをグラフィックスに利用した例として、「コッホ曲線」を描画する方法を紹介します。コッホ曲線とは、数学者ヘルゲ・フォン・コッホが考案した曲線で、線分を3等分して、中央の線分を辺とする正三角形を作成するといった操作をそれぞれの辺に繰り返すことによって得られる図形です。

 図4を基に説明すると、線分p0-p4を三等分し、p1-p3を辺とする正三角形を作成すると、頂点p2が得られます。次に、点p0からp4を順に結ぶと、1次のコッホ曲線が得られます。この操作を各辺に行うと、2次のコッホ曲線が得られます。同様の操作を繰り返すと、高次のコッホ曲線が得られます。

図4 1次のコッホ曲線

 コッホ曲線を作成する関数mファイルを作成していきます。まず、図4の定義に基づいて、点p0、p1、p2、p3、p4の位置を計算します。ここでは、複素平面を利用することで1つの変数で処理することにします(複素平面とは、複素数の実数部がx座標、虚数部がy座標となる平面のこと)。

 P1はp0に(p4-p0)/3を加えたものになります。また、p3はp0に2*(p4-p0)/3を加えたものになります。P2は、長さがp1と同じで、水平から60度回転した向きの線分の先端になるので、p2=p1+(p1-p0)*exp(i*pi/3)となります。以上の4点を配列として並べると、1次のコッホ曲線になります。

 高次のコッホ曲線は、以上の操作をそれぞれの辺に繰り返せばよいので、先の操作を「koch(po,p4,n).m」という関数mファイルに定義し、[koch(po,p1,n-1), koch(p1,p2,n-1), koch(p2,p3,n-1), koch(p3,p4,n-1)]とすると、高次のコッホ曲線の配列が得られます。nは次数で、nが1ずつ減少し、0となった時点で、p0-p4を線分とする0次のコッホ曲線を出力して終了します。以上が下記の「koch.m」ファイルです。

function ret=koch(p0,p4,n)
if n==0
ret=[p0,p4];
else
p1=p0+1/3*(p4-p0);
p2=p1+(p1-p0)*exp(i*pi/3);
p3=p0+2/3*(p4-p0);
ret=[koch(p0,p1,n-1),koch(p1,p2,n-1),koch(p2,p3,n-1),koch(p3,p4,n-1)];
end
koch.m

>>「koch.m」ダウンロード

 コマンドウィンドウ上で以下のように入力すると、図5に示す4次のコッホ曲線が得られます。

--> plot(koch(0,1,4))

図5 4次のコッホ曲線

 コッホ曲線を利用して、雪の結晶のような図形を作成してみます。先ほどのコッホ曲線を120度回転させて、前の曲線の最後に接続するということを繰り返すと、図6に示すようなコッホ雪片あるいはコッホ島と呼ばれる図形が得られます。以下に示す「kochcurve.m」をワーキングフォルダに保存し、コマンドウィンドウでkochcurveと入力すると得られます。kochcurve.mでは、axis('equal');axis('off')として、縦横が等倍で、縦軸と横軸が非表示となるようにしています。

function kochcurve
ret1=koch(0,1,4);
ret2=ret1(end)+abs(ret1).*exp(i*(angle(ret1)-2/3*pi));
ret3=ret2(end)+abs(ret1).*exp(i*(angle(ret1)+2/3*pi));
ret=[ret1,ret2,ret3];
plot(ret);axis('equal');axis('off');
function ret=koch(p0,p4,n)
if n==0
ret=[p0,p4];
else
p1=p0+1/3*(p4-p0);
p2=p1+(p1-p0)*exp(i*pi/3);
p3=p0+2/3*(p4-p0);
ret=[koch(p0,p1,n-1),koch(p1,p2,n-1),koch(p2,p3,n-1),koch(p3,p4,n-1)];
end
kochcurve.m

>>「kochcurve.m」ダウンロード

図6 コッホ雪片


 次回からは、応用編として、具体的にプログラムを作成していきます。手始めに、MATLABにあって、FreeMatにはないコマンドを作成してみます。

参考文献

  • 「MATLABハンドブック」小林一行著、秀和システム刊
  • 「はじめてのFreeMat」赤間世紀著、工学社刊

無償ソフトで技術計算しよう

FreeMat

無償の工学計算ソフトでも、かなり高度な計算ができる!


筆者紹介

伊藤孝宏(いとう・たかひろ)

1960年生。小型モーターメーカーのエンジニア。博士(工学)。専門は流体工学、音・振動工学。現在は、LabVIEWを使って、音不良の計測・診断ソフト、特性自動検査装置などの開発を行っている。



前のページへ 1|2       

Copyright © ITmedia, Inc. All Rights Reserved.