A little over two years ago, I got interested in generating pictures of Penrose kite and dart tilings. I followed the standard deflation rules and used floating point matrix transformations to place the tiles. This is the kind of thing that has always gotten on my nerves: using floating point for an intrinsically discrete problem. It's true that you need geometry to place and render the tiles, but you don't need it to find their adjacencies.

One thing I noticed along the way is how easy it is to understand both deflation and consequences such as the relation to Fibonacci numbers by looking at ways to split a 36°-72°-72° triangle ("kite half") or a 72°-72°-108° triangle ("dart half") into two smaller triangles, one of each kind. To turn this into a deflation rule, you only have to note that the dart half that results from the kite half split must be split one more time to get a kite and a dart half, each at the appropriate scale.

This shows the progression and how to label these triangles based on the starting point (k for kite half) and which side of the split we chose (which could be d for dart half). Note that because a kite half needs to be split twice to reduce scale uniformly, these strings are not all the same length. The path from a kite half to a dart half (kd) results in a dart half at the same scale, so a kite half must be split into kk, kdd, and kdk, while a dart half is split into dd and dk.

It's very easy to write recursive code to come up with all the labels of these triangles at a given scale. It is harder to keep track of the adjacency. A split at a high level results in a long boundary along which many adjacencies lie. Instead of keeping track of adjacency (though I may work on that next) I solved the more challenging problem of how to find the neighbors adjacent to a triangle given just its label. I was tempted to wait until I had a convincing writeup, but I will just supply some Python code instead.

Code: Select all

```
import sys
LONG = 'l'
SHORT = 's'
INTERNAL = 'i'
DD = {LONG: INTERNAL, SHORT: LONG}
DK = {LONG: LONG, INTERNAL: INTERNAL}
KD = {LONG: LONG, INTERNAL: SHORT}
KK = {SHORT: LONG, INTERNAL: SHORT}
DART = 'd'
KITE = 'k'
MATCHED_FINAL = [('dk', 'dd'), ('dkk', 'ddd')]
MATCHED_INSIDE = [('kk', 'kdk'), ('dkkd', 'ddd')]
TRANSITIONS = sorted(set(x for pair in MATCHED_FINAL + MATCHED_INSIDE for x in pair),
key = lambda x: -len(x))
def to_bimap(pairs):
return{k: v for k, v in pairs + [(v, k) for k, v in pairs]}
TO_MATCH_FINAL = to_bimap(MATCHED_FINAL)
TO_MATCH_INSIDE = to_bimap(MATCHED_INSIDE)
def find_transition(s):
for transition in TRANSITIONS:
if s.startswith(transition):
matched = TO_MATCH_FINAL[transition] if s == 'ddd' else TO_MATCH_INSIDE.get(transition,
TO_MATCH_FINAL.get(transition))
return (transition, matched)
return None
def adjacent(s, i):
transition, matched = find_transition(s[i:])
return s[:i] + matched + s[i + len(transition):]
def neighbors(path):
return {k: adjacent(path, v) for k, v in backtrack_path(path).items()}
def invert(mapping):
return {v: k for (k, v) in mapping.items()}
INVERSE_MAPPINGS = {
'd': {
'd': invert(DD),
'k': invert(KD)
},
'k': {
'd': invert(DK),
'k': invert(KK)
}
}
def compose(map1, map2):
return {k: map2[v] for (k, v) in map1.items() if v in map2}
def backtrack_path(path):
path_len = len(path)
reverse_path = path[::-1]
mapping = {'l': 'l', 's': 's', 'i': 'i'}
positions = {}
last_c = reverse_path[0]
for i in range(1, path_len):
c = reverse_path[i]
old_mapping = mapping
mapping = compose(mapping, INVERSE_MAPPINGS[last_c][c])
removed = set(old_mapping).difference(mapping)
if removed:
(side,) = removed
positions[side] = path_len -1 - i
last_c = c
return positions
def traverse(node, seen):
if node not in seen:
seen.add(node)
sides = neighbors(node)
print(node, sorted((k, v) for k, v in sides.items()))
for k in sorted(sides):
traverse(sides[k], seen)
path = sys.argv[1]
traverse(path, set())
```

Because this code does a marking traversal with adjacency, it does not have to carry out a hierarchical split at all. Starting with

*kdkkkdk*from the picture above, we can expand into the full graph of 55 triangles and their adjacency. Use kdkkkdk as the argument.

Code: Select all

```
kdkkkdk [('i', 'kdkkkk'), ('l', 'kkkkdk'), ('s', 'kdkkkdd')]
kdkkkk [('i', 'kdkkkdk'), ('l', 'kdkdkkk'), ('s', 'kdkkdkk')]
kdkdkkk [('i', 'kdkdkkdk'), ('l', 'kdkkkk'), ('s', 'kdkdkdkk')]
kdkdkkdk [('i', 'kdkdkkk'), ('l', 'kdkdddk'), ('s', 'kdkdkkdd')]
kdkdddk [('i', 'kkdddk'), ('l', 'kdkdkkdk'), ('s', 'kdkdddd')]
kkdddk [('i', 'kdkdddk'), ('l', 'kkdkkdk'), ('s', 'kkdddd')]
kkdkkdk [('i', 'kkdkkk'), ('l', 'kkdddk'), ('s', 'kkdkkdd')]
kkdkkk [('i', 'kkdkkdk'), ('l', 'kkkkk'), ('s', 'kkdkdkk')]
kkkkk [('i', 'kkkkdk'), ('l', 'kkdkkk'), ('s', 'kkkdkk')]
kkkkdk [('i', 'kkkkk'), ('l', 'kdkkkdk'), ('s', 'kkkkdd')]
kkkkdd [('i', 'kdkkkdd'), ('l', 'kkkdkdd'), ('s', 'kkkkdk')]
kdkkkdd [('i', 'kkkkdd'), ('l', 'kdkkdkdd'), ('s', 'kdkkkdk')]
kdkkdkdd [('i', 'kdddkdd'), ('l', 'kdkkkdd'), ('s', 'kdkkdkdk')]
kdddkdd [('i', 'kdkkdkdd'), ('s', 'kdddkdk')]
kdddkdk [('i', 'kdddkk'), ('l', 'kdkkdkdk'), ('s', 'kdddkdd')]
kdddkk [('i', 'kdddkdk'), ('l', 'kddddd')]
kddddd [('i', 'kddkkdd'), ('l', 'kdddkk'), ('s', 'kddddk')]
kddkkdd [('i', 'kddddd'), ('l', 'kddkdkdd'), ('s', 'kddkkdk')]
kddkdkdd [('l', 'kddkkdd'), ('s', 'kddkdkdk')]
kddkdkdk [('i', 'kddkdkk'), ('s', 'kddkdkdd')]
kddkdkk [('i', 'kddkdkdk'), ('l', 'kddkddd'), ('s', 'kddkkk')]
kddkddd [('l', 'kddkdkk'), ('s', 'kddkddk')]
kddkddk [('s', 'kddkddd')]
kddkkk [('i', 'kddkkdk'), ('s', 'kddkdkk')]
kddkkdk [('i', 'kddkkk'), ('l', 'kddddk'), ('s', 'kddkkdd')]
kddddk [('i', 'kdkkddk'), ('l', 'kddkkdk'), ('s', 'kddddd')]
kdkkddk [('i', 'kddddk'), ('l', 'kdkdkddk'), ('s', 'kdkkddd')]
kdkdkddk [('l', 'kdkkddk'), ('s', 'kdkdkddd')]
kdkdkddd [('i', 'kdkkddd'), ('l', 'kdkdkdkk'), ('s', 'kdkdkddk')]
kdkkddd [('i', 'kdkdkddd'), ('l', 'kdkkdkk'), ('s', 'kdkkddk')]
kdkkdkk [('i', 'kdkkdkdk'), ('l', 'kdkkddd'), ('s', 'kdkkkk')]
kdkkdkdk [('i', 'kdkkdkk'), ('l', 'kdddkdk'), ('s', 'kdkkdkdd')]
kdkdkdkk [('i', 'kdkdkdkdk'), ('l', 'kdkdkddd'), ('s', 'kdkdkkk')]
kdkdkdkdk [('i', 'kdkdkdkk'), ('s', 'kdkdkdkdd')]
kdkdkdkdd [('l', 'kdkdkkdd'), ('s', 'kdkdkdkdk')]
kdkdkkdd [('i', 'kdkdddd'), ('l', 'kdkdkdkdd'), ('s', 'kdkdkkdk')]
kdkdddd [('i', 'kdkdkkdd'), ('l', 'kdkddkk'), ('s', 'kdkdddk')]
kdkddkk [('i', 'kdkddkdk'), ('l', 'kdkdddd')]
kdkddkdk [('i', 'kdkddkk'), ('l', 'kkddkdk'), ('s', 'kdkddkdd')]
kkddkdk [('i', 'kkddkk'), ('l', 'kdkddkdk'), ('s', 'kkddkdd')]
kkddkk [('i', 'kkddkdk'), ('l', 'kkdddd')]
kkdddd [('i', 'kkdkkdd'), ('l', 'kkddkk'), ('s', 'kkdddk')]
kkdkkdd [('i', 'kkdddd'), ('l', 'kkdkdkdd'), ('s', 'kkdkkdk')]
kkdkdkdd [('l', 'kkdkkdd'), ('s', 'kkdkdkdk')]
kkdkdkdk [('i', 'kkdkdkk'), ('s', 'kkdkdkdd')]
kkdkdkk [('i', 'kkdkdkdk'), ('l', 'kkdkddd'), ('s', 'kkdkkk')]
kkdkddd [('i', 'kkkddd'), ('l', 'kkdkdkk'), ('s', 'kkdkddk')]
kkkddd [('i', 'kkdkddd'), ('l', 'kkkdkk'), ('s', 'kkkddk')]
kkkdkk [('i', 'kkkdkdk'), ('l', 'kkkddd'), ('s', 'kkkkk')]
kkkdkdk [('i', 'kkkdkk'), ('s', 'kkkdkdd')]
kkkdkdd [('l', 'kkkkdd'), ('s', 'kkkdkdk')]
kkkddk [('l', 'kkdkddk'), ('s', 'kkkddd')]
kkdkddk [('l', 'kkkddk'), ('s', 'kkdkddd')]
kkddkdd [('i', 'kdkddkdd'), ('s', 'kkddkdk')]
kdkddkdd [('i', 'kkddkdd'), ('s', 'kdkddkdk')]
```

Here's one more figure that I'll include without much explanation. It is intended to show how long, short, and interior sides are rearranged with each split and how to match up triangles on boundaries. Each series of splits results in a new boundary that is shared by triangles at greater split depth.