Tessellations from Space-Filling Curves

Year: 2025 Authors: Tis Veugen

Core claim

Node Oriented Deformation Scheme and Edge Oriented Deformation Scheme can generate valid tessellations from qualifying space-filling curves in square and hexagonal grids.

Topics

space-filling curves, Escheresque tessellations, tile deformation, square grid, hexagonal grid

Domains

fractal geometry, tiling theory, curve generation, grid geometry, mathematical art, tessellation design, pattern design, Escher-style imagery

Methods

NODS, EODS, edge-replacement method, deformation schemes, heuristic search

Media

square tiles, hexagonal tiles, triangular grids, rhombuses, deformed prototiles

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2025 Conference Proceedings

Tessellations from Space-Filling Curves

Tis Veugen

Waalre, The Netherlands; tis.veugen@gmail.com

Abstract

This paper shows that space-filling curves are an excellent source for creating Escheresque tessellations. The irregular path of the curve challenges to look more closely at artworks with such tessellations. The focus is to investigate deformation schemes of the tiles which are related to the path of the curve. The schemes discovered by Richard Hassell for a square grid are described, and adapted for a hexagonal grid.

Introduction

Since their discovery by Peano [9] in 1890, space-filling curves have been analyzed for their mathematical properties [10]. Less attention has been paid to their suitability as a framework for tessellations. In this paper, we show how a variety of space-filling curves form the basis for attractive tessellations after a limited number of generations. Two aspects play an important role. First, the path of the curve has a rather irregular pattern. A work of art with an underlying space-filling curve challenges the viewer to unravel the path, and it is less common than regular tessellations. Second, the tiles can be deformed in an Escheresque way so that they relate to the path of the curve. In general, multiple prototiles will be needed and their deformation will make them fit together.

Space-filling curves are constructed in a grid of triangles, squares, or hexagons [11]. The polygons in such a grid will be the tiles of a tessellation. Each segment of the curve is assigned to a specific tile, and hence the tessellation becomes a sequence of tiles underlying the curve. In Escheresque tessellations [1], the edges of tiles are deformed. By working in regular grids, the well-known isohedral types [8] can be applied for deforming edges. Our goal, however, is to correlate the deformed shape and/or the image of the tile with the path of the space-filling curve. Many isohedral types cannot be applied then. Fortunately, the specific path of a curve allows for special deformation schemes.

Two different categories of deformation schemes can be discerned, that we name Node Oriented Deformation Scheme (NODS) and Edge Oriented Deformation Scheme (EODS). In case of NODS, a vertex of the curve lies at the center of a tile. In case of EODS, an edge of the curve lies between two vertices of a tile, and often it will be a side of a tile. Our overview shows examples of both categories. In addition, we will also present less common types of tessellations derived from space-filling curves.

Node Oriented Deformation Scheme

In a NODS, each vertex of the curve is located at the center of a tile. Each curve segment connects the center of a tile to the center of the next tile. Two restrictions on a curve are needed for applying NODS. Firstly, each curve segment crosses a common tile side of two subsequent tiles. Secondly, all curve vertices must be different, since a tile may only be visited once.

The well-known Peano curve in the square grid is used to elaborate our deformation scheme, refer to Figure 1. The curve segments are drawn by arrows to show the path. There are three ways in which the path crosses the sides of a square: from the incoming side, the path continues straight to the opposite side (green arrow), or it turns to the adjacent side on the left (red arrow) or on the right (blue arrow). So, three prototiles suffice to generate the tessellation, because they can be rotated by multiples of 90 degrees for all four incoming sides. The deformations of the prototiles relate to each other as is illustrated in Figure 2.

341

Veugen

Figure 1: Peano curve with colored segments and deformed tiles

The prototiles in Figure 2 correspond to the curve turning right (a), going straight (b), and turning left (c). There are only two classes of deformed edges, denoted by $s$ and $t$ . Edge $s^{+}$ is a translation of edges, and edge $t^{+}$ is a mirror of edge $t$ . Prototiles (a) and (c) are mirrors of each other only if the deformation of edge $s$ is symmetric with respect to the perpendicular of the right side of the square, drawn by the red dashed line in Figure 2(b). Edges $t$ and $t^{+}$ must be center-symmetric. All these constraints about the deformation of edges must be satisfied for having a valid NODS.

(a)

(b)

(c) Figure 2: Prototiles in square grid, (a) turning right, (b) going straight, (c) turning left.

A NODS has firstly been applied by Richard Hassell in his artwork Komodo Flow II [4]. However, the description of the artwork lacks a detailed explanation. Their underlying curve is not a Peano curve, but contains square supertiles of 5 by 5 square tiles. Any space-filling curve in a square grid obeying the above two curve restrictions can be tessellated using a NODS. The rationale is that edges $s$ and $s^{\prime }$ follow the path of the curve. Edges $t$ appear only on the left side of the curve, and edges $t^{\prime }$ appear only on the right side of the curve. Thanks to center symmetry, edges $t$ (and $t^{\prime }$ ) match their siblings where the curve goes in the opposite direction.

In the same way as for the square grid a NODS can be defined for space-filling curves in a hexagonal grid. Five prototiles are needed in the proposed deformation scheme: one for going straight, two for turning left with angles of 60 degrees and 120 degrees, and similarly two for turning right. Figure 3 shows the design of the prototiles. The two prototiles for turning right are mirrors of those turning left in Figure 3(b) and (c). The deformation of edge $s$ is symmetric with respect to the perpendicular of the right side of the hexagon, drawn by the red dashed line in (a). The constraints of the edges $s$ , $s^{\prime }$ , $t$ and $t^{\prime }$ are analogous to those of the square grid above. The edges of the two prototiles turning right have type $t$ on the left side of the curve and type $t^{\prime }$ on the right side thanks to the mirroring. So, for all five prototiles holds that the edges $t$ only appear on the left side of the curve, and the edges $t^{\prime }$ only on the right side.

Any space-filling curve in a hexagonal grid obeying the above two curve restrictions can be tessellated using a NODS. An example of a tessellation using the prototiles of Figure 3 can be found in Figure 4 for the well-known Gosper curve [2].

Tessellations from Space-Filling Curves

(a)

(b)

(c)

Figure 3: Prototiles in hexagonal grid, (a) going straight, (b) turning left 60 degrees, (c) turning left 120 degrees. Figure 4: The 5 deformed fish prototiles follow the path of the Gosper curve.

Edge Oriented Deformation Scheme

An EODS relies on the construction of a space-filling curve by the edge-replacement method [2][7]. In this method each vertex of a curve lies on a tile corner. In triangular grids and square grids, a curve segment lies on the side of a tile. The generator for the curve dictates for each segment (1) whether the tile to the left or to the right of the segment is assigned to that curve segment, and (2) whether in the next iteration the segment is replaced in the forward direction of the curve or in its backward direction. In hexagonal grids a curve segment lies inside a hexagon because it skips one corner of a hexagon, see [2].

A simple example of a curve in a triangular grid is designed in Figure 5(a). The curve starts at the bottom left corner and ends at the bottom right corner. The half arrowhead indicates the assigned tile and the iteration direction. Note that subsequent assigned tiles need not have a side in common. In the example, tile 3 and tile 4 only share a corner. For drawing a continuous path of the curve by a thick line,

Veugen

one must cross the area of tile 2. Figure 5(b) shows how tessellations after 2 iterations can be combined: the curve continues from the end point of one triangle to the beginning point of the next triangle rotated by 60 degrees. A triangle can, due to the symmetry, be reflected as indicated by the large arrow under the rightmost triangle in (b). In fact, each of the 4 triangles of the generator can be reflected, yielding 16 possible generators.

(a)

(b) Figure 5: (a) Generator of triangle and (b) concatenation of 3 tessellations after 2 iterations.

Deformation of the triangle edges is limited to isohedral type IH90 [8], meaning that all 3 edges have the same center symmetric deformation. The path of the curve needs to be painted in the tiles, since there is no way to indicate it otherwise. The triangles of the example in Figure 6 are filled with a seal, with the path as an overlay. Concatenation of 6 rotated triangles gives a closed curve. Three of the triangles are reflected. Due to these reflections and also due to reflections in the generator, some of the curve edges touch each other. The white overlay of the curve slightly away from the edges illustrates that. Sometimes the curve makes a U-turn, and at some edges the curve meets itself in opposite directions.

Figure 6: Closed curve of 6 rotated triangles, filled with seals.

In the square grid, Benoit Mandelbrot discovered a space-filling curve known as Mandelbrot’s Quartet [6]. Figure 7(a) shows the generator of 5 segments, where the dark red and blue bars represent the path of the curve, starting at the left and ending at the top. Figure 7(b) shows a tessellation of 125 tiles at the third generation of the curve. The segments with blue bars iterate the curve in forward direction, those with red bars backward, which is achieved by going through the generator in reverse order. Two consecutive segments in this tessellation can have the same color or different colors. However, two consecutive segments in the same direction always have different colors, so that their tiles have only a single corner in common, and no sides. Emphasizing the path of the curve is then possible by painting the tiles appropriately, see the example in Figure 8.

Tessellations from Space-Filling Curves

(a)

(b)

Figure 7: (a) Generator of Mandelbrot’s Quartet curve, and (b) third generation tessellation. Figure 8: The mouths follow the path of the Mandelbrot’s Quartet curve.

Deforming the tile’s edges can again be done according the well-known isohedral types for a square (e.g., IH62) with the drawback that such deformations do not relate to the curve’s path. Richard Hassell developed for his artwork Coral Geckos I [5] an alternative deformation scheme that does not belong to the regular isohedral types. This scheme called EODS is shown with example deformations in Figure 9.

(a)

(b) Figure 9: EODS scheme in square grid for prototile left to the curve (a), and right to the curve (b).

The prototile in Figure 9(a) corresponds to the red tile in Figure 7(a). Its three sides with label $s$ have the same deformation. Its side with label $t$ has the same deformation as the three sides with label $t$ of the other prototile in Figure 9(b), which corresponds to the blue tile in Figure 7(a). All the deformed edges have rotational symmetry around their center, so that it does not matter from which of both tiles their

Veugen

common edge is observed. It turns out that this deformation scheme can be applied to any curve made with edge replacement in a square grid!

Furthermore, the curve in Figure 7(b) has no touching vertices, so that it meets the curve restrictions in the NODS section. Therefore, the NODS scheme can be applied to this curve as an alternative tessellation. The tiles are then shifted by half the tile side in both horizontal and vertical direction. In general, any self-avoiding curve in the square grid (see e.g., [7]) can be tessellated by the NODS scheme!

Also in a hexagonal grid an EODS can be designed for space-filling curves made by edge replacement. Figure 10 shows the two prototiles with example deformations. Edges with the same label $(r,R,t,T)$ have the same deformation.

(a)

(b) Figure 10: EODS in hexagonal grid for the prototile left to the curve (a), and right to the curve (b).

In the prototile of Figure 10(a) the curve segment runs from corner ${\mathrm{P}}_1$ to ${\mathrm{P}}_3$ , so that the prototile is located to the left of the curve. The deformed edge with label $r$ between ${\mathrm{P}}_1$ and ${\mathrm{P}}_2$ is rotated 120 degrees clockwise around ${\mathrm{P}}_2$ to become the deformed edge between ${\mathrm{P}}_2$ and ${\mathrm{P}}_3$ with label $R$ . The deformed edges with labels $t$ and $T$ are defined by the other prototile in Figure 10(b). That prototile is located to the right of the curve, since the curve segment runs from corner ${\mathrm{Q}}_1$ to ${\mathrm{Q}}_3$ . The deformed edge with label $t$ between ${\mathrm{Q}}_1$ and ${\mathrm{Q}}_2$ is rotated 120 degrees counterclockwise around ${\mathrm{Q}}_2$ to become the deformed edge between ${\mathrm{Q}}_2$ and ${\mathrm{Q}}_3$ with label $T$ .

The EODS scheme can be applied to any Gosper curve mentioned by Fukuda [2]. An example of a closed Gosper 19 curve is presented in Figure 11.

(a) Figure 11: Closed Gosper 19 curve with EODS scheme, (a) full artwork, (b) detail.

(b)

Tessellations from Space-Filling Curves

Miscellaneous Tessellations

The following tessellations are based on space-filling curves with dedicated deformed tiles.

Richard Hassell found out that the Gosper curve can also be tessellated with 3 pentagon prototiles, see Figure 12(a). In fact they are degenerated hexagons with a vertex in the middle of a long edge. He went a step further in his artwork FlowFish [3] by adding 2 vertices to each prototile, so that all deformed tiles have the same shape or are mirrors, see a sketch in Figure 12(b).

(a)

(b) Figure 12: Tessellation of Gosper curve with (a) degenerated hexagons and (b) degenerated octagons.

A constructed Hilbert curve is not suited to assigning a square tile to each segment, because that would lead to unfilled squares. Instead, the area around a curve segment can be filled by alternating a parallelogram and a triangle. Figure 13 shows a tessellation with deformed prototiles. Other curves like the Peano can also be tessellated with parallelograms and triangles, but not with a simple alternating sequence.

Figure 13: Hilbert curve, tessellated with parallelograms and triangles.

Finally, for the Gosper 13 curve we designed a tessellation with rhombuses. Fukuda [2] shows the construction of this curve with dark equilateral triangles, each attached to a curve segment. One of the two white neighbor equilateral triangles can be combined with the dark triangle to become a rhombus. The choice of the correct white triangle is based on some heuristic rules and a search algorithm. Figure 14(a) shows the triangles of the covered grid, together with the curve in red. A black triangle and a white triangle with a circle form a rhombus. Figure 14(b) shows a corresponding artwork with birds as deformed rhombuses. All edges of the rhombuses have the same deformation (IH34), with the additional constraint of center symmetry. So, all birds have the same shape, colored yellow to the right of the curve and blue to the left. The tint difference indicates whether a rhombus is made from the right or left white neighbor triangle of the black triangle. Alternatively, the deformation scheme $tsss$ and $sttt$ , explained above for square tiles, can be applied for the rhombuses. The two prototiles on the left side of the curve and the two prototiles on the right side of the curve then have four different shapes.

Veugen

(a)

(b) Figure 14: Tessellation of Gosper13 curve with rhombuses. (a) design, see text, (b) artwork.

Summary and Conclusions

We have shown in various ways that Escheresque tessellations can be made from space-filling curves. We documented two deformation schemes for the square grid which were discovered by Richard Hassell. These two schemes, named Node Oriented Deformation Scheme (NODS) and Edge Oriented Deformation Scheme (EODS), can be applied in general to space-filling curves which meet the imposed restrictions. We derived NODS and EODS schemes for tessellations of space-filling curves in a hexagonal grid. And we have discussed some tessellations that are less obvious to design.

References

[1] R. Fathauer. Tessellations: Mathematics, Art, and Recreation. CRC Press, 2021. [2] H. Fukuda, M. Shimizu, and G. Nakamura. “New Gosper Space Filling Curves.” Proceedings of the International Conference on Computer Graphics and Imaging (CGIM2001), 2001, pp. 34-38. [3] R. Hassell. “FlowFish.” Bridges Seoul 2014 Art Exhibition Catalog. https://gallery.bridgesmathart.org/exhibitions/2014-bridges-conference/richard-hassell [4] R. Hassell. “Komodo Flow II.” 2016. https://www.richardhassell.net/strange-creatures-series-gallery [5] R. Hassell. “Coral Geckos I.” 2018. https://www.richardhassell.net/onlinegallery/prosperity-puppies [6] B. Mandelbrot. The Fractal Geometry of Nature. W. H. Freeman and Company, 1977. [7] D. M. McKenna. “SquaRecurves, E-Tours, Eddies, and Frenzies: Basic Families of Peano Curves on the Square Grid.” The Lighter Side of Mathematics: Proceedings of the Eugène Strens Memorial Conference on Recreational Mathematics and its History, The Mathematical Association of America, 1994, pp. 49-73. [8] T. McLean. Isohedral Tilings. Mirror site hosted by J. Scherphuis. https://www.jaapsch.net/tilings/mclean/ [9] G. Peano. “Sur une courbe, qui remplit toute une aire plane.” Mathematische Annalen, vol. 36, 1890, pp. 157-160. [10] H. Sagan. Space-Filling Curves. Springer, 1991. [11] J. Ventrella. Brain-Filling Curves - A Fractal Bestiary. Eyebrain Books, 2012.