09再帰の海に棲むドラゴンを描いてみよう【問題と解説】
CodeIQの再帰の海に棲むドラゴンを描いてみように挑戦ありがとうございます。
今回は再帰関数に潜む美しい数学的図形を堪能してもらいたいと思って、出題しました。
問題文
再帰の海に棲むドラゴンを描いてみよう
今回の問題は再帰関数を使ってC曲線とドラゴン曲線という再帰曲線を描く問題です。
準備問題 （解答を提出する必要はありません）
この問題はタートルグラフィックスという描画方法を使って作図をします。
タートルグラフィックスとは、描画の際に描画ポイントをダイレクトに示すのではなく、
ペンの場所 (x0, y0) から右に10ピクセル、90度回転、左に10ピクセル進む等のコマンドで描画する方法です。描画のためのクラスTurtleを定義してください。
Turtleクラスには現在の描画座標 (x0, y0) をプロパティとして持っています。Turtleクラスには下記のメソッド（関数）を定義してください。
１）new(width, height)
描画するキャンバスのサイズを指定して、Turtleオブジェクトを生成する。
ここでは、width=1200, height=800としてください。
２）set_initial_point(x, y)
描画開始の座標を指定します。
３）plot_line(length, theta)
角度 theta でlengthピクセル描画します。
角度 theta の単位はラジアンです。つまり、90度はπ/2。
４）save(o_file)
ファイル名 o_file にpngまたはjpeg形式でイメージを出力する。
Turtleと同じ機能を示す関数やライブラリがある場合はTurtleを作成する必要はありません。
C曲線 （解答は図のみをPDF形式にして送ってください。プログラムは送る必要はありません）
再帰関数を利用して、C曲線を描いてみましょう。
Turtleに対して、メソッドccurve(length, theta) を再帰的に定義して曲線を描きましょう。
与えられた線の上側にπ/2ラジアン（45度）回転した線分を２つ描きます。これを何度も繰り返し行います。lengthの値が4px以下になった場合に描画するようにしてください。
描画の開始座標はset_initial_point(800, 300)。
ccurve(400, 0) で描画を開始します。
ドラゴン曲線（解答は図のみをPDF形式にして送ってください。プログラムは送る必要はありません）
C曲線を描くことができたら、次はいよいよドラゴン曲線に挑戦してみます。
メソッドdragon(length, theta, flip)を再帰的に定義してドラゴン曲線を描いてみましょう。
C曲線の場合は、新しい線は元の線の同じ側に作っていましたが、ドラゴン曲線は新しい線を作る側が交互に変わっていきます。ドラゴン曲線のステップ２では、最初の線（左）は上側に、次の線（右）は下側に作られています。同じ手順が繰り替えされ、曲線が作られていきます。
lengthの値が5px以下になった時に描画を行います。
ヒント
変数flipは+1, -1の値を取り、線を上側に描くか、下側に書くかの情報を表しています。ステップ１以降、flipの値は以下のように+1, -1が交替で現れます。
+1,-1,+1,-1,…,+1,-1,+1,-1描画は下記の値で試してください。
set_initial_point(300, 300)
dragon(600, 0, +1)ここでは数学の座標系を使って説明しましたが、計算機の座標系ではy軸が反転していますので、注意してください。
描画下限値lengthの値を変えてみて、綺麗に描画される値を探してみてください。
【解説】再帰の海に住むドラゴンを描いてみよう
今回は再帰関数を用いてC曲線とドラゴン曲線を描く問題です。
準備問題は言語やOS等によって異なりますので、個々に対応してください。
タートルグラフィックスは直前の描画終了点を記憶し、描画の長さlengthと描画の方向角度thetaを入力変数として描画を行うシステムです。
C曲線
アルゴリズムが正しければ、以下のような綺麗な図形が現れます。
まるで、宮殿のようですね。
ここでは開口部が上を向いていますが、右に立てて描画することも可能です。形がCの形に似ているので、C曲線と名付けられました。
PythonによるC曲線とドラゴン曲線のプログラム例
#!/usr/bin/python # # dragon.py # from PIL import Image, ImageDraw from math import cos, sin, pi, sqrt class Turtle: def __init__(self, width=1200, height=800): mode = "RGB" # Black and White bg = "#ffffff" self.window = Image.new(mode, (width,height), bg) self.dr = ImageDraw.Draw(self.window) def set_initial_point(self, x, y): self.x0, self.y0 = x, y def plot_line(self, length, theta): x1 = self.x0 + length*cos(theta) y1 = self.y0 + length*sin(theta) ### #self.dr.line*1 ### here is a bug for Hatena Diary display self.dr.line*2 self.x0, self.y0 = x1, y1 def save(self, o_file, form="PNG"): self.window.show() self.window.save(o_file, form) def ccurve(self, length, theta): if length <= 4: self.plot_line(length, theta) else: self.ccurve(length/sqrt(2), theta + pi/4) self.ccurve(length/sqrt(2), theta - pi/4) def dragon(self, length, theta, flip): if length <= 5: self.plot_line(length, theta) else: self.dragon(length/sqrt(2), theta + flip*pi/4, 1) self.dragon(length/sqrt(2), theta - flip*pi/4, -1) if __name__ == '__main__': d = Turtle(1200, 800) d.set_initial_point(400, 300) # C-CURVE d.ccurve(400, 0) d.save("ccurve.png") d = Turtle(1200, 800) d.set_initial_point(300, 300) # DRAGON CURVE d.dragon(600, 0, +1) d.save("dragon.png")
C曲線の解説
C曲線を描くには元の親関数から次々に子供関数を再帰的に定義していく必要があります。
例えば、最初のステップ0では長さlength=1, 角度theta=0 (0度)とすると、次のステップ1では２つの子供関数に引き継がれます。
最初の子供関数では次のようになります。
length = length ÷ √2 = 1/√2
theta = theta + π/4 = π/4 = 45度
もうひとつの子供関数では次のようになります。
length = length ÷ √2 = 1/√2
theta = theta - π/4 = -π/4 = -45度
この操作が繰り返され、長さlengthはどんどん短くなっていきます。
length = 1, 1/√2, 1/(√2)^2, 1/(√2)^3,1/(√2)^4,…
繰り返していくと、最後に綺麗なC曲線ができます。
停止条件がないと無限に計算して止まらなくなるので、lengthがある値以下になったら終了するように設定しておきます。
ドラゴン曲線
アルゴリズムが正しければ、以下のような得体の知れない生き物のような図になります。
解答者の中にはグラデーションをつけて、より神秘的なドラゴンを描いてくれた人もいました。
ドラゴン（竜）に見えますか。ドラゴンと言うよりリーフィーシードラゴンですね。
（ウィキペディアより転載）
ドラゴン曲線の解説
ドラゴン曲線の手順は少し面倒です。C曲線と似ていますが、規則的に線の上側（正の角度）と下側（負の角度）に入れ替わるように描画していきます。
親関数は２つの子供関数に引き継がれます。ここで、最初の子供関数を長男関数、二番目の子供関数を次男関数と名づけます。
flipの値を次のように決めます。
上側ならば、flip = +1
下側ならば、flip = -1
長男関数も次男関数も親関数から上側に描くか下側に描くかの情報を引き継ぎますが、必ず長男関数は上側を、次男関数は下側としてｆlip値を引き継ぎます。
親関数は自分が受け取ったflip値に基づいて、長男及び次男関数を上側ならば、／＼の形に、下側ならば＼／の形で描画するように指示します。
つまり、
上側（flip = +1) →子供関数それぞれのthetaの増減値を+π/4, -π/4
下側（flip = -1）→子供関数それぞれのthetaの増減値を-π/4, +π/4
各パラメーターをいじってみて、綺麗に描画できる値を探してみてください。
