L-System User Notes
(Lindenmayer Systems)
Written by Paul Bourke
Version 2.5, July 1991
Introduction
This program implements some of the L-Systems discussed in "Lecture Notes in
Biomathematics" by Przemyslaw Prusinkiewcz and James Hanan. A brief description
of an 0L system will be presented here but for a more complete description the
user should consult the literature.
The application was initially written to investigate methods of incorporating
objects with a large number of drawing elements (lines, polygons) into a CAD
package. L Systems is one way for example of "generating" trees at the
rendering stage but not during the editing stage where the image complexity
will slow down the response time.
Simple example of a 0L system
A string of characters (symbols) is rewritten on each iteration according to
some replacement rules. Consider an initial string (axiom)
F+F+F+F
and a rewriting rule
F --> F+F-F-FF+F+F-F
After one iteration the following string would result
F+F-F-FF+F+F-F + F+F-F-FF+F+F-F + F+F-F-FF+F+F-F + F+F-F-FF+F+F-F
For the next iteration the same rule is applied but now to the string resulting
from the last iteration
F+ F-F-FF+ F+ F-F+ F+ F-F-FF+ F+ F-F-F+ F-F-FF+ F+ F-F-F+ F-F-FF+ F+ F-FF+
F-F-FF+ F+ F-F+ F+ F-F-FF+ F+ F-F+ F+ F-F-FF+ F+ F-F-F+ F-F-FF+ F+ F-F+ F+
F-F-FF+ F+ F-F+ F+ F-F-FF+ F+ F-F-F+ F-F-FF+ F+ F-F-F+ F-F-FF+ F+ F-FF+ F-F-FF+
F+ F-F+ F+ F-F-FF+ F+ F-F+ F+ F-F-FF+ F+ F-F-F+ F-F-FF+ F+ F-F+ F+ F-F-FF+ F+
F-F+ F+ F-F-FF+ F+ F-F-F+ F-F-FF+ F+ F-F-F+ F-F-FF+ F+ F-FF+ F-F-FF+ F+ F-F+ F+
F-F-FF+ F+ F-F+ F+ F-F-FF+ F+ F-F-F+ F-F-FF+ F+ F-F+ F+ F-F-FF+ F+ F-F+ F+
F-F-FF+ F+ F-F-F+ F-F-FF+ F+ F-F-F+ F-F-FF+ F+ F-FF+ F-F-FF+ F+ F-F+ F+ F-F-FF+
F+ F-F+ F+ F-F-FF+ F+ F-F-F+ F-F-FF+ F+ F-F
Some symbols are now given a graphical meaning, for example, F means move
forward drawing a line, + means turn right by some predefined angle (90 degrees
in this case), - means turn left.
Using these symbols the initial string F+F+F+F is just a rectangle (ø =
90). The replacement rule F --> F+F-F-FF+F+F-F replaces each forward
movement by the following figure
The first iteration interpreted graphically is
|
|
The next iteration interpreted graphically is:
|
and so on.
|
Example:
Axiom X
F --> FF
X --> F-[[X]+X]+F[+FX]-X
ø = 22.5
|
|
Example:
Axiom F+F+F+F
F --> FF+F-F+F+FF
ø = 90
|
|
Symbols
The following characters have a geometric interpretation.
Character Meaning
F Move forward by line length drawing a line
f Move forward by line length without drawing a line
+ Turn left by turning angle
- Turn right by turning angle
| Reverse direction (ie: turn by 180 degrees)
[ Push current drawing state onto stack
] Pop current drawing state from the stack
# Increment the line width by line width increment
! Decrement the line width by line width increment
@ Draw a dot with line width radius
{ Open a polygon
} Close a polygon and fill it with fill colour
> Multiply the line length by the line length scale factor
< Divide the line length by the line length scale factor
& Swap the meaning of + and -
( Decrement turning angle by turning angle increment
) Increment turning angle by turning angle increment
When drawing the graphical representation of the L string all other characters
are ignored.
The user may choose and use any other single printable characters for the
replacement rules except, note: this excludes "white" characters such as spaces
and tabs. For context sensitive L systems the * character is used to represent
any match.
See the SYMBOL menu item for a summary of the reserved symbols.
Menus
|
As
with most applications the ABOUT menu item located in the Apple menu before the
desk accessories displays information such as the version number and contact
address of the developer.
|
|
This
is the standard FILE menu although some of the items are not implemented.
NEW resets all the variables including the rules to their default values.
OPEN to load a rule description file previously saved or possibly created with
a text editor.
SAVE and SAVE AS create rule description files.
PRINT and PAGESETUP control direct printing.
QUIT to exit from the program when finished.
|
|
The standard EDIT menu. The first 5 items are only included for compatibility
reasons and do not apply to this application. (they are used with desk
accessories in some cases)
The two special copy items allow images to be transferred to other applications
depending on the preferred data type. Line drawings should be copied for CAD
packages and bitmaps for painting programs.
Normally images will be scaled to fit the window, it is possible to zoom in or
out of areas with the last two items.
|
|
This is the main menu for this application.
REDRAW updates the current display, for example, if the drawing was cancelled
with clover-. (period)
Menu items 2 through 4 control the iteration depth. RESET sets it to 0, the
number of iterations to compute may be incremented, decremented, or set to any
particular number.
FRAME, FILL and BACKGROUND are pop-up menus that allow the colour of the lines,
polygon fills and background to be set.
PRODUCTIONS allows the current rules to be altered. AXIOM menu item sets the
initial string. STATE menu item varies environment variables. SYMBOL LIST
displays the meaning given to various predefined and reserved symbols.
The type of system is selectable from the last 3 items.
|
|
This
contains a number of predefined image specifications grouped together in
categories given by the pop-up menu names.
Users are encouraged to submit further examples that can be added to this
library.
|
Advanced features/comments
Always ensure that the '[' and ']' brackets match in number, ie: there
should always be the same number of each type. If not a stack overflow will
quickly occur, a message displayed, and the iteration depth decremented. Note:
non matching brackets are not tested before the string in interpreted, a
problem only occurs when a stack overflow situation is encountered.
Polygons (using "{" and "}") cannot be nested, ie: there can only be one
open at a time. If a polygon open symbol "{" is encountered while another
polygon is still open it will be ignored. If a polygon is left open when the
end of the string is reached it will be automatically closed.
For a complete list of predefined symbol meanings look at the SYMBOL list
under the ACTION menu.
Best quality hardcopy line drawing images can be obtained by using
MacDraw or Claris CAD. In both cases copy the image as a line drawing, paste it
into MacDraw say, set the lines to black and line width 0.1mm, then print on a
LaserWriter. Note: the number of lines can quickly approach the thousands and
even tens of thousands, don't expect the printing to be fast.
Time consuming drawing may be cancelled by typing clover-. (period)
The maximum length of the strings generated is 300,000 symbols.
Attempting to exceed this will give an error message and automatic decrementing
of the iteration count.
The maximum stack depth is 100. This means that a bracketed string cannot
have brackets nested more than 100 deep.
ie: [ [ [ ] ] [ [ [ [ ] ] [ ] ] ] ]
1 2 3 2 1 2 3 4 5 4 3 4 3 2 1 0 is nested 5 deep
If the maximum stack depth is exceeded an appropriate error message will be
displayed and the iteration depth decremented until the stack no longer
overflows.
When copying to the clipboard as lines make the drawing window as large
as possible for maximum resolution.
References
Heinz-Otto and Deitmar Saupe.
The Science of Fractal Images.
Springer-Verlag
Przemyslaw Prusinkiewicz.
Application of L-Systems to Computer Imagery.
Lecture Notes in Computer Science #291, Pages 534-548
Przemyslaw Prusinkiewicz, James Hanan.
Lecture Notes in Biomathematics #79
Prusinkiewicz, P.
Graphical Applications of L-Systems.
Proc. of Graphics Interface 1986 - Vision Interface, 1986, Pages 247-253.
Smith, A.R.
Plants, Fractals, and Formal Languages.
Computer Graphics, 18, 3, 1984, Pages 1-10
Prusinkiewicz, P and Lindenmayer A.
The Algorithmic Beauty of Plants.
Springer Verleg, 1990, Pages 40-50
L-System Leaf
Written by Paul Bourke
axiom = a
F -> >F<
a -> F[+x]Fb
b -> F[-y]Fa
x -> a
y -> b
angle = 45
length factor = 1.36
|
|
L-System Bushes
Written by Paul Bourke
axiom = Y
X -> X[-FFF][+FFF]FX
Y -> YFX[+Y][-Y]
angle = 25.7
|
|
axiom = F
F -> FF+[+F-F-F]-[-F+F+F]
angle = 22.5
|
|
axiom = F
F -> F[+FF][-FF]F[-F][+F]F
angle = 35
|
|
Attributed to Saupe
axiom = VZFFF
V -> [+++W][---W]YV
W -> +X[-W]Z
X -> -W[+X]Z
Y -> YZ
Z -> [-FFF][+FFF]F
angle = 20
|
|
axiom = FX
X -> >[-FX]+FX
angle = 40
|
|
L-System sticks
Written by Paul Bourke
axiom = X
F -> FF
X -> F[+X]F[-X]+X
angle = 20
|
|
L-System algae
Written by Paul Bourke
axiom = aF
a -> FFFFFv[+++h][---q]fb
b -> FFFFFv[+++h][---q]fc
c -> FFFFFv[+++fa]fd
d -> FFFFFv[+++h][---q]fe
e -> FFFFFv[+++h][---q]fg
g -> FFFFFv[---fa]fa
h -> ifFF
i -> fFFF[--m]j
j -> fFFF[--n]k
k -> fFFF[--o]l
l -> fFFF[--p]
m -> fFn
n -> fFo
o -> fFp
p -> fF
q -> rfF
r -> fFFF[++m]s
s -> fFFF[++n]t
t -> fFFF[++o]u
u -> fFFF[++p]
v -> Fv
angle = 12
|
|
axiom = aF
a -> FFFFFy[++++n][----t]fb
b -> +FFFFFy[++++n][----t]fc
c -> FFFFFy[++++n][----t]fd
d -> -FFFFFy[++++n][----t]fe
e -> FFFFFy[++++n][----t]fg
g -> FFFFFy[+++fa]fh
h -> FFFFFy[++++n][----t]fi
i -> +FFFFFy[++++n][----t]fj
j -> FFFFFy[++++n][----t]fk
k -> -FFFFFy[++++n][----t]fl
l -> FFFFFy[++++n][----t]fm
m -> FFFFFy[---fa]fa
n -> ofFFF
o -> fFFFp
p -> fFFF[-s]q
q -> fFFF[-s]r
r -> fFFF[-s]
s -> fFfF
t -> ufFFF
u -> fFFFv
v -> fFFF[+s]w
w -> fFFF[+s]x
x -> fFFF[+s]
y -> Fy
angle = 12
|
|
L-System Weed
Written by Paul Bourke
axiom = F
F -> FF-[XY]+[XY]
X -> +FY
Y -> -FX
angle = 22.5
|
|
Triangle
Written by Paul Bourke
July 1990
L-Systems
axiom = F+F+F
F -> F-F+F
angle = 120
As an IFS
The IFS equations are as follows
xn+1 = a xn + b yn + e
yn+1 = c xn + d yn + f
The parameter table:
set 1 set 2 set 3
a 0.0 0.0 0.0
b 0.577 0.577 0.577
c -0.577 -0.577 -0.577
d 0.0 0.0 0.0
e 0.0951 0.4413 0.0952
f 0.5983 0.7893 0.9893
probability 1/3 1/3 1/3
Quadratic Gosper
Written by Paul Bourke
June 1990
Attributed to Dekking, 1982
axiom = -YF
X -> XFX-YF-YF+FX+FX-YF-YFFX+YF+FXFXYF-FX+YF+FXFX+YF-FXYF-YF-FX+FX+YFYF-
Y -> +FXFX-YF-YF+FX+FXYF+FX-YFYF-FX-YF+FXYFYF-FX-YFFX+FX+YF-YF-FX+FX+YFY
angle = 90
Square Sierpinski
Written by Paul Bourke
August 1990
First reported circa 1912
axiom = F+XF+F+XF
X -> XF-F+F-XF+F+XF-F+F-X
angle = 90
Crystal
Written by Paul Bourke
June 1990
axiom = F+F+F+F
F -> FF+F++F+F
angle = 90
Derby, Western Australia
Peano Curve
Written by Paul Bourke
June 1990
First documented circa 1890
axiom = X
X -> XFYFX+F+YFXFY-F-XFYFX
Y -> YFXFY-F-XFYFX+F+YFXFY
angle = 90
Quadratic Snowflake
Written by Paul Bourke
July 1990
axiom = F
F -> F-F+F+F-F
angle = 90
Variation by Hasan Hosam.
December 2018
axiom = FF+FF+FF+FF
F -> F+F-F-F+F
angle = 90
Quadratic Koch Island
Written by Paul Bourke
July 1990
axiom = F+F+F+F
F -> F+F-F-FFF+F+F-F
angle = 90
String length: 63
String length: 567
String length: 5103
String length: 45927
axiom = F+F+F+F
F -> F-FF+FF+F+F-F-FF+F+F-F-FF-FF+F
angle = 90
Variation by Hasan Hosam.
December 2018
axiom = X+X+X+X+X+X+X+X
X -> X+YF++YF-FX--FXFX-YF+X
Y -> -FX+YFYF++YF+FX--FX-YF
angle = 45
Koch Curve
Written by Paul Bourke
June 1990
Fractal Dimension: 1.5
axiom = F+F+F+F
F -> F+F-F-FF+F+F-F angle = 90
Board
Written by Paul Bourke
June 1990
axiom = F+F+F+F
F -> FF+F+F+F+FF
angle = 90
Hilbert
Written by Paul Bourke
June 1990
Attributed to the German mathematician David Hilbert, circa 1891
axiom = X
X -> -YF+XFX+FY-
Y -> +XF-YFY-FX+
angle = 90
Sierpinski Arrowhead
Written by Paul Bourke
June 1990
axiom = YF
X -> YF+XF+Y
Y -> XF-YF-X
angle = 60
YF+XF+YF-XF-YF-XF-YF+XF+YF
XF-YF-XF+YF+XF+YF+XF-YF-XF-YF+XF+YF-XF-YF-XF-YF+XF+YF-XF-YF-XF+YF+XF+YF+XF-YF-XF
YF+XF+YF-XF-YF-XF-YF+XF+YF+XF-YF-XF+YF+XF+YF+XF-YF-XF+YF+XF+YF-XF-YF-XF-YF+XF+YF
-XF-YF-XF+YF+XF+YF+XF-YF-XF-YF+XF+YF-XF-YF-XF-YF+XF+YF-XF-YF-XF+YF+XF+YF+XF-YF-X
F-YF+XF+YF-XF-YF-XF-YF+XF+YF+XF-YF-XF+YF+XF+YF+XF-YF-XF+YF+XF+YF-XF-YF-XF-YF+XF+YF
XF-YF-XF+YF+XF+YF+XF-YF-XF-YF+XF+YF-XF-YF-XF-YF+XF+YF-XF-YF-XF+YF+XF+YF+XF-YF-XF
+YF+XF+YF-XF-YF-XF-YF+XF+YF+XF-YF-XF+YF+XF+YF+XF-YF-XF+YF+XF+YF-XF-YF-XF-YF+XF+Y
F+XF-YF-XF+YF+XF+YF+XF-YF-XF-YF+XF+YF-XF-YF-XF-YF+XF+YF-XF-YF-XF+YF+XF+YF+XF-YF-
XF-YF+XF+YF-XF-YF-XF-YF+XF+YF+XF-YF-XF+YF+XF+YF+XF-YF-XF+YF+XF+YF-XF-YF-XF-YF+XF
+YF-XF-YF-XF+YF+XF+YF+XF-YF-XF-YF+XF+YF-XF-YF-XF-YF+XF+YF-XF-YF-XF+YF+XF+YF+XF-Y
F-XF-YF+XF+YF-XF-YF-XF-YF+XF+YF+XF-YF-XF+YF+XF+YF+XF-YF-XF+YF+XF+YF-XF-YF-XF-YF+
XF+YF-XF-YF-XF+YF+XF+YF+XF-YF-XF-YF+XF+YF-XF-YF-XF-YF+XF+YF-XF-YF-XF+YF+XF+YF+XF
-YF-XF+YF+XF+YF-XF-YF-XF-YF+XF+YF+XF-YF-XF+YF+XF+YF+XF-YF-XF+YF+XF+YF-XF-YF-XF-Y
F+XF+YF+XF-YF-XF+YF+XF+YF+XF-YF-XF-YF+XF+YF-XF-YF-XF-YF+XF+YF-XF-YF-XF+YF+XF+YF+
XF-YF-XF
String length: 2186
String length: 6560
Von Koch Snowflake
Written by Paul Bourke
June 1990
Fractal Dimension: log(4)/log(3) = 1.262
L-Systems
axiom = F++F++F
F -> F-F++F-F
angle = 60
IFS
The IFS equations are as follows
xn+1 = a xn + b yn + e
yn+1 = c xn + d yn + f
The parameter table:
set 1 set 2 set 3 set 4
a 0.3330 0.3330 0.1670 0.1670
b 0.0000 0.0000 -0.2890 0.2890
c 0.0000 0.0000 0.2890 -0.2890
d 0.3330 0.3330 0.1670 0.1670
e -0.3330 0.3330 -0.0830 0.0830
f 0.0000 0.0000 0.1440 0.1440
Cross
Written by Paul Bourke
June 1990
axiom = F+F+F+F
F -> F+FF++F+F
angle = 90
Cross
Written by Paul Bourke
August 1990
axiom = F+F+F+F
F -> F+F-F+F+F
angle = 90
Pentaplexity
Written by Paul Bourke
September 1990
axiom = F++F++F++F++F
F -> F++F++F|F-F++F
angle = 36
If your L-Systems software doesn't support the "|" symbol (like the implementation
in the PGF/TikZ), then just replace the "|" with "+++++".
Tiles
Written by Paul Bourke
June 1990
Fractal Dimension: log(7)/log(3) = 1.771
axiom = F+F+F+F
F -> FF+F-F+F+FF
angle = 90
Rings
Written by Paul Bourke
June 1990
axiom = F+F+F+F
F -> FF+F+F+F+F+F-F
angle = 90
Dragon Curve
Written by Paul Bourke
August 1990
Attributed to David and Knuth, 1970
axiom = FX
X -> X+YF+
Y -> -FX-Y
angle = 90
Hexagonal Gosper
Written by Paul Bourke
July 1990
Attributed to Mandelbrot, 1982
axiom = XF
X -> X+YF++YF-FX--FXFX-YF+
Y -> -FX+YFYF++YF+FX--FX-Y
angle = 60
Lévy curve
Written by Paul Bourke
February 2019
axiom = F
F -> -F++F-
angle = 45
Classic Sierpinski Curve
Written by Paul Bourke
Rules by Chris Wallace
November 2019
axiom = F--XF--F--XF
X -> XF+F+XF--F--XF+F+X
angle = 45
Krishna Anklets
Written by Paul Bourke
axiom = -X--X
X -> XFX--XFX
angle = 45
Mango Leaf
Written by Paul Bourke
axiom = Y---Y
X -> {F-F}{F-F}--[--X]{F-F}{F-F}--{F-F}{F-F}--
Y -> f-F+X+F-fY
angle = 60
Snake Kolam
Written by Paul Bourke
axiom = F+XF+F+XF
X -> X{F-F-F}+XF+F+X{F-F-F}+X
angle = 90
Kolam
January 2019
axiom = (-D--D)
A -> F++FFFF--F--FFFF++F++FFFF--F
B -> F--FFFF++F++FFFF--F--FFFF++F
C -> BFA--BFA
D -> CFC--CFC
angle = 45
Kolams from India
Kolam patterns from the South of India, drawn by rice powder in front of
houses every morning before the doorway is used.
|