Synthesis of Space-Filling Curves on the Square Grid

Przemyslaw Prusinkiewicz¹ Aristid Lindenmayer² F. David Fracchia¹

¹Department of Computer Science, University of Regina, Regina, Saskatchewan, Canada
²Theoretical Biology Group, University of Utrecht, Utrecht, The Netherlands

Abstract

This paper investigates a relationship between a class of polygonal fractal curves and tilings of the plane. The curves are constructed by connecting polygons inscribed into tiles using inserted line segments. Conditions are imposed to ensure that the resulting curve is approximately space-filling, self-avoiding, simple (single-stroke) and self-similar. Such curves are referred to as FASS curves. Their relationship to tilings is used to explain the design of classic space-filling curve, and is applied to synthesize new FASS curves. A program which generates FASS curves on a square grid is described, and examples of curves produced using this program are given. The FASS curves are expressed using the formalism of L-systems with turtle interpretation. Thus, the paper provides a method for synthesizing L-systems that generate classic and new space-filling curves.

Reference

Przemyslaw Prusinkiewicz, Aristid Lindenmayer, and F. David Fracchia. 1989.

Download the PDF here (6 Mb).