Space-Filling Curves

Introduction

A space-filling curve is typically defined as the limit of a sequence of curves. The Java applet below draws the sequences of curves that define the 2-dimensional Hilbert, Sierpinski and Peano space-filling curves and several of their variations.

Usage Guide

• Select the curve and the recursive level using the first two choice buttons. Press the "Draw" button to draw the curve.
• Click the "Grid" switch to turn it on/off. Curves drawn while it is on will include a background grid that shows how the unit square is subdivided into cells.
• If the "Draw" button is pressed in succession with the state of the other 3 controls unchanged, the applet will automatically advance to the next level of the currently chosen curve.
• A known problem: On some platforms, resizing the browser window while an applet is running in the browser will cause all java.awt.Choice widgets placed near the border of the applet to freeze. This is a problem only in JDK 1.1 capable browsers. If this happens, finish resizing the browser window and then reload an equivalent applet.

Brief Notes

• The mathematical entity known as a space-filling curve is only the limit of the displayed curves. For example, the name Hilbert space-filling curve should properly be used only for the limit curve reached as the level parameter of the Hilbert curves tends to infinity.

• Drawing a curve may be viewed as a two step process:
  1. Subdividing the unit square (the drawing area) into a number of cells;
  2. Traversing the cells in a characteristic order, subject to the following rules:
     • Each cell may be visited only once;
     • Cells visited in succession must be neighboring cells.
     There are some curves such as the Z-curve that do not follow the second rule.

• The Hilbert and Moore curves use square cells -- the level n curve has 4ⁿ cells (and hence 4ⁿ - 1 lines). The Moore curve has the same recursive structure as the Hilbert curve, but ends one cell away from where it started. The Hilbert curve starts and ends at opposite ends of a side of the unit square.

• The Sierpinski group of curves use isosceles right-angled triangles as cells. The Sierpinski_C curve and the Sierpinski curve are, in a sense, complements of each other: the shape of the areas excluded by one curve is the shape included by the other. The Sierpinski_R curve is a variation of Sierpinski with right angles and equal length lines everywhere.

• The Peano curves use square cells; but, unlike the Hilbert curve, each cell is subdivided into 9 cells at the next recursive level. The increased choice in traversing 9 cells gives rise to the variety in the Peano curves. (For 4 cells, not counting reversed and rotated versions, there is only one way to do the traversal: the Hilbert way.) The labels Peano_S, Peano_R and Peano_M stand, respectively, for the serpentine, reflected and meandering variations of the Peano curve.

A Good Reference

• Hans Sagan, Space-Filling Curves, Springer-Verlag, New York, 1994. ISBN: 0-387-94265-3.