再帰曲線

普段使うプログラミング言語はSchemeが多い. その1つの実装, MITSchemeにはgraphicsの機能があることは, うすうす知ってはいたが, 使ってみたら存外簡単であった.

(define mydevice (make-graphics-device 'x))

で四角い描画領域が出来る. 座標は左下が(-1,-1), 右上が(1,1)だ.

点(x0,y0)から点(x1,y1)へ直線を引くには,

(graphics-draw-line mydevice x0 y0 x1 y1)

でよい.

早速絵を描いてみる. 関数型言語だから, 再帰的な絵がいい. となるとhilbert曲線とdragon曲線である. 描き方は後回しとして, 出来映えは





の通り.

どちらも良く知られている曲線であるが, 私は次のように考えて描いた. hilbertの方は, 以前, 情報処理学会誌にも書いたことがある.



上の図で, 左端は, 1次から4次までのhilbert曲線が重ねて描いてある. こうして見ると, フラクタルのように, 最初の直線を, 少しずつ曲げて作られていることが分かる. 中のは, hilbert曲線の要素で, 見かけは同じようだが, 下のXは左から来て, 左折, 右折, 右折, 左折し右に抜け, 上のYは右から来て, 右折, 左折, 左折, 右折し左へ抜ける.

中の下のXを右のXのようにするには, +を左折, -を右折とすると,
X -> + Y F - X F X - F Y +
Y -> - X F _ Y F Y - F X -
と変換すればよい. Fは1歩前へ進むことである.

従って, hilbert曲線のプログラムは, 関数名を変更し, +をleft, -をright, Xをp, Yをqと書くと,

(define mydevice (make-graphics-device 'x))

(define (l) (let ((t dx)) (set! dx (- dy)) (set! dy t)))
(define (r) (let ((t dy)) (set! dy (- dx)) (set! dx t)))
(define (f)
 (graphics-draw-line mydevice x y (+ x dx) (+ y dy))
 (set! x (+ x dx)) (set! y (+ y dy)))

(define (p) (if (> n 0) (begin (set! n (- n 1)) (l) (q) (f)
 (r) (p) (f) (p) (r) (f) (q) (l) (set! n (+ n 1)))))
(define (q) (if (> n 0) (begin (set! n (- n 1)) (r) (p) (f)
 (l) (q) (f) (q) (l) (f) (p) (r) (set! n (+ n 1)))))

(define n 6) (define x -0.8) (define y -0.8)
(define dx 0.025) (define dy 0)
(p)

となる.

次にdragon曲線.



dragon曲線は, 紙を半分に折り, それを開くと, 上の左端のようになる. 次に紙を半分に折り, さらに半分に折り, それを開くと, 左から2番目のようになる.


線の開始点には, 小さい黒四角, 折り返し点には小さい白四角がついている.

半分に折る方向は, 山折, 谷折両方があるが, ここでは開いた絵が, 左折するようにしている.
そして左折を+, 右折を-と表示する. 折り返し点は常に + にしてある.

半分折りを3回続け, それを開くと, 右端のようになる. この辺からがdragon曲線らしくなる. 曲がる向きを順に書くと

+ + - + + - - + + + - - + - -

になる. 記号は15個あるが, 中央の + が最初の折り目で, その両側はもともと重なっていたのを開いたから, 並び順が中央を中心にして対象で, しかも+と-が入れ替わっている.

つまりこれを X₂ + Y₂ と書くと,
X₂ = + + - + + - -
Y₂ = + + - - + - -
である. するとこの両枝は同じなので,
X₂ = X₁ + Y₁
Y₂ = X₁ - Y₁
X₁ = + + -
Y₁ = + - -
最後は
X₀ = +
Y₀ = -

これをプログラムにすればよいから, 前と同様に, +をleft, -をright, Xをp, Yをqと書くが,

(define mydevice (make-graphics-device 'x))

(define (l) (let ((t dx)) (set! dx (- dy)) (set! dy t)))
(define (r) (let ((t dy)) (set! dy (- dx)) (set! dx t)))
(define (f)
 (graphics-draw-line mydevice x y (+ x dx) (+ y dy))
 (set! x (+ x dx)) (set! y (+ y dy)))

(define (p) (if (= n 0) (begin (l) (f))
 (begin (set! n (- n 1)) (p) (l) (f) (q) (set! n (+ n 1)))))
(define (q) (if (= n 0) (begin (r) (f))
 (begin (set! n (- n 1)) (p) (r) (f) (q) (set! n (+ n 1)))))

(define n 10) (define x 0.4) (define y -0.2) 
(define dx 0.025) (define dy 0)
(f) (p)

となる.