Penrose tile adjacency without geometry

[pcallahan]

This has been an on-going project for me that I could probably finish a lot faster if I would just concentrate, but there's no urgency. I have also been spending a lot of time working on 3D prints of Penrose tiles, which you can find here: https://www.printables.com/@PaulCallaha ... ns/1519873

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).

Screenshot 2024-09-07 at 10.49.44 AM.png (305.81 KiB) Viewed 213 times

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())

To understand the output, consider the sides of each triangle to be "short" (s), "long" (l), or "interior" (i). The interior side is the one incident to the other half of the kite or dart, and having excluded that, short and long are self-explanatory.

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')]

I haven't checked output at this scale by hand, so please let me know if you see an error. A spot check succeeds, such as the fact that kddkddk is a corner triangle and the only one with just one neighbor.

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.

Screenshot 2024-09-07 at 11.06.40 AM.png (268.22 KiB) Viewed 213 times

Each series of splits results in a new boundary that is shared by triangles at greater split depth.

[confocaloid]

[...] 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. [...]

[...] OK, one way is just to keep track of boundary tiles as three ordered lists and then stitch them together for each deflation. That clearly works, but I wonder if there is a discrete coordinate system that would make adjacency more apparent. If you maintain real coordinates of tile centers, you can look at Euclidean nearest neighbors, but that seems inelegant to me.

Similar questions arise for regular hyperbolic tilings. (Is there a discrete coordinate system to represent locations, determine adjacencies, perform rotations/reflections, count the number of steps needed to go from one tile to another tile, and so on?)

One possible approach is to choose a "viewpoint" such that the coordinates of vertices and tile centres are algebraic numbers. Each algebraic number can then be represented by several integer numbers. Natural questions about the tiling can then be answered through (exact) computations with such algebraic number coordinates.

This doesn't always work nicely (for example, if I remember right, the tiling {7,3} is hard to manipulate this way, due to "multidimensional" coordinates). For some tilings and for some choices of the "viewpoint" (for example, a vertex-focused view of the tiling {5,4} in the conformal disk model), the resulting coordinate system is reasonably simple. I did not make this into some 'finished' project, but I did convince myself that the approach actually works.

[pcallahan]

To follow up on this, I decided to construct the adjacencies while doing the deflation, using a local transformations. You might wonder (indeed I do) why I didn't do this in the first place. But I think the problem of finding the adjacencies directly from the strings was bothering me too much to solve a simpler problem. This method is easier to explain. We enumerate all possible adjacencies between kite and dart halves. There aren't that many.

• Kite halves can be adjacent along long, short, and internal sides.
• Dart halves can be adjacent along long and internal sides, but not short.
• Kite halves can be can be adjacent to dart halves along long and short sides but not internal.

When we deflate a dart half to kite and dart halves, or a kite half to a kite and a dart half, we also create new edges. This is shown in the following diagram. The highlighted triangles are adjacency along the edges created by deflation.

Screenshot 2024-09-08 at 9.24.56 PM.png (269.65 KiB) Viewed 130 times

I did not mention earlier, but there is no need to keep track of whether a triangle is flipped. The graph is 2-colorable based on whether triangles are flipped so this information is easily calculated once you've assigned the status of one triangle.

Finally, how much easier is this approach? Well, this is a 37 line Python program. There is very little ad hoc logic, since the expansion rules are represented in dictionaries.

Code: Select all

import sys

NEW_EDGE = {
  'd': [('dd', 'dk', 's')],
  'k': [('kdk', 'kk', 'i'), ('kdd', 'kdk', 's')]}

SPLIT_EDGE = {
  ('k', 'k', 'i'): [('kdd', 'kdd', 'l'), ('kk', 'kk', 's')],
  ('k', 'k', 'l'): [('kdd', 'kdd', 'i'), ('kdk', 'kdk', 'l')],          
  ('k', 'k', 's'): [('kk', 'kk', 'l')],
  ('d', 'd', 'i'): [('dk', 'dk', 'i')],
  ('d', 'd', 'l'): [('dd', 'dd', 'i'), ('dk', 'dk', 'l')],
  ('d', 'k', 's'): [('dd', 'kk', 'l')],
  ('d', 'k', 'l'): [('dd', 'kdd', 'i'), ('dk', 'kdk', 'l')]
}

def new_edge(triangle):
  return [(triangle[:-1] + t1, triangle[:-1] + t2, side)
          for t1, t2, side in NEW_EDGE[triangle[-1]]] 

def split_edge(edge):
  triangle1, triangle2, side = edge
  return [(triangle1[:-1] + t1, triangle2[:-1] + t2, split_side)
           for t1, t2, split_side in SPLIT_EDGE[(triangle1[-1], triangle2[-1], side)]] 

triangles = [sys.argv[1]]
depth = int(sys.argv[2])

edges = []
for i in range(1, depth):
  new_edges = [edge for triangle in triangles for edge in new_edge(triangle)]
  split_edges = [child_edge for edge in edges for child_edge in split_edge(edge)] 
  edges = new_edges + split_edges
  triangles = sorted(set(triangle for edge in edges for triangle in edge[:2]))

for node, neighbor, side in edges:
  print(node, neighbor, side)

Running arguments "k 5" we get these 72 edges.

Code: Select all

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

This is enough information to produce the geometric layout though I have not done it. Begin with any triangle and assign a position and orientation, including whether it is flipped. Then this information can be calculated for its neighbors depending on the type of adjacency. I am not sure if you need to handle the 7 cases separately or whether the local origin can be chosen in such a way to reduce it to 3.

[pcallahan]

Note that you can produce a symmetric layout using the same approach by initializing the starting adjacencies. E.g., if you want to start with a "sun" (five kites), you would begin with these adjacencies between the 10 kite halves, numbered 0 through 4 with - or + indicating whether each is flipped. Halves are connected within a kite by an internal edge (i) and between cyclic neighbors by a long edge (l).

Code: Select all

edges = [('0+k', '0-k', 'i'),
         ('0-k', '1+k', 'l'),
         ('1+k', '1-k', 'i'),
         ('1-k', '2+k', 'l'),
         ('2+k', '2-k', 'i'),
         ('2-k', '3+k', 'l'),
         ('3+k', '3-k', 'i'),
         ('3-k', '4+k', 'l'),
         ('4+k', '4-k', 'i'),
         ('4-k', '0+k', 'l')] 

The complete code is:

Code: Select all

import sys

NEW_EDGE = {
  'd': [('dd', 'dk', 's')],
  'k': [('kdk', 'kk', 'i'), ('kdd', 'kdk', 's')]}

SPLIT_EDGE = {
  ('k', 'k', 'i'): [('kdd', 'kdd', 'l'), ('kk', 'kk', 's')],
  ('k', 'k', 'l'): [('kdd', 'kdd', 'i'), ('kdk', 'kdk', 'l')],          
  ('k', 'k', 's'): [('kk', 'kk', 'l')],
  ('d', 'd', 'i'): [('dk', 'dk', 'i')],
  ('d', 'd', 'l'): [('dd', 'dd', 'i'), ('dk', 'dk', 'l')],
  ('d', 'k', 's'): [('dd', 'kk', 'l')],
  ('d', 'k', 'l'): [('dd', 'kdd', 'i'), ('dk', 'kdk', 'l')]
}

def new_edge(triangle):
  return [(triangle[:-1] + t1, triangle[:-1] + t2, side)
          for t1, t2, side in NEW_EDGE[triangle[-1]]] 

def split_edge(edge):
  triangle1, triangle2, side = edge
  return [(triangle1[:-1] + t1, triangle2[:-1] + t2, split_side)
           for t1, t2, split_side in SPLIT_EDGE[(triangle1[-1], triangle2[-1], side)]] 

depth = int(sys.argv[1])

edges = [('0+k', '0-k', 'i'),
         ('0-k', '1+k', 'l'),
         ('1+k', '1-k', 'i'),
         ('1-k', '2+k', 'l'),
         ('2+k', '2-k', 'i'),
         ('2-k', '3+k', 'l'),
         ('3+k', '3-k', 'i'),
         ('3-k', '4+k', 'l'),
         ('4+k', '4-k', 'i'),
         ('4-k', '0+k', 'l')] 
triangles = sorted(set(triangle for edge in edges for triangle in edge[:2]))

for i in range(1, depth):
  new_edges = [edge for triangle in triangles for edge in new_edge(triangle)]
  split_edges = [child_edge for edge in edges for child_edge in split_edge(edge)] 
  edges = new_edges + split_edges
  triangles = sorted(set(triangle for edge in edges for triangle in edge[:2]))

print("triangles")
for triangle in triangles:
  print(triangle)

print()

print("edges")
for node, neighbor, side in edges:
  print(node, neighbor, side)

The output at depth 2 includes the 30 resulting tile halves (corresponding to 10 kites and 5 darts) along with their adjacencies.

Code: Select all

triangles
0+kdd
0+kdk
0+kk
0-kdd
0-kdk
0-kk
1+kdd
1+kdk
1+kk
1-kdd
1-kdk
1-kk
2+kdd
2+kdk
2+kk
2-kdd
2-kdk
2-kk
3+kdd
3+kdk
3+kk
3-kdd
3-kdk
3-kk
4+kdd
4+kdk
4+kk
4-kdd
4-kdk
4-kk

edges
0+kdk 0+kk i
0+kdd 0+kdk s
0-kdk 0-kk i
0-kdd 0-kdk s
1+kdk 1+kk i
1+kdd 1+kdk s
1-kdk 1-kk i
1-kdd 1-kdk s
2+kdk 2+kk i
2+kdd 2+kdk s
2-kdk 2-kk i
2-kdd 2-kdk s
3+kdk 3+kk i
3+kdd 3+kdk s
3-kdk 3-kk i
3-kdd 3-kdk s
4+kdk 4+kk i
4+kdd 4+kdk s
4-kdk 4-kk i
4-kdd 4-kdk s
0+kdd 0-kdd l
0+kk 0-kk s
0-kdd 1+kdd i
0-kdk 1+kdk l
1+kdd 1-kdd l
1+kk 1-kk s
1-kdd 2+kdd i
1-kdk 2+kdk l
2+kdd 2-kdd l
2+kk 2-kk s
2-kdd 3+kdd i
2-kdk 3+kdk l
3+kdd 3-kdd l
3+kk 3-kk s
3-kdd 4+kdd i
3-kdk 4+kdk l
4+kdd 4-kdd l
4+kk 4-kk s
4-kdd 0+kdd i
4-kdk 0+kdk l

I have not checked this by hand, so I hope there's no bug. The next step will be laying them out based on adjacencies.