Note: This blogpost is heavily inspired from this wolfram community article.
Whether a single geometrical shape exists that can tile plane aperiodically was open problem until recently. Since discovery of hat and related shapes we know answer is affirmative. In this blog we will draw tiling of plane using hat and its reflection. Hat is a ploykite with 13 components, 3 different edge lengths and interior angles multiples of 30 degree. Using metapict library, let’s draw canonical hat and its reflection.
#lang racket
(require metapict)
(struct H-edge (turn) #:transparent)
(struct T1 H-edge () #:transparent)
(struct T2 H-edge () #:transparent)
(struct T3 H-edge () #:transparent)
(define hat
(list (T1 -1) (T1 1) (T2 4) (T2 6) (T1 3)
(T1 5) (T2 8) (T2 6) (T1 9) (T1 7)
(T2 10) (T3 12) (T2 14)))
(define flipped-hat
(list (T2 -2) (T3 0) (T2 2)
(T1 5) (T1 3) (T2 6) (T2 4) (T1 7)
(T1 9) (T2 6) (T2 8) (T1 11) (T1 1)))
(define (H-edge-length e)
(cond
[(T1? e) (sqrt 12)]
[(T2? e) 2]
[(T3? e) 4]))
(define (scan init fn lst)
(if (null? lst)
(list init)
(cons init
(scan (fn init (first lst)) fn (rest lst)))))
(define (H-edges->curve origo turn edges)
(let ([points (scan origo pt+
(map (lambda (e)
(pt@d (H-edge-length e)
(* 30 (+ turn (H-edge-turn e)))))
edges))])
(apply make-curve (append
(apply append (map (lambda (p) (list p --))
(drop-right points 1)))
(list cycle)))))
(with-window (window -7 7 -7 7) (draw (H-edges->curve (pt 0 0) 0 hat)))
(with-window (window -7 7 -7 7) (draw (H-edges->curve (pt 0 0) 0 flipped-hat)))When above code is run, it will draw shapes shown below minus grid and interior being colored blue.
Larger and larger area of plane can be tiled using substitution tiling. In case of hat tiling, substitution is given in terms of metatiles H, T, P and F. Let’s look at them and code used to draw them.
(struct M-edge (turn) #:transparent)
(struct X+ M-edge () #:transparent)
(struct X- M-edge () #:transparent)
(struct A+ M-edge () #:transparent)
(struct A- M-edge () #:transparent)
(struct B+ M-edge () #:transparent)
(struct B- M-edge () #:transparent)
(struct F+ M-edge () #:transparent)
(struct F- M-edge () #:transparent)
(struct L M-edge () #:transparent)
(define meta-H
(list (X+ 0)
(B- 1) (X- 1)
(X+ 2)
(B- 3) (X- 3)
(X+ 4)
(A+ 5) (X- 5)))
(define meta-T
(list (A- 0)
(A- 2)
(B+ 4)))
(define meta-P
(list (X+ 0) (A- 0)
( L 2) (X- 2)
(X+ 3) (B+ 3)
( L 5) (X- 5)))
(define meta-F
(list (X+ 0) (L 0) (X- 0)
(F+ 1)
(F- 2)
(X+ 3) (B+ 3)
( L 5) (X- 5)))
(define (M-edge-length e)
(cond
[(or (A+? e) (A-? e) (B+? e) (B-? e)) 12]
[else 4]))
(define (M-edges->curve origo turn edges)
(let ([points (scan origo pt+
(map (lambda (e)
(pt@d (M-edge-length e)
(* 60 (+ turn (M-edge-turn e)))))
edges))])
(apply make-curve (append
(apply append (map (lambda (p) (list p --))
(drop-right points 1)))
(list cycle)))))
(with-window (window -20 20 -20 20) (draw (M-edges->curve (pt 0 0) 0 meta-H)))
(with-window (window -20 20 -20 20) (draw (M-edges->curve (pt 0 0) 0 meta-T)))
(with-window (window -20 20 -20 20) (draw (M-edges->curve (pt 0 0) 0 meta-P)))
(with-window (window -20 20 -20 20) (draw (M-edges->curve (pt 0 0) 0 meta-F)))
Notice that there is mismatch in number between edges in picture and code. Also there are two variants, positive and negative, of edge types (X+, X- etc) except L. Why such oddities will be clear when one looks how hats are projected into these metatiles.
Edges of metatiles are deconstructed into parts and type and attribute (positive or negative) are given to them. Positive or negative label depends on whether parts of hats are bulging out or deflating in around metatile edges. Substitution rule should line up A+ and A-, B+ and B-, X+ and X- so on. This is required so that no gap remains in tiling. Next let’s look at substitution rules of metatile H, T, P and F respectively.
Since projection of hats in metatiles is not invariant under rotation but 3 metatiles are, substitution rule should also specify orientation of metatiles. In our case this orientation is specified by local origin of metatile.
Up until now all our drawing is done at origin (pt 0 0) without rotation even though our methods H-edges->curve and M-edges->curve can account for translation and rotation. To expand metatiles using substitution rule we will require translation and rotation. We wrap our canonical drawing of metatiles in p-meta structure which includes rotation turn and translation dist. Translation is not given as single vector but list of vectors each of which is given in terms of metatile edges M-edge. Idea is if we travel along these edges from origin we arrive at point which is local origin of wrapped metatile. Also notice that attributes (+ / -) of M-edge does n’t matter in translation vector as + and - of same type are always lined up. Replacing X+ with X- (or any other such pairing) or vice versa makes no difference.
(struct p-meta
(meta turn dist) #:transparent)
(define meta-H~>
(list (p-meta meta-H 0 (list (F- 1) (X+ 2) (B+ 2) (X- 1)))
(p-meta meta-H -2 (list (F- 1) (X+ 2) (B+ 2) (X- 1)))
(p-meta meta-H 0 (list (F- 1) (X+ 0) (B- 1) (X- 1)))
(p-meta meta-T 0 (list (F- 1) (X+ 2) (B+ 2) (X- 1)
(X+ 0)))
(p-meta meta-F -1 (list (F- 3) (X+ 2) (L 2) (X- 2)))
(p-meta meta-F 1 (list (F- 1) (X+ 0) (B- 1) (X- 1)
(X+ 0) (L 0) (X- 0)))
(p-meta meta-F 3 (list (F- 1) (X+ 2) (B+ 2) (X- 1)
(X+ 0) (B- 1) (X- 1) (X+ 2)
(L 2) (X- 2)))
(p-meta meta-P 2 (list (F- 1) (X+ 2) (B+ 2) (X- 1)))
(p-meta meta-P 1 (list (F- 1) (X+ 0) (L 0) (X- 0)))
(p-meta meta-P 3 (list (F- 1) (X+ 0) (B- 1) (X- 1)
(X+ 0) (B- 1) (X- 1) (X+ 2)
(L 2) (X- 2)))))Picture below shows how translation of H metatiles are calculated using M-edges. Notice that first and second H metatile has same local origin. Second H metatile (bottom one) is rotated by 120 degree clockwise (-2 * 60).
We now need to write substitute-many so that we can call it successively to get bigger and bigger substitution. To achieve this we need substitution rules for M-edges for fixing dist which is given by M-edge-reps.
(define (M-edge-reps e)
(let ([turn (M-edge-turn e)])
(cond
[(A-? e) (list (B- turn) (X- turn) (X+ (+ turn 1)))]
[(A+? e) (list (X- (+ turn 1)) (X+ turn) (B+ turn))]
[(B-? e) (list (X- (+ turn 1)) (X+ turn) (A- turn))]
[(B+? e) (list (A+ turn) (X- turn) (X+ (+ turn 1)))]
[(F-? e) (list (X+ turn) (L turn) (X- turn) (F+ (+ turn 1)))]
[(F+? e) (list (F- (+ turn 1)) (X+ turn) (L turn) (X- turn))]
[(L? e) (list (L (- turn 1)))]
[(X-? e) (list (X- (- turn 1)) (X+ turn) (L turn) (X- turn) (F+ (+ turn 1)))]
[(X+? e) (list (F- (+ turn 1)) (X+ turn) (L turn) (X- turn) (X+ (- turn 1)))])))
(define (turn-M-edge e t)
(cond
[(A-? e) (A- (+ t (M-edge-turn e)))]
[(A+? e) (A+ (+ t (M-edge-turn e)))]
[(B-? e) (B- (+ t (M-edge-turn e)))]
[(B+? e) (B+ (+ t (M-edge-turn e)))]
[(F-? e) (F- (+ t (M-edge-turn e)))]
[(F+? e) (F+ (+ t (M-edge-turn e)))]
[( L? e) ( L (+ t (M-edge-turn e)))]
[(X-? e) (X- (+ t (M-edge-turn e)))]
[(X+? e) (X+ (+ t (M-edge-turn e)))]))
(define (substitute pm)
(let ([o-turn (p-meta-turn pm)]
[o-dist (p-meta-dist pm)]
[o-meta (p-meta-meta pm)])
(map
(lambda (p) (struct-copy p-meta p
[turn (+ o-turn (p-meta-turn p))]
[dist (append (apply append (map M-edge-reps o-dist))
(map (lambda (e) (turn-M-edge e o-turn))
(p-meta-dist p)))]))
(cond
[(eq? o-meta meta-H) meta-H~>]
[(eq? o-meta meta-T) meta-T~>]
[(eq? o-meta meta-P) meta-P~>]
[(eq? o-meta meta-F) meta-F~>]))))
(define (substitute-many p-metatiles)
(apply append (map substitute p-metatiles)))
We have all machinery ready for hat tiling. Code is listed here which also includes functions to project hats into metatiles, which is not covered here.
