バーティカルバーの極意（Vol.65掲載）

筆者：飯尾淳

　今回はデータ分析から少し離れてフラクタル図形について語りましょ
う。例として、縦棒（バーティカルバー）と横棒が縦横無尽に組み合わさった図形であるヒルベルト曲線を考えます。ヒルベルト曲線はフラクタル図形の一つで、自己相似性という特徴を持ちます。本記事ではこれを描画するプログラムを紹介します。シンプルなプログラムでこんなにも複雑な図形を描くことができるのかと驚くはずです。

シェルスクリプトマガジン Vol.65は以下のリンク先でご購入できます。

図4　図を出力するためのHTMLコード

<!DOCTYPE html>
<html>
  <head>
    <title>Hilbert Curve</title>
    <meta charset="utf-8">
    <meta name="description" content="Drawing Hilbert curve">
    <meta name="author" content="Jun Iio">
    <meta name="viewport" content="width=device-width,initial-scale=1">
  </head>
  <body>
    <canvas id="theCanvas" width="1000" height="1000"></canvas>
    <script src="hilbert.js"></script>
  </body>
</html>

図5　1次ヒルベルト曲線を描くJavaScriptコード

// the canvas and its graphic context
var cs  = document.getElementById('theCanvas');
var ctx = cs.getContext('2d');

ctx.lineWidth   = 5;
ctx.strokeStyle = 'black';

ctx.beginPath();
[ [0.25, 0.25], [0.25, 0.75], [0.75, 0.75], [0.75, 0.25] ]
	.map(p => [p[0]*cs.width, p[1]*cs.height])
    	.forEach(p => { ctx.lineTo(p[0],p[1]); });
ctx.stroke();

図7　n次のヒルベルト曲線を描く手続き

function hilbert(n, R) {
  if (n > 1) {
    hilbert(n-1, R’=f(R,"左上"));
    hilbert(n-1, R’=f(R,"左下"));
    hilbert(n-1, R’=f(R,"右下"));
    hilbert(n-1, R’=f(R,"右上"));
  } else {
    （Rで示される座標上で1次のヒルベルト曲線を描くコード）
  }

図10　座標変換ルールを格納した配列を定義するコード

var tm = [
  // tm[0]
    [ [   0,  1/2,   0],
      [ 1/2,    0,   0],
      [   0,    0,   1] ],
  // tm[1]
    [ [ 1/2,    0,   0], 
      [   0,  1/2, 1/2], 
      [   0,    0,   1] ],
  // tm[2]
    [ [ 1/2,    0, 1/2],
      [   0,  1/2, 1/2], 
      [   0,    0,   1] ],
  // tm[3]
    [ [   0, -1/2,   1], 
      [-1/2,    0, 1/2], 
      [   0,    0,   1] ]
]

図11　1次から8次までのヒルベルト曲線を描くコード

// the canvas and its graphic context
var cs  = document.getElementById('theCanvas');
var ctx = cs.getContext('2d');

// line style
var colors = [ 'gray', 'navy', 'purple', 'brown',
                'red', 'orange', 'yellowgreen', 'skyblue' ];
var widths = [5, 4, 3, 2, 2, 1, 1, 0.5 ];

var tm = [
  [ [  0,  1/2,   0], [ 1/2,   0,   0], [0, 0, 1] ],
  [ [1/2,    0,   0], [   0, 1/2, 1/2], [0, 0, 1] ],
  [ [1/2,    0, 1/2], [   0, 1/2, 1/2], [0, 0, 1] ],
  [ [  0, -1/2,   1], [-1/2,   0, 1/2], [0, 0, 1] ]
];
var E = [ [ 1, 0, 0], [0, 1, 0], [0, 0, 1] ];

function affine_transform(m, p) {
  return [ m[0][0] * p[0] + m[0][1] * p[1] + m[0][2],
           m[1][0] * p[0] + m[1][1] * p[1] + m[1][2] ];
}

function mat_mul(m0, m1) {
  return [ [m0[0][0]*m1[0][0]+m0[0][1]*m1[1][0]+m0[0][2]*m1[2][0],
            m0[0][0]*m1[0][1]+m0[0][1]*m1[1][1]+m0[0][2]*m1[2][1],
            m0[0][0]*m1[0][2]+m0[0][1]*m1[1][2]+m0[0][2]*m1[2][2]],
           [m0[1][0]*m1[0][0]+m0[1][1]*m1[1][0]+m0[1][2]*m1[2][0],
            m0[1][0]*m1[0][1]+m0[1][1]*m1[1][1]+m0[1][2]*m1[2][1],
            m0[1][0]*m1[0][2]+m0[1][1]*m1[1][2]+m0[1][2]*m1[2][2]],
           [m0[2][0]*m1[0][0]+m0[2][1]*m1[1][0]+m0[2][2]*m1[2][0],
            m0[2][0]*m1[0][1]+m0[2][1]*m1[1][1]+m0[2][2]*m1[2][1],
            m0[2][0]*m1[0][2]+m0[2][1]*m1[1][2]+m0[2][2]*m1[2][2]] ];
}
function hilbert(n, m) {
  if (n > 0) {
    tm.forEach(mm => { hilbert(n-1, mat_mul(m, mm)); });
  } else {
    [ [0.25, 0.25], [0.25, 0.75], [0.75, 0.75], [0.75, 0.25] ]
        .map(p => affine_transform(m, p))
        .map(p => [p[0]*cs.width, p[1]*cs.height])
        .forEach(p => { ctx.lineTo(p[0],p[1]); });
  }
}

function drawHilbert(i) {
  ctx.beginPath();
  ctx.lineWidth   = widths[i];
  ctx.strokeStyle = colors[i];
  hilbert(i, E);
  ctx.stroke();
}

for(i=0; i<colors.length; i++) { drawHilbert(i); }