|Main index||Other Papers index||About author|
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.
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.
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 216–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, 7+4=11, 20+10=30, 48+31=79, 126+82=208, 329+203=532, 860+536=1396, 2256+1401=3657, 5919+3667=9586, 15453+9567=25020, and 40449+25030=65479. The output from the last of these steps should be sufficient for most practical purposes.
In the limit there are (1+√5)/2 ≈ 1.618 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%.
If the sides have unit length, the thins have area Sin[36°] = √((5-√5)/8) ≈ 0.587785; and the fats have area Sin[72°] = √((5+√5)/8) ≈ 0.9510565. So the average area is ½√(25-10√5) ≈ 0.81229924. So the number of tiles is, approximately, the area in square units × 1.231.
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 and those off the page are removed, to prevent purposeless growth in the size of the PDF file, and to allow extra recursions before reaching 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 painting of the rhombi is done in two passes, first an execform of the fat rhombi, then an execform of the thins. 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 to change the colours.
|— Julian D. A. Wiseman|
March 2010 and January 2015
On 15th January 2015 an email was received from Maarten van Tol, saying that “… I wanted to create a Penrose floor in wood in my home. The floor is currently in final stages of construction, attached pics give an impression.”
Thank you for sending the report: one of the pictures is on the right.
|Main index||Top||About author|