A Penrose Tiling

Julian D. A. Wiseman

Contents: Publication history; Introduction; The code and its output; The Algorithm. Also see the PostScript program itself and the PDF file generated therefrom.

Publication history: only at www.jdawiseman.com/papers/trivia/penrose_tiling.html. Usual disclaimer and copyright terms apply.

Introduction

A Penrose tiling is described by Wikipedia as being “a nonperiodic tiling generated by an aperiodic set of prototiles named after Sir Roger Penrose”. In 1997 the author tiled his roof terrace with a Penrose tiling of rhombi, and, to guide the laying of the tiles, needed to generate a picture. The code that made the picture, somewhat tidied, is published at www.jdawiseman.com/papers/trivia/penrose_tiling.ps.

The code and its output

A PostScript program recursively generates the tiling, starting with one thin tile. The code has been used to produce a PDF file, showing the starting step and each subsequent step. Unfortunately PostScript limits the size of an array and of the stack to 2¹⁶–1 items, so the PostScript as written cannot further recurse.

The number of rhombi in each step of the recursion, expressed as Fats+Thins=Total, is 0+1=1, 2+2=4, 9+6=15, 29+19=48, 86+57=143, 248+160=408, 691+441=1132, 1890+1192=3082, 5093+3192=8285, 13599+8477=22076, and 36060+22413=58473. The output from the last of these steps should be sufficient for most practical purposes. (In the limit there are (1+√5)/2 times as many fats as thins, each of which has an area bigger by the same ratio, so the fats become (5+√5)/10 ≈ 72.36% of the area, and the thins (5–√5)/10 ≈ 27.639%.)

The Algorithm

At each recursion thin rhombi are replaced with two fats and two thins, and fat rhombi replaced with three fats and two thins. Then duplicate rhombi are removed, both to prevent purposeless growth in the size of the PDF file, and to allow an extra three recursions before hitting PostScript implementation limits. To facilitate swift finding of duplicates, the rhombi are kept in order on the stack, new non-duplicates being rolled into place. This sorting reduces run time from about O(n²) to O(n Ln[n]); and also causes the rhombi to be drawn on the page in order, top first to bottom last.

The rendering of the rhombi is done in two passes, first an execform of the fat rhombi, then an execform of the thins. It might be that, in some picture editing programs, this simplifies selection of all the rhombi of one type. The immediately following page uses the same data, but instead of rendering the outside of the rhombi, shown are small arcs within. In any event, it is not difficult to alter the PostScript program so as to change the colouration of the output.