Zenn
🔰

再帰処理とL-Systemであっさりフラクタル3選

2024/05/29に公開
JavaScript
初心者
p5.js
fractal
tech

フラクタルとは!?

"フラクタル"とは、図形の部分と全体が自己相似になっているものです。(Wikipediaありざます)

今回は、再帰処理を使った有名なフラクタルアート3種類をまとめてみます。
(シェルピンスキー3兄弟)

  1. シェルピンスキーのギャスケット
  2. シェルピンスキーのカーペット
  3. シェルピンスキーの曲線

ここでは、図形の描画にOpenProcessingを利用します。
使い方に関しては、p5.jsをかじる本を参考にして頂けると幸いです。

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

"フラクタル"を検索すると、結果としてほぼ間違いなくこの図形と出会う事になります。
三角形の中に三角形があり、またその三角形の中に三角形があり...
なんとも魅力的な図形ですね。ޱ(ఠ皿ఠ)ว


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

この図形を描画する手順を次の様に考えてみました。

  1. 三角形を描く(白)
  2. その中央に逆三角形を描く(青)
  3. 残った3つの三角形の...(2に戻る)


手順のイメージ

2と3の手順を再帰処理で記述すると次の様になります。
(クリックで全コードを見る事ができます)

シェルピンスキーのギャスケット
main.js
"use strict"

const WHITE = "#eeeeee";
const BLACK = "#2f6690";

function setup(){
	createCanvas(windowWidth, windowHeight);
	angleMode(DEGREES);
	noLoop(); noFill(); noStroke();
}

function draw(){
	background(BLACK);

	// 最初の三角形の中心座標
	const x = width / 2;
	const y = height * 0.65;

	// 最初の三角形の各頂点を求める
	const len = width<height?width*0.5:height*0.6;
	const deg = -90;
	const aX = x + len * cos(deg);// 1つ目の頂点
	const aY = y + len * sin(deg);
	const bX = x + len * cos(deg+120);// 2つ目の頂点
	const bY = y + len * sin(deg+120);
	const cX = x + len * cos(deg+240);// 3つ目の頂点
	const cY = y + len * sin(deg+240);
	const points = [[aX, aY], [bX, bY], [cX, cY]];
	drawFractal(points, 5, BLACK);// 再帰処理の開始
}

function drawFractal(points, depth, c){

	// 再帰する必要が無い場合(depthが0)は逆三角形を描画
	if(depth <= 0){
		fill(c);
		triangle(
			points[0][0], points[0][1],
			points[1][0], points[1][1],
			points[2][0], points[2][1]);
		return;// これ以上は再帰処理を行わない
	}

	// 逆三角形の頂点を求める(各辺の中間地点)
	const pA = getMid(points[0], points[1]);
	const pB = getMid(points[1], points[2]);
	const pC = getMid(points[2], points[0]);
	drawFractal([pA, pB, pC], 0, BLACK);

	drawFractal([points[0], pA, pC], depth-1, WHITE);// 上の三角形に再帰
	drawFractal([points[1], pA, pB], depth-1, WHITE);// 左の三角形に再帰
	drawFractal([points[2], pB, pC], depth-1, WHITE);// 右の三角形に再帰
}

function getMid(pA, pB){
	const x = (pA[0] + pB[0]) / 2;
	const y = (pA[1] + pB[1]) / 2;
	return [x, y];
}

再帰処理をしている関数は、"drawFractal()"です。
再帰回数を"5"とし、この値が0になるまで再帰を繰り返します。

main
drawFractal(points, 5, BLACK);// 再帰処理の開始

実際に動いているコードはこちらになります。

シェルピンスキーのカーペット

次はカーペットです。
9分割した四角形の中に四角形があり四角形の四角形の...以下略
こちらもギャスケットと同じ理屈で考える事ができそうですね。ޱ(ఠ皿ఠ)ว


シェルピンスキーのカーペット

この場合の手順は次の様に考えてみました。

  1. 四角形を描く(白)
  2. 9分割した中央に四角形を描く(青)
  3. 中央以外の8つの四角形に対し...(2に戻る)


手順のイメージ

2と3の手順を再帰処理で記述すると次の様になります。
(クリックで全コードを見る事ができます)

シェルピンスキーのカーペット
main.js
"use strict"

const WHITE = "#eeeeee";
const BLACK = "#2f6690";

function setup(){
	createCanvas(windowWidth, windowHeight);
	angleMode(DEGREES);
	noLoop(); noFill(); noStroke();
}

function draw(){
	background(BLACK);

	// 四角形の辺の長さと座標
	const len = (width<height)?width*0.8:height*0.8;
	const x = width/2 - len/2;
	const y = height/2 - len/2;
	fill(WHITE);
	square(x, y, len);// 最初の四角形を描く
	fill(BLACK);
	drawFractal(x, y, len, 3);// 再帰処理の開始
}

function drawFractal(x, y, len, depth){

	// 四角形の辺を3等分する
	const pad = len / 3;
	// 9x9の四角形の座標を求める
	for(let r=0; r<3; r++){
		for(let c=0; c<3; c++){
			// 分割された四角形の座標
			const cX = x + pad*c;
			const cY = y + pad*r;
			// 中央の四角形であれば四角形を描画
			if(r==1 && c==1){
				square(cX, cY, pad);
				continue;
			}
			if(depth <= 0) continue;// これ以上再帰をしない
			// その他の8つの四角形に対して再帰
			drawFractal(cX, cY, pad, depth-1);
		}
	}
}

具体的な再帰処理の関数は、"drawFractal()"です。
ここでは再帰回数を"3"としており、この値が0になるまで再帰を繰り返します。

main
drawFractal(x, y, len, 3);// 再帰処理の開始

実際に動いているコードはこちらになります。

シェルピンスキーの曲線

これまでの例では、再帰処理を使って再帰と描画を同時に行ってきました。
最後の例では、L-Systemというアイデアを使ってフラクタルを実装してみます。

L-Systemとは、植物の成長プロセスを初めとした様々な自然物の構造を記述・表現できるアルゴリズムです。(Wikipediaありざます)


シェルピンスキーの曲線

L-Systemの具体例

L-Systemでは、先ず初期文字列(イニシエーター)を元にして、
それを特定のパターン(置換規則)に則って置き換えを繰り返していきます。

例えば次の様な置換規則があるとします。

置き換え前 置き換え後
A AB
B BAA

イニシエーター"A"を元にして置き換えをしていくと、
次の様に文字列が変化していきます。

世代 文字列
0 A
1 AB
2 ABBAA
3 ABBAABAAABAB

あらかじめ、Aには"直線をまっすぐ引く"、Bには"左に30度向く"等の命令を持たせておき、
完成した文字列をコマンドとして実行し図形を描画します。

シェルピンスキーの曲線のL-System

シェルピンスキーの曲線に必要なL-Systemを次にまとめます。

置換規則

置き換え前 置き換え後
A BABA
B BABB

命令

文字 命令
A 直線を引く、90度右に向く、直線を引く、90度右に向く
B 直線を引く、45度左に向く、直線を引く(2回)、左に45度向く

文字列の変化

イニシエーターを"AA"として、文字列を変化させます。

世代 文字列
0 AA
1 BABABABA
2 BABBBABABABBBABABABBBABABABBBABA
3 以下略

最終的に得られた文字列を元にして、以降の図形を描画します。

シェルピンスキーの曲線の実装

具体的なコードを確認してみましょう。
(クリックで全コードを見る事ができます)

シェルピンスキーの曲線
main.js
"use strict"

const WHITE = "#eeeeee";
const BLACK = "#2f6690";

function setup(){
	createCanvas(windowWidth, windowHeight);
	angleMode(DEGREES);
	noLoop(); stroke(WHITE); strokeWeight(2);
}

function draw(){
	background(BLACK);
	drawFractal();
}

function drawFractal(x, y){
	const depth = 3;// 再帰処理をする回数
	const cmds = createCmds("AA", depth);// 再帰処理の開始
	const len = ((width<height)? width:height)/100;
	drawCmds(width/2, 0, cmds, len);// コマンドを元に図形を描画
}

function createCmds(str, depth){
	if(depth <= 0) return str;
	let result = "";
	for(let s of str){
		if(s == "A") result += "BABA";// Aを置き換える
		if(s == "B") result += "BABB";// Bを置き換える
	}
	return createCmds(result, depth-1);// 再帰処理
}

function drawCmds(x, y, cmds, len){
	translate(x, y);
	rotate(90);
	for(let cmd of cmds){
		if(cmd == "A"){// "A"の描画命令
			line(0, 0, len, 0);
			translate(len, 0);
			rotate(90);
			line(0, 0, len, 0);
			translate(len, 0);
			rotate(90);
			continue;
		}
		if(cmd == "B"){// "B"の描画命令
			line(0, 0, len, 0);
			translate(len, 0);
			rotate(-45);
			line(0, 0, len*2, 0);
			translate(len*2, 0);
			rotate(-45);
			continue;
		}
	}
}

再帰処理を実装している箇所は、文字列を組み立てている"createCmds()"関数です。
"depth"には、再帰数を指定します。

main.js
const cmds = createCmds("AA", depth);// 再帰処理の開始

再帰処理の回数に応じて、曲線が大きくなっていく事がわかります。
(なんだか凄い!!)


左から再帰回数2回,3回,4回

実際に動いているコードはこちらになります。

最後に

今回は再帰処理だけを使ったフラクタルや、L-Systemを使ったフラクタルをご紹介致しました。
上手く出来た時は快感ですwww
実装方法に答えは無いので、さまざまなアプローチを考えてみるのも楽しそうです。
是非挑戦してみてくださいね。
ここまで読んでいただき有難うございました。

Discussion