再帰曲線

今回は3次元のHilbert曲線が話題である. この2月は思わぬ風邪引きで, それも歳をとったせいか, 全治に時間がかかった.

それで家に引き籠もっている折, 例の「ハッカーのたのしみ」を眺めていたら, 3次元Hilbert曲線の基本部品という図を見つけた. 確かに3次元でも出来そうであるが, さてどうやったら描けるのか. しばらくそれが気になっていた.

2次元だと, 右折, 左折などを繰り返すと何となくアルゴリズムが見つかるが, 3次元の場合, これをどういえばよいか. 試行錯誤の結果, 基本部品に名前をつけ, それを組合せると描けそうだというところまで来た. もっともまだ最後まで出来たわけではなく, 今後挫折するかもしれないのだが.

とりあえず, 1次と2次の図を描いてみたのが下だ.



赤の太い線が1次, 黒の細いのが2次である. 通過した順が分かるように, 節点に0から番号を付けてある. 1次のは向こうの下の方0から始まる. この座標を000としよう. それから図で左下へ進む. この方向をxとする. つまり次の点1の座標はzyxの順に書けば001である. 今度は右下へ進む. この方向をyとする. 次の点2の座標は011だ. この伝でいくと, 010, 110, 111, 101, 100のように進むことになる.

もう1度揃えて書くと

zyx
000
001
011
010
110
111
101
100

これは誰が見てもGrayコードである.

ところで, 2次を見ると, 1次の0の回りを0→1→...→7と同様にGrayコードで進む8点で囲む. 1の回りを8→9→...→15の8点で囲む. ... 7の回りを56→57→...→63の8点で囲む. この8点の形はよく見ると5種類ある. つまり1と2(B), 3と4(C), 5と6(D)の回りの8点はそれぞれ同じで, その他に0(A)と7(E)で5種類である. Grayコードの部品がたくさんあるが, 全体がGrayコードになっているのではない.

A    B    C    D    E
zyx  zyx  zyx  zyx  zyx
000  000  011  110  101
010  001  001  111  111
110  101  000  011  011
100  100  010  010  001
101  110  110  000  000
111  111  100  001  010
011  011  101  101  110
001  010  111  100  100
x+z^ y+z^ z+xv y-zv x-zv

さてこれに分かりやすい名前を付けたい. Aを見ると最上段と最下段ではxが0から1と増えている. zは0から1になり0に戻る. yはふらふらして元に戻るから無視すると, xは増え(x+)zは010(^)の凸型ということで, x+z^と呼ぶことにする. 他のBからEも同じ要領で命名してある. 上にあった1次の形は, この方式でいうとz+y^である.

そのそれぞれを描くと次のようになる. 左上は1次の形である.



この1次の形z+y^は2次で描くとA, B, B, C, C, D, D, Eで出来ていたのだ. つまり

z+y^ = x+z^ 2(y+z^) 2(z+xv) 2(y-zv) x-zv.
        A      B       C       D     E

x座標はAで増え, Cで2回減増し, Eで減るから変化なし.
y座標はBで増え, Dで減るからy^である.
z座標はAで増減し, Cで増え, Eで減増するからz+である. 全体でz+y^となるわけだ.

2次のA, B, C, D, Eがこのように分解出来るなら, 3次も描けることになる.



分解を上の図を見ながらもう一度考えてみよう.

最初の+か-を伴う座標を主軸といおう. 次の^かvの座標を副軸といおう. 最後に名称に出てこないのを従軸といおう.

• 3と4は主軸の+, -により+か-になる. +の場合, 0,1,2では主軸は^, 5,6,7ではvになり, -なら逆になる.

• 副軸は^なら1と2で+, 5と6で-, vなら逆になる.

• 従軸の初期値は, 主軸と副軸の初期値と偶数パリティになるようにとる. それが0なら0で+, 3と4でv, 7で+. 1なら逆になる.

さっそく挑戦してみる.

x+z^ = y+x^ 2(z+x^) 2(x+yv) 2(z-xv) y-xv.

そう分かるとプログラムが書ける.

(define (xyz a) (list-ref '(x y z) a))
(define (+- b) (list-ref '(+ -) b))
(define (ud b) (list-ref '(^ v) b))

(define (bar a0 b0 a1 b1)
 (let ((a2 (- 3 a0 a1)) (b2 (modulo (+ b0 b1) 2)))
  (list
   (list (xyz a0) (+- b0) (xyz a1) (ud b1))
   (list (xyz a2) (+- b2) (xyz a0) (ud b0));0
   (list (xyz a1) (+- b1) (xyz a0) (ud b0));1,2
   (list (xyz a0) (+- b0) (xyz a2) (ud (- 1 b2)));3,4
   (list (xyz a1) (+- (- 1 b1)) (xyz a0) (ud (- 1 b0)));5,6
   (list (xyz a2) (+- (- 1 b2)) (xyz a0) (ud (- 1 b0))))));7

(z + y ^)は(bar 2 0 1 0)と入力する. すると

(bar 2 0 1 0) =>
((z + y ^) (x + z ^) (y + z ^) (z + x v) (y - z v) (x - z v))

と得られる. リストの先頭は入力パターンである. 従って上の図と同じになる.

Aを分解すると,

(bar 0 0 2 0) =>
((x + z ^) (y + x ^) (z + x ^) (x + y v) (z - x v) (y - x v))

一方, Grayコードを得るには次のプログラムでよい.

(define (foo a0 b0 a1 b1)
 (let ((b '()) (a (list 0 0 0)) (a2 (- 3 a0 a1))
  (b2 (modulo (+ b0 b1) 2)))
  (list-set! a a0 b0) (list-set! a a1 b1) (list-set! a a2 b2)
  (set! b (cons (reverse a) b))
  (list-set! a a2 (- 1 (list-ref a a2)))
  (set! b (cons (reverse a) b))
  (list-set! a a1 (- 1 (list-ref a a1)))
  (set! b (cons (reverse a) b))
  (list-set! a a2 (- 1 (list-ref a a2)))
  (set! b (cons (reverse a) b))
  (list-set! a a0 (- 1 (list-ref a a0)))
  (set! b (cons (reverse a) b))
  (list-set! a a2 (- 1 (list-ref a a2)))
  (set! b (cons (reverse a) b))
  (list-set! a a1 (- 1 (list-ref a a1)))
  (set! b (cons (reverse a) b))
  (list-set! a a2 (- 1 (list-ref a a2)))
  (set! b (cons (reverse a) b))
  (reverse b)))

初期値を設定してから, 従軸, 副軸, 従軸, 主軸, 従軸, 副軸, 従軸の順に1と0を交換する. "z+y^"は(foo 2 0 1 0)と入力する.

(foo 2 0 1 0) =>
((0 0 0)(0 0 1)(0 1 1)(0 1 0)(1 1 0)(1 1 1)(1 0 1)(1 0 0))

と得られる.

Aを１次とみて, その2次の絵を描いてみると,

なんだかうまく行っているらしい. 春から縁起がいいわ.