Plane-filling Curves on Transitive Grids

Year: 2016 Authors: Jörg Arndt; Julia Handl

Core claim

L-system-based edge-filling curves on several transitive polygonal grids can be systematically transformed into point-filling curves on related grids.

Topics

plane-filling curves, transitive grids, L-systems, self-similarity

Domains

fractal geometry, tilings and patterns, graph traversal, combinatorics, mathematical visualization, generative design, pattern formation, algorithmic art

Methods

L-system construction, grid transformation, symbol replacement rules, case-based curve search

Media

triangular grid, square grid, honeycomb grid, tri-hexagonal grid

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.

Jörg Arndt and Julia Handl, Technische Hochschule Nürnberg, Germany

Abstract

We present constructions for plane-filling curves on some of the transitive grids of the plane. Our starting point are curves on grids that traverse every edge once. These curves are converted into curves that traverse every point once.

Search for Curves Traversing all Edges once

We begin with curves that traverse all edges once and can be specified by Lindenmayer-systems as described by Prusinkiewicz and Lindenmayer [4]. An L-system is a triple $(\Omega ,A,P)$ where $\Omega$ is an alphabet, $A$ a word over $\Omega$ (called the axiom), and $P$ a set of maps from each letters $\in \Omega$ to words over $\Omega$ . An example of such a curve is the terdragon, described by Davis and Knuth [1]. It can be generated by the L-system with axiom F and maps $\mathrm{F}\mapsto \mathrm{F}+\mathrm{F}-\mathrm{F},+\mapsto +$ , and $-\mapsto -$ . The curve can be drawn by interpreting every F as “draw an edge of unit length” and every + and - as turns by respectively $+120^{\circ }$ and $-120^{\circ }$ . The terdragon is shown on the left of Figure 1, with slightly rounded corners to make its path apparent. In the limit it traverses the edges of the triangular grid shown in Figure 2 (b).

Figure 1: Two known curves on the triangular grid (left) and on the square grid (right).

Figure 2: Square grid (a), triangular grid (b), tri-hexagonal grid (c), and honeycomb grid (d).

For curves on the square grid, we must use turns by $\pm 90^{\circ }$ . The L-system with the map $\mathrm{F}\mapsto \mathrm{F}+\mathrm{F}+\mathrm{F}-\mathrm{F}-\mathrm{F}$ gives the curve on the right in Figure 2. It was described by Dekking [2].

We call the number of letters $\mathbf{F}$ in the production of itself in the L-system the order of the curve. For example, the curves just described respectively have orders 3 and 5.

We are interested in curves on the transitive grids consisting of regular convex polygons. These are grids with just one class of points modulo the translational and rotational symmetries, described by Grünbaum and Shephard [3, p. 63]. Curves that traverse all edges once do only exist if the number of edges incident to every point is even. This rules out the honeycomb grid shown in Figure 2 (d) as whenever a point is traversed, the remaining incident edge is a dead end.

Figure 3: A curve on the triangular grid, decomposed into 13 copies of itself.

About a million curves have been found, a detailed description of the search is under preparation. One previously unknown curve is shown in Figure 3. It has the L-system with map $\mathrm{F}\mapsto \mathrm{F}+\mathrm{FFF}-\mathrm{F}-\mathrm{F}+\mathrm{FF}+\mathrm{F}+\mathrm{F}-\mathrm{FF}-\mathrm{F}$ and is of order 13. The coloration makes its self-similarity apparent. The striking appearance of these curves was one motivation for this work.

Constructions for Curves Traversing all Points once Figure 4: A curve on the triangular grid (left) and two curves obtained from it, traversing all points on the honeycomb grid (middle) and the tri-hexagonal grid (right).

A rendering of a curve with map $\mathrm{F}\mapsto \mathrm{F}+\mathrm{F}-\mathrm{F}-\mathrm{F}+\mathrm{F}+\mathrm{F}-\mathrm{F}$ on the triangular grid is shown on the left of Figure 4. If the corners are rounded so that all resulting edges are of the same length, we obtain a curve that (in the limit) traverses all points of the honeycomb grid (middle). This can be achieved by replacing all $+\mathrm{F}$ by $+\mathrm{F}+\mathrm{F}$ and all $-\mathrm{F}$ by $-\mathrm{F}-\mathrm{F}$ , and using turns of $\pm 60^{\circ }$ . The curve shown at the right in Figure 4 traverses all points on the tri-hexagonal grid once. It results from rounding so that nothing of the original edges remains, or from dropping all $\mathrm{F}$ , then replacing all $+$ by $+\mathrm{F}+$ and all $-$ by $-\mathrm{F}-$ and again using turns of $\pm 60^{\circ }$ .

Figure 5: The curve on the left traverses the points of the grid on the right.

Figure 5 shows a curve traversing all points of the uniform grid consisting of triangles and dodecagons. It is obtained from the curve shown at the left in Figure 4 as follows. Replace all $+\mathrm{F}$ by X and all $-\mathrm{F}$ by Y, then replace all X by $\mathrm{F}-\mathrm{F}++++\mathrm{F}-\mathrm{F}-\mathrm{F}++++\mathrm{F}-$ and all Y by $\mathrm{F}+\mathrm{F}---\mathrm{F}+\mathrm{F}+\mathrm{F}---\mathrm{F}+$ . Here turns by $30^{\circ }$ have to be used.

The recipes given so far only work for curves with non-zero turns between all edges.

Figure 6: A curve of order 7 (left) and a curve traversing all points once obtained from it (right).

The following transformations work for curves where one third of the turns are by zero degrees. We choose the curve of order 7 with L-system $\mathrm{F}\mapsto F0F+F0F-\mathrm{F}-\mathrm{F}+\mathrm{F}$ , shown on the left of Figure 6, for the following constructions. The symbol 0 in the L-system denotes a non-turn. A curve traversing all points of the triangular grid once, shown at the right, can be obtained as follows. Drop all F, then replace all + by +F+, all - by -F-, and all 0 by F0F. Again, turns by $30^{\circ }$ are used.

Figure 7: A curve (left) traversing all points of the grid shown at the right.

The curve shown in Figure 7 is obtained by replacing all $+$ by $\mathfrak{p}$ and all - by $\mathfrak{m}$ , then all Fp by $+F++F+$ , all Fm by $--F--$ , all F0 by $+F-F-F+$ . Turns by $30^{\circ }$ have to be used.

Figure 8: A curve (left) traversing all points of the grid shown at the right.

The curve shown in Figure 8 is obtained by replacing all $\mathrm{F}+$ by $\mathrm{F}+\mathrm{F}+\mathrm{F}+\mathrm{F}+$ , all $\mathrm{F}-$ by $\mathrm{F}--\mathrm{F}--$ , and all F0 by $\mathrm{F}+\mathrm{F}+\mathrm{F}--\mathrm{F}--\mathrm{F}+\mathrm{F}+$ , and again using turns by $30^{\circ }$ .

These are just some of the constructions found. Constructions of this kind for all transitive grids consisting of regular convex polygons will be presented in a future publication.

References

[1] Chandler Davis, Donald E. Knuth: Number representations and dragon curves, in: Selected Papers on Fun and Games, CSLI Publications, pp. 571-614, (2011). [2] Michel Dekking, M. Mendes France, A. J. van der Poorten: Folds!, The Mathematical Intelligencer, vol. 4, no. 4, pp. 190-195, (December-1982). [3] Branko Grünbaum, Geoffrey C. Shephard: Tilings and Patterns, Freemann, NY, (1986). [4] P. Prusinkiewicz, A. Lindenmayer: The Algorithmic Beauty of Plants, Springer-Verlag, (1990). URL: http://algorithmicbotany.org/papers/#abop.