📐

シェルピンスキーのギャスケットの簡単な書き方

2024/05/06に公開

42 Tokyo

フラクタル

tech

 目標シェルピンスキーのギャスケットを描く方法を考えます。

https://ja.wikipedia.org/wiki/シェルピンスキーのギャスケット

 最初は直角三角形で考える正三角形でシェルピンスキーのギャスケットを描くのは計算が面倒なので、最初は直角三角形バージョンのシェルピンスキーのギャスケットを考えます。

そこまで描くことができたら、座標変換して正三角形バージョンにすることは簡単です。


 (0 \leq x \leq 1), (0 \leq y \leq 1)で考える直角三角形バージョンのシェルピンスキーのギャスケットを描くために、まずは0 \leq x \leq 1, 0 \leq y \leq 1の範囲で考えます。
まず、直角三角形を描くには以下3つの条件を全て満たす点に色を塗れば直角三角形を描くことができます。

 条件1x \geq 0
y \geq 0
(x + y) \leq 1
では、真ん中の三角形を抜くには？

条件1を満たしつつ、次の条件2を全て満たす場合は色を塗らないようにすれば、真ん中を抜いた直角三角形を描くことができます。

 条件2x \leq 1/2
y \leq 1/2
(x + y) \geq 1/2
真ん中を抜く操作を①、②、③の三角形に適用すると、この様になります。

後は再帰的に真ん中を抜いていけば、直角三角形バージョンのシェルピンスキーのギャスケットの完成です。

 再帰回数と拡大シェルピンスキーのギャスケットの面積は0のため、再帰を何度も繰り返すと何も表示されなくなってしまいます。初期表示は大きさにもよりますが、6,7回程度で再帰を抜けると、それっぽい画像になります。
では画像を拡大した時、どの様に再帰回数を増やしていけばよいでしょうか？



例えば2倍に拡大したとき、1回再帰回数を増やせば、小さい三角形の大きさは同じになります。

最初の再帰回数をC（=6,7回）、拡大率をZとしたとき、 再帰回数Nは下記のようになります。

N = log_2(Z) + C

 座標変換直角三角形のままでもシェルピンスキーのギャスケットと言って問題ありませんが、せっかくなので正三角形に座標変換してあげます。
赤い平行四辺形から青い正方形に線形変換する行列Aは

A = 
\begin{pmatrix}
   a & b \\
   c & d
\end{pmatrix}
として、以下の連立方程式からa,b,c,dを求めればよいです。


\begin{pmatrix}
   a & b \\
   c & d
\end{pmatrix}
\begin{pmatrix}
   1 \\
   0
\end{pmatrix}
=
\begin{pmatrix}
   1 \\
   0
\end{pmatrix}

\\

\begin{pmatrix}
   a & b \\
   c & d
\end{pmatrix}
\begin{pmatrix}
   1/2 \\
   \sqrt{ 3}/2
\end{pmatrix}
=
\begin{pmatrix}
   0 \\
   1
\end{pmatrix}

最終的に、変換行列Aは下記のように求められます。

A = 
\begin{pmatrix}
   1 & -\sqrt{3}/3 \\
   0 & 2\sqrt{3}/3
\end{pmatrix}
画面の座標系(w,h)として、変換行列Aをかけて座標系(x,y)に変換し、その(x,y)座標系で直角三角形のシェルピンスキーのギャスケット描けば、正三角形バージョンの完成です。


A
\begin{pmatrix}
   w \\
   h
\end{pmatrix}
=
\begin{pmatrix}
   x \\
   y
\end{pmatrix}

https://www.youtube.com/watch?v=RtrgNxcRbIo

 おまけフラクタル図形をリアルタイムでサクサク描画させたい場合は、下記を参考にして下さい。

https://zenn.dev/grigri_grin/articles/5d201067dedfdb