再帰処理とL-Systemでかんたんフラクタル3選
フラクタルとは!?
"フラクタル"とは、図形の部分と全体が自己相似になっているものです。(Wikipediaありざます)
今回は、再帰処理を使った有名なフラクタルアート3種類をまとめてみます。
(シェルピンスキー3兄弟)
- シェルピンスキーのギャスケット
- シェルピンスキーのカーペット
- シェルピンスキーの曲線
ここでは、図形の描画にOpenProcessingを利用します。
使い方に関しては、p5.jsをかじる本を参考にして頂けると幸いです。
シェルピンスキーのギャスケット
"フラクタル"を検索すると、結果としてほぼ間違いなくこの図形と出会う事になります。
三角形の中に三角形があり、またその三角形の中に三角形があり...
なんとも魅力的な図形ですね。ޱ(ఠ皿ఠ)ว
シェルピンスキーのギャスケット
この図形を描画する手順を次の様に考えてみました。
- 三角形を描く(白)
- その中央に逆三角形を描く(青)
- 残った3つの三角形の...(2に戻る)
手順のイメージ
2と3の手順を再帰処理で記述すると次の様になります。
(クリックで全コードを見る事ができます)
シェルピンスキーのギャスケット
"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になるまで再帰を繰り返します。
drawFractal(points, 5, BLACK);// 再帰処理の開始
実際に動いているコードはこちらになります。
シェルピンスキーのカーペット
次はカーペットです。
9分割した四角形の中に四角形があり四角形の四角形の...以下略
こちらもギャスケットと同じ理屈で考える事ができそうですね。ޱ(ఠ皿ఠ)ว
シェルピンスキーのカーペット
この場合の手順は次の様に考えてみました。
- 四角形を描く(白)
- 9分割した中央に四角形を描く(青)
- 中央以外の8つの四角形に対し...(2に戻る)
手順のイメージ
2と3の手順を再帰処理で記述すると次の様になります。
(クリックで全コードを見る事ができます)
シェルピンスキーのカーペット
"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になるまで再帰を繰り返します。
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 | 以下略 |
最終的に得られた文字列を元にして、以降の図形を描画します。
シェルピンスキーの曲線の実装
具体的なコードを確認してみましょう。
(クリックで全コードを見る事ができます)
シェルピンスキーの曲線
"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"には、再帰数を指定します。
const cmds = createCmds("AA", depth);// 再帰処理の開始
再帰処理の回数に応じて、曲線が大きくなっていく事がわかります。
(なんだか凄い!!)
左から再帰回数2回,3回,4回
実際に動いているコードはこちらになります。
最後に
今回は再帰処理だけを使ったフラクタルや、L-Systemを使ったフラクタルをご紹介致しました。
上手く出来た時は快感ですwww
実装方法に答えは無いので、さまざまなアプローチを考えてみるのも楽しそうです。
是非挑戦してみてくださいね。
ここまで読んでいただき有難うございました。
Discussion