Generating the P3 TilingHOMEBLOGRSSGenerating the P3 Tiling2026-06-28Have 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.
Introduction to Tilings
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)

Subdivision Rules
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.
A Term Rewriting System
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 CC, DD, XX, and YY to represent the four triangle colors in the order presented above. Then, a light blue triangle with vertices pp, qq, and rr, for example, can be represented symbolically as C(p,q,r)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 SS and TT 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 SS and TT in terms of the parent vertices. Robinson triangles have a nice geometric property we can leverage: SS and TT always lie 1φ\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⇒qp \Rightarrow q to represent the point reached by traveling 1φ\frac{1}{\varphi} of the distance from pp to qq.
With that in mind, we're ready to express the subdivision rules as term rewriting rules.

C(p,q,r)C(p, q, r)
→\rightarrow
C(q,r⇒q,p)×Y(r,p,r⇒q)C(q, r \Rightarrow q, p) \; \times \; Y(r, p, r \Rightarrow q)

D(p,q,r)D(p, q, r)
→\rightarrow
D(r⇒p,p,q)×X(q,r,r⇒p)D(r \Rightarrow p, p, q) \; \times \; X(q, r, r \Rightarrow p)

X(p,q,r)X(p, q, r)
→\rightarrow
C(r,p⇒r,p⇒q)×X(q,r,p⇒q)×Y(p,p⇒q,p⇒r)C(r, p \Rightarrow r, p \Rightarrow q) \; \times \; X(q, r, p \Rightarrow q) \; \times \; Y(p, p \Rightarrow q, p \Rightarrow r)

Y(p,q,r)Y(p, q, r)
→\rightarrow
D(q⇒r,r,q⇒p)×X(q⇒p,q,q⇒r)×Y(r,p,q⇒p)D(q \Rightarrow r, r, q \Rightarrow p) \; \times \; X(q \Rightarrow p, q, q \Rightarrow r) \; \times \; Y(r, p, q \Rightarrow p)

The color symbols CC, DD, XX, and YY 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 pp, qq, and rr 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;
}
A Coordinate System
Using some clever mathematics, we can represent all of the vertices in a P3 tiling using only integer coordinates. This will come in handy if we ever want to compare points for equality; it'll mean we don't have to worry about floating point imprecision.
The basic idea is that the set
{ζ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}

forms a basis for the space of P3 coordinates. We can represent any point in a P3 tiling as a linear combination (with integer coefficients) of those four vectors.
To prove this, we'll argue by structural induction on the subdivision rules. First, notice that both φ\varphi and φ−1\varphi^{-1} have representations in this system:
φ=1+ζ2−ζ31φ=ζ2−ζ3
\varphi = 1 + \zeta^2 - \zeta^3 \qquad \qquad \frac{1}{\varphi} = \zeta^2 - \zeta^3

The starting coordinates (i.e. the points of the outer 𝐗\textbf{X} triangle) are representable:
P=0Q=1R=ζφ
P = 0
\qquad
Q = 1
\qquad
R = \frac{\zeta}{\varphi}

The midpoint operation used in the subdivision rules is linear interpolation by 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)

So all we need to show is that the span is closed under addition, subtraction, and multiplication; those are the operations needed to compute the midpoint. Addition and subtraction are straightforward; they work component-wise. Multiplication is a bit more complicated, because distributing yields terms of up to degree six...
Consider the regular pentagon constructed by taking the alternating vertices of a regular decagon with radius one:

The vertices of any regular polygon around the origin sum to zero:
1+ζ2+ζ4+ζ6+ζ8=0
1 + \zeta^2 + \zeta^4 + \zeta^6 + \zeta^8 = 0 \qquad

Using the fact that ζ5=−1\zeta^5 = -1, we can rewrite this as
ζ4=ζ3−ζ2+ζ−1
\zeta^4 = \zeta^3 - \zeta^2 + \zeta - 1

We can use this identity, which is related to what are called "cyclotomic polynomials", to reduce the degree of the term we get from multiplication back down to three. Working out the details is a bit tedious, but here's the implementation I ended up with:
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));
}
Resources
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!
HOMEBLOGRSS

The concept of a tiling involves a pattern that completely covers a two-dimensional plane without any gaps. Tiling is characterized by its prototiles, which are the specific shapes that constitute the pattern; for a chessboard tiling, the single prototile is a square. A tiling can be periodic if the pattern exhibits translational symmetry, such as shifting the pattern to yield an identical arrangement, or aperiodic if it admits no such translational symmetry. Penrose tilings are notable as the first known aperiodic tilings of the plane utilizing only two prototiles, with variants including P1, P2, and P3, with the focus here being on P3.

The generation of P3 is governed by a set of four subdivision rules applied to initial triangles, which are termed Robinson triangles. These rules dictate how one triangle is recursively replaced by a set of smaller triangles. Structurally, these rules guarantee that the subdivision process results in pairs of acute and obtuse triangles, which can ultimately be assembled to form the rhombii characteristic of P3.

These subdivision rules are framed within the context of term rewriting systems. The geometric transformations are expressed symbolically using color symbols and specific operators, such as a splitting symbol and a product symbol, which act as function symbols. The process involves representing the structure of the triangles as symbolic terms, where vertices are denoted by variables, and the subdivision rules operate as term rewriting rules. The geometric nature of the subdivision is deeply linked to the golden ratio, phi, which arises because the resulting vertices after subdivision are related by $\phi$ or $\phi^{-1}$, reflecting the fivefold rotational symmetry inherent in Penrose tilings. The relationship governing the subdivision is expressed as a linear interpolation involving $\phi$, which dictates the positions of new vertices relative to the original edge.

To manage the geometric complexity, the vertices of the P3 tiling can be represented using a coordinate system based on the set $\{\zeta^3, \zeta^2, \zeta, 1\}$, where $\zeta$ is the fifth root of unity, $\zeta = e^{\pi i/5}$. This set forms a basis for the coordinate space of the tiling. Any point in the tiling can be expressed as an integer linear combination of these four basis vectors. The midpoint operation used in the subdivision rules is implemented through linear interpolation using the golden ratio, which simplifies coordinate management and avoids imprecision associated with floating-point numbers. This framework is supported by algebraic identities related to the structure of regular polygons, allowing for term multiplication and algebraic manipulations that reduce the complexity of the expressions arising from the subdivision rules. In essence, the generation method combines recursive geometric subdivision rules with an algebraic foundation rooted in the geometry of the golden ratio to define the coordinates of the resulting aperiodic tiling.