20010. 7.18.
石立 喬
Visual C++ 2010 Express の易しい使い方（１４）
―― Turtle Graphicsを用いた、再帰プログラムの例題としてのフラクタル図形の描画 ――
概要
プログラムの学習には、再帰プログラムが欠かせない。ここでは、再帰プログラムの例としてよく知られているコッホ曲線、樹木曲線、ドラゴン曲線のフラクタル図形を描画する。描画のための座標の獲得にはTurtle
Graphicsを使用した。
再帰プログラム
再帰プログラムとは、呼び出されたメソッドの中で、再び「自分自身」のメソッドを呼び出すもので、初心者には頭が混乱してしまって理解し難い。もちろん、自分自身を無限に呼び出すわけではなく、ある条件になると別の処理を実行して呼び出されたメソッドに戻る。再帰プログラムは、複雑な事柄を簡単に表現できるメリットがある。
再帰プログラムには、下記が必要である。
１）メソッドの中に、自分自身を呼び出す命令を記述する。
２）一定の条件（呼び出し回数、扱う数値の大きさなど）では自分自身を呼び出さないで別の命令を実行する「ストッパー」を用意しておく。
３）メソッドを呼び出す毎に、呼び出し回数や数値を変更する命令を記述する。
フラクタル図形
フラクタル（Fractal）図形とは、「Visual C++ 2010 Express の易しい使い方（１２）」ですでに紹介したマンデルブロー（Benoit
Mandelbrot）が命名した言葉で、自己相似性を持ち、図形の一部を拡大すると、また同じような図形が現れるものを言う。代表的な図形にコッホ（Helge
von Koch）曲線や樹木曲線、ドラゴン（竜）曲線がある。
Turtle Graphics
グラフィックスを描画する簡単なツールとして、古くからTurtle Graphicsが使われている。これは、ペン（筆）をTurtle（亀）に見立てて、向きを変えさせたり、前方に歩ませたりして描画する。画面全体の座標に対する位置情報ではなく、ローカルな相対的な位置情報によって描画するので、繰り返して多数回使用すると、誤差が累積し易いが、プログラムの容易さから、フラクタル図形の描画に使われることが多い。
ここでは、Turtleクラスを自作して使用したが、本来のTurtle Graphicsの便利さを多少犠牲にして、精度を落とさないように努力した。また、再帰プログラムのため、Turtleに直接線を引かせることはしないで、座標点を獲得させるにとどめた。
クラスの作り方
◎ウイザードの使用方法
１）図１に示す「ソリューションエクスプローラ」で、「プロジェクト名（この例ではC1014）」を右クリックし、「追加」→「クラス」を選択する。
図1 「ソリューションエクスプローラー」の例
２）図２に示す「クラスの追加」ウインドウが開くので、
テンプレート --- C++
クラス --------- C++クラス（テンプレートにC++を選ぶと、これしか無い）
を選択し、右欄の「空のC++クラスを追加します」を確認して、下方の「追加」をクリックする。
図2 「クラスの追加」ウインドウ
３）続いて開く「汎用C++クラスウイザード」で、
クラス名 ------ Turtle （入力する）
.hファイル ---- Turtle （自動的に入る）
.cppファイル -- Turtle.cpp （自動的に入る）
基本クラス ---- 空欄のまま
アクセス ------ public （そのままにしておく）
マネージ ------ チェック（そのままにしておく）
を設定し、「完了」をクリックする。
４）.hファイルのスケルトンへの記述
「Turtle.h」には、図3のようなスケルトンができている。クラスは、デフォルトで参照クラス（ref
class）になっているので、これを使用する。「Turtle(void);」は、一番簡単なコンストラクタで、この下に、さらにより具体的なコンストラクタや、メソッドの宣言を追加する。
図3 自動的に作成されるヘッダファイル
Turtleクラスの作成
クラスのメンバー変数として、座標上の位置（point）、向き（direction）、座標のx方向の正逆（sign）を設定する。コンストラクタには、Turtleの出発点（startPoint）と、Turtleが向かおうとしている点（endPoint）を指定する。ただし、これは位置（point）、向き（direction）、正逆（sign）を求めるためのみに使用され、将来、実際に点（endPoint）に移動する必要はない。座標位置は、最終的な描画時には整数になるべきものであるが、点を実数で表すPointF構造体を用いて、誤差の発生を抑えている。
図4は、Turtleのコンストラクタにおいて、directionとsignを求める方法を示す。startPointは、そのままpointになる。
図4 Turtleのコンストラクタでdirectionとsignを決める
メンバーメソッドは、前進（forward）と回転（turn）のみの簡単なものである。後進は、lengthを負にすればよく、回転が右方向か左方向かは、angleの正負で与える（左が正、右が負）。
◎Turtle.hの内容
PointF構造体を使用するために、名前空間System::Drawingを追加しておく。
#pragma once
using namespace System::Drawing;
ref class Turtle
{
public:
PointF point;
float direction;
int sign;
Turtle(void);
Turtle(PointF pt1,PointF pt2);
void forward(float length);
void turn(float angle);
};
◎Turtle.cppの内容
インクルードファイルと最も簡単なコンストラクタは自動的に設定されている。三角関数ライブラリとPointF構造体を使用するために、名前空間SystemおよびSystem::Drawingを追加しておく。
#include "StdAfx.h"
#include "Turtle.h"
using namespace System;
using namespace System::Drawing;
Turtle::Turtle(void)
{
}
Turtle::Turtle(PointF pt1,PointF pt2){
point=pt1;
direction=Math::Atan((double)(pt1.Y-pt2.Y)/(pt2.X-pt1.X));
sign=((pt2.X-pt1.X)>=0)? 1:-1;
}
void Turtle::forward(double length){
point.X+=sign*length*Math::Cos(direction);
point.Y-=sign*length*Math::Sin(direction);
}
void Turtle::turn(double angle){
direction+=angle*Math::PI/180.0;
}
コッホ（Koch）曲線
図5は、上が元になる直線、その下が、その直線を1/3の位置で60°に折り曲げた折れ線、この折れ線には４本の直線があるので、これらの直線を元の直線とみなし、さらに折れ線に置き換えたものが一番下の図である。この操作を多数回（パソコンの画面では、解像度より小さい直線を表現できず、計算の途中でゼロ割りや不定が発生する恐れがあるので、回数に限界がある）繰り返したものがコッホ曲線である。
図5 コッホ曲線の作り方
コッホ曲線描画プログラム
◎Form1_Paint()メソッド
コッホ曲線を描くためのパソコン画面上の座標を指定し、別途作成するメソッドdrawKoch()を呼び出す。
具体的には、逆三角形の３個の頂点を表すPointF構造体のap、bp、cpを指定し、その間をdrawKoch()で結んでコッホ島と呼ばれる図形を描く。
◎drawKoch()メソッド
図6は、与えられた直線の座標（startPointとendPoint）から、firstPoint、secondPoint、thirdPointを求める方法を示す。誤差の累積を避けるために、一個のTurtleを継続的に使用することなく、新しい別のTurtleを使ってthirdPointを求めている。
詳細は以下の通り。
１）startPointとendPointの距離を計算し、その1/3をlengthとする。
２）startPointとendPointを与えて、Turtleを設定する。これにより、Turtleの出発点（point）と向き（directionとsign）が決まる（図6左）。
３）Turtleをlengthだけ進ませる→firstPoint
４）Turtleの向きを60°左へ回転（angle=60）させた後、lengthだけ進ませる→secondPoint
５）新しい別のTurtleを設定する（図6右）。
６）Turtleをlength*2だけ進ませる→thirdPoint
再帰を繰り返している間は、ここで求めたstartPoint→firstPoint、firstPoint→secondPoint、secondPoint→thirdPoint、thirdPoint→endPointの区間に対して、さらにdrawKoch()メソッドを呼び出す。終了時には、g->DrawLine()でこれらの区間を線で結ぶ。
図6 コッホ曲線を描くためのTurtleの動かし方
樹木曲線
図7は、左が元になる直線、中央が、下から25%を幹とし、そこから左右に50%の長さの枝を伸ばしたもの、右は幹、枝、および幹の上部それぞれの直線を元の直線とみなし、さらに枝分かれさせたものである。
図7 樹木曲線の作り方
樹木曲線描画プログラム
◎Form1_Paint()メソッド
樹木曲線を描くために、パソコン画面の座標上に上下２個の点を表すPointF構造体のap、bpを指定し、その間をメソッドdrawTree()で結ぶ。
◎drawTree()メソッド
主な変数の説明をすると、以下の通りである。
stem_ratio ------ 与えられた直線のどれだけを幹とするかの割合で、例では0.25である
branch_ratio ---- 与えられた直線に対して、横に出る枝の長さの割合で、例では0.5である
stem_length ----- stem_ratioによって決まる幹の部分の長さである。
branch_length --- branch_ratioによって決まる横に出る枝の長さである。
angle1 ---------- 左側の枝の角度である。例では、与えられた直線に対して60°左側に曲げてある（60）。
angle2 ---------- 右側の枝の角度である。例では、与えられた直線に対して60°右側に曲げてある（-60）。
図8は、与えられた直線の座標（startPointとendPoint）から、firstPoint、secondPoint、thirdPointを求める方法を示す。
詳細は以下の通り。
１）startPointとendPointの距離を計算し、そのstem_ratio倍をstem_length、そのbranch_ratio倍をbranch_lengthとする。
２）startPointとendPointを与えて、Turtleを設定する。これにより、Turtleの出発点（point）と向き（directionとsign）が決まる（図7左）。
３）Turtleをstem_lengthだけ進ませる→firstPoint
４）Turtleの向きを60°だけ左へ回転（angle1=60）させた後、branch_lengthだけ進ませる→secondPoint
５）新しい別のTurtle1を設定する（図7右）。
６）Turtleをstem_lengthだけ進ませた後、向きを60°だけ右へ回転（angle=-60）させて、branch_lengthだけ進ませる→thirdPoint
７）startPointとfirstPointの区間は、幹の部分なので、再帰は行わず、g->DrawLine()でこの区間を線で結ぶ。
再帰を繰り返している間は、ここで求めたfirstPoint→secondPoint、firstPoint→thirdPoint、firstPoint→endPointの区間に対して、さらにdrawTree()メソッドを呼び出す。終了時には、g->DrawLine()でこれらの区間を線で結ぶ。
図8 樹木曲線を描くためのTurtleの動かし方
ドラゴン（Dragon、竜）曲線
できた結果が、中国風のドラゴン（竜）に似ているところから、この名称がある。図9の上が元になる直線、その下が置き換えられた折れ線である。折れ線の二本の直線は、元の直線を斜辺とする直角三角形を形成する。一番下は、それをさらに折り曲げた状態を示す。
図9 ドラゴン曲線を描く置き換え方法と座標の求め方
ドラゴン曲線描画プログラム
◎Form1_Paint()メソッド
ドラゴン曲線を描くための出発点となる２個の点を表すPoint構造体のap、bpを指定し、メソッドdrawDragon()を呼び出す。
◎drawDragon()メソッド
図10は、元になる直線の座標（startPointとendPoint）から、midPointを求める方法を示す。
詳細は以下の通り。
１）startPointとendPointの距離を計算し、その1/2をlengthとする。
２）startPointとendPointを与えて、Turtleを設定する。これにより、Turtleの出発点（point）と向き（directionとsign）が決まる。
３）Turtleをlengthだけ進ませる
４）Turtleの向きを90°右へ回転（angle=-90）させた後、lengthだけ進ませる→midPoint
再帰を繰り返している間は、ここで求めたstartPoint→midPoint、endPoint→midPointの区間に対して、さらにdrawDragon()メソッドを呼び出す。終了時には、g->DrawLine()でこれらの区間を線で結ぶ。
midPointを新たに設け、点の間を直線で結ぶ場合に、必ず、startPoinからmidPointへ、endPointからmidPointへ線を引くことが重要である。midPointからendPointに向かって線を引くと、折れ曲がる方向が逆になるので注意を要する。ただし、再帰が終わって実際に線を引く場合は、特に注意の必要はない。startPointから、45°右にTurtleを回転させ、length*Math::Sqrt(2.0)だけ進めるのが、本来のTurtleの使い方であるが、精度を考慮して、この方法を選んだ。
図10 midPointの求め方
プログラム
int type,n;
private: System::Void Form1_Load(System::Object^ sender, System::EventArgs^ e)
{
type=0; //コッホ曲線に初期化
comboBox1->SelectedIndex=0;
n=3; //再帰回数を3回に初期化
comboBox2->SelectedIndex=3;
}
private: System::Void comboBox1_SelectedIndexChanged(System::Object^ sender, System::EventArgs^
e) {
type=comboBox1->SelectedIndex;
Invalidate();
}
private: System::Void comboBox2_SelectedIndexChanged(System::Object^ sender, System::EventArgs^ e) {
n=comboBox2->SelectedIndex; //「文字列コレクション」は、「n=0」から始まるので、そのまま使用
Invalidate();
}
private: System::Void Form1_Paint(System::Object^ sender, System::Windows::Forms::PaintEventArgs^
e) {
PointF ap,bp,cp;
switch(type){
case 0: //コッホ曲線を描く
if(n>=5){
MessageBox::Show("n>=5 は使用できません。");
return;
}
ap=PointF(100,140);
bp=PointF(400,140);
cp=PointF(250,400);
drawKoch(ap,bp,n);
drawKoch(bp,cp,n);
drawKoch(cp,ap,n);
break;
case 1: //樹木曲線を描く
if(n>=8) {
MessageBox::Show("n>=8 は使用できません。");
return;
}
ap=PointF(250,380);
bp=PointF(250,80);
drawTree(ap,bp,n);
break;
case 2: //ドラゴン曲線を描く
if(n>=12) {
MessageBox::Show("n>=12 は使用できません。");
return;
}
ap=PointF(180,120);
bp=PointF(380,320);
drawDragon(ap,bp,n);
break;
}
}
//点apと点bpの間にコッホ曲線を描く
private: Void drawKoch(PointF startPoint,PointF endPoint,int n){
Graphics^ g=this->CreateGraphics();
PointF firstPoint,secondPoint,thirdPoint;
float xx,yy;
float length;
//点startPointと点endPointの間の距離を求め、lengthをその1/3に設定する
xx=endPoint.X-startPoint.X;
yy=endPoint.Y-startPoint.Y;
length=Math::Sqrt(xx*xx+yy*yy)/3.0;
Turtle^ turtle1=gcnew Turtle(startPoint,endPoint);
//Turtleを設定する
turtle1->forward(length); //Turtleをlengthだけ進ませる
firstPoint=turtle1->point; //Turtleの位置をfirstPointにする
turtle1->turn(60); //Turtleの向きを60°左に回転させる
turtle1->forward(length); //Turtleをlengthだけ進ませる
secondPoint=turtle1->point; //Turtleの位置をsecondPointにする
Turtle^ turtle2=gcnew Turtle(startPoint,endPoint); //別の新しいTurtleを設定する
turtle2->forward(length*2); //Turtleをlength*2だけ進ませる
thirdPoint=turtle2->point; //Turtleの位置をthirdPointにする
if(n>0){ //再帰
drawKoch(startPoint,firstPoint,n-1);
drawKoch(firstPoint,secondPoint,n-1);
drawKoch(secondPoint,thirdPoint,n-1);
drawKoch(thirdPoint,endPoint,n-1);
}
else{ //描画
g->DrawLine(Pens::Black,startPoint,firstPoint);
g->DrawLine(Pens::Black,firstPoint,secondPoint);
g->DrawLine(Pens::Black,secondPoint,thirdPoint);
g->DrawLine(Pens::Black,thirdPoint,endPoint);
}
}
//点apと点bpの間に樹木曲線を描く
private: Void drawTree(PointF startPoint,PointF endPoint,int n){
Graphics^ g=this->CreateGraphics();
PointF firstPoint,secondPoint,thirdPoint;
float xx,yy;
float length;
float angle1=60.0f,angle2=-60.0f,stem_ratio=0.25f,branch_ratio=0.5f;
float stem_length,branch_length;
//点startPointと点endPointの間の距離lengthを求め、stem_lengthをそのstem_ratio倍に設定する
xx=endPoint.X-startPoint.X;
yy=endPoint.Y-startPoint.Y;
length=Math::Sqrt(xx*xx+yy*yy);
stem_length=length*stem_ratio;
branch_length=length*branch_ratio;
Turtle^ turtle1=gcnew Turtle(startPoint,endPoint); //Turtleを設定する
turtle1->forward(stem_length); //Turtleをstem_lengthだけ進ませる
firstPoint=turtle1->point; //Turtleの位置をfirstPointにする
turtle1->turn(angle1); //Turtleの向きをangle1だけ回転させる
turtle1->forward(branch_length); //Turtleをbranch_lengthだけ進ませる
secondPoint=turtle1->point; //Turtleの位置をsecondPointにする
Turtle^ turtle2=gcnew Turtle(startPoint,endPoint);
//別の新しいTurtleを設定する
turtle2->forward(stem_length); //Turtleをstem_lengthだけ進ませる
turtle2->turn(angle2); //Turtleをangle2だけ回転させる
turtle2->forward(branch_length); //Turtleをbranch_lengthだけ進ませる
thirdPoint=turtle2->point; //Turtleの位置をthirdPointにする
g->DrawLine(Pens::Black,startPoint,firstPoint); //幹の部分は再帰させないで、直ちに描画する
if(n>0){ //再帰
drawTree(firstPoint,secondPoint,n-1);
drawTree(firstPoint,thirdPoint,n-1);
drawTree(firstPoint,endPoint,n-1);
}
else{ //描画
g->DrawLine(Pens::Black,firstPoint,secondPoint);
g->DrawLine(Pens::Black,firstPoint,thirdPoint);
g->DrawLine(Pens::Black,firstPoint,endPoint);
}
}
//点apと点bpの間にドラゴン曲線を描く
private: Void drawDragon(PointF startPoint,PointF endPoint,int n){
Graphics^ g=this->CreateGraphics();
PointF midPoint;
float xx,yy;
float length;
//点startPointと点endPointの間の距離を求め、lengthをその1/2に設定する
xx=endPoint.X-startPoint.X;
yy=endPoint.Y-startPoint.Y;
length=Math::Sqrt(xx*xx+yy*yy)/2.0;
Turtle^ turtle1=gcnew Turtle(startPoint,endPoint);
//Turtleを設定する
turtle1->forward(length); //Turtleをlengthだけ進ませる
turtle1->turn(-90); //Turtleを90°右に回転させる
turtle1->forward(length); //Turtleをlengthだけ進ませる
midPoint=turtle1->point;
//Turtleの位置をmidPointにする
if(n>0){ //再帰
drawDragon(startPoint,midPoint,n-1);
drawDragon(endPoint,midPoint,n-1);
}
else{ //描画
g->DrawLine(Pens::Black,startPoint,midPoint);
g->DrawLine(Pens::Black,endPoint,midPoint);
}
}
プログラムの実行結果
結果を以下の図に示す。パソコン画面の解像力を超えないように再帰の回数に制限がしてあるが、樹木曲線以外は、その最大限を選んである。
図11 再帰を4回（折れ線化を5回）繰り返したコッホ島
図12 再帰を6回（樹木描画を7回）繰り返した樹木曲線
図13 再帰を11回（折れ線化を12回）繰り返したドラゴン曲線
「Visual C++ の勉強部屋」（目次）へ