2026-06-28

Have you heard of Penrose tilings? Today, I want to describe one algorithm you can use to generate them. My hope is that this article will serve as necessary background material for some future subjects I have in mind, the details of which I'll leave in suspense for now.

What's a tiling, in the first place? Mathematicians call any pattern that covers the 2D plane with no gaps a tiling of the 2D plane. For example, imagine a chessboard extending infinitely in all directions.

The set of shapes that appear in a tiling are called its prototiles. The chessboard tiling uses only one prototile, a square.

A tiling is called periodic if there is a way of shifting the whole plane in such a way that gets you back to the pattern you started at. The chessboard tiling is periodic, because, for example, you can shift the whole thing one square to the right and arrive at an identical pattern. A tiling is called aperiodic if it admits no such translational symmetry.

Penrose tilings were the first known aperiodic tilings of the plane to use only two prototiles. They were discovered by Roger Penrose in the 1970s. There are three variants that I'm aware of, known as P1, P2, and P3. P1 uses four prototiles, while P2 and P3 use only two. We'll concentrate on P3 today.

P1

P2 (Kites and Darts)

P3 (Rhombii)

The following set of four rules constitutes an algorithm to generate P3:

We have four triangles, identified by their color. Each rule explains how to replace one triangle with a set of smaller ones. Starting from any one of the four, we can recursively apply the rules. Each round of subdivision will result in a more detailed tiling of the starting triangle. Watch what happens when you execute the rules a few times using the buttons below.

- +

These prototiles are named Robinson triangles after Raphael Robinson, who discovered them not long after Penrose first discovered P2 and P3. See section 10.3 of Tilings and Patterns by Grünbaum and Shephard, if you're interested in the history.

You may be noticing that Robinson triangles don't look like the rhombii in P3. Well, it turns out that these rules will always generate patterns of pairs. The acute triangles come in pairs, as do the obtuse ones; always joined at the base. (Except for the tiles on the rim.) So, once we're done subdividing, we can sew these pairs together to get our rhombii. The red rhombii in the rendering of P3 above are the acute pairs, and the blue rhombii are the obtuse pairs.

Why are the rules guaranteed to generate pairs in this way? Essentially, by structural induction on the subdivision rules.

I claimed the subdivision rules constitute an algorithm. That's only sort of true. The rules are given pictorally, and computers can't operate directly on pictures.

There's a framework for writing down systems like this amenable to machine execution: term rewriting. Let's see if we can express the rules as term rewriting rules. If you've not encountered term rewriting before, don't worry; I'll explain as we go. The first chapter of Term Rewriting and All That by Baader and Nipkow is a good introduction to the theory, if you want one.

A Robinson triangle is uniquely identified by its color together with its vertices. Say we choose the letters $C$, $D$, $X$, and $Y$ to represent the four triangle colors in the order presented above. Then, a light blue triangle with vertices $p$, $q$, and $r$, for example, can be represented symbolically as $C(p, q, r)$. That's a term — a piece of syntax — and we want to express the subdivision rules as manipulations of terms.

Above is a reproduction of the subdivision rules, with labels added for reference. Notice each subdivision rule creates at least one new vertex. The vertices created by subdivision are labeled $S$ and $T$ on the right hand side of each rule.

If we're going to express the rules as manipulations of terms, we'll need a way of expressing $S$ and $T$ in terms of the parent vertices. Robinson triangles have a nice geometric property we can leverage: $S$ and $T$ always lie $\frac{1}{\varphi}$ of the distance along the edge, where $\varphi$ is the golden ratio. The golden ratio shows up here because it's the ratio of a regular pentagon's diagonal to its side, and the Penrose tilings are all about fivefold rotational symmetry. We'll write $p \Rightarrow q$ to represent the point reached by traveling $\frac{1}{\varphi}$ of the distance from $p$ to $q$.

With that in mind, we're ready to express the subdivision rules as term rewriting rules.

The color symbols $C$, $D$, $X$, and $Y$ are what are called "function symbols" in the term rewriting literature: names with a fixed arity (a fixed number of inputs). The splitting symbol $\Rightarrow$ and the product symbol $\times$ are also function symbols, but I've chosen to use them in infix form for clarity. If we were being completely formal, we'd need separate product symbols for arity 2 and for arity 3.

The lowercase letters $p$, $q$, and $r$ are variables. They range over arbitrary terms. The left hand side of each rule is a pattern; the rule can be applied whenever a satisfying instantiation of the variables in it is found.

Translated into code, this might look something like the recursive function I wrote to generate the P3 images on this page:

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;
}

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

// The ten points of the decahedron.
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));
}

You can inspect this page for the source code used to produce the images here. Simon Tatham's excellent article on the same subject is part of what inspired me to write this. The Tilings Encyclopedia is also a useful reference. Please email me if you have questions or comments!