コッホ曲線

コッホ曲線とは

コッホ曲線 (Koch curve) とは「線分を3等分し、分割した2点を頂点とする正三角形を作る」という操作を無限に繰り返すことによって得られるフラクタル図形の一種である。図1に原点 (0, 0) と点 (1, 0) を結ぶ線分から作成したコッホ曲線を示す。

図1: コッホ曲線

点 P0 と P1 を結ぶ線分 [P0, P1] からコッホ曲線を作成するには次のような操作を行う。まず、1回目の操作では線分 (P0, P1) に対して点 Q0, Q1, Q2 を次のように定める（図2）。

Q0: 線分 [P0, P1] を 1:2 に内分する点
Q2: 線分 [P0, P1] を 2:1 に内分する点
Q1: Q0 を中心に Q2 を反時計回りに 60 度回転させて得られる点（有向線分 [P0, P1] の「左側」に正三角形 Q0, Q1, Q2 ができるように Q1 を置く）

元の点 P0, P1 と新しい点 Q0, Q1, Q2 を結ぶことにより1回目の操作が完了する。同じ操作を4つの線分 [P0, Q0], [Q0, Q1], [Q1, Q2], [Q2, P1] に対して行うと、さらに複雑な図形が得られる。この操作を無限に繰り返すことによりコッホ曲線が得られる。作図方法からわかるように、1回の分割操作で線分の長さが 4/3 倍になるので、コッホ曲線は無限の長さを持つ。もちろん、分割を無限に続けることは不可能なので、実際に作図する場合にはある程度細かくなったところで分割を打ち切る必要がある。

図2: コッホ曲線の作図方法

2つの頂点 P0, Q0 や Q0, Q1 の間に含まれるコッホ曲線の一部分は P0, P1 の間に含まれるコッホ曲線全体と相似になっている。もっと小さな区間にも全体と相似な図形が存在し、コッホ曲線には全体と相似な図形が無数に含まれる。このような性質を「自己相似」という。

再帰関数 koch() の作成

このコッホ曲線をプログラムで作図することを考える。以下の方針に従って、コッホ曲線の頂点の座標を出力する再帰関数 koch() を作成する。

koch() は P0 の座標 (xp0, yp0) と P1 の座標 (xp1, yp1) を引数として受け取る。
2点 P0, P1 の距離がしきい値 EPS 未満の場合は分割を打ち切り、始点 P0 の座標を画面に出力して return する。
2点 P0, P1 の距離がしきい値 EPS 以上の場合は分割を行う。 Q0, Q1, Q2 の座標を計算し、4つの線分 [P0, Q0], [Q0, Q1], [Q1, Q2], [Q2, P1] に対して koch() を再帰呼び出しする。

関数 koch() を始点 P0 (0, 0) と終点 P1 (1, 0) に対して実行すると、図1に示したコッホ曲線の各頂点の座標リストが得られる（EPS は 0.002 とした）。また、koch() は終点の座標を出力しないので、一番最後に終点 P1 の座標を出力する必要がある。

以下にプログラムのアウトラインを示す。

【クリックしてプログラムのアウトラインを表示】

/*
  コッホ曲線の頂点を出力するプログラム
 */
#include <stdio.h>
#include <math.h>               /* sqrt() */

/*
  引数として始点 P0 (xp0, yp0), 終点 P1 (xp1, yp1) の座標を受け取る。
  点 P0, P1 の距離が EPS 以上離れていれば分割を行い、分割した各線分
  に対して koch() を再帰的に適用する。距離が EPS 未満なら始点 P0 の
  座標値を出力して再帰を終了する。
*/
void koch(double xp0, double yp0, double xp1, double yp1)
{
    double d, xq0, xq1, xq2, yq0, yq1, yq2;
    const double EPS = 0.002;   /* 2点間の距離のしきい値 */

    /* (P0, P1) の距離 */
    d = ...;

    /* 点 P0, P1 が十分近ければ点 P0 の座標を出力して再帰終了 */
    if (d < EPS) {
        printf("%20.12e %20.12e\n", xp0, yp0);
        return;
    }

    /* 以下は点 P0, P1 が EPS 以上離れている場合 */

    /* Q0, Q1, Q2 の座標を求める */
    xq0 = ...;
    yq0 = ...;
    xq2 = ...;
    yq2 = ...;
    xq1 = ...;
    yq1 = ...;

    /* 再帰呼び出しにより各線分をさらに分割 */
    koch(xp0, yp0, xq0, yq0);   /* P0, Q0 */
    koch(xq0, yq0, xq1, yq1);   /* Q0, Q1 */
    koch(xq1, yq1, xq2, yq2);   /* Q1, Q2 */
    koch(xq2, yq2, xp1, yp1);   /* Q2, P1 */

    return;
}

/*
  (0, 0), (1, 0) を端点とする Koch 曲線の頂点データを作成する
*/
int main(void)
{
    koch(0.0, 0.0, 1.0, 0.0);                   /* P0 (0, 0), P1 (1, 0) */
    printf("%20.12e %20.12e\n", 1.0, 0.0);      /* koch() は終点の座標を出力しないので P1 を出力 */

    return 0;
}

プログラムを実行するとコッホ曲線の頂点の座標が各行に1つ、x 座標と y 座標の組で出力される。これを Gnuplot で描画するには次のようにすればよい。

% ./a.out > koch.dat
% gnuplot
gnuplot> set size ratio 0.3
gnuplot> plot 'koch.dat' with line title 'Koch curve'

コッホ雪片

コッホ曲線を3つつなぎ合わせたものがコッホ雪片 (Koch snowflake) である。コッホ雪片の面積は有限であるが、無限に長い周囲を持つ。

図3: コッホ雪片