Notes on tiling
| Date | Changes |
|---|---|
| 2025-02-08 | converted to .qmd. |
| 2023-11-15 | Converted to .md. |
| 2023-02-14 | Updated. |
| 2022-04-15 | Initial draft. |
Notes on tiling
This notebook tries to draw together various threads (excuse the pun) as we expand out from making woven maps to the broader category of tiling.
The first thing to say is that tiling is an impossibly vast terrain, unless we restrict attention to specific classes to tiling. A constant theme, throughout Grünbaum and Shephard1 (hereinafter GS87) is that there are just too many possibilities to make sense of unless we restrict the focus. One strategy they adopt for this is to define various tiling properties and then examine the possibilities of tilings that have those properties.
Among the properties they are quick to emphasise is that every tile shape should be a topological disc (i.e. topologically equivalent to a circle, without holes, and not disjoint with itself). This is not a property we necessarily care about, but it is convenient to go along with GS87 and worry about that possibility later. [I suspect our interest in tiles with holes will be because we consider local tiles at several locations to be part of the ‘same’ tile so there will be some tilings we make that mathematically break this restriction.]
GS87 is pretty full-on. Kaplan2 provides a more tractable introduction, emphasizing the isohedral tilings (I’ll get to that).
More recent work that is relevant is on computational tiling theory, which although it starts in the 1980s does not appear in the otherwise encyclopedic GS87, and which really only comes into its own over two decades later (see Huson3, Delgado-Friedrichs4, Zeller et al.5). This work really has moved things along: to see just how far, take a look at the Tegula program (also here: github.com/husonlab/tegula).
Properties of tilings
Some definitions
A mathematical tiling turns out to be a GIS coverage! Thus:
"A plane tiling is a countable family of closed sets \(\mathcal{T}=\{T_1,T_2,\ldots\}\) which covers the plane without gaps or overlaps. More explicitly, the union of the sets \(T_1,T_2,\ldots\) (which are known as the tiles of \(\mathcal{T}\)) is to be the whole plane, and the interiors of the sets \(T_i\) are to be pairwise disjoint” (GS87 p16)
GS87 are careful to distinguish vertices and edges of a tiling \(\mathcal{T}\) from the corners and sides of the tiles \(T_i\) that form the tiling. Tilings in which every edge of the tiling is also a side of a tile are referred to as edge-to-edge which becomes an important constraint in some situations. The tiling below left is not edge-to-edge, but is topologically equivalent to the regular tiling by hexagons. Note that a lot of the ‘tilings’ we produce by ‘weaving’ break this restriction!
At each tiling vertex, the number of tiling edges that meet is the valence of the vertex. GS87 are interested to explore tiling properties contingent on their vertex valences. By definition two tiles meet at each tiling edge, and the number of tiles that meet at each vertex is also given by the valence.
In tilings composed of regular polygons, each vertex can be described by the number of sides of the n-gons coincident at it. For example the vertices of the tiling by squares are all \((4\cdot4\cdot4\cdot4)\) or equivalently \((4^4)\). This is termed the species of the vertex (GS87, p59). Tilings by regular polygons can be designated by listing the vertex species they include. So the regular hexagonal tiling is \((6^3)\).
Given these definitions, we can think about a number of possible tiling properties.
Tile shape
A \(k\)-hedral tiling is formed from \(k\) distinct shapes of tile (including under reflection and rotation). So, for example the arrowhead and parallelogram tilings below are monohedral.
In general, it seems like we might want tilings that are \(k\)-hedral where \(k>1\), to allow tiles to be distinguished from one another. Likely what we want is more subtle than that. After all, the arrows in the above tiling are readily distinguished from one another and could be symbolised separately with little danger of confusion.
In any case this brings us to…
Symmetry
Both tiles and tilings may have symmetries, but they are defined slightly differently.
The symmetry groups of a tile
A symmetry of a tile \(T_i\) is any transformation \(S\) of the Euclidean plane that preserves the shape and size of the tile. Technically such transformations are referred to as isometries. Five isometries are possible:
- The identity (trivially);
- Reflections in lines;
- Rotations at some specified angle around a point;
- Translations by some specified vector; and
- Glide reflections (reflection in a line followed by a translation parallel to the line).
The symmetry group of a tile \(G(T)\) is the set of isometries that preserve its shape, that is \(G(T)=\{S\in G:S(T)=T\}\). These fall into three groups:
- Those that contain no translations, but consist only of reflections and/or rotations. These will be either: \(c_n\) or, the \(n\)-fold cyclic symmetry group of rotations by \(2\pi k/n\) for \(k\in\{1\ldots n\}\); or \(d_n\) the dihedral group or order \(n\) which includes \(c_n\) and \(n\) reflections in \(n\) equally spaced lines that pass through the centre of rotation of \(c_n\).
- Those that contain translations along only one direction. These give rise to 7 frieze groups.
- Those that contain translations in more than one direction and give rise to the 17 wallpaper groups.
The wallpaper groups are fundamental to tiling and are also referred to as periodic. Any pair of the translations in the group can be used to tile the plane with a pattern.
The symmetry groups of a tiling
The symmetry group of a tiling \(G(\mathcal{T})\) is the set of symmetries under which any tile \(T_i\) is mapped onto some other tile \(T_j\). That is, a symmetry of a tiling is some isometry that permutes its tiles. In general, the symmetries of a tiling are not the same as the symmetries of its constituent tiles, but must contain some of them, i.e. \(G(\mathcal{T})\subseteq\{G(T_i) \forall T_i\in\mathcal{T}\}\). [I haven’t seen this spelled out in GS87 or elsewhere, but think it follows from the definitions.]
NOTE: need to get a better handle on what is meant by the induced symmetries of a tiling.
Isohedral tilings and transitivity groups
The symmetries of a tiling will map various tiles on to other tiles. The number of sets of tiles related to one another in this way gives rise to the concept of transitivity groups of tiles. These are the distinct sets of tiles that are mapped onto one another by the symmetries of the tiling. An isohedral tiling is one with only one transitivity group. A nice way to think of it is that the tiles in an isohedral tiling are locally indistinguishable from one another: the tiling looks the same from the perspective of any tile. An isohedral tiling is necessarily monohedral.
The concept extends naturally to \(k\)-isohedrality. It is important to realise that a tiling may be monohedral or \(m\)-hedral with \(m=1\) and \(k\)-isohedral with \(m\neq k\) and in fact that \(m\leq k\). The simple example noted in GS87 and elsewhere (see also Kaplan, p36) is shown below.
The darker coloured tiles cannot be mapped onto the paler set by any isometry hence the tiling is monohedral and \(2\)-isohedral.
Again, it seems like it might be important for cartographic purposes that tilings be \(k\)-isohedral with \(k>1\) to allow tiles to be distinguished from one another. However this is by no means clear. For example the tiling below has 4 distinguishable tiles but is isohedral.
Isogonality and isotoxality
Isogonality takes the notion of the transitivity groups of a tilings tiles and applies it instead to the vertices. So an isogonal tiling has some symmetry that maps every vertex to every other, while a \(k\)-isogonal tiling has \(k\) distinct sets of vertices under the transformations of its symmetries.
Isotoxality takes the notion and applies it to the tiling’s edges.
Neither of these notions seems likely to be as significant for our purposes as the isohedrality of a tiling.
Thoughts
It’s not at all clear what the import of any of the above might be for choosing or designing tilings suitable for multivariate mapping.
Because directionality or orientation is not a property of tilings per se given that tiles are considered identical subject to rotation, but is probably an important consideration from a cartographic symbolisation perspective, it is hard to say anything definitive. Many monohedral, isohedral tilings exist that allow for directionally distinguishable tiles given that we will impose a tiling at some chosen orientation.
The notion of periodicity in tilings, i.e., that they should have at least two linearly independent (not orthogonal) translational symmetry vectors is important. There are tilings that have no such symmetry (spiral tilings, for example) which probably hold no interest for our purposes. With respect to the implementation of the woven patterns and the current application of some elements of that code base to tiling, periodicity is central, because ‘rolling out’ a weave unit or tile unit across a map is entirely based on generating a grid of translation vectors (whether the grid is rectangular or hexagonal or ‘rhombical’). It’s hard to imagine this not being a feature of any implementation.
The Archimedean tilings
The Archimedean tilings are the 11 possible tilings by regular polygons. Since the angles at the corners of a regular polygon with \(n\) sides are \(\pi(n-2)/n\) and must sum to \(2\pi\) where they meet at a tiling vertex, we can see that the vertex species in these tilings must satisfy
\[\sum_{i=1}^k\frac{n_i-2}{n_i}=2\]
where \(k\) non-distinct polygons meet at each vertex. It can be shown that only 17 combinations of integer values of \(n\) match this constraint, including such unlikely candidates as \(\{3,7,42\}\) but only 11 of these yield tileable configurations:
(from Kaplan, p31)
Three of these are the regular tilings whose flags—or vertex-edge-tile triples—are transitive under its symmetries. The remaining 8 are semi-regular. All 11 are isogonal but not isohedral (since they are not all monohedral). Which of these are most suitable for mapping is open to conjecture. The three regular tilings (discussed below) likely required a bit more work. The others, with more than one polygon may be more immediately applicable. Even so, the two containing dodecagons, given how much larger these are than the other polygons, may have only limited use.
The three regular tilings and their possibilities
It seems limiting to focus too closely on the simplest of tilings—squares, hexagons and triangles—but even here there’s plenty to think about. Assuming that our end goal is locally readable maps where it is possible to distinguish among several symbolisations of attribute values at each location, we have to somehow ‘dissect’ the polygons in the regular tilings into distinguishable ‘subtiles’.
The square and triangle admit of such dissections into identical square or triangular subtiles. Assuming the insertion of suitable ‘insets’ or margins around each ‘major’ tile, it should be possible to symbolise reasonable numbers of attributes in distinguishable ways.
Hexagonal tiles are a bit trickier, but some careful thought shows that readable subtiles with 3, 7, 19, 37 and higher numbers are possible (and anything much above 7 seems unlikely anyway!) The 7 subtiles ‘dissection’ is identical to the subtiles used in Uber’s H3 indexing scheme, and is really just a rescaling (by \(1/\sqrt{7}\)) and rotation. 19 subtiles can be formed in the same way but with a 3-4-5-4-3 hexagon of subtiles. Introducing a ‘margin’ around each grouping could enable individual subtiles to be identified ‘indexically’.
Note that this approach leans on the idea that any periodic tiling can be considered as some dissection of one of the regular tilings. This might be a subset of tilings that we are interested in. Potentially interesting is that numerous dissections of any regular tiling are possible, including those that omit some subtiles. For example plausible hex-based subdivisisions of a hexagaonal ‘main’ tile from 8 to 19 elements are shown below. These all start from the 19 hexagon 3-4-5-4-3 subtiling and symmetrically omit a suitable number of tiles to give the desired number of elements.
Carrying this thought further, we can consider various potential dissections of the three regular tilings. For any even number of classes, a basket weave with equal numbers of strands in each direction would also be an obvious option. For any number of classes divisible by 3, triaxial weaves are similarly an obvious option. Triangle grids can only really subdivided as rhombuses otherwise orientation is liable to lead to confusion.
But a lot more options than this present themselves: after all a hexagon can be subdivided into triangles also, from which polyiamonds of various shapes and sizes can be assembled. See Polyiamond hexagon tiling. Squares can be similarly dissected by polyominoes, although in general it seems harder to do this with identical polyominoes (which might not be a problem for us!)
Anyway… the TL;DR; is that some suggested set of dissection tilings could be assembled in this way, and supported as defaults in code.
Dual tilings
It would be good to be able to make duals of tilings [UPDATE now we can, more or less… at least up to labelling]. The duals of the Archimedean tilings, the Laves tilings provide examples, many of which look interesting as possible map tilings. Note that 3 of these are the regular tilings by triangles, squares and hexagons, and that one \([3\cdot6\cdot3\cdot6]\) is the cube weave which we can already generate. All are isohedral because their dual tilings are isogonal.
(from Kaplan, p32)
The Laves tilings are also important as the basis for the 81 distinct isohedral tilings identified by GS87. I have no idea why these are the basis, although the fact they are all monohedral is obviously both a prerequisite and also (at least initially) surprising. However, since these are the dual tilings of tilings whose key property is that they have only one species of vertex, this is not actually suprising!
Many of the Laves tilings show up in the dissection of the regular tilings, as various colourings.
The regular tilings as the basis of any other tiling
Given that only two translational symmetries are required to define a tiling that covers the plane, it follows that all periodic tilings can be generated based on parallelogram shaped tiles, or equivalently on an affine-transformed square tiling. In some cases it is likely more intuitive or convenient to use a hexagonal unit (although any hexagonal tiling can also be generated based on a rhomboidal grid).
Some examples are shown below.
The 32.4.3.4 tiling and Cairo tiling (its dual)
The repeating unit of both these tilings is square. It probably makes more sense to generate a prototile consisting of complete subtiles as shown, rather than to cut the subtiles at the square unit boundaries. Note how the areas where the subtiles exceed the base unit on one side match the missing areas on the opposite side.
(see also 33434 tiles and Cairo tiles)
Under the code as it stands below some notebook examples are linked.
Note that the codebase now provides tiling.get_dual_tiling() which more or less works (up to not quite accurately relabelling the resulting new set of polygons).
Escherian tilings
This is an informal name for tiles that modify a simple base tile by replacing straight line segment edges with more complex arcs or ‘polylines’. Paying attention to the symmetries of the base tile (square, triangle or hexagon) the replacement edge can be repeated or mirrored or rotated on other edges to give a range of 81 distinct isohedral tilings based on changes in shape alone. This is essentially the technique used by Escher. A simple example is shown below based on \((4^4)\).
(see ‘wobbly-edged’ Escherian tiles)
NOTE: need to read this material more closely—have a general handle on it, but exactly how it works might be relevant to developing code, I think. See for example, Kaplan’s TactileJS.
Examples of what the code can do
Some examples are provided in the following notebooks. Some of these use the built-in tiling options, others are ‘handcrafted’.
References
Footnotes
Grünbaum B, GS Shephard, 1987. Tilings and Patterns (W. H. Freeman and Company, New York)↩︎
Kaplan CS, 2009. Introductory tiling theory for computer graphics (Morgan & Claypool, S.l.)↩︎
Huson DH, 1993. The generation and classification of tile-k-transitive tilings of the Euclidean plane, the sphere and the hyperbolic plane. Geometriae Dedicata 47(3) 269–296↩︎
Delgado-Friedrichs O, 2003. Data structures and algorithms for tilings I Theoretical Computer Science 15 (note there is no II or the promised III and IV!)↩︎
Zeller R, O Delgado-Friedrichs, DH Huson, 2021. Tegula – exploring a galaxy of two-dimensional periodic tilings. Computer Aided Geometric Design 90 102027↩︎