Mark Dow

Geek art

Simple recursive systems and fractal patterns

Space-filling curve L-systems    

    A few examples of block replacement L-systems that have fixed points that are space-filling curves.

    What distinguishes systems that result in space-filling curves? Given a space-filling curve defined in some other way, can it, and how can it, be generated with a block replacement L-system?

Spiral space-filling system pattern, link to Anti-symmetric spiral space-filling system, link to Spiral space-filling system average pattern, link to Hilbert curves Hilbert curves Peano curves Peano curves Peano curves

About space-filling curves
Complete traversals of a lattice

2x2 two symbol systems

Hilbert curves
[To Do: list]
3x3 two symbol systems

Peano curves
[To Do: list]
Spiral space-filling system
Progressive spiral space-filling system
Double S spiral space-filling system
Double F spiral space-filling system
Anti-symmetric spiral space-filling system

[To Do: R-Tree, rotated bars, Z traversal, more complex traversals.]

References

About space-filling curves

    What continuous and nowhere differentiable curves pass through every point of a region of space, without crossing? How can space-filling curves be specified and constructed?

        Space-filling curves are deceptively simple. While they are described by very short recursive algorithms, and their representations are highly redundant (through space and across scales), the number and form of the system elements are not obvious from looking at the curve elements. How many unique segments, and rotations and mirrors of segments, are required to form one of these curves? What is the arrangement, or pattern, of each the segments?

    Space-filling curves can be described with string-rewriting systems, where the symbols (alphabet) represent line segments and turn directions. They can then be visualized as prototypical curves, whose elements (segments and turns) are recursively replaced by scaled copies of themselves. [To Do: Illustrate a turtle graphics string rewriting system.]

Spiral space-filling by generation graphic
 The first six generations of the Hilbert curve.

Spiral space-filling by generation graphic
The first three generations of a Peano curve construction.

    This visual representation is a block replacement system, but the replacement rules are not explicit. For example there are several ways to arrange the Peano "S" at each of 3x3 locations at the second iteration. [To Do: Illustrate with 3x3 block background, centers, and underdetermined tails.] Other space-filling curves, such as the Hilbert curve, are also described by block replacement systems on a 2x2 or larger square lattices. Other regular lattices (triangular, hexagonal) also support space filling systems.

Complete traversals of a lattice [To Do: Finish this.]

    Here is one way of thinking about these systems that has helped me think about how to design other space-filling systems.

    The generating rules (axioms) for space-filling curves are complete lattice traversals, where more than one traversals are defined by mutual replacement.

    Here's a recipe for finding space filling curves:

    First, pick a lattice geometry that can be defined by replacement system.  Most of the examples on this page are on a square lattice with 2x2 or 3x3 lattice replacements. The lattice can be defined by replacing a lattice point, represented by a square, with an n x m set of points, represented by an n x m array of squares. [Are there any good examples of space-filling systems defined by anisotropic lattice replacements, for example on a 2x3 replacement system?]
    Square, hexagonal, and triangular lattices are obvious choices. Lattices on higher dimensions can alsp be used [To Do: Link to 3-D Hilbert analogue example]. There are also other topologies and geometries, such as periodic and aperiodic substitution tilings, that fit the bill.

2x2 replacement system

A system that results in a 2nx2n lattice after n iterations.

               3x3 replacement system
A system that results in a 3nx3n lattice after n generations.		                
A system that results in a periodic lattice with a fractal boundary.

    Second, choose a set of complete traversals of the replacement lattice. By complete traversal, I mean a curve having an enterance and exit point, visits each lattice point (passes into each quadrant), and doesn't cross (or touch) itself. Here's a several examples 2x2 traversals. Below them are traversal symbols that represent only the entrance and exit points, with the understanding that this traversal symbol (or motif) is to be replaced by a 2x2 complete traversal that enters and exits at the same relative locations.


    What are the possible traversals, unique up to rotation and a mirror? Here are many, but not all:

2x2 traversal motif

2x2 traversal
 2x2 traversal motif

2x2 traversal		 2x2 traversal motif

2x2 traversal		 2x2 traversal motif

2x2 traversal
2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal
2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal
2x2 traversal 2x2 traversal 2x2 traversal
2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal

2x2 traversal





2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif
2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif
2x2 traversal motif 2x2 traversal motif 2x2 traversal motif
2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif

2x2 traversal motif




2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal





























2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif




























    Third, find a set of 2x2 complete traversals composed of only 1x1 traversal symbols (or their rotations and mirrors) that appear in the set of complete traversals. For example there are several traversals that only include the traversal icons of which they are composed:
2x2 traversal
 2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal
2x2 traversal 2x2 traversal
2x2 traversal 2x2 traversal

2x2 traversal 2x2 traversal

2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif
2x2 traversal motif 2x2 traversal motif
2x2 traversal motif 2x2 traversal motif

2x2 traversal motif 2x2 traversal motif
   
    Are there more such pairs? Traversals that use two symbols that don't include their own symbol [example] can't be a member of such a pair. This narrows the list considerably. Also, the pairs must share the property of  "only corner to corner", "only side to side centered, or "only side to side off-center" [graphic list]

    There is a case that appears to be unique, a traversal that only uses it's own traversal icon. It fails the check in the next step, in that it is self-intersecting.

    Here are examples of sets of three traversals (only one traversal is different, and the traversal icons (entrance and exit points) are the same:




 2x2 traversal motif

2x2 traversal
 2x2 traversal 2x2 traversal



2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal






2x2 traversal motif 2x2 traversal motif



2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif



not used


[To Do: Finish.]  
There's a surprising lack of variety in this list of triplets. I woud have guessed on combinatorial principles that there would be a steep increase in the number of triplets, because many more combinations of symbols can plausibly be used to construct traversals. Are there a large number of triplets I missed in this list? 







2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal
2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal









2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif
2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif










2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal


2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal









2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif


2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif



Milbert curve traversal set








2x2 traversal 2x2 traversal 2x2 traversal 2x2 traversal














2x2 traversal motif 2x2 traversal motif 2x2 traversal motif 2x2 traversal motif








It doesn't work. Many variations (using different traversals with the same enterance and exit points) also didn't work.
L_system_tiling( 'test', 5, 4, 1, 0, 'trav_22sc_22ac_21o_21a_rgbv_motif.png', 0, [103 22; 2 123], [22 11; 2 10], [103 10; 2 21], [103 3; 2 2] );
[To Do: Finish.]  

    Fourth, these sets need to be checked for intersections at edges. [To Do: Some sets don't have tangents to the edge, so it is guarenteed that any combinations won't intersect. But several 2-symbol systems do intersect the edge, and when they are replaced, intersect an adjacent replacement.]




2x2 2-symbol systems

Hilbert curves

Hilbert curve symbol structure

Hilbert curve algorithm graphic

Hilbert curve by generation graphic
 Hilbert curve pattern, 0th generation
generation 0		 Hilbert curve pattern, 1st generation
generation 1 		Hilbert curve pattern, 2nd generation
generation 2 		Hilbert curve pattern, 3rd generation
generation 3		 Hilbert curve pattern, 4th generation
generation 4		 Hilbert curve pattern, 5th generation
generation 5

     Three quadrants are exactly self-similar to the previous generation, but the fourth (lower right) is geometrically similar to the system initialized with the second symbol (below).
Hilbert curve algorithm graphic

Hilbert curve by generation graphic
 Hilbert curve pattern, 0th generation
generation 0, 1x1		 Hilbert curve pattern, 1st generation
generation 1, 2x2		 Hilbert curve pattern, 2nd generation
generation 2, 4x4 		Hilbert curve pattern, 3rd generation
generation 3, 8x8 		Hilbert curve pattern, 4th generation
generation 4, 16x16

    Initializing with the second symbol results in the same pattern, except for the bottom right corner at each generation. In this case the pattern is always bileaterally symmetric, but each quadrant is not exactly self-similar to the previous generation. Each quadrant is exactly similar to the system above that starts with the first symbol, above.
Hilbert curve algorithm graphic

Hilbert curve by generation graphic
 Hilbert curve pattern, 0th generation
generation 0, 1x1		 Hilbert curve pattern, 1st generation
generation 1, 3x3		 Hilbert curve pattern, 2nd generation
generation 2, 9x9 		Hilbert curve pattern, 3rd generation
generation 3, 27x27 		Hilbert curve pattern, 4th generation


    What are the sequences along the curves?

MATLAB commands:
>> imOut = L_system_tiling( 'Hilbert', [ng], 2, 1, 0, '', 0, [100 0; 10 31], [100 0; 10 110] );
 >> imOut = L_system_tiling( 'Hilbert', [ng], 2, 1, 0, 'TS_symb_27_motif.png', 0, [100 0; 10 31], [100 0; 10 110] );
>> imOut = L_system_tiling( 'Hilbert', [ng], 2, 1, 0, 'TS_symb_27_motif.png', 1, [100 0; 10 31], [100 0; 10 110] );
>> imOut = L_system_tiling( 'Hilbert', [ng], 2, 1, 0, 'TS_rb_9_motif.png', 1, [100 0; 10 31], [100 0; 10 110] );
>> imOut = L_system_tiling( 'Hilbert', [ng], 2, 1, 0, '', 1, [100 0; 10 31], [100 0; 10 110] );
where [ng] is the number of generations.

Hilbert region system

    Four symbols are required to represent the two regions that the Hilbert curve separates. The boundary between black and white of the system pattern is a Hilbert curve. Note that the boundaries within the motifs mimic the typical curve replacement system. This example is initialized with the second symbol, resulting in the bilaterally symmetric Hilbert curve.

Hilbert region algorithm graphic

Hilbert region by generation graphic
 Hilbert region system pattern. link to 10th generation
Hilbert region system pattern		 Hilbert region system average pattern. link to 10th generation
average across generations		 Hilbert region system self-symmetries, init = 1
self-symmetries initializated with the second symbol (of the rules, before replacement with motifs)		 Hilbert region system self-symmetries, init = 0
self-symmetries (of the rules, before replacement with motifs)		         Hilbert region system self-symmetries
self-symmetries at infinite limit (of the pattern, after replacement with motifs)


     
Hilbert region, 1st generation
 Hilbert region, 2nd generation Hilbert region, 3rd generation Hilbert region, 4th generation Hilbert region, 5th generation Hilbert region, 6th generation
Hilbert average region, 1st generation Hilbert average region, 2nd generation Hilbert average region, 3rd generation Hilbert average region, 4th generation Hilbert average region, 5th generation Hilbert average region, 6th generation
Initializated with the second symbol (the bilaterally symmetric case), the system pattern (top) and  average pattern (bottom) by generation.

Hilbert region Fourier transform

Hilbert region system pattern. link to 10th generation

Hilbert region system pattern 		  FT
<==>		 Hilbert region Fourier transform, link to 10th generation
hue-phase scale bar
DFT amplitudes colored by phase 		 = Hilbert region Fourier transform amplitude, link to 10th generation

amplitudes 		* Hilbert region Fourier transform phase no drift, link to 10th generation

phases, no drift		 * Hilbert region Fourier transform phase drift, link to 10th generation

phase drifts 		      Hilbert region Fourier transform integral phases, link to 10th generation
quarter-phase scale bar
integer multiples of pi/2 radian phases

Hilbert region average Fourier transform

Hilbert region system average pattern. link to 10th generation

Hilbert region average pattern
   FT
<==>		 Hilbert region average Fourier transform, link to 10th generation
hue-phase scale bar
DFT amplitudes colored by phase 		= Hilbert region Fourier transform amplitude, link to 10th generation

amplitudes 		* Hilbert region average Fourier transform phase no drift, link to 10th generation

phases, no drift		 * Hilbert region average Fourier transform phase drift, link to 10th generation

phase drifts		       Hilbert region average Fourier transform integral phases, link to 10th generation
quarter-phase scale bar
integer multiples of pi/2 radian phases
MATLAB command:
>> imOut = L_system_tiling( 'Hilbert', [ng], 4, 1, 0, 'adj_opp_sides_inv_motif.png', 1, [100 0; 12 33], [100 0; 12 112], [102 2; 10 31], [102 2; 10 110] );
where [ng] is the number of generations.
Hardcoded:
bAverageAfterReplacement    = true;
flPhaseDriftX        = 1*pi;
flPhaseDriftY        = 1*pi;
flAvgPhaseDriftX     = 1*pi;
flAvgPhaseDriftY     = 1*pi;

Hilbert 2-symbol system

    This is the same 2-symbol system that was used for Hilbert curve symbol structure, but without replacement with a "segment" motif. Rotations and mirrors of the two symbols are not represented in the resulting patterns.

Hilbert 2-symbol algorithm graphic

Hilbert 2-symbol by generation graphic
 Hilbert 2-symbol system pattern. link to 10th generation
Hilbert 2-symbol system pattern		 Hilbert 2-symbol system average pattern. link to 10th generation
average across generations		 Hilbert 2-symbol system self-symmetries
self-symmetries		  ==> Hilbert 2-symbol system infinite limit self-symmetries
self-symmetries at infinite limit

Hilbert 2-symbol algorithm graphic

Hilbert 2-symbol by generation graphic
 Hilbert 2-symbol system pattern. link to 10th generation
Hilbert 2-symbol system pattern		 Hilbert 2-symbol system average pattern. link to 10th generation
average across generations		 Hilbert 2-symbol system self-symmetries
self-symmetries		 ==> Hilbert 2-symbol system infinite limit self-symmetries
self-symmetries at infinite limit


Hilbert 2-symbol Fourier transform

Hilbert region system pattern. link to 10th generation

Hilbert region system pattern 		  FT
<==>		 Hilbert region Fourier transform, link to 10th generation
hue-phase scale bar
DFT amplitudes colored by phase 		 = Hilbert region Fourier transform amplitude, link to 10th generation

amplitudes 		* Hilbert region Fourier transform phase no drift, link to 10th generation

phases, no drift		 * Hilbert region Fourier transform phase drift, link to 10th generation

phase drifts 		      Hilbert region Fourier transform integral phases, link to 10th generation
quarter-phase scale bar
integer multiples of pi/2 radian phases

Hilbert 2-symbol average Fourier transform

Hilbert region system average pattern. link to 10th generation

Hilbert region average pattern
   FT
<==>		 Hilbert region average Fourier transform, link to 10th generationHilbert region average Fourier transform, link to 10th generation
hue-phase scale bar
DFT amplitudes colored by phase 		= Hilbert region Fourier transform amplitude, link to 10th generation

amplitudes 		* Hilbert region average Fourier transform phase no drift, link to 10th generation

phases, no drift		 * Hilbert region average Fourier transform phase drift, link to 10th generation

phase drifts		       Hilbert region average Fourier transform integral phases, link to 10th generation
quarter-phase scale bar
integer multiples of pi/2 radian phases
MATLAB command:
>> imOut = L_system_tiling( 'Hilbert', [ng], 4, 1, 0, 'adj_opp_sides_inv_motif.png', 1, [100 0; 12 33], [100 0; 12 112], [102 2; 10 31], [102 2; 10 110] );
where [ng] is the number of generations.
Hardcoded:
bAverageAfterReplacement    = true;
flPhaseDriftX        = 1*pi;
flPhaseDriftY        = 1*pi;
flAvgPhaseDriftX     = 1*pi;
flAvgPhaseDriftY     = 1*pi;


3x3 2-symbol systems (with rotations)

Peano curves

Peano curves symbol structure

Peano space-filling algorithm graphic

Peano space-filling by generation graphic
 Peano space-filling system pattern
generation 0, 1x1		 Peano space-filling system pattern
generation 1, 3x3		 Peano space-filling system pattern
generation 2, 9x9 		Peano space-filling system pattern
generation 3, 27x27

Peano space-filling algorithm graphic

Peano space-filling by generation graphic
 generation 1 Peano space-filling system pattern
generation 0, 1x1		 generation 1 Peano space-filling system pattern
generation 1, 3x3		 generation 2 Peano space-filling system pattern
generation 2, 9x9 		generation 3 Peano space-filling system pattern
generation 3, 27x27

Peano space-filling algorithm graphic

Peano space-filling by generation graphic
 Peano space-filling system pattern. link to 7th generation
Peano space-filling pattern		 Peano space-filling system pattern. link to 7th generation
 Peano space-filling system pattern. link to 7th generation
    What are the sequences of symbols along the curves?
1 1 0 0  1  0 0 1 1   1 1 0 0 1 1 0 0 1 1     
0,0,1,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0,0

MATLAB commands:
>> imOut = L_system_tiling( 'Peano', [ng], 2, 1, 0,  'adj_opp_1a_motif.png', 0, [0 100 0; 101 1 101; 1 30 20], [0 100 1; 101 1 101; 1 30 20] );
>> imOut = L_system_tiling( 'Peano', [ng], 2, 1, 0,  'adj_opp_1a_motif.png', 1, [0 100 0; 101 1 101; 1 30 20], [0 100 1; 101 1 101; 1 30 20] );
 >> imOut = L_system_tiling( 'Peano', [ng], 2, 1, 0, 'adj_opp_br_motif.png', 0, [0 100 0; 101 1 101; 1 30 20], [0 100 1; 101 1 101; 1 30 20] );
where [ng] is the number of generations.

Peano two symbol system


Hilbert region algorithm graphic

Hilbert region by generation graphic
 Peano two symbol pattern. link to 7th generation
Peano two symbol system pattern		 Peano two symbol average pattern. link to 7th generation
average across generations		 Peano two symbol system self-symmetries
self-symmetries
     Note that there are more "almost" self-symmetries.  For example, the upper right and left quadrants differ only at a single point, their lower left and right (respectively) corners. [To Do: An "almost" self-symmetry diagram.]

Peano two symbol Fourier transform

Peano two symbol pattern. link to 7th generation

Peano two symbol system pattern 		  FT
<==>		 Peano two symbol Fourier transform, link to 7th generation
hue-phase scale bar
DFT amplitudes colored by phase 		 = Peano two symbol Fourier transform amplitude, link to 7th generation

amplitudes 		* Peano two symbol Fourier transform phase no drift, link to 7th generation

phases, no drift		 * Peano two symbol Fourier transform phase drift, link to 7th generation

phase drifts 		      Peano two symbol Fourier transform integral phases, link to 7th generation
quarter-phase scale bar
integer multiples of pi/2 radian phases

Peano two symbol average Fourier transform

Peano two symbol average pattern. link to 7th generation

Peano two symbol average pattern
   FT
<==>		 Peano two symbol average Fourier transform, link to 7th generation
hue-phase scale bar
DFT amplitudes colored by phase 		= Peano two symbol Fourier transform amplitude, link to 7th generation

amplitudes 		* Peano two symbol average Fourier transform phase no drift, link to 7th generation

phases, no drift		 * Peano two symbol average Fourier transform phase drift, link to 7th generation

phase drifts		       Peano two symbol average Fourier transform integral phases, link to 7th generation
quarter-phase scale bar
integer multiples of pi/2 radian phases


MATLAB command:
 >> imOut = L_system_tiling( 'Peano', [ng], 2, 1, 0, '', 1, [0 100 0; 101 1 101; 1 30 20], [0 100 1; 101 1 101; 1 30 20] );
where [ng] is the number of generations.
Hardcoded:
flPhaseDriftX        = 1*pi;
flPhaseDriftY        = 1*pi;
flAvgPhaseDriftX     = 1*pi;
flAvgPhaseDriftY     = 1*pi;

Peano region system

   The boundary between black and white of the system pattern is a Peano curve. Note that the boundaries within the motifs mimic the typical curve replacement system.

Peano region algorithm graphic

Peano region by generation graphic
 Peano region system pattern. link to 6th generation
Peano region system pattern		 Peano region system average pattern. link to 6th generation
average across generations		 Peano region system self-symmetries
self-symmetries
     Note that there are more "almost" self-symmetries.  For example, the lower left 1/3x1/3 differs only at a single point, its upper-right corner. [To Do: An "almost" self-symmetry diagram.]


Peano region, 1st generation
 Peano region, 2nd generation Peano region, 3rd generation Peano region, 4th generation

Peano average region, 1st generation Peano average region, 2nd generation Peano average region, 3rd generation Peano average region, 4th generation

Pattern (top) and  average pattern (bottom) by generation.

Peano region Fourier transform

Peano region system pattern. link to 6th generation

Peano region system pattern 		  FT
<==>		 Peano region Fourier transform, link to 6th generation
hue-phase scale bar
DFT amplitudes colored by phase 		 = Peano region Fourier transform amlitudes, link to 6th generation

amplitudes 		* Peano region Fourier transform phases, link to 6th generation

phases, no drift		       Peano region Fourier transform integral phases, link to 6th generation
quarter-phase scale bar
integer multiples of pi/2 radian phases

Peano region average Fourier transform

Peano region system average pattern. link to 6th generation

Peano region average pattern
   FT
<==>		 Peano region average Fourier transform, link to 6th generation
hue-phase scale bar
DFT amplitudes colored by phase 		= Peano region Fourier transform amplitude, link to 6th generation

amplitudes 		* Peano region average Fourier transform phase no drift, link to 6th generation

phases, no drift		 * Peano region average Fourier transform phase drift, link to 6th generation

phase drifts		       Peano region average Fourier transform integral phases, link to 6th generation
quarter-phase scale bar
integer multiples of pi/2 radian phases
MATLAB command:
>> imOut = L_system_tiling( 'Peano', 4, 4, 1, 0, 'adj_opp_sides_inv_r_motif.png', 0, [0 100 0; 103 3 103; 1 32 22], [0 100 1; 103 3 103; 1 32 22], [2 102 2; 101 1 101; 3 30 20], [2 102 3; 101 1 101; 3 30 20] );
where [ng] is the number of generations.
Hardcoded:
bAverageAfterReplacement    = true;
flAvgPhaseDriftX     = 1*pi;
flAvgPhaseDriftY     = 1*pi;

Spiral space-filling system

    This system has complement symmetric rules. The boundary between black and white is a space-filling curve. The pattern itself is not symmetric, unless the initial rule is modified to use the two symbols symmetrically (see example below).
    The pattern is similar too, but not the same as to Walter Wunderlich's (3rd) variation of the Peano system which is formed by 2x2 replacements on an initial 3x3 array [To Do: Show this Peano variation]. While Wunderlich's variations are formed of 2x8 = 16 unique symbol replacements (all rotations and mirrors of two symbols), this system is formed by only 4x2 =8 unique symbol replacements (all rotations of two symbols).

    I found this system just through tinkering with symmetric rules. The space-filling curve is not represented explicitly, only through the juxtoposition of squares. How can the edge be represented explicitly?
Spiral space-filling algorithm graphic

Spiral space-filling by generation graphic
 Spiral space-filling system pattern. link to 7th generation
Spiral space-filling pattern		 Spiral space-filling system average pattern. link to 7th generation
average across generations		 Spiral space-filling system self-symmetries
self-symmetries

Spiral space-filling Fourier transform

Spiral space-filling system pattern. link to 7th generation

Spiral space-filling pattern

   FT
<==>		 Spiral space-filling Fourier transform, link to 7th generation
hue-phase scale bar
DFT amplitudes colored by phase
  = Spiral space-filling Fourier transform amplitude, link to 7th generation

amplitudes 		* Spiral space-filling Fourier transform phase no drift, link to 7th generation

phases, no drift		 * Spiral space-filling Fourier transform phase drift, link to 7th generation

phase drifts
       Spiral space-filling Fourier transform integral phases, link to 7th generation
quarter-phase scale bar
integer multiples of pi/2 radian phases

Serpinski right triangle average Fourier transform

Spiral space-filling system average pattern, link to 7th generation

Spiral space-filling average pattern
   FT
<==>		 Spiral space-filling average Fourier transform, link to 7th generation
hue-phase scale bar
DFT amplitudes colored by phase 		= Spiral space-filling average Fourier transform amplitude, link to 7th generation

amplitudes 		* Spiral space-filling average Fourier transform phase no drift, link to 7th generation

phases, no drift		 * Spiral space-filling average Fourier transform phase drift, link to 7th generation

phase drifts		       Spiral space-filling average Fourier transform integral phases, link to 7th generation
quarter-phase scale bar
integer multiples of pi/2 radian phases
MATLAB command:
>> imOut = L_system_tiling( 'SP', [ng],  2, 1, 0, '', 0, [0 2 2; 0 1 4; 0 7 7], [1 3 3; 1 0 5; 1 6 6] );
where [ng] is the number of generations.
Hardcoded:
flPhaseDriftX        = 1*pi;
flPhaseDriftY        = 1*pi;
flAvgPhaseDriftX     = 1*pi;
flAvgPhaseDriftY     = 1*pi;

Progressive (np = 3) Spiral space-filling system (not shown)
>> imOut = L_system_tiling( 'PG', 3, 3, 1, 0, '', 0, [0 3 3; 0 1 6; 0 10 10], [1 4 4; 1 2 7; 1 11 11], [2 5 5; 2 0 8; 2 9 9] );
 where [ng] is the number of generations.
Arithmetic subsequence  SP( 3n + b ), b = [1,3], of the Spiral space-filling system pattern:
Spiral space-filling system pattern, arithmetic subsequence SP( 3n + 0 )
Spiral space-filling system pattern, arithmetic subsequence SP( 3n + 0 )
 Spiral space-filling system pattern, arithmetic subsequence SP( 3n + 1 )
Spiral space-filling system pattern, arithmetic subsequence SP( 3n + 1 )
This is the inverse of the pattern itself.		 Spiral space-filling system pattern, arithmetic subsequence SP( 3n + 2 )
Spiral space-filling system pattern, arithmetic subsequence SP( 3n + 2 )
[To Do: Self-similarity diagram. Is there an iterated morphism for this pattern?]

MATLAB command:
>> imOut = L_system_tiling( 'SP', [ng], 2,  3, [o], '', 0, [0 2 2; 0 1 4; 0 7 7], [1 3 3; 1 0 5; 1 6 6] );
where [ng] is the number of generations and [o] is the offset [1,3].
   

Double S spiral space-filling system

Double S spiral space-filling algorithm graphic

Double S spiral space-filling by generation graphic
 Double S spiral space-filling system pattern

    Could the boundary be a solution to a boundary length maximization problem, with some constraint on the number of right angles?

[To Do: A smooth boundary morphing between a generation. Assemble a checkerboard such that four armed connected regions can be colored.]

MATLAB command:
>> imOut = L_system_tiling( 'SP', [ng],  2, 1, 0, '', [0; 5], [0 2 2; 0 1 4; 0 7 7], [1 3 3; 1 0 5; 1 6 6] );
where [ng] is the number of generations.

Double F spiral space-filling system

Double F spiral space-filling algorithm graphic

Double F spiral space-filling by generation graphic
 Double F spiral space-filling system pattern

MATLAB command:
>> imOut = L_system_tiling( 'SP', [ng],  2, 1, 0, '', [0 5], [0 2 2; 0 1 4; 0 7 7], [1 3 3; 1 0 5; 1 6 6] );
where [ng] is the number of generations.

Anti-symmetric spiral space-filling system

Anti-symmetric spiral space-filling algorithm graphic

Anti-symmetric spiral space-filling by generation graphic
 Anti-symmetric spiral space-filling system pattern
Anti-symmetric spiral space-filling pattern		 Anti-symmetric spiral space-filling system pattern
average across generations
    This system has the same rules as the Spiral space-filling system (above), but with a 3x4 set of initial symbols such that the resulting system/pattern is fully anti-symmetric (identical after a pi/2 rotation and complement). These initial symbol pattern is a hybrid of the rules themselves, the first (or second) rule and the anti-symmetric copy of the first (or second) rule.

MATLAB command:
>> imOut = L_system_tiling( 'SP', [ng],  2, 1, 0, '', [0 2 2 5; 0 1 4 5; 0 7 7 5], [0 2 2; 0 1 4; 0 7 7], [1 3 3; 1 0 5; 1 6 6] );
where [ng] is the number of generations.


[To Do: 

Hilbert
L_system_tiling( 'SF_Hilbert', 5, 2, 1, 0, 'Hilbert_motif_a.png', 0, [100 0; 10 31], [100 0; 10 110] );
Diagonally supplemented Hilbert
L_system_tiling( 'Z2', 5, 5, 1, 0, 'Z_motif_a.png', 4, [100 0; 10 31], [100 0; 10 110], [100 0; 10 112], [100 0; 11 112], [22 13; 33 2]);
L_system_tiling( 'FourZ', 2, 5, 1, 0, 'Z_motif_a.png', [14 4; 4 14], [100 0; 10 31], [100 0; 10 110], [100 0; 10 112], [100 0; 11 112], [22 13; 33 2]);

(other space filling systems)
L_system_tiling( 'SF1', 2, 2, 1, 0, 'SF1_2s_motif.png', 0, [1 10 1; 11 10 31; 21 30 21], [1 30 1; 0 1 0; 31 10 11] );
L_system_tiling( 'R_tree', 4, 2, 1, 0, 'R_motif_b.png', 0, [0 0; 1 1], [1 0; 1 0] );

L_system_tiling( 'Pinwheel_3s_v1', 5, 3, 1, 0, 'trav_11a_21o_21a_rgb_motif.png', 0,   [131 0; 32 10], [102 121; 1 122], [30 0; 1 1] );
L_system_tiling( 'Pinwheel_3s_v2', 5, 3, 1, 0, 'trav_11a_21o_21a_rgb_motif.png', 0,   [131 132; 112 132], [102 121; 1 122], [30 0; 1 1] );
% Kiss failure examples.
L_system_tiling( 'Pinwheel_3s_v3', 3, 3, 1, 0, 'trav_11a_21o_21a_rgb_motif.png', 0, [131 0; 32 10], [102 121; 1 122], [21 121; 1 1] );
L_system_tiling( 'Pinwheel_3s_v4', 3, 3, 1, 0, 'trav_11a_21o_21a_rgb_motif.png', 0, [131 132; 112 132], [102 121; 1 122], [21 121; 1 1] );

L_system_tiling( 'Pinwheel_3s', 3, 6, 1, 0, 'crn_opp_adj_15s6d_motif.png', [30 0; 20 10],   [134 0; 32 10], [105 121; 1 122], [33 3; 4 1]   , [131 3; 35 13], [102 124; 4 125], [30 0; 1 4] );
]




Checkerboards

L_system_tiling( 'X', 6, 2, 1, 0, '', 0, [0 1 0; 1 0 1; 0 1 0], [1 0 1; 0 1 0; 1 0 1] );
L_system_tiling( 'test', 6, 2, 1, 0, '', 0, [0 1 0; 1 0 1; 0 1 0], [0 1 0; 1 0 1; 0 1 0] );


Boundaries

L_system_tiling( 'BD1', 6, 3, 1, 0, '', 0, [1 2 2; 2 7 2; 2 2 1], [0 3 0; 2 2 9; 2 2 0], [2 2 2; 2 2 2; 2 2 2] );
L_system_tiling( 'BD2', 6, 3, 1, 0, '', 0, [1 4 1; 2 2 10; 2 2 1], [0 2 2; 2 6 2; 2 2 0], [2 2 2; 2 2 2; 2 2 2] );

L_system_tiling( 'BD2a', 6, 3, 1, 0, '', 0, [1 4 1; 2 2 10; 2 2 1], [0 2 2; 2 6 2; 2 2 1], [2 2 2; 2 2 2; 2 2 2] );

L_system_tiling( 'BD3', 5, 3, 1, 0, '', 0, [0 2 2; 2 7 2; 2 2 0], [0 3 0; 2 2 9; 2 2 0], [2 2 2; 2 2 2; 2 2 2] );
L_system_tiling( 'BD4', 5, 3, 1, 0, '', 0, [0 2 2; 2 7 2; 2 2 6], [0 3 0; 2 2 9; 2 2 0], [2 2 2; 2 2 2; 2 2 2] );

L_system_tiling( 'BD5', 5, 3, 1, 0, '', 0, [1 2 2; 2 0 2; 2 2 7], [0 3 0; 2 2 9; 2 2 0], [2 2 2; 2 2 2; 2 2 2] );
L_system_tiling( 'BD6', 6, 3, 1, 0, '', 0, [1 2 2; 2 6 2; 2 2 7], [0 3 0; 2 2 9; 2 2 0], [2 2 2; 2 2 2; 2 2 2] );
L_system_tiling( 'BD6str', 5, 3, 1, 0, '', [15 0; 0 15], [1 2 2; 2 6 2; 2 2 7], [0 3 0; 2 2 9; 2 2 0], [2 2 2; 2 2 2; 2 2 2] );
L_system_tiling( 'BD6sqr', 5, 3, 1, 0, '', [3 0; 0 9], [1 2 2; 2 6 2; 2 2 7], [0 3 0; 2 2 9; 2 2 0], [2 2 2; 2 2 2; 2 2 2] );


L_system_tiling( 'MT', 8, 3, 1, 0, '', 0, [10 7;  1 4], [0 0; 2 0], [2 2; 2 2] ); % Monohedral turtle


Repeat inverse
L_system_tiling( 'test', 5, 2, 1, 0, '', 0, [1 0 0; 0 1 0; 0 0 1], [0 1 1; 1 0 1; 1 1 0] );
L_system_tiling( 'H', 6, 2, 1, 0, '', 0, [0 1 0; 0 0 0; 0 1 0], [1 0 1; 1 1 1; 1 0 1] );
L_system_tiling( 'SP', 5,  2, 1, 0, '', 0, [0 2 1; 0 4 1; 0 3 1], [1 3 0; 1 5 0; 1 2 0] );
L_system_tiling( 'test', 6, 2, 1, 0, '', 0, [1 0 0; 0 1 0; 0 0 1], [0 1 1; 1 0 1; 1 1 0] );
L_system_tiling( 'test', 6, 2, 1, 0, '', 0, [3 0 0; 0 3 0; 0 0 3], [2 1 1; 1 2 1; 1 1 2] );

L_system_tiling( 'test', 5, 2, 1, 0, '', 0, [0 1 0 0; 0 1 1 1; 1 1 1 0; 0 0 1 0], [ 1 0 1 1; 1 0 0 0; 0 0 0 1; 1 1 0 1 ] );

L_system_tiling( 'test', 5, 2, 1, 0, '', 0, [0 0 0 0; 0 1 1 0; 0 1 1 0; 0 0 0 0], [ 1 1 1 1; 1 0 0 1; 1 0 0 1; 1 1 1 1 ] );

L_system_tiling( 'test', 6, 2, 1, 0, '', 0, [0 1 0; 0 1 0; 0 0 0], [1 0 1; 1 0 1; 1 1 1] );

L_system_tiling( 'test', 6, 2, 1, 0, '', 0, [2 1 2; 2 2 2; 2 1 2], [1 1 1; 1 1 1; 1 1 1] ); % monohedral tiling
L_system_tiling( 'test', 6, 3, 1, 0, '', 0, [1 2 2; 2 1 2; 2 2 1], [0 3 0; 2 2 3; 2 2 0], [2 2 2; 2 2 2; 2 2 2] );
L_system_tiling( 'test', 6, 2, 1, 0, '', 0, [0 3 0; 0 0 0; 0 3 0], [1 2 1; 1 1 1; 1 2 1] );
L_system_tiling( 'HX, 6, 2, 1, 0, '', 0, [0 1 0; 0 0 0; 0 1 0], [1 0 1; 0 0 0; 1 0 1] );
 L_system_tiling( 'test', 5, 2, 1, 0, '', 0, [1 0 0; 0 1 0; 0 0 1], [1 1 0; 1 0 1; 0 1 1] );
L_system_tiling( 'test', 5, 2, 1, 0, '', 0, [1 0 0; 0 1 0; 0 0 1], [0 0 1; 0 1 0; 1 0 0] );
L_system_tiling( 'test', 6, 2, 1, 0, '', 0, [1 0 0; 0 1 0; 0 0 1], [1 1 0; 1 0 1; 0 1 1] );
L_system_tiling( 'test', 6, 2, 1, 0, '', 0, [1 0 0; 0 1 0; 0 0 1], [0 1 0; 1 0 1; 0 1 0] );
L_system_tiling( 'test', 6, 2, 1, 0, '', 0, [0 0 1; 1 0 1; 1 1 0], [1 1 1; 1 1 1; 1 1 1] );
L_system_tiling( 'test', 6, 2, 1, 0, '', 0, [0 0 1; 1 0 0; 1 1 0], [1 1 1; 1 1 1; 1 1 1] );
L_system_tiling( 'test', 6, 2, 1, 0, '', 0, [0 0 0; 1 0 0; 1 1 0], [1 1 1; 1 1 1; 1 1 1] ); % Seirpinski
L_system_tiling( 'test', 6, 2, 1, 0, '', 0, [0 0 0; 0 0 0; 1 0 0], [1 1 1; 1 1 1; 1 1 1] );
L_system_tiling( 'test', 6, 2, 1, 0, '', 0, [1 1 0; 1 0 1; 0 1 1], [1 0 0; 0 1 0; 0 0 1] );

L_system_tiling( 'test', 6, 2, 1, 0, '', 0, [0 0 1; 1 0 1; 1 0 0], [1 1 1; 1 1 1; 1 1 1] ); % Terminating

L_system_tiling( 'X', 6, 2, 1, 0, '', 0, [0 1 0; 1 0 1; 0 1 0], [1 1 1; 1 1 1; 1 1 1] );
L_system_tiling( 'HI', 6, 2, 1, 0, '', 0, [0 1 0; 0 0 0; 0 1 0], [1 1 1; 1 1 1; 1 1 1] );
L_system_tiling( 'test', 6, 2, 1, 0, '', 0, [6 0 1; 1 8 1; 1 10 2], [1 1 1; 1 1 1; 1 1 1] ); % Hairy boundary
L_system_tiling( 'test', 6, 2, 1, 0, '', 0, [0 6 4; 2 1 1; 4 1 1], [1 1 1; 1 1 1; 1 1 1] );
L_system_tiling( 'test', 5, 2, 1, 0, '', 0, [4 6 4; 1 1 2; 1 1 4], [1 1 1; 1 1 1; 1 1 1] );
L_system_tiling( 'test', 5, 2, 1, 0, '', 0, [0 0 0; 1 1 6; 1 1 0], [1 1 1; 1 1 1; 1 1 1] );
L_system_tiling( 'test', 5, 2, 1, 0, '', 0, [0 6 0; 1 1 2; 1 1 0], [1 1 1; 1 1 1; 1 1 1] );




L_system_tiling( 'test', 6, 3, 1, 0, '', 1, [0 0 0; 0 1 0; 0 0 0], [0 0 0; 2 1 0; 2 2 2], [2 2 2; 2 1 2; 2 2 2] );
L_system_tiling( 'test', 6, 3, 1, 0, '', 1, [0 0 0; 0 1 0; 0 0 0], [0 2 0; 1 1 1; 2 0 2], [2 2 2; 2 1 2; 2 2 2] );
L_system_tiling( 'test', 6, 3, 1, 0, '', 1, [0 0 0; 0 1 0; 0 0 0], [0 2 0; 0 1 2; 2 0 2], [2 2 2; 2 1 2; 2 2 2] );
L_system_tiling( 'test', 6, 3, 1, 0, '', 1, [0 0 0; 0 1 0; 0 0 0], [0 0 2; 2 1 2; 2 0 0], [2 2 2; 2 1 2; 2 2 2] );
L_system_tiling( 'test', 6, 3, 1, 0, '', 1, [0 0 0; 0 2 0; 0 0 0], [0 0 2; 2 1 2; 2 0 0], [2 2 2; 2 0 2; 2 2 2] );
L_system_tiling( 'test', 6, 3, 1, 0, '', 1, [0 0 0; 0 1 0; 0 0 0], [0 0 1; 0 1 2; 1 2 2], [2 2 2; 2 1 2; 2 2 2] );
L_system_tiling( 'test', 6, 3, 1, 0, '', 1, [0 0 0; 0 2 0; 0 0 0], [0 0 2; 2 4 2; 2 0 0], [2 2 2; 2 0 2; 2 2 2] );
L_system_tiling( 'test', 6, 3, 1, 0, '', 1, [0 0 0; 0 4 0; 0 0 0], [0 0 2; 2 4 2; 2 0 0], [2 2 2; 2 4 2; 2 2 2] );
L_system_tiling( 'test', 6, 3, 1, 0, '', 1, [4 4 4; 4 0 4; 4 4 4], [0 0 2; 2 4 2; 2 0 0], [4 4 4; 4 2 4; 4 4 4] );
L_system_tiling( 'test', 6, 3, 1, 0, '', 1, [4 4 4; 4 2 4; 4 4 4], [0 0 2; 2 4 2; 2 0 0], [4 4 4; 4 0 4; 4 4 4] );

L_system_tiling( 'test', 6, 3, 1, 0, '', 1, [0 2 0; 1 0 1; 0 2 0], [1 0 1; 2 1 2; 1 0 1], [2 1 2; 0 2 0; 2 1 2] );

L_system_tiling( 'test', 6, 3, 1, 0, '', 1, [2 2 1; 1 3 1; 1 2 2], [0 0 2; 2 4 2; 2 0 0], [1 1 0; 0 5 0; 0 1 1] );

L_system_tiling( 'test', 6, 2, 1, 0, '', 0, [1 1 0; 0 0 0; 0 1 1], [1 1 0; 0 1 0; 0 1 1] );
L_system_tiling( 'test', 6, 2, 1, 0, '', 0, [3 3 0; 0 0 0; 0 3 3], [1 1 2; 2 1 2; 2 1 1] );
L_system_tiling( 'test', 6, 2, 1, 0, '', 0, [1 1 0; 0 2 0; 0 1 1], [0 0 1; 1 3 1; 1 0 0] );
L_system_tiling( 'test', 6, 2, 1, 0, '', 0, [1 1 2; 2 2 2; 2 1 1], [0 0 3; 3 3 3; 3 0 0] );
L_system_tiling( 'test', 6, 2, 1, 0, '', 0, [1 1 2; 2 2 2; 2 1 1], [3 3 0; 0 3 0; 0 3 3] );

L_system_tiling( 'test', 6, 4, 1, 0, '', 0, [1 1 0; 0 0 0; 0 1 1], [2 2 1; 1 1 1; 1 2 2], [3 3 2; 2 2 2; 2 3 3], [0 0 3; 3 3 3; 3 0 0] );
L_system_tiling( 'test', 6, 4, 1, 0, '', 0, [1 1 0; 0 0 0; 0 1 1], [1 1 2; 2 1 2; 2 1 1], [3 3 2; 2 2 2; 2 3 3], [3 3 0; 0 3 0; 0 3 3] );

L_system_tiling( 'test', 6, 3, 1, 0, '', 1, [0 0 0; 0 0 0; 0 0 0], [0 2 0; 0 1 2; 2 0 2], [2 2 2; 2 2 2; 2 2 2] );
L_system_tiling( 'test', 6, 3, 1, 0, '', 1, [0 0 0; 0 0 0; 0 0 0], [0 0 0; 0 1 2; 2 2 2], [2 2 2; 2 2 2; 2 2 2] );
L_system_tiling( 'test', 6, 3, 1, 0, '', 1, [0 0 0; 0 0 0; 0 0 0], [0 0 0; 0 4 2; 2 2 2], [2 2 2; 2 2 2; 2 2 2] );
L_system_tiling( 'test', 6, 3, 1, 0, '', 1, [0 0 0; 0 0 0; 0 0 0], [0 0 0; 0 7 2; 2 2 2], [2 2 2; 2 2 2; 2 2 2] );
L_system_tiling( 'test', 6, 3, 1, 0, '', 1, [0 0 0; 0 0 0; 0 0 0], [0 0 0; 0 10 2; 2 2 2], [2 2 2; 2 2 2; 2 2 2] );
L_system_tiling( 'test', 6, 3, 1, 0, '', 1, [0 0 0; 0 0 0; 0 0 0], [0 0 2; 2 1 2; 2 0 0], [2 2 2; 2 2 2; 2 2 2] );

L_system_tiling( 'BF', 9, 4, 1, 0, '', 0, [0 2; 2 0], [0 3; 3 0], [1 2; 2 1], [1 3; 3 1] ); % Dragon curve (paper folding) sequence
L_system_tiling( 'BF', 9, 4, 1, 0, '', 0, [10 12; 12 10], [10 13; 13 10], [11 12; 12 11], [11 13; 13 11] );


% Diagonal systems
L_system_tiling( 'BF', 8, 4, 1, 0, '', 0, [0 11; 11 0], [12 10; 10 12], [13 10; 10 13], [11 10; 10 11] );
L_system_tiling( 'BF', 9, 4, 1, 0, '', 0, [0 11; 11 0], [10 12; 12 10], [10 13; 13 10], [10 11; 11 10] );

L_system_tiling( 'BF', 9, 8, 1, 0, '', 0, [1 4; 4 1], [0 5; 5 0], [13 16; 16 13], [12 17; 17 12], [13 10; 10 13], [12 11; 11 12], [15 13; 13 15], [14 12; 12 14] );
\



References

Plane filling curves, Cut-the-knot

Walter Wunderlich's (3rd) Peano curve variation

Sagan, Space-Filling Curves, Springer-Verlag, 1994

SquaRecurves, E-Tours, Eddies, and Frenzies: Basic Families of Peano Curves on the Square Grid
Douglas M. McKenna
A chapter from The Lighter Side of Mathematics - Proceedings of the Eugene Strens Memorial Conference on Recreational Mathematics and its History, Math. Assoc. of America, 1994


Tag-systems for the Hilbert curve
Patrice Séébold
Journal of Automata, Languages and Combinatorics

Hilbert words correspond to finite approximations of the Hilbert space filling curve. The Hilbert infinite word H is obtained as the limit of these words. It gives a description of the Hilbert (infinite) curve. We give a uniform tag-system to generate automatically H and, by showing that it is almost cube-free, we prove that it cannot be obtained by simply iterating a morphism.


Graphical applications of L−systems
Przemyslaw Prusinkiewicz

A new method for generating pictures is presented and illustrated with examples. The idea is to generate a string of symbols using an L−system, and to interpret this string as a sequence of commands which control a "turtle". Suitable generalizations of the notions of the L−system and of a turtle are introduced. The resulting mathematical model can be used to create a variety of (finite approximations of) fractal curves, ranging from Koch curves, to classic space−filling curves, to relatively realistic−looking pictures of plants and trees. All these pictures are defined in a uniform and compact way.
------------------------------------
There are no restrictions on use of the images on this page. Claiming to be the originator of the material, explicitly or implicitly, is bad karma. A link (if appropriate), a note to dow[at]uoregon.edu, and credit are appreciated but not required.

 Comments are welcome (dow[at]uoregon.edu).