De Bruijn Tilings

Generating aperiodic rhombus tilings from grid intersections — Penrose tilings and beyond.

The de Bruijn method

In 1981, N. G. de Bruijn discovered that Penrose tilings can be constructed with a simple formula:

1. Draw N families of parallel lines at evenly spaced angles. For a Penrose tiling, N=5 gives families at 36° apart. Each family has lines at integer spacings, slightly offset so that no three lines ever meet at the same point.
2. At each intersection of two lines, the angle between the two families determines a rhombus. The rhombus edges are unit-length, perpendicular to the two crossing families. With N=5 families, only two shapes appear: a wide rhombus (72°) and a thin rhombus (36°).
3. Assemble the tiling by placing rhombi edge-to-edge, walking outward from a seed via BFS along shared grid lines. The result is a gap-free, overlap-free aperiodic tiling of the plane.

→

→

Assembly walkthrough

The key insight is that the grid lines encode all the combinatorial information needed to tile the plane. The assembly step is purely topological — no optimization or backtracking. Here is that process animated step by step:

1 Generate parallel grid lines

2 Place rhombi at each intersection

3 Find pairs that are neighbors on a joining line

4 Assign a colors to each unique shape

5 Join edges of each pair, forming a tiling

Why it works: the offset trick

Each line in family j satisfies:

Two lines from different families always intersect at exactly one point. But if three lines meet at the same point, the construction breaks — we'd get an ambiguous vertex. De Bruijn showed this can never happen if the offsets are all rational, distinct, and no two sum to an integer. The proof is elegant: at a triple intersection, certain ratios of cosines would need to be rational, but values produce only irrational ratios (or unity, which distinct offsets exclude).

Generalizations

The method generalizes beyond N=5. Any N≥3 produces a valid tiling with ⌊N/2⌋ distinct rhombus types. Higher N yields increasingly intricate patterns with higher-order rotational symmetry.

Grid types

Beyond the classic regular grid, I messed around with a few other grid constructions:

• Regular — the classic de Bruijn grid. N families of parallel lines at angles jπ/N. Produces Penrose tilings when N=5.
• Random — N completely random lines crossing the bounding box. Produces wild, asymmetric patches.
• Random-angle — N families with random orientations but regular parallel spacing within each family. A middle ground between structured and chaotic.
• Projection — projects the edges of an N-dimensional hypercube onto 2D via a random orthonormal basis. The parallel edges of the hypercube naturally form line families.

Usage

The code is at github.com/samacqua/tilings.

# Generate a classic Penrose tiling
python main.py -N 5 -B 5 -O out

# Try different grid types
python main.py -N 5 -G random -S 42 -O out/random
python main.py -N 5 -G projection -S 42 -O out/projection

# Higher-order symmetry
python main.py -N 12 -B 4 -O out/n12

Each run produces SVGs of the grid, the rhombi at intersections, and the final assembled tiling. Rhombi are colored by their smallest internal angle, giving each distinct tile shape its own color.

References

• de Bruijn, N. G. (1981). “Algebraic theory of Penrose's non-periodic tilings of the plane”
• Penrose Tiling Explained — Preshing
• De Bruijn Tilings — Adam Ponting
• MathPages: Penrose Tiles