Fractint L-System Spacefilling Curves

A tutorial by William McWorter
mcworter@midohio.net
version 1.4
January 1997

Back to Tutorial Index




SPACEFILLING CURVES


It was profoundly disturbing to mathematicians to discover that 1-dimensional curves exist that fill 2-dimensional space. A famous example is Heighway's Dragon curve. It was originally formed by paperfolding. Take a long strip of paper laid out in front of you from left to right. Fold the right end over the left end. Next fold the right end of the result over the left end, fold the right end of the result over the left end, and so on. It is claimed that you can't do this more than seven times because it would be like trying to fold a 128 page book in half. Now open each fold to 90 degrees. The result looks like a scaly dragon. Here is an L-system to draw this curve.


Hiway { 
  Angle 4
  Axiom fx
  x=fx+fy
  y=fx-fy
  f=
  }

x represents the first half of the curve and y represents the second half. After FRACTINT draws the first half, no matter what orientation FRACTINT is in when it finishes drawing the first half, it must turn left 90 degrees because that is the middle fold, the very first fold created in the folding process. The second half y is exactly the same as the first half x but it is traced backwards. This is why the replacement string for x is fx+fy and the replacement string for y is fx-fy, x backwards. This L-system is somewhat simpler and more efficient than Adrian Mariano's Dragon L-system in fractint.l. Adrian's L-system has the feature that the beginning and end of the curve form the endpoints of a horizontal line at all orders, while the above L-system has these endpoints turning left 45 degrees with each increase in order.

While studying Heighway's dragon, Davis and Knuth invented their own spacefilling curve called the Terdragon. It's L-system is:

Terdragon {
  Angle 3   ; Only need turns of 120=360/3 degrees
  Axiom f   ; Draw one Terdragon
  f=f+f-f   ; Replace with the Terdragon, turn left, another Terdragon, turn right, another
            ; Terdragon
  }

The above spacefilling curves were invented long after the mathematical crisis engendered by spacefilling curves. One of the original crisis-makers was Peano's spacefilling curve. Here is an L-system to render Peano's curve.


Peano1 { ; Adrian Mariano
; from The Fractal Geometry of Nature by Mandelbrot
  Angle 4
  Axiom F
  F=F-F+F+F+F-F-F-F+F
  }

I've changed the axiom line of Peano1 in the file fractint.l so that only Peano's original curve shows. Note that FRACTINT ignores text following a ";" and also ignores case; "F" is the same as "f" to FRACTINT.

Another recently discovered spacefilling curve was invented by Dekking. I include it here because it exemplifies the case where a figure is made up of parts dissimilar from each other.

Dekking { ; Dekking's Church
  ; Advances in Math, vol. 44, 1982, pp. 78-104
  Angle 4
  Axiom C32WC06ZC15YC06X
  F=
  W=FW+F-XFW-F+Z
  X=++F--Y-F+Z++F--Y-F+Z
  Y=++F--Y+F-X
  Z=FW+F-X
  }

Note that each part, W, X, Y, Z, has a different replacement string. Note also that each + or - that precedes an f is followed by its opposite. This is because FRACTINT does not allow replacing + and - by nothing (maybe in version 19.6?). The strings "c32", "c06", and "c15" tell Fractint to color the following lines in the color in the color palette in the position indicated by the number following the "c".

This curve looks like a church on which a mural is painted reminiscent of the painting of God giving life to Adam.

Earlier I described a tiling involving dissecting two isosceles triangles. This tiling was chosen in such a way that I could create a spacefilling curve based on the tiling. Here is the resulting L-system.


Pentive3 { 
  Angle 10
  Axiom q
  f=
  p=--fr++++fs--fu
  q=ft++fr----fs++
  r=++fp----fq++ft
  s=fu--fp++++fq--
  t=+fu--fp+
  u=-fq++ft-
  }

All of the spacefilling curves described so far revisit certain points, but there are many spacefilling curves which never revisit any points. An example is the Cross. It is named so because there is an underlying tiling of crosses.

Cross {
  Angle 4
  Axiom FX
  X=FX+FX+FXFY-FY-
  Y=+FX+FXFY-FY-FY
  F=
  }

The symbol X tells FRACTINT how the Cross is made up. It says draw X, turn left, draw X, turn left, draw X, draw Y (i.e., draw X backwards), turn right, draw Y, turn right. The F's precede each X and Y because, without them FRACTINT would create long strings of X's and Y's with no drawing commands. The replacement string for Y must do the same thing that the replacement string for X does only backwards. The text line "F=" is there to tell FRACTINT to replace each F by nothing so that F's used at one order are not involved in the next order.

Note also that the replacement strings for X and Y each have the same number of +'s as -'s. This is to insure that when FRACTINT is drawing the Cross it is oriented the same way after drawing X or Y as it was when it began drawing X or Y. This is the safe thing to do if you don't understand how the orientation may affect the outcome of your L-system.

There is another famous spacefilling curve that does not revisit any points due to Hilbert. It's discussion is relegated to the final section which follows the next section.



On to The next chapter or back to the Tutorial Index

Back to The Fractint Home Page. or back to The Fractint Index Page.

This page maintained by

Noel Giffin,
noel@triumf.ca