Chapter 67

フラクタル

miku
miku
2021.11.19に更新

この章では、再帰の利用例としてフラクタルを描画するアルゴリズムについて学ぶ。フラクタルは描かれる図形を分解していくと、全体と同じ形が再現されていく構造になる特殊な性質を持っている。

コッホ曲線

手順1

koch(n, a, b);

コッホ曲線を描く koch(n, a, b) には、再帰回数 n と、2点 a, b を指定する。

手順2

const c = lerp2d(a, b, 1 / 3);
const d = lerp2d(a, b, 2 / 3);

a, b 間に線分を引いたときに、その線分を3等分する2点 c, d を計算する。

手順3

let angle = atan2(d.y - c.y, d.x - c.x);
angle -= 60;

const k = dist(c.x, c.y, d.x, d.y);
const e = { x: c.x + cos(angle) * k, y: c.y + sin(angle) * k };

c, d 間の線分が1辺となる正三角形を作る場合、点があと1つ必要だが、その点の位置 e を計算する。この場合、c から d の方向から-60度あるいは60度の方向の点になる。どちらを採用してもいいが、最終的にできる曲線の向きが変わる。

手順4

koch(n - 1, a, c);
koch(n - 1, c, e);
koch(n - 1, e, d);
koch(n - 1, d, b);

これで5つの点ができたが、(a, c), (c, e), (e, d), (d, e) の2点をもとに再帰的に koch() を呼び出す。

手順5

if (n === 0) {
  line(a.x, a.y, b.x, b.y);
  return;
}

再帰の回数分だけ計算したら、ab 間に線を引く。

コード例

function setup() {
  createCanvas(windowWidth, windowHeight);
  angleMode(DEGREES);
  stroke(240);
  noFill();

  const a = { x: 0, y: (height / 4) * 3 };
  const b = { x: width, y: (height / 4) * 3 };
  koch(5, a, b);
}

function koch(n, a, b) {
  if (n === 0) {
    line(a.x, a.y, b.x, b.y);
    return;
  }

  const c = lerp2d(a, b, 1 / 3);
  const d = lerp2d(a, b, 2 / 3);

  let angle = atan2(d.y - c.y, d.x - c.x);
  angle -= 60;

  const k = dist(c.x, c.y, d.x, d.y);
  const e = { x: c.x + cos(angle) * k, y: c.y + sin(angle) * k };

  koch(n - 1, a, c);
  koch(n - 1, c, e);
  koch(n - 1, e, d);
  koch(n - 1, d, b);
}

function lerp2d(a, b, t) {
  return { x: lerp(a.x, b.x, t), y: lerp(a.y, b.y, t) };
}

シェルピンスキーのギャスケット

手順1

gasket(n, a, b, c);

シェルピンスキーのギャスケットを描く gasket(n, a, b, c) には、再帰回数 n と、正三角形の3つの点 a, b, c を指定する。

手順2

const d = lerp2d(a, b, 0.5);
const e = lerp2d(b, c, 0.5);
const f = lerp2d(c, a, 0.5);

a, b, b, c, c, a の中点 d, e, f の位置を計算する。

手順3

gasket(n - 1, a, d, f);
gasket(n - 1, d, b, e);
gasket(n - 1, f, e, c);

a, d, f, d, b, e, f, e, c に小さな正三角形が3つできる。この三角形をもとにまた再帰を行う。

手順4

if (n === 0) {
  triangle(a.x, a.y, b.x, b.y, c.x, c.y);
  return;
}

再帰の回数分だけ計算したら、abc の点を繋いで三角形を描く。

コード例

function setup() {
  createCanvas(windowWidth, windowHeight);
  angleMode(DEGREES);
  stroke(240);
  noFill();

  const size = 300;
  const a = { x: 0, y: size };
  const b = { x: a.x + size, y: a.y };
  const c = { x: a.x + cos(-60) * size, y: a.y + sin(-60) * size };
  gasket(5, a, b, c);
}

function gasket(n, a, b, c) {
  if (n === 0) {
    triangle(a.x, a.y, b.x, b.y, c.x, c.y);
    return;
  }

  const d = lerp2d(a, b, 0.5);
  const e = lerp2d(b, c, 0.5);
  const f = lerp2d(c, a, 0.5);

  gasket(n - 1, a, d, f);
  gasket(n - 1, d, b, e);
  gasket(n - 1, f, e, c);
}

function lerp2d(a, b, t) {
  return { x: lerp(a.x, b.x, t), y: lerp(a.y, b.y, t) };
}

ドラゴン曲線

手順1

dragon(n, a, b);

ドラゴン曲線を描く dragon(n, a, b) には、再帰回数 n と、2点 a, b を指定する。

手順2

const deg = atan2(b.y - a.y, b.x - a.x) - 45 * sign;
const d = dist(a.x, a.y, b.x, b.y) * (sqrt(2) / 2);
const c = { x: a.x + cos(deg) * d, y: a.y + sin(deg) * d };

a, b 間の中点を c として、角cabが45度になるまで c を引っ張る。c の位置を計算するには a, c 間の距離が必要だが、これは三平方の定理を利用して計算する。

a, b 間の距離が仮に 1 だとすると、a から仮に用意した d までの距離は \sqrt{2} になる。その半分が c までの距離なので a から c までの距離は \frac{\sqrt{2}}{2} になる。

手順3

これで a, b, c の3つの点ができたが、a, b, b, c の組み合わせで更に再帰を行う。ただし、a, b は-45度で、b, c は45度にする必要がある。

function setup() {
  createCanvas(windowWidth, windowHeight);
  angleMode(DEGREES);
  stroke(240);
  noFill();

  const a = { x: width / 2, y: height / 2 };
  const b = { x: width / 2 + 100, y: height / 2 };
  dragon(12, a, b, 1);
}

function dragon(n, a, b, sign) {
  if (n === 0) {
    line(a.x, a.y, b.x, b.y);
    return;
  }

  const deg = atan2(b.y - a.y, b.x - a.x) - 45 * sign;
  const d = dist(a.x, a.y, b.x, b.y) * (sqrt(2) / 2);
  const c = { x: a.x + cos(deg) * d, y: a.y + sin(deg) * d };

  dragon(n - 1, a, c, 1);
  dragon(n - 1, c, b, -1);
}