再帰関数で作るフラクタル図形 ~コッホ曲線~

今回はフラクタル図形の各頂点の座標を求める問題に挑戦していきたいと思います．再帰関数の理解を深めるのにちょうどいい問題でしたのでぜひ挑戦してみてください．

目次

フラクタル図形とは

図形の部分と全体が自己相似（再帰）によってできているものをフラクタルと呼ぶそうです(wiki参照).
シェルピンスキーのギャスケット(初めて名前知りました…)がみなさん見たことあるフラクタル図形の一つだと思います．

フラクタル図形は自然界にもたくさんある形です．こういった幾何学模様は不思議な魅力があって綺麗に見えますよね.

コッホ曲線

コッホ曲線は先ほど説明したフラクタル図形の一つです.
線分を3等分し、分割した2点を頂点とする正三角形の作図するということを無限に繰り返すことによって得られる図形を指しています.
画像参考サイト

正三角形からこのコッホ曲線を描くと雪片のようになることでも有名です.

問題

今回扱う問題はALDS1_5_C: Koch Curveになります．
問題の内容としては入力nを受け,深さnの再帰呼び出しによって作成されるコッホ曲線の頂点の座標を出力するというものです.
作らなければならない動作としては

• 与えられた線分(p1, p2)を三等分にする
• 線分を三等分する2点(s, t)を頂点とする正三角形(s, t, u)を作成し，その座標を求める
• 新しくできた全ての線分[(p1, s),(s, u), (u, t), (t, p2)]に対して上記の処理を再帰的に繰り返す．

コード&解説

n=1の時は直感的にuの座標がわかると思うのですが，nが増えていくに連れてわかりづらくなると思います． (自分はここで詰まりました…)
ここで，点uの座標を求めるのに使うのが回転行列です．

原点中心に θ 回転して点 (x, y) が (x ', y ') に写るとすると、図形的考察または三角関数の加法定理より、x', y ' は以下のように表されることが分かる。
x'= x cosθ - y sinθ
y'= x sinθ + y cosθ
wiki参照

また，図形的考察をしてくれているサイトもあるのでこちらも参考にしてみてください(参考サイト).

では，これらの知識を活用して上記であげた動作をするプログラムを実装していきましょう.

import math

def koch(n, p1, p2):
    if n == 0:
        return
    sx = 2p1[0]/3 + p2[0]/3
    sy = 2p1[1]/3 + p2[1]/3
    tx = p1[0]/3 + 2p2[0]/3
    ty = p1[1]/3 + 2p2[1]/3
    ux = (tx - sx)math.cos(math.radians(60))  - (ty - sy)math.sin(math.radians(60)) + sx
    uy = (tx - sx)math.sin(math.radians(60)) + (ty - sy)math.cos(math.radians(60)) + sy
    koch(n-1, p1, [sx, sy])
    print(sx, sy)
    koch(n-1, [sx, sy], [ux, uy])
    print(ux, uy)
    koch(n-1, [ux, uy], [tx, ty])
    print(tx, ty)
    koch(n-1, [tx, ty], p2)

n = int(input())
#問題文より，端点がp1 = (0,0), p2 =(100,0)と指定されている
p1 = [0, 0]
p2 = [100, 0]
print(p1[0], p1[1])
koch(n, p1, p2)
print(p2[0], p2[1])

上記のコードを実行することでp1から順に繋がった形で線分の座標を出力することができます．
点uの座標を求める方法を考えるのに苦労しましたがコードにすると意外と簡潔になりますね．
再帰関数に関してはこの前 やったばかりなのでお手の物でした！
Pythonを使ってこれらの図形を実際に描くこともできるそうなので今度試してみたいと思います．