# Penrose Kite and Dart Tilings with Haskell Diagrams

Revised version (no longer the full program in this literate Haskell)

Infinite non-periodic tessellations of Roger Penrose’s kite and dart tiles.

As part of a collaboration with Stephen Huggett, working on some mathematical properties of Penrose tilings, I recognised the need for quick renderings of tilings. I thought Haskell diagrams would be helpful here, and that turned out to be an excellent choice. Two dimensional vectors were well-suited to describing tiling operations and these are included as part of the diagrams package.

This literate Haskell uses the Haskell diagrams package to draw tilings with kites and darts. It also implements the main operations of compChoicescompChoices and decompose which are essential for constructing tilings (explained below).

Firstly, these 5 lines are needed in Haskell to use the diagrams package:

{-# LANGUAGE NoMonomorphismRestriction #-}
{-# LANGUAGE FlexibleContexts          #-}
{-# LANGUAGE TypeFamilies              #-}
import Diagrams.Prelude
import Diagrams.Backend.SVG.CmdLine

and we will also import a module for half tiles (explained later)

import HalfTile

These are the kite and dart tiles.

The red line marking here on the right hand copies, is purely to illustrate rules about how tiles can be put together for legal (non-periodic) tilings. Obviously edges can only be put together when they have the same length. If all the tiles are marked with red lines as illustrated on the right, the vertices where tiles meet must all have a red line or none must have a red line at that vertex. This prevents us from forming a simple rombus by placing a kite top at the base of a dart and thus enabling periodic tilings.

All edges are powers of the golden section $\phi$ which we write as phi.

phi::Double
phi = (1.0 + sqrt 5.0) / 2.0

So if the shorter edges are unit length, then the longer edges have length phi. We also have the interesting property of the golden section that $phi^2 = phi + 1$ and so $1/phi = phi-1$, $phi^3 = 2phi +1$ and $1/phi^2 = 2-phi$.

All angles in the figures are multiples of tt which is 36 deg or 1/10 turn. We use ttangle to express such angles (e.g 180 degrees is ttangle 5).

ttangle:: Int -> Angle Double
ttangle n = (fromIntegral (n mod 10))*^tt
where tt = 1/10 @@ turn

## Pieces

In order to implement compChoices and decompose, we need to work with half tiles. We now define these in the separately imported module HalfTile with constructors for Left Dart, Right Dart, Left Kite, Right Kite

data HalfTile rep = LD rep -- defined in HalfTile module
| RD rep
| LK rep
| RK rep

where rep is a type variable allowing for different representations. However, here, we want to use a more specific type which we will call Piece:

type Piece = HalfTile (V2 Double)

where the half tiles have a simple 2D vector representation to provide orientation and scale. The vector represents the join edge of each half tile where halves come together. The origin for a dart is the tip, and the origin for a kite is the acute angle tip (marked in the figure with a red dot).

These are the only 4 pieces we use (oriented along the x axis)

ldart,rdart,lkite,rkite:: Piece
ldart = LD unitX
rdart = RD unitX
lkite = LK (phi*^unitX)
rkite = RK (phi*^unitX)

Perhaps confusingly, we regard left and right of a dart differently from left and right of a kite when viewed from the origin. The diagram shows the left dart before the right dart and the left kite before the right kite. Thus in a complete tile, going clockwise round the origin the right dart comes before the left dart, but the left kite comes before the right kite.

When it comes to drawing pieces, for the simplest case, we just want to show the two tile edges of each piece (and not the join edge). These edges are calculated as a list of 2 new vectors, using the join edge vector v. They are ordered clockwise from the origin of each piece

pieceEdges:: Piece -> [V2 Double]
pieceEdges (LD v) = [v',v ^-^ v'] where v' = phi*^rotate (ttangle 9) v
pieceEdges (RD v) = [v',v ^-^ v'] where v' = phi*^rotate (ttangle 1) v
pieceEdges (RK v) = [v',v ^-^ v'] where v' = rotate (ttangle 9) v
pieceEdges (LK v) = [v',v ^-^ v'] where v' = rotate (ttangle 1) v

Now drawing lines for the 2 outer edges of a piece is simply

drawPiece:: Piece -> Diagram B
drawPiece = strokeLine . fromOffsets . pieceEdges

It is also useful to calculate a list of the 4 tile edges of a completed half-tile piece clockwise from the origin of the tile. (This is useful for colour filling a tile)

tileEdges:: Piece -> [V2 Double]
tileEdges (LD v) = pieceEdges (RD v) ++ map negated (reverse (pieceEdges (LD v)))
tileEdges (RD v) = tileEdges (LD v)
tileEdges (LK v) = pieceEdges (LK v) ++ map negated (reverse (pieceEdges (RK v)))
tileEdges (RK v) = tileEdges (LK v)

To fill whole tiles with colours, darts with dcol and kites with kcol we can use leftFillDK. This uses only the left pieces to identify the whole tile and ignores right pieces so that a tile is not filled twice.

leftFillDK:: Colour Double -> Colour Double -> Piece -> Diagram B
leftFillDK dcol kcol c =
case c of (LD _) -> (strokeLoop $glueLine$ fromOffsets $tileEdges c) # fc dcol (LK _) -> (strokeLoop$ glueLine $fromOffsets$ tileEdges c)
# fc kcol
_      -> mempty

To fill half tiles separately, we can use fillPiece which fills without drawing edges of a half tile.

fillPiece:: Colour Double -> Piece -> Diagram B
fillPiece col piece = drawJPiece piece # fc col # lw none

For an alternative fill operation  we can use fillDK which fills darts and kites with given colours and draws the edges with drawPiece.

fillDK:: Colour Double -> Colour Double -> Piece -> Diagram B
fillDK dcol kcol piece = drawPiece piece <> fillPiece col piece where
col = case piece of (LD _) -> dcol
(RD _) -> dcol
(LK _) -> kcol
(RK _) -> kcol


By making Pieces transformable we can reuse generic transform operations. These 4 lines of code are required to do this

type instance N (HalfTile a) = N a
type instance V (HalfTile a) = V a
instance Transformable a => Transformable (HalfTile a) where
transform t ht = fmap (transform t) ht

So we can also scale a piece  and rotate a piece by an angle. (Positive rotations are in the anticlockwise direction.)

scale:: Double -> Piece -> Piece
rotate :: Angle Double -> Piece -> Piece

## Patches

A patch is a list of located pieces (each with a 2D point)

type Patch = [Located Piece]

To turn a whole patch into a diagram using some function cd for drawing the pieces, we use

decomps pc = vsep 1 $fmap drawPatch$ take 5 $decompositionsP [pc at origin]  We have made use of the fact that we can create an infinite list of finer and finer decompositions of any patch, using: decompositionsP:: Patch -> [Patch] decompositionsP = iterate decompPatch We could get the n-fold decomposition of a patch as just the nth item in a list of decompositions. For example, here is an infinite list of decomposed versions of sun. suns = decompositionsP sun The coloured tiling shown at the beginning is simply 6 decompositions of sun displayed using leftFillDK sun6 = suns!!6 filledSun6 = patchWith (leftFillDK red blue) sun6 # lw ultraThin The earlier figure illustrating larger kites and darts emphasised from the smaller ones is also sun6 but this time drawn with experimentFig = patchWith experiment sun6 # lw thin where pieces are drawn with experiment:: Piece -> Diagram B experiment pc = emph pc <> (drawJPiece pc # dashingN [0.002,0.002] 0 # lw ultraThin) where emph pc = case pc of -- emphasise join edge of darts in red (LD v) -> (strokeLine . fromOffsets) [v] # lc red (RD v) -> (strokeLine . fromOffsets) [v] # lc red -- emphasise long edges for kites (LK v) -> (strokeLine . fromOffsets) [rotate (ttangle 1) v] (RK v) -> (strokeLine . fromOffsets) [rotate (ttangle 9) v] ## Compose Choices You might expect composition to be a kind of inverse to decomposition, but it is a bit more complicated than that. With our current representation of pieces, we can only compose single pieces. This amounts to embedding the piece into a larger piece that matches how the larger piece decomposes. There is thus a choice at each composition step as to which of several possibilities we select as the larger half-tile. We represent this choice as a list of alternatives. This list should not be confused with a patch. It only makes sense to select one of the alternatives giving a new single piece. The earlier diagram illustrating how decompositions are calculated also shows the two choices for embedding a right dart into either a right kite or a larger right dart. There will be two symmetric choices for a left dart, and three choices for left and right kites. Once again we work with located pieces to ensure the resulting larger piece contains the original in its original position in a decomposition. compChoices :: Located Piece -> [Located Piece] compChoices lp = case viewLoc lp of (p, RD vd)-> [ RD vd' at (p .+^ v') , RK vk at p ] where v' = (phi+1) *^ vd -- vd*phi^2 vd' = rotate (ttangle 9) (vd ^-^ v') vk = rotate (ttangle 1) v' (p, LD vd)-> [ LD vd' at (p .+^ v') , LK vk at p ] where v' = (phi+1) *^ vd -- vd*phi^2 vd' = rotate (ttangle 1) (vd ^-^ v') vk = rotate (ttangle 9) v' (p, RK vk)-> [ LD vk at p , LK lvk' at (p .+^ lv') , RK rvk' at (p .+^ rv') ] where lv' = phi*^rotate (ttangle 9) vk rv' = phi*^rotate (ttangle 1) vk rvk' = phi*^rotate (ttangle 7) vk lvk' = phi*^rotate (ttangle 3) vk (p, LK vk)-> [ RD vk at p , RK rvk' at (p .+^ rv') , LK lvk' at (p .+^ lv') ] where v0 = rotate (ttangle 1) vk lv' = phi*^rotate (ttangle 9) vk rv' = phi*^rotate (ttangle 1) vk rvk' = phi*^rotate (ttangle 7) vk lvk' = phi*^rotate (ttangle 3) vk As the result is a list of alternatives, we need to select one to make further composition choices. We can express all the alternatives after n steps as compNChoices n where compNChoices :: Int -> Located Piece -> [Located Piece] compNChoices 0 lp = [lp] compNChoices n lp = do lp' <- compChoices lp compNChoices (n-1) lp' This figure illustrates 5 consecutive choices for composing a left dart to produce a left kite. On the left, the finishing piece is shown with the starting piece embedded, and on the right the 5-fold decomposition of the result is shown. fiveCompChoices = hsep 1$ fmap drawPatch [[ld,lk'], multiDecomp 5 [lk']] where
-- two separate patches
ld  = (ldart at origin)
lk  = compChoices ld  !!1
rk  = compChoices lk  !!1
rk' = compChoices rk  !!2
ld' = compChoices rk' !!0
lk' = compChoices ld' !!1

Finally, at the end of this literate haskell program we choose which figure to draw as output.

fig::Diagram B
fig = filledSun6
main = mainWith fig

That’s it. But, What about composing whole patches?, I hear you ask. Unfortunately we need to answer questions like what pieces are adjacent to a piece in a patch and whether there is a corresponding other half for a piece. These cannot be done easily with our simple vector representations. We would need some form of planar graph representation, which is much more involved. That is another story.

Many thanks to Stephen Huggett for his inspirations concerning the tilings. A library version of the above code is available on GitHub

## Further reading on Penrose Tilings

As well as the Wikipedia entry Penrose Tilings I recommend two articles in Scientific American from 2005 by David Austin Penrose Tiles Talk Across Miles and Penrose Tilings Tied up in Ribbons.

There is also a very interesting article by Roger Penrose himself: Penrose R Tilings and quasi-crystals; a non-local growth problem? in Aperiodicity and Order 2, edited by Jarich M, Academic Press, 1989.