The Looping Theorem in 2D and 3D Turtle Geometry

Year: 2023 Authors: Tom Verhoeff

Core claim

For repeated turtle programs, closed and proper behavior can be characterized by total turning in 2D and screw-motion structure in 3D.

Topics

turtle geometry, looping theorems, rotational symmetry, screw motions

Domains

geometry, group-like transformations, quaternions, geometric algebra, mathematical art, generative patterning, symmetry design

Methods

theorem generalization, case analysis, screw decomposition, quaternion multiplication

Media

virtual turtle programs, 2D paths, 3D paths, supplementary illustrations

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 2023 Conference Proceedings

The Looping Theorem in 2D and 3D Turtle Geometry

Tom Verhoeff

Department of Mathematics and Computer Science, Eindhoven University of Technology, Netherlands; T.Verhoeff@tue.nl

Abstract

In their book Turtle Geometry, Abelson and diSessa formulate and prove the POLY Closing Theorem, which gives an exact condition for when a path produced by the POLY program closes (initial and final turtle position are equal) properly (initial and final turtle heading are equal). The POLY program repeats a translation (Move command) followed by a rotation (Turn command). Their Looping Lemma states that any repeated turtle program is rotation-symmetry equivalent to a POLY program. The POLY Closing Theorem and Looping Lemma are useful in understanding and creating artistic motifs because repeating the same turtle program so that it closes properly, leads to a rotationally symmetric path. In this article, we generalize their result to 3D. A surprising corollary is that when repeating a non-closed non-proper turtle program, its path is closed if and only if it is proper.

Introduction

In Turtle Geometry [6][1], you command a (virtual) turtle to draw a path. A sequence of turtle commands is also known as a turtle program, and it is way of defining a path. During execution of a turtle program, the turtle has a state, defined by its position (a point) and its attitude, both of which can change over time. In 2D, the attitude is fully determined by the turtle’s heading (a unit vector), but in 3D [8], there is additionally the turtle’s normal (a unit vector, perpendicular to its heading, defining its relative up direction). For state $s$, we denote its position by $s.pos$ and its attitude by $s.att$. Our turtle obeys these commands:

• $Move(d)$: move distance $d$ forward in the direction of the current heading, changing only its position;
• $Turn(\phi )$: turn (yaw) clockwise by angle $\phi$ (about its current position/normal), changing only its heading;
• $Roll(\psi )$: roll clockwise about the current heading by angle $\psi$, changing only its normal (in 3D).

In the default initial state $I$, the turtle is positioned at the origin, with its heading along the positive X-axis and its normal along the positive Z-axis. The final state after executing turtle program $P$ will be denoted by $F(P)$. For turtle program $P$, we define:

• $P$ is closed when $F(P).pos=I.pos$;
• $P$ is proper when $F(P).att=I.att$;
• $P$ is properly closed when $F(P)=I$, i.e., when $P$ is closed and proper.

Note that in [1], the term closed is used for what we call properly closed.

Looping Theorem in 2D

In [1], turtle program POLY is defined by $(Move(d);Turn(\varphi ){)}^{\ast }$ using our notation, where the superscript * indicates unbounded repetition. POLY has two parameters: a fixed distance $d$ and a fixed angle $\varphi$. We now rephrase some theorems from [1, §1.2, §1.3]:

Closed-Path Theorem The total turning along any properly closed path is a multiple of $360^{\circ }$.

Proof: By definition, along any proper path (even non-closed) the total turning modulo $360^{\circ }$ equals 0.

Verhoeff

Simple-Closed-Path Theorem The total turning in a simple (i.e., without self intersection) properly closed path is $\pm 360^{\circ }$ .

POLY Closing Theorem A path drawn by the POLY program with $d=0$ or $\varphi \mathrm{mod}360^{\circ }\ne 0$ will close properly if and only if the total turning reaches a multiple of $360^{\circ }$ .

In [1], the authors prove this theorem in three ways, which are also explored in the book review [5].

Looping Lemma Any turtle program that is an unbounded repetition of a sequence of turtle commands, has precisely the structure of the POLY program for appropriate parameter values $d$ and $\varphi$ .

Note however that repeating an arbitrary turtle program need not produce a mirror symmetric path, whereas a closed POLY program does. So, the theorem is about rotational symmetry only.

It is insightful to generalize the POLY Closing Theorem to the repetition of an arbitrary program. We denote the total turning of $P$ by $\Theta (P)$ . Then $\Theta (P)$ taken modulo $360^{\circ }$ equals the angle between the initial and final heading after executing $P$ . Consider the turtle program $P$ and its $k$ -fold repetition $P^k$ , where $P^0$ is the empty program with $F(P^0)=I$ . We now have that $\Theta (P^k)=k\Theta (P)$ .

2D Looping Theorem The properties of $P$ being closed and being proper transfer to $P^k$ as follows.

${}^a$ In these cases, $P^k$ stays within a disk or annulus as $k\to \infty$ . ${}^b$ In this case, $P^k$ stays inside a strip and wanders off to infinity as $k\to \infty$ .

The supplementary material provides illustrations for each case. The key observations for the proof are:

• If $P$ is proper, then the final state of $P$ can be obtained from the initial state by a translation along the vector from initial to final position.
• If $P$ is not proper, then the final state can be obtained from the initial state by a rotation about some center $C$ by the angle $\theta =\Theta (P)\mathrm{mod}360^{\circ }$ . If $P$ is closed, that center is at the initial (and final) position, and otherwise it can be constructed, as illustrated in Fig. 1, from the fact that the rotation angle $\theta =\angle ICF$ , and hence $\angle CIF=90^{\circ }-\theta /2$ . Thus, the angular position w.r.t. $C$ and the heading change by the same angle $\theta$ , and therefore $P^k$ will be closed if and only if it is proper.

Figure 1: Construction (see text) of rotation center $C$ when $P$ is neither closed nor proper.

The Looping Theorem in 2D and 3D Turtle Geometry

Looping Theorem in 3D

Before stating the Looping Theorem for 3D, we need to handle some preliminaries. The generalization of POLY to 3D is $(Move(d);Roll(\psi );Turn(\varphi ){)}^{\ast }$ . We will, however, consider general 3D looping programs, that repeat and arbitrary sequence $P$ of turtle commands. By Mozzi-Chasles’ Theorem [3, Ch. 7], there exists a unique screw operation $q$ , consisting of a rotation about $\ell$ by a directed angle $\theta$ and a translation parallel to directed line $\ell$ over distance $d$ , such that $q$ transforms the initial state into $P$ ‘s final state: $F(P)=q(I)$ . In general, line $\ell$ does not pass through the turtle’s position. We denote $P$ ‘s screw operation by $Screw(P)$ , and the line, angle, and distance of screw operation $q$ by $q.\ell$ , $q.\theta$ , and $q.d$ . The line $\ell$ is also called the (Mozzi) axis of the screw operation. The supplementary material shows how to construct $\ell$ , $\theta$ , and $d$ . Here are some basic properties of screw operations.

• A rotation about line $\ell$ and a translation parallel to that same line $\ell$ commute. That is, their order is irrelevant for the final result. In fact, you can combine them into a continuous motion along a helix (also useful for the purpose of inter- and extrapolation).
• Changing all signs of a screw operation gives the same screw operation, that is, a screw operation with (directed) line $\ell$ , translation distance $d$ , and rotation angle $\theta$ is the same as the screw operation with line $-\ell$ , translation distance $-d$ , and rotation angle $-\theta$ .
• If $d=0$ and $\theta =0$ , then the screw operation is the identity (which does nothing), and the choice of $\ell$ is irrelevant (no line is needed; all lines are equivalent).
• If $d=0$ and $\theta \ne 0$ , then the screw operation is a pure rotation.
• It $d\ne 0$ and $\theta =0$ , then the screw operation is a pure translation, and only the direction of the line is relevant, not its location in space (all parallel lines are equivalent).
• The screw operation $r=q^k$ (i.e., $q$ repeated $k$ times) has $r.\ell =q.\ell$ , $r.d=k\ast q.d$ , and $r.\theta =k\ast q.\theta$ . This also holds when $k$ is not an integer, which corresponds inter/extrapolation along a helix.

We are again interested in conditions for when $P^k$ is closed and/or proper as captured by the following theorem. Also see the illustrations for each of the cases in the supplementary material.

3D Looping Theorem The properties of $P$ being closed and being proper transfer to $P^k$ as follows, where we abbreviate $d=\text{Screw}(P).d$ and $\theta =\text{Screw}(P).\theta$ .

${}^a$ In these cases, $P^k$ stays within a ball as $k\to \infty$ . ${}^b$ In these cases, $P^k$ stays inside a cylinder along the screw axis and wanders off to infinity as $k\to \infty$ .

Proof Note that the screw axis takes up the same relative position and orientation with respect to the initial state $I$ as to the final state $F(P)$ . (This is the main insight.) Consequently, $Screw(P^k)=Screw(P{)}^k$ . If $Screw(P).d\ne 0$ , then $P^k$ (including $P^1=P$ ) cannot be closed, since it moves away from the origin, parallel to the screw axis. If $Screw(P).d=0$ , then $Screw(P)$ is a pure rotation and all points $F(P^k)$ .pos lie in a plane (which need not be perpendicular to the initial normal vector). So, we can apply the 2D Looping Theorem, which immediately yields the desired results. (End of Proof)

Verhoeff

Corollaries

• If $P$ is not closed, then for all integers $k$, $P^k$ is closed if and only if $P^k$ is properly closed.
• If $P$ is not closed and $\text{Screw}(P).d=0$, both the turtle’s position and attitude rotate by the same angle $\theta$ for each repetition of $P$. Hence, $P^k$ is closed (the final position equals the initial position) if and only if the final attitude equals the initial attitude.

The Simple-Closed-Path Theorem mentioned for 2D does not generalize to 3D. It is possible to have 3D paths without self-intersection and winding number unequal to $\pm 1$ (e.g., a trefoil knot; also see the supplementary material). In 2D, it is easy to keep track of the total change in attitude, by adding all turn angles. In 3D, the total effect of all Turn and Roll commands on the attitude is harder to compute. This is best done by multiplying the quaternions associated with the Turn and Roll commands Or better still, use bivectors and the geometric product from Geometric Algebra; see for instance [4].

Conclusion

We stated Looping Theorems in 2D and 3D Turtle Geometry. Although the mathematical results are not new, the precise formulations as we have given them do not appear in [1]. We separated the notions of closed and proper for turtle programs. This helped improve the formulation of the Looping Theorems, providing further insight into these important theorems for creating rotationally symmetric paths. In particular, we could formulate the somewhat counterintuitive result that a repeated non-closed non-proper turtle path is closed if and only if it is proper. For (artistic) applications we refer to [9][7][2].

Acknowledgements

The author would like to thank Anton Bakker for drawing attention again to the phenomenon that for some repeated turtle paths the notions of ‘being closed’ and ‘being proper’ coincide, and also for helpful discussions.

References

[1] H. Abelson and A. diSessa. Turtle Geometry: The Computer as a Medium for Exploring Mathematics. MIT Press, 1980. Open access: https://mitpress.mit.edu/9780262510370/turtle-geometry [2] A. Bakker and T. Verhoeff. “Domain-Specific Languages for Efficient Composition of Paths in 3D.” Bridges Conference Proceedings, Halifax, Nova Scotia, Canada, July 27–31, 2023. [3] H. Coxeter. Introduction to Geometry, 2nd ed. Wiley, 1969. [4] C. Doran and A. Lasenby Geometric Algebra for Physicists. Cambridge Univ. Press, 2003. DOI: https://doi.org/10.1017/CBO9780511807497 [5] G. K. Francis. “Book Review of Turtle Geometry: The Computer as a Medium for Exploring Mathematics.” AMM, vol. 90, no. 6, 1983, pp. 412–415. [6] S. Papert. Mindstorms: Children, Computers, and Powerful Ideas, 1st ed. Basic Books, 1980. [7] M. van Veenendaal and T. Verhoeff. “Pretty 3D Polygons: Exploration and Proofs.” Bridges Conference Proceedings, Virtual, Aug. 1–3, 2021, pp. 111–118. http://archive.bridgesmathart.org/2021/bridges2021-111.html [8] T. Verhoeff. “3D Turtle Geometry: Artwork, Theory, Program Equivalence and Symmetry.” Int. J. of Arts and Technology, vol. 3, no. 2/3, 2010, pp. 288–319. DOI: http://dx.doi.org/10.1504/IJART.2010.032569 [9] T. Verhoeff and K. Verhoeff. “Regular 3D Polygonal Circuits of Constant Torsion.” Bridges Conference Proceedings. Banff, Canada, July 26–30, 2009, pp. 223–230. http://archive.bridgesmathart.org/2009/bridges2009-223.html