Creating the P3 Tiling

Date: 2026-06-28
Categories: Home | Blog | RSS

Have you ever encountered the concept of Penrose tilings?

In this post, I intend to outline a specific algorithm used to generate them. I view this piece as a foundational primer for some upcoming topics I plan to explore—though I'll keep those specific details secret under wraps for now.

Fundamental Concepts

To understand Penrose tilings, we first need to define a few mathematical terms.

Tiling of the 2D Plane: Any pattern that covers a two-dimensional surface completely, leaving no gaps and no overlaps.

Consider an infinite chessboard as a classic example. The specific shapes used to construct such a pattern are known as prototiles.

Periodic vs. Aperiodic

We can categorize tilings based on their symmetry:

1. Periodic Tilings: These possess translational symmetry. If you shift the entire plane by a certain vector, the resulting pattern is identical to the original. (e.g., shifting a chessboard by one square).
2. Aperiodic Tilings: These can be shifted admit no such translational symmetry.

Penrose tilings are historically significant because they were the first aperiodic tilings discovered that utilized only two distinct prototiles.

The Three Variants

There are three primary versions of these tilings:

---

The Subdivision Algorithm for P3

To generate the P3 variant, we employ a set of four specific rules. We begin with four types of triangles, distinguished by their colors. Each rule dictates how a single triangle is replaced by a collection of smaller triangles.

The Process

By applying these rules recursively, we can increase the complexity and detail of the tiling.

These shapes are called Robinson triangles, named after Raphael Robinson. For those interested in the academic history, I recommend checking out Tilings and Patterns by Grünbaum and Shephard (Section 10.3).

From Triangles to Rhombii

You might notice that Robinson triangles aren't rhombuses. However, the subdivision rules are designed such that triangles always appear in pairs joined at their bases (except at the very edges of the map).

• Acute pairs $\rightarrow$ Red Rhombii
• Obtuse pairs $\rightarrow$ Blue Rhombii

This relationship is guaranteed via structural induction based on the rules themselves.

---

Implementing a Term Rewriting System

Since computers cannot process pictorial rules directly, we must translate them into a formal system. I've chosen term rewriting. For a deep dive into this theory, Term Rewriting and All That by Baader and Nipkow is an excellent resource.

Formalizing the Geometry

A Robinson triangle is defined by its color and its three vertices. Let's assign the following function symbols to the colors: C, D, X, and Y.

A light blue triangle with vertices $p, q, r$ is represented as the term: C(p, q, r).

To handle the creation of new vertices ($S$ and $T$) during subdivision, we use the Golden Ratio ($\phi$). Because Penrose tilings rely on fivefold rotational symmetry, new points always appear at a distance of $1/\phi$ along an edge.

We define the operation $p \Rightarrow q$ as: $\text{The point located } \frac{1}{\phi} \text{ of the distance from } p \text{ to } q.$

The Rewriting Rules

The pictorial rules are converted into the following symbolic transformations:

• $C(p, q, r) \to C(q, r \Rightarrow q, p) \times Y(r, p, r \Rightarrow q)$
• $D(p, q, r) \to D(r \Rightarrow p, p, q) \times X(q, r, r \Rightarrow p)$
• $X(p, q, r) \to 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) \to D(q \Rightarrow r, r, q \Rightarrow p) \times X(q \Rightarrow p, q, q \Rightarrow r) \times Y(r, p, q \Rightarrow p)$

Technical Breakdown

• Function Symbols: C, D, X, Y have a fixed arity of 3.
• Infix Operators: $\Rightarrow$ and $\times$ are used for readability.
• Matching: A rule is triggered whenever a term matches the pattern on the left-hand side.

Implementation Checklist

• Define vertex coordinates.
• Implement the $\Rightarrow$ linear interpolation function.
• Create a recursive function to handle depth.
• Map the four color symbols to their respective subdivision logic.

The following JavaScript snippet demonstrates how this logic is structured:

function generateP3(type, p, q, r, depth) {
    const triangle = { 
        type: type, 
        depth: depth, 
        p: p, 
        q: q, 
        r: r 
    };

    if (depth === 0) {
        // Base case: return the triangle for rendering
        return [triangle];
    }

    // Recursive step: apply term rewriting rules
    switch (type) {
        case 'C':
            return [
                ...generateP3('C', q, interpolate(r, q), p, depth - 1),
                ...generateP3('Y', r, p, interpolate(r, q), depth - 1)
            ];
        // Other cases (D, X, Y) follow the same pattern...
    }
}