この記事はSESSIONS Advent Calendar 2024、１４日目の記事です。 adventar.org
前回、SESSIONS 2024参加記事を書きましたので、そちらもよろしければ。
今回は私が投稿した作品、Golden Hex Blinkerで使用されている、Golden Hex置換ルールについてより詳しく解説します。
この図は三角形、平行四辺形、台形で敷き詰められています。 下図は色を塗り直した図です。もともと、この図は三角形を各図形で敷き詰めた図になっており、赤の三角形、緑の平行四辺形、水色と青の台形で構成されていることがわかります。
この図は置換タイリングとよばれる手法でタイル張りをしました。
置換タイリングでは、ある入力タイルに対して、それを置き換えるタイルの組が決められています。 それらの置き換えを再帰的に行っていくことで、タイル張りができます。そして今回、私が使用したのがGolden Hex置換ルールとよばれるものです。
さっそくそのルールについてみていきましょう。 Golden Hexの入力タイルは４つあります。それぞれ、正三角形T、２辺の比率が黄金比の平行四辺形PD、同様に、２辺の比率が黄金比の等脚台形ZD,、ZTです。（ZD、ZTは合同な図形で、それぞれ異なる置換ルールをもちます。）
これらの４種類のタイルで上図の三角形のタイル張りが構成されていることが確認できるはずです。 そして、それぞれのタイルに対する置換ルールは次のようなっています。
さて、置換ルールがわかったところで、実際に描画するためには、分割された各図形の内分点を求める必要が出てきます。初歩的な平面幾何学の問題ですが、私はこれにちょっと時間をかけてしまいました……適当な辺を未知数として、適当な補助線を引いて方程式を立てれば求めることができます。また、TとPZの内分点がわかれば、台形ZD, ZTは簡単に求められます。よくみるとPZの上にTが乗っかっている形であることがわかると思います。 実際に算出した値についてはソースコードを参照ください。
内分点がわかれば、これらの置換ルールをＴ，ＰＤ、ＺＤ、ＺＴの順に適用させ、タイルの座標を計算することができます。置換によって得られるタイル張りは以下のようになります。
この置換プロセスは無限に行うことができますが、数回行えば十分な見た目なタイル張りができます。さらに、この三角形を各辺による鏡映でうつしてやれば平面全体を敷き詰めることができるでしょう。
非周期モノタイルとの関連について
最後に簡単に表題の非周期モノタイルとの関連について触れます。今回私がこのタイル張り題材に選んだのは、最近非周期モノタイルについて調べているからです。
正方形や正三角形といった図形は一定の規則にそって敷き詰めることで、平面全体を隙間も重なりもなく敷き詰めることができるというのは簡単にわかるかと思います。それでは、非周期的にしか敷き詰められない図形というのは存在するのでしょうか。この非周期にしか並べられないタイルを見つけるというのは、大きな関心を持たれている問題でした。
非周期的なタイル張りとして最も有名なものはペンローズタイリングかと思います。このペンローズタイリングは２種類のタイルを組み合わせることで非周期的なタイル張りを実現できます。
Shadertoyにもいくつか実装がありました。
それでは１種類のタイルではどうでしょうか？この非周期モノタイルが存在しているのかどうかが未解決な問題として長い間研究され続けていました。 しかし、昨年、2023年の初め頃にこのタイルが見つかったと話題になったのです。
今回の記事のゴールデンヘックス置換ルールは非周期モノタイルが平面充填できることを証明するための一助となります。 非周期モノタイルの一種であるスミス亀タイルと呼ばれるタイル張りにはGolden Hexに近いパターンが出てきます。 それがS.Akiyama, Yoshiaki Araki (2023) An Alternative Proof for An Aperiodic Monotile,より引用した以下の図です。
先のGolden Hex置換ルールの各タイルがスミス亀タイルの塊になっており、その境界線はデコボコとしています。しかし、置換の回数が増えるごとに、そのタイルの境界線は直線へと近似されていきます。そのため、著者らはこれを近似Golden Hexルールと呼んでいます。この近似Golden Hexの「頂点地図」とよばれる概念を用いることで、スミス亀タイルが平面を充填することができることを証明しています。
非周期モノタイルの置換ルールについては少々複雑で、私はまだ描画するに至っていません。そこで、描画のとっかかりとしてGolden Hexによる置換タイリングを描画することにしました。 非周期モノタイルのタイリングの中にはフラクタル状の境界線を見て取れるものもあり、非常に興味深いです。後々はそれらの図を描画したいと考えています。
最後に参考としたリソースを紹介しておきます。
周期的なタイリングからペンローズタイル、非周期モノタイルまで、タイリング関連の話題を幅広く扱っています。非周期モノタイルに興味が湧いたのであれば、ひとまずこの書籍を読むことをお勧めします。Golden Hex置換ルールについても記載があります。 そして、より深い内容が知りたくなった場合は上記のサイトにある各種の参考文献などをあたるのもよいと思います。
この論文でGolden Hex置換ルール、近似Golden Hex置換ルールが導出されました。非周期モノタイルの非周期性や平面充填可能性をよりエレガントな手法で証明したという論文です。
