Geometric patterns and self-similarity are abundant in plant life, and so it is natural to look for a mathematical way to describe and perhaps lend understanding to these patterns. The concept of an L-system, developed in 1968 by Aristid Lindenmayer, was initially used in the study of formal languages, but soon came to be recognized as a mechanism for modeling various plant-like structures. The idea of repetition is inherent in L-systems, and so the geometric objects that result from application of an L-system have fractal properties.
L-Systems
An L-system is a scheme for rewriting strings of symbols -- "words" formed out of a very limited "alphabet." The rewriting takes place by replacing certain strings of characters in a word by other strings of characters. These replacements often utilize repetitions of the string of characters being replaced, and so complex strings are built up from simple strings, the complex strings containing replications of the basic strings. To give geometric life to a string of characters, we interpret a character string as a sequence of geometric drawing instructions using a scheme that is commonly referred to as "turtle graphics": the geometric object is formed out of the trail left by a "turtle" that follows very specific but brief motions. When many of these motions are put together -- because the character string is very long -- we obtain a geometric object that would be very difficult to describe by standard Euclidean geometry.
In this vignette, we will look at a simplified L-system scheme, which
is limited to 2-dimensional drawings, and which does not allow for any
randomness in the generation of strings. A more complex L-system
scheme would allow for the generation of 3-dimensional objects, and also
for an element of chance in the way an object is drawn. In our simplified
scheme, our alphabet consists of the six symbols F, b, [, ], + and -, with
the following geometric interpretations:
F | Move forward one step, drawing the path of motion |
b | Move forward one step, but do not draw |
[ | Begin a branch |
] | End a branch |
+ | Increase angle of direction by amount |
- | Decrease angle of direction by amount |
To specify a particular L-system, we include:
A Simple L-System
As an example, consider the L-system defined as follows:
Axiom | F |
Angle | 60^{o} |
Rule |
Applying the rewriting rule repeatedly, we obtain the following sequence
of strings:
Step | String |
0 | F |
1 | F + F - - F + F |
2 | F + F - - F + F + F + F - - F + F - - F + F - - F + F + F + F - - F + F |
The colors are used to show you how each of the F's in step 1
is replaced by the string F + F - - F + F at step 2. At step
3, each of the F's would again be replaced by F + F - - F + F,
giving a total of 64 F's (and a bunch of +'s and -'s to boot).
Only time and patience limit how far you could carry out the string replacements.
At whatever level you choose, you simply stop the string replacements,
and pass the current string to a turtle graphics processor to be drawn.
For this particular L-system, here is the sequence of images that result,
for steps 0 through 3:
Step 0 | |
Step 1 | |
Step 2 | |
Step 3 |
You may recognize the shape that is being formed as the Koch curve, which was introduced in Vignette 3. Notice that, at each step, we adjust the size of a turtle step, so as to make the entire image fit into the same size space each time.
But What About Plants?
By introducing the branching symbols, and by changing the axiom, angle
and/or production rules, we can alter the finished geometric object so
that it looks considerably more plant-like. The branching symbol
"[" will be interpreted by a turtle graphics processor as meaning that
the present location should be remembered, and when the matching symbol
"]" is encountered, go back to that location and continue to process the
turtle steps and turns. As an example, consider the L-system
Axiom: | F |
Angle: | 30^{o} |
Rule: |
The first several steps give us the following geometric images:
Step 1 | |
Step 2 | |
Step 3 | |
Step 4 |
At step n, there are 6^{n} turtle steps required, so that step 4 requires 6^{4} = 1296 steps!
Minor variations of this L-system give us other plant-like images:
Whether an image is drawn horizontally or vertically is determined simply by the original direction of the turtle.
Even more realism can be added to our plant-like images by incorporating some element of randomness into when the branching occurs and the angle of branching, and also by including the ability to branch in 3-dimensional space rather than in just two dimensions. These options are discussed in some of the references below.
Further Exploration