desmosで遊ぼう②　～複雑な図形を作ろう～

# 2度目の自己紹介

みなさんこんにちは！
Physics Lab. 副統括 兼 ニュートン祭委員長のはいぱぼと申します！[^12/2kiji]

本日はPhysics Lab. のアドベントカレンダーにて毎週土曜日に投稿しているdesmos記事の2日目です！
一つ目の記事をまだご覧になっていない方は、ぜひそちらもご覧ください！

https://qiita.com/Haipabo/items/faec4bdcc80d0a72771c

desmosとは何かに始まり、基本的な使い方やそれらを用いたdesmosの利用法の例として「関数を拡大する虫眼鏡」を作りました！

今回は、もう少し高度なコマンドを用いて、desmosをより詳しく見ていきましょう！

:::note warn
警告
深夜テンションで書きあげたので、読みづらい箇所が多数あると思われます。
大変申し訳ありません。本記事が公開されたあとも可読性の向上のため定期的に回収を行えたらと尾も持っております。
:::

# 今回作りたいもの
![IMG_2786.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3924145/e679445b-c2f7-b288-6f60-bac71a14c515.png)

本日作るのは、フラクタルの一種、シェルピンスキーのギャスケットです！

上向き正三角形の中に半分のサイズの上向き三角形が３つ入っていて、それぞれの中にその半分の大きさの上向き正三角形が3つずつ入っていて……というのが無限に続く、フラクタルという図形の一種です。[^yuugen]

[リンク](https://www.desmos.com/calculator/doqlnyyaxt?lang=ja)

# 必要な知識
今回の内容は、desmosの知識と、数学の知識が必要なので、章に分けて説明していきます。

## desmos編
### 配列
![IMG_2787.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3924145/08c510f6-5c35-a3d5-b865-dfae42da4e43.png)
[グラフのリンク]()
desmosでは、数の組をリストにして一つの変数にすることもできます。
その変数は、一つの数のように他の箇所で使えます。その際の挙動は、上図からもわかる通り「リストの変数がある個所に、リストの値を順々に代入していってリストの個数分の点として扱う」といった具合になります。

![IMG_2789.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3924145/6a8efd22-72c8-74ad-491f-0dbba9e59522.png)
省略の記法を使えばこんなことだってできちゃいます
[グラフのリンク](https://www.desmos.com/calculator/zxwezi05am?lang=ja)

$ $
$ $

![IMG_2791.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3924145/ad94f34d-f367-5373-d807-a189e41ad09f.png)


[グラフのリンク](https://www.desmos.com/calculator/ko0muywkxk)

残念ながら一般的なプログラミングとは違い、配列の中に配列を入れた「2次元配列」[^2d]をdesmos内で作ることはできないのですが[^fornow]、例外的に「複数の配列を式に使用し、それらを動かしたときの全パターンの挙動を見る」ことで、いわゆる「for文を2重に回す」みたいな操作は可能になっています。

$ $
$ $

![IMG_2793.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3924145/ea078176-c85e-3b73-4c33-c3f330c2b04f.png)

[グラフのリンク](https://www.desmos.com/calculator/2mosld2xee)
また、配列の要素には点を入れることができます。今回のグラフではこれをよく使います。初見だと困惑しがちなところかもしれませんが、使えるといろいろなところで便利なので慣れていきましょう。

### if文
![IMG_2794.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3924145/a9df6b0a-0db8-2b74-54f7-86e3e533fce1.png)

desmosでは、なんとif文を作ることができます！
``` desmos
{(条件文):(条件文に合致する場合に返す値),(合致しない場合に返す値)}
```
みたいな書き方をします。ExcelのIF()や様々なプログラミング言語と同じ、「3項演算子」といわれる記法です。

## 数学編
グラフを書くのに使用した数学のちょこっとした知識を書いていきます
### シェルピンスキーのギャスケット
冒頭でも書きましたが、フラクタルの一種です。再掲ですが下図のように「上向き三角形の中に半分の大きさの上向き三角形を３つ敷き詰める」という操作を無限に繰り返すことで生成されます。
![IMG_2786.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3924145/e679445b-c2f7-b288-6f60-bac71a14c515.png)

### パスカルの三角形
|1|1|1|1|1|1|1|1|・・・|
|--|--|--|--|--|--|--|--|--|
|1|2|3|4|5|6|7|8|・・・|
|1|3|6|10|15|21|28|36|・・・|
|1|4|10|20|35|56|84|120|・・・|
|1|5|15|35|70|126|210|330|・・・|
|1|6|21|56|126|252|462|792|・・・|
|1|7|28|84|210|462|924|1716|・・・|
|1|8|36|120|330|792|1716|3432|・・・|
|1|9|45|165|495|1287|3003|6435|・・・|
|：|：|：|：|：|：|：|：|

と、こんな感じで「表の上端、左端に1を敷き詰め、それ以外は一つ上のマスと左のマスの合算値を書いていく」方法で作られる表を、パスカルの三角形といいます。[^pas]
このパスカルの三角形には面白い特徴が山ほどあり、それっらを述べているとそれだけで１記事書けてしまいそうなので、泣く泣くその中でも今回用いる特徴のみを以下に記します。
- 上の表のm行n列の値は、組み合わせの記号を用いて$_{m+n}C_n$で表せる
    - 表の任意のマスの数値が、左上のマスから今考えているマスまで最短経路で行く方法が何通りかを表していることに気が付くと示せます
- 上の表の奇数部分だけを塗りつぶしていくと、シェルピンスキーのギャスケットの模様が浮かび上がる
    - 上の表の奇数のみを●で塗ると以下の様になります

|●|●|●|●|●|●|●|●|●|・・・|
|--|--|--|--|--|--|--|--|--|--|
|●||●||●||●||●|・・・|
|●|●|||●|●|||●|・・・|
|●||||●||||●|・・・|
|●|●|●|●|||||●|・・・|
|●||●||||||●|・・・|
|●|●|||||||●|・・・|
|●||||||||●|・・・|
|●|●|●|●|●|●|●|●|●|・・・|
|●||●||●||●||●|・・・|
|●|●|||●|●|||●|・・・|
|●||||●||||●|・・・|
|：|：|：|：|：|：|：|：|

なんとなく見えてきたでしょうか
詳しいことや分かりやすい図は[こちらの記事](https://manabitimes.jp/math/1042)に書いてあります

# 作っていこう！
それでは、これらの知識を使ってグラフを書いていきましょう！

## step1. 任意の位置、任意の大きさに三角形を書く関数を作ろう
今回は、狙った点に狙った大きさで三角形を描写することが大いに必要です。そのため、まずは点$(p,q)$から大きさ$1/2^n$の正三角形をはやす関数$f(p,q,n)$を作っていきます。

![IMG_2796.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3924145/192564f4-8e52-fbb5-0d65-b171540bee2e.png)


[グラフのリンク](https://www.desmos.com/calculator/otfwcfge4u)

先ほど説明した配列の知識や先週のpolygon関数を使うとこのように書けます。
ここで重要なのが、後から座標の変更はできるので、今は正三角形ではなく考えやすい直角二等辺三角形を取っています。

## step2. 三角形を表示する場所を求める
パスカルの三角形の章を参考にすると、$0<x<1,0<y<1$を縦横$2^n$個に分割して$0$～$2^n-1$と番号を割り振り、パスカルの三角形のm行n列にある値が奇数なら、そこに大きさ$1/2^n$の三角形を配置していけばよいです。これを行うと、図は以下の様になります。

![IMG_2798.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3924145/3813ea29-3001-55af-7ebc-f4915cad361e.png)


[グラフのリンク](https://www.desmos.com/calculator/a1eoqykwnw)

ここで、上図のp,qは0～1を$2^n$等分した時のp,q個めを意味するので、描画の関数の$(p,q)$の係数を$1/2^r$倍しました。また、後のことを考えて、どれくらいまで描写するかを決める変数kを作りました。

途端にそれっぽくなってきましたね！しかし、右上に何やらありそうです。

これは、今考えているa,bが$a=[0,...,2^k-1],b=[0,...,2^k-1]$となっており、x,yがそれぞれ0～1を動く正方形の中をすべて探索しているためです。a,bの探索の範囲を左下の三角形だけに制限する必要があります。

## step3. if関数で論理演算をしてうまく範囲を絞ろう
上記の問題を解決するため、描画の関数に微修正を加えます。
![IMG_2800.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3924145/baf90bfe-dfa8-1eaf-6bac-126e48b62c4a.png)

[グラフのリンク](https://www.desmos.com/calculator/2urzozfrm9)

t(p,q)は、p<qの時に1、それ以外なら0を返す関数です。$mod(x,2)$は0か1を返すので、$t(0,mod(nCr(a,b),2))$は三角形を描画したいとき($\Leftrightarrow mod(nCr(a,b),2) = 1$のとき)だけ1となり、それ以外では0となります。
また、左下の三角形の範囲は$0 \leq a, 0 \leq b, a+b \leq 2^k$ なので、$t(a+b,2^k)$とすると、これは考えたい描画範囲では1となり、それ以外では0となります。
よって、これらの条件をすべてみたすような場合を考えるときは、波括弧{}で条件を設けて、その条件を「これら２つの積が1になるとき」とすればよいと分かります。

## step4. 正三角形にする
今の図形は、考えやすくするために２辺がx,y軸と平行な三角形になっています。これを正三角形の形にして終わらせたいです。

そのためには、描画をつかさどっている$f(p,q,r)$の$p,q$の部分をいじればよく、具体的には
- $(p,q) \rightarrow (p+\frac{q}2,q)$　（y軸に平行だった辺が動いて2等辺三角形になる）
- $(p+\frac{q}2,q) \rightarrow (p+\frac{q}2,\frac{\sqrt{3}}2q)$　（y軸方向に偏倍して２等辺三角形を正３角形にする）

とすればよいと分かります。これをすると、以下の様になります。
![IMG_2801.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3924145/e681f9d9-983f-78d0-a098-b26fa0e061ea.png)
きちんと正三角形でシェルピンスキーのギャスケットを書くことができました！！

kを0から5まで動かしても、どれくらい細かい正三角形まで描画するかが変わるだけで正しい図形が出力されています！

# 一件落着……？
いや～$0 \leq k \leq 5$でうまくいったってことは、ちゃんとシェルピンスキーのギャスケットが任意のkに対して描画できてよかったよかｔｔ……
$ $
$ $
![IMG_2803.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3924145/645bce27-d2c8-732f-865d-b29a3094eb4b.jpeg)
$ $
$ $
ん……？
$ $
$ $
![IMG_2804.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3924145/2282da00-6bc4-48be-eb46-6291068ff310.jpeg)
$ $
<b>k=6のときも本当にうまくいくの……？</b>

いやいや、さすがに計算も間違えてないしkが5まで正しい値出てるんだからk=6のときも……
$ $

![IMG_2805.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3924145/c2400dcc-e303-6d93-a810-c7879abab638.png)

<b>！？！？</b>

なんか崩れちゃいました、いったいどうしてなんででしょうか……？

## 描画が崩れたところでは何が起きてるのか
具体的に何が起きているのか考えてみましょう。
今k=6なので、a,bは0から64までを動いています。描画が崩れた部分は、$A \simeq B \simeq 60$、といったあたりでしょうか。
この時だけ特異的に値が変になりそうなところを探してみると……
![IMG_2806.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3924145/d9fa3f86-2751-b638-d7db-89d8dec29a14.jpeg)

なんだかこいつが悪そうです
$ $
$_{a+b}C_a = \frac{(a+b)!}{a!b!}$は、a,bの値が大きくなると急激に値が大きくなります。
実際、 $a=b=60$などを代入してみると、$10^{35}$ 程度の値となっています。
$ $
desmosの内部でどういう風に計算が行われているのか知らないのですが、限られたビット数であまりに大きい値を計算しようとした結果、1の位の値が変わってしまった可能性があります。（整数だけど丸め誤差的な何かが生じている？）
推測でしかないので、もし知見をお持ちの方がいらっしゃったら教えてくださいますと幸いです。

ちなみに、desmosでは要素の数が10000を超えるような配列は作ることができないので$k \geq 7$ はどのみち作れません($(2^6)^2 \leq 10000 \leq (2^7)^2$なので)

# 最後に
ということで、シェルピンスキーのギャスケットを演習形式で作り上げてもらいました！いかがだったでしょうか？
来週も、さらに高度で魅力的なdesmosの技術を引き続きお伝えする予定ですので、ぜひそちらもご覧ください！お読みいただきありがとうございました！

[^12/2kiji]:[副統括挨拶](https://www.desmos.com/calculator/7rvkcgqt68)もご覧ください！
[^yuugen]:無限回描画するのは不可能なので、図示する際は有限解の繰り返しにとどまっています。
[^2d]:[[1,2,3],[2,4,6]]みたいに、数学で言う行列やテンソルみたいに扱えるもののことです
[^fornow]:アドベントカレンダー執筆時の情報です。desmosはアプデがかなり頻繁に行われ、つい先日も[3dグラフ計算機](https://www.desmos.com/3d?lang=ja)ができたり[複素数モード](https://www.desmos.com/calculator/0nay3rvrhl)が追加されたりと新機能が次々出ていますので、もしかしたら後日できるようになっているかもしれません。期待ですね
[^pas]:三角形という名前がついているのは、以下の様に書かれることが多いからです。
　　　　　１
　　　　１　１
　　　１　２　１ 
　　１　３　３　１
　１　４　６　４　１
１　５　10　10　５　１