P3タイリングの生成

P3タイリングの生成 2026-06-28 ペンローズタイリングを聞いたことがありますか？今日は、それらを生成するために使用できるアルゴリズムの1つについて説明したいと思います。この記事が、私が考えているいくつかの将来のトピックのための必要な背景資料として役立つことを願っています。その詳細は、今のところ秘密にしておきます。 タイリング入門 そもそもタイリングとは何でしょうか？数学者は、隙間なく2次元平面を覆うパターンを2次元平面のタイリングと呼びます。たとえば、チェッカーボードがすべての方向に無限に広がっていると想像してください。タイリングに出現する形状のセットは、プロトタイルと呼ばれます。チェッカーボードタイリングは、正方形という1つのプロトタイルのみを使用します。 タイリングは、平面全体をシフトしても元のパターンに戻すことができる場合、周期的と呼ばれます。チェッカーボードタイリングは周期的です。たとえば、全体を1マス右にシフトすると、同一のパターンに到達できるからです。タイリングは、そのような並進対称性を許容しない場合、非周期的と呼ばれます。ペンローズタイリングは、2つのプロトタイルのみを使用して平面の非周期的タイリングとして最初に知られたものです。それらは1970年代にロジャー・ペンローズによって発見されました。私が知っている限り、P1、P2、P3として知られる3つのバリアントがあります。P1は4つのプロトタイルを使用し、P2とP3は2つのみを使用します。今日はP3に焦点を当てます。 P1 P2（カイトとダーツ） P3（ひし形） 細分化ルール 以下の4つのルールのセットが、P3を生成するアルゴリズムを構成します。私たちは、色で識別される4つの三角形を持っています。各ルールは、1つの三角形をより小さな三角形のセットに置き換える方法を説明しています。4つのうちのいずれかから開始して、ルールを再帰的に適用できます。各ラウンドの細分化により、開始三角形のより詳細なタイリングが得られます。 以下のボタンを使用して、ルールを数回実行したときに何が起こるかを確認してください。 - + これらのプロトタイルは、ペンローズが最初にP2とP3を発見した直後にそれらを発見したラファエル・ロビンソンにちなんでロビンソン三角形と名付けられました。歴史に興味がある場合は、GrünbaumとShephardによる「Tilings and Patterns」のセクション10.3を参照してください。 ロビンソン三角形がP3のひし形のように見えないことに気づいているかもしれません。さて、これらのルールは常にペアのパターンを生成することが判明しています。鋭角三角形はペアで現れ、鈍角三角形も同様です。常に基部で結合されています。（縁のタイルを除く。）したがって、細分化が完了したら、これらのペアを縫い合わせてひし形を得ることができます。上記のP3のレンダリングにおける赤いひし形は鋭角のペアであり、青いひし形は鈍角のペアです。なぜルールがこのようにペアを生成することが保証されているのでしょうか？本質的には、細分化ルールに対する構造的帰納法によってです。 項書き換えシステム 細分化ルールがアルゴリズムを構成すると主張しました。それは部分的にしか真実ではありません。ルールは画像で与えられ、コンピュータは直接画像で操作することはできません。このようなシステムを機械実行に適した形で記述するためのフレームワークがあります。それが項書き換えです。項書き換えに遭遇したことがない場合は、心配しないでください。説明しながら進めます。BaaderとNipkowによる「Term Rewriting and All That」の第1章は、理論の優れた入門書です。 ロビンソン三角形は、その色と頂点によって一意に識別されます。たとえば、上記の順序で4つの三角形の色を表すためにCC、DD、XX、YYという文字を選択するとします。この場合、頂点pp、qq、rrを持つ薄い青色の三角形は、シンボリックにC(p,q,r)と表すことができます。それは項（構文の一部）であり、項の操作として細分化ルールを表現したいのです。 上記は、参照のためにラベルが追加された細分化ルールの再現です。各細分化ルールは少なくとも1つの新しい頂点を作成することに注意してください。細分化によって作成される頂点は、各ルールの右側にあるSSとTTでラベル付けされています。ルールを項の操作として表現する場合、SSとTTを親頂点の観点から表現する方法が必要になります。 ロビンソン三角形には、利用できる優れた幾何学的特性があります。SSとTTは常に、黄金比φに対する辺に沿って1/φの距離にあります。黄金比は、正五角形の対角線とその辺の比率であるため、ここで現れます。ペンローズタイリングはすべて五重回転対称性に関係しています。ppからqqへの距離の1/φを移動した点に到達することをp⇒qと書きます。それを念頭に置いて、細分化ルールを項書き換えルールとして表現する準備ができました。 C(p,q,r) → C(q, r ⇒ q, p) × Y(r, p, r ⇒ q) D(p,q,r) → D(r ⇒ p, p, q) × X(q, r, r ⇒ p) X(p,q,r) → C(r, p ⇒ r, p ⇒ q) × X(q, r, p ⇒ q) × Y(p, p ⇒ q, p ⇒ r) Y(p,q,r) → D(q ⇒ r, r, q ⇒ p) × X(q ⇒ p, q, q ⇒ r) × Y(r, p, q ⇒ p) 色シンボルCC、DD、XX、YYは、項書き換えの文献で「関数記号」と呼ばれるものです。固定の項数（固定の入力数）を持つ名前です。分割記号⇒と積記号×も関数記号ですが、明確にするためにインフィックス形式で使用することを選択しました。完全に形式的である場合、2項および3項の積記号を別に用意する必要があります。小文字のpp、qq、rrは変数です。それらは任意の項にわたります。各ルールの左辺はパターンであり、変数に満足のいくインスタンス化が見つかるとルールを適用できます。 コードに翻訳すると、このページでP3画像を生成するために私が書いた再帰関数のようなものになるかもしれません。 function generateP3(type, p, q, r, depth) { const triangle = { type: type, depth: depth, p: p, q: q, r: r, }; if (depth > 0) { switch (type) { case "C": { const s = midpoint(r, q); triangle.y = generateP3("Y", r, p, s, depth - 1); triangle.c = generateP3("C", q, s, p, depth - 1); break; } case "D": { const s = midpoint(r, p); triangle.x = generateP3("X", q, r, s, depth - 1); triangle.d = generateP3("D", s, p, q, depth - 1); break; } case "X": { const d = midpoint(p, q); const e = midpoint(p, r); triangle.x = generateP3("X", q, r, d, depth - 1); triangle.y = generateP3("Y", p, d, e, depth - 1); triangle.c = generateP3("C", r, e, d, depth - 1); break; } case "Y": { const d = midpoint(q, p); const e = midpoint(q, r); triangle.x = generateP3("X", d, q, e, depth - 1); triangle.y = generateP3("Y", r, p, d, depth - 1); triangle.d = generateP3("D", e, r, d, depth - 1); break; } default: { console.log("Unexpected color."); break; } } } return triangle; } 座標系 巧妙な数学を使用すると、整数座標のみを使用してP3タイリングのすべての頂点を表現できます。これは、ポイントの等価性を比較したい場合に役立ちます。浮動小数点精度の問題を気にする必要がなくなります。 基本的な考え方は、集合 {ζ^3, ζ^2, ζ, 1}、ここで ζ = e^(πi/5) は、P3座標の空間の基底を形成することです。4つのベクトルの線形結合（整数係数付き）として、P3タイリング内の任意の点を表現できます。これを証明するために、細分化ルールに対する構造的帰納法で議論します。まず、φとφ^-1の両方がこのシステムで表現を持つことに注意してください。 φ = 1 + ζ^2 - ζ^3 1/φ = ζ^2 - ζ^3 開始座標（つまり、外側のX三角形の点）は表現可能です。 P = 0 Q = 1 R = ζ/φ 使用される中間点操作