# Penrose Tiling Explained

August 31, 2011

Last week, I posted some obfuscated Python which generates Penrose tiling. Today, I’ll explain the basic algorithm behind that Python script, and share the non-obfuscated version.

The algorithm manipulates a list of red and blue isosceles triangles. Each red triangle has a 36° angle at its apex, while each blue triangle has a 108° angle.

In Python, we can represent such triangles as tuples of the form (color, A, B, C). For the first element, color, a value of 0 indicates a red triangle, while 1 indicates blue. The rest of the tuple gives the co-ordinates of the A, B and C vertices, expressed as complex numbers. Complex numbers work well here since they can represent any point on the 2D plane — the real component gives the x co-ordinate, while the imaginary component gives the y co-ordinate.

As you can see, we draw an outline along the sides of the triangle, but not along the base. This allows each triangle to connect with another triangle of the same color, forming the rhombus-shaped tiles that are visible in the final Penrose tiling.

Now here’s the fun part. Given a list of such triangles, we can subdivide each one to generate another triangle list. A red triangle is subdivided into two smaller triangles as follows:

The above subdivision introduces a new vertex P, located at a point along the edge AB which satisfies the golden ratio, $\frac{1 + \sqrt{5}}{2}$.

Similarly, each blue triangle is subdivided into three smaller triangles:

This subdivision introduces two new vertices: Q along the edge BA, and R along the edge BC, at points which also satisfy the golden ratio. As well, two of the resulting triangles are mirrored — I’ve drawn a highlight in the corner of each triangle to help identify which ones are mirrored and which are not.

All of the above steps can be performed using just a few lines of Python. This function accepts a list of triangles represented as tuples, subdivides each one, and returns the new triangle list:

goldenRatio = (1 + math.sqrt(5)) / 2

def subdivide(triangles):
result = []
for color, A, B, C in triangles:
if color == 0:
# Subdivide red triangle
P = A + (B - A) / goldenRatio
result += [(0, C, P, B), (1, P, C, A)]
else:
# Subdivide blue triangle
Q = B + (A - B) / goldenRatio
R = B + (C - B) / goldenRatio
result += [(1, R, C, A), (1, Q, R, B), (0, R, Q, A)]
return result


And here’s some code to actually draw the triangle list. It uses pycairo, a Python wrapper around the excellent cairo drawing library.

# Draw red triangles
for color, A, B, C in triangles:
if color == 0:
cr.move_to(A.real, A.imag)
cr.line_to(B.real, B.imag)
cr.line_to(C.real, C.imag)
cr.close_path()
cr.set_source_rgb(1.0, 0.35, 0.35)
cr.fill()

# Draw blue triangles
for color, A, B, C in triangles:
if color == 1:
cr.move_to(A.real, A.imag)
cr.line_to(B.real, B.imag)
cr.line_to(C.real, C.imag)
cr.close_path()
cr.set_source_rgb(0.4, 0.4, 1.0)
cr.fill()

# Determine line width from size of first triangle
color, A, B, C = triangles[0]
cr.set_line_width(abs(B - A) / 10.0)
cr.set_line_join(cairo.LINE_JOIN_ROUND)

# Draw outlines
for color, A, B, C in triangles:
cr.move_to(C.real, C.imag)
cr.line_to(A.real, A.imag)
cr.line_to(B.real, B.imag)
cr.set_source_rgb(0.2, 0.2, 0.2)
cr.stroke()


Using all of the above code, we can, for example, start with a single red triangle, subdivide it several times, and draw the result after each subdivision. You can see the tiling pattern begin to emerge:

You can even begin the sequence using another triangle list. Here’s some code to start with a “wheel” shape consisting of 10 red triangles:

# Create wheel of red triangles around the origin
triangles = []
for i in xrange(10):
B = cmath.rect(1, (2*i - 1) * math.pi / 10)
C = cmath.rect(1, (2*i + 1) * math.pi / 10)
if i % 2 == 0:
B, C = C, B  # Make sure to mirror every second triangle
triangles.append((0, 0j, B, C))


If we subdivide this wheel shape repeatedly, we get the following sequence of tilings. Notice that each tiling contains a lot of symmetry — both reflective and rotational symmetry around 5 different axes:

If you study either the top or bottom row of this sequence carefully, you’ll notice that for each tiling except the first, an upside-down copy appears in the tiling to the right. I’ve drawn some yellow outlines to make this more obvious. Looking at it another way: if you take any of these tilings, subdivide it twice, flip it vertically and enlarge the result, you’ve basically added another ring around the tiling. By repeating this process indefinitely, you can see how a Penrose tiling could be made to completely fill the entire plane.

Finally, here’s a (non-obfuscated) Python script which ties everything together: download penrose.py. It starts with a wheel pattern, subdivides it 10 times, and renders the enlarged, cropped result inside a 1000×1000 image.

I pieced this explanation together from various sources: mainly this page at UBC and the Wikipedia entry. Mind you, this is not the only algorithm which can generate a Penrose tiling. Another method involves projecting a 5-dimensional set of lattice points onto a 2D plane. I haven’t taken the time to fully understand that one, but it seems to open up the possibility of interesting color patterns.

I’ve been meaning to document my own Penrose tile generating python scripts, but they aren’t finished yet. You might find it simpler or more versatile if you split a rhomb in two steps. The first step splits the obtuse triangles into a single obtuse triangle (ARC in your example) and a single acute triangle (ABR). The second step splits the acute triangles as you have shown.

Not only does this make the splitting a little simpler, but if you do just one of the steps (instead of both) you will have converted a rhomb tiling into a kite and dart tiling, or vice versa.

This can be reversed as well, so an area can be tiled by starting with a small triangle and reversing the splitting process. There are only 4 ways to do expand a tile, each tile can be expanded into a larger one of the same shape, or one that is of the other type. To tile the region, take the small tile and expand it (randomly?) until the entire region is inside a single triangle, then start splitting that one triangle until it is back to the desired size. Be careful if you don’t do it randomly, you might only fill everything to one side of one of the triangle edges. This can happen for a while if doing it randomly as well, but eventually the random selections will cause the rest of the region to be filled.

When doing this, I have also found that it is helpful to stop the splitting early if the triangle about to be split is completely outside the region you are trying to fill. It saves a lot of time splitting and drawing tiles that are not going to be used anyway.

Here’s a modified version that output the darts and kites tiling instead:

def subdivide(triangles):
result = []
for color, A, B, C in triangles:
if color == 0:
# Subdivide red (sharp isosceles) (half kite) triangle
Q = A + (B – A) / goldenRatio
R = B + (C – B) / goldenRatio
result += [(1, R, Q, B), (0, Q, A, R), (0, C, A, R)]
else:
# Subdivide blue (fat isosceles) (half dart) triangle
P = C + (A – C) / goldenRatio
result += [(1, B, P, A), (0, P, C, B)]
return result

# Create wheel of red triangles around the origin
triangles = []
for i in xrange(10):
B = cmath.rect(1, (2*i – 1) * math.pi / 10)
C = cmath.rect(1, (2*i + 1) * math.pi / 10)
if i % 2 == 0:
B, C = C, B # Make sure to mirror every second triangle
triangles.append((0, B, 0j, C))