P3タイリングの生成

P3タイリングの生成

• HOME
• BLOG
• RSS

2026-06-28

ペイズリータイリング（Penrose tilings）を聞いたことがありますか？今日は、それらを生成するために使用できるアルゴリズムの1つを説明したいと思います。この記事が、私が考えている今後のいくつかのトピックのための必要な背景資料として役立つことを願っています。その詳細は、今は伏せておきます。

タイリング入門

そもそもタイリングとは何でしょうか？数学者は、隙間なく2次元平面を覆うパターンをすべて、2次元平面のタイリングと呼びます。例えば、チェス盤が全方向に無限に広がっていると想像してください。

［画像: image］

タイリングに現れる図形の集合をプロトタイルと呼びます。チェス盤のタイリングは、正方形という1つのプロトタイルのみを使用します。

タイリングは、平面全体をシフトしても元のパターンに戻る方法がある場合、周期的と呼ばれます。チェス盤のタイリングは周期的です。例えば、全体を右に1マスシフトすると、同じパターンになります。タイリングは、そのような並進対称性を許さない場合、非周期的と呼ばれます。

ペイズリータイリングは、2つのプロトタイルのみを使用した、平面の最初の既知の非周期的タイリングでした。これは1970年代にロジャー・ペイズリーによって発見されました。私が知る限り、P1、P2、P3として知られる3つのバリエーションがあります。P1は4つのプロトタイルを使用しますが、P2とP3は2つのみです。今日はP3に焦点を当てます。

P1

［画像: image］

P2（カイトとダーツ）

P3（ひし形）

分割ルール

以下の4つのルールからなるセットは、P3を生成するためのアルゴリズムを構成します。

［画像: image］

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)C(p, q, r)として表すことができます。これは項—構文の一部—であり、項の操作として分割ルールを表現したいのです。

［画像: image］

上記は分割ルールの再現であり、参照のためにラベルが追加されています。各分割ルールは少なくとも1つの新しい頂点を生成することに注意してください。分割によって生成される頂点は、各ルールの右辺でSSとTTとしてラベル付けされています。

ルールを項の操作として表現する場合、SSとTTを親頂点の観点から表現する方法が必要になります。ロビンソン三角形には、利用できる良い幾何学的特性があります。SSとTTは常に、φ\frac{1}{\varphi}の距離だけエッジに沿った位置にあります。ここで、φ\varphiは黄金比です。黄金比は、正五角形の対角線とその辺の比率であり、ペイズリータイリングはすべて五重回転対称性に関連しているため、ここで現れます。ppからqqへの距離の1φ\frac{1}{\varphi}だけ移動して到達する点を、p⇒qp \Rightarrow qと書きます。

それを念頭に置いて、分割ルールを項書き換えルールとして表現する準備ができました。

CC、DD、XX、YYという色記号は、項書き換え文献で「関数記号」と呼ばれるものです。これは、固定のarity（固定の入力数）を持つ名前です。分割記号 ⇒\Rightarrowと積記号 ×\timesも関数記号ですが、明確にするためにこれらを中置記法で使用することにしました。完全に形式的に行う場合、arity 2とarity 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}withζ
=eπi5 \Bigl{ \zeta^3 , \zeta^2 , \zeta , 1 \Bigr} \qquad \qquad \text{with} \qquad \qquad \zeta = e^\frac{\pi i}{5}

がP3座標空間の基底を形成することです。4つのベクトルの線形結合（整数係数付き）として、P3タイリング内の任意の点を表現できます。

これを証明するために、分割ルールの構造的帰納法によって議論します。まず、φ\varphiとφ−1\varphi^{-1}の両方がこのシステムで表現できることに注意してください。

φ
=1+ζ2−ζ31φ
=ζ2−ζ3 \varphi = 1 + \zeta^2 - \zeta^3 \qquad \qquad \frac{1}{\varphi} = \zeta^2 - \zeta^3

開始座標（つまり、外側の𝐗\textbf{X}三角形の点）は表現可能です。

P
=0Q
=1R
=ζφ P = 0 \qquad Q = 1 \qquad R = \frac{\zeta}{\varphi}

分割ルールで使用される中間点操作は、1φ\frac{1}{\varphi}による線形補間です。

p⇒q
=p+q−pφ
=p+φ−1(q−p) p \Rightarrow q = p + \frac{q - p}{\varphi} = p + \varphi^{-1} (q - p)

したがって、示す必要があるのは、スパンが加算、減算、乗算で閉じていることだけです。これらは中間点を計算するために必要な操作です。加算と減算は簡単です。コンポーネントごとに機能します。乗算は、分配すると最大次数6の項が得られるため、少し複雑です。

正十角形の交互の頂点を取り出して構築される正五角形を考えます。

［画像: image］

原点を中心とする任意の正多角形の頂点の合計はゼロになります。

1+ζ2+ζ4+ζ6+ζ8
=0 1 + \zeta^2 + \zeta^4 + \zeta^6 + \zeta^8 = 0 \qquad

ζ5
=−1\zeta^5 = -1 という事実を使用して、これを次のように書き換えることができます。

ζ4
=ζ3−ζ2+ζ−1 \zeta^4 = \zeta^3 - \zeta^2 + \zeta - 1

この恒等式（「円分多項式」と呼ばれるものに関連しています）を使用して、乗算から得られる項の次数を3にまで減らすことができます。詳細を計算するのは少し面倒ですが、私が最終的に実装したものは次のとおりです。

const phi = { a: -1, b: 1, c: 0, d: 1 };
const phiInverse = { a: -1, b: 1, c: 0, d: 0 };

// 十面体の10個の点。
const z0 = { a:  0, b:  0, c:  0, d:  1 };
const z1 = { a:  0, b:  0, c:  1, d:  0 };
const z2 = { a:  0, b:  1, c:  0, d:  0 };
const z3 = { a:  1, b:  0, c:  0, d:  0 };
const z4 = { a:  1, b: -1, c:  1, d: -1 };
const z5 = { a:  0, b:  0, c:  0, d: -1 };
const z6 = { a:  0, b:  0, c: -1, d:  0 };
const z7 = { a:  0, b: -1, c:  0, d:  0 };
const z8 = { a: -1, b:  0, c:  0, d:  0 };
const z9 = { a: -1, b:  1, c: -1, d:  1 };

function sum(x, y)
{
  return {
    a: x.a + y.a,
    b: x.b + y.b,
    c: x.c + y.c,
    d: x.d + y.d,
  };
}

function difference(x, y)
{
  return {
    a: x.a - y.a,
    b: x.b - y.b,
    c: x.c - y.c,
    d: x.d - y.d,
  };
}

function product(x, y)
{
  return {
    a: x.a * y.d + x.b * y.c + x.c * y.b + x.d * y.a + x.a * y.c + x.b * y.b + x.c * y.a,
    b: x.b * y.d + x.c * y.c + x.d * y.b - (x.a * y.c + x.b * y.b + x.c * y.a),
    c: x.c * y.d + x.d * y.c - x.a * y.a + (x.a * y.c + x.b * y.b + x.c * y.a),
    d: x.d * y.d - x.a * y.b - x.b * y.a - (x.a * y.c + x.b * y.b + x.c * y.a),
  }
}

function shorten(p)
{
  return product(phiInverse, p);
}

function midpoint(p, q)
{
  const side = difference(q, p);
  return sum(p, shorten(side));
}

リソース

ここで画像を作成するために使用したソースコードをこのページで確認できます。Simon Tatham による同じテーマに関する優れた記事が、私がこの記事を書くきっかけとなりました。Tilings Encyclopediaも有用な参考資料です。質問やコメントがあれば、私にメールしてください！