Space Filling Curve

Start with a square and two line segments of equal length at right angles that start at the lower left and finish at the lower right. Subdivide the square into four equal subsquares and form a new polygonal path with the motif shown above consisting of four pairs of triangular line segments at right angles, with one pair in each subsquare. For the next iteration, repeat this construction on each of the four subsquares, with the motif scaled by 1/2 and oriented in the same direction as the line segment pair in the original subsquare. This creates 16 new squares each containing a pair of triangular line segments at right angles. Now keep repeating ad infinitum.

Each iteration will produce a continuous polygonal path that starts at the lower left corner of the original square and ends at the lower right corner. This path will intersect but never cross itself. The limit of this sequence of continuous paths will produce a continuous Peano space-filling curve that passes through every point in the original square. In other words, the limit set of this iterative construction will be the filled square. You can get a sense of why this should happen since the nth iteration produces a continuous polygonal path consisting of 4ⁿ pairs of triangular line segments with each pair lying in a square of edge length 1/2ⁿ. As those squares shrink in size as n goes to infinity, the polygonal path will cover more and more of the initial square. Given any particular point in the square, one can make the polygonal path go arbitrarily close to that point by taking the nth iteration for a sufficient large n. [For a more formal proof, see the topology text by Munkres.]

The motif is constructed by taking four copies of the original pair of line segments and rotating the first and last copies by 90° clockwise and 90° counterclockwise, respectively.

${f_1}({\bf{x}}) = \left[ {\begin{array}{{20}{c}} 0 & {1/2} \\ {-1/2} & 0 \\ \end{array}} \right]{\bf{x}} + \left[ {\begin{array}{{20}{c}} 0 \\ {1/2} \\ \end{array}} \right]$	scale by 1/2, rotate −90°
${f_2}({\bf{x}}) = \left[ {\begin{array}{{20}{c}} {1/2} & 0 \\ 0 & {1/2} \\ \end{array}} \right]{\bf{x}} + \left[ {\begin{array}{{20}{c}} {0} \\ {1/2} \\ \end{array}} \right]$	scale by 1/2
${f_3}({\bf{x}}) = \left[ {\begin{array}{{20}{c}} {1/2} & 0 \\ 0 & {1/2} \\ \end{array}} \right]{\bf{x}} + \left[ {\begin{array}{{20}{c}} {1/2} \\ {1/2} \\ \end{array}} \right]$	scale by 1/2
${f_4}({\bf{x}}) = \left[ {\begin{array}{{20}{c}} 0 & {-1/2} \\ {1/2} & 0 \\ \end{array}} \right]{\bf{x}} + \left[ {\begin{array}{{20}{c}} {1} \\ 0 \\ \end{array}} \right]$	scale by 1/2, rotate 90°

The attractor for this IFS is the filled-in unit square [0,1]x[0,1] with four self-similar parts (the four subsquares.) The black "L" in each colored square indicates the orientation of that square according to the corresponding function in the IFS.

square

The square is self-similar with 4 non-overlapping copies of itself, each scaled by the factor r = 1/2. Therefore the similarity dimension, d, of the attractor of the IFS is the solution to

$$\sum\limits_{k = 1}^4 {{r^d}} = 1\quad \Rightarrow \quad d = \frac{{\log (1/4)}}{{\log (r)}} = \frac{{2\log (1/2)}}{{\log (1/2)}} = 2$$

The image below of a back stitch embroidery shows the sixth iteration for the space filling IFS described here. The curve starts in the lower left corner and traces a continuous path through the red section into the blue, orange, and green sections, ending in the lower right corner. As noted above, the curve intersects itself at many points but never crosses itself. The piece was stitched along this continuous path. Each of the four sections uses two alternating shades of color to illustrate the basic design of the IFS based on the motif of 8 line segments at right angles. The motif is repeated throughout the design in horizontal and vertical orientations.

[Enlarge]
Space Filling Curve (6th Iteration)
12.5" x 12.5" (14 point canvas)
Larry Riddle, 2013

Classic Iterated Function Systems