Lindenmayer systems
Lindenmayer systems
A Lindenmayer system, or L-system, is a parallel rewriting system and a type of formal grammar.
History and origins
History and origins
L-systems were introduced and developed in 1968 by Aristid Lindenmayer to capture the behaviour of cell divisions in multicellular organisms, where many divisions may
occur at the same time. Lindenmayer used them to model the growth patterns of algae and plants, but they can also be used for modelling fractals.
occur at the same time. Lindenmayer used them to model the growth patterns of algae and plants, but they can also be used for modelling fractals.
Derivation
Derivation
An L-system is defined by an alphabet of symbols that can be used to make strings, a collection of production rules that expand each symbol into some larger string of symbols, an initial “axiom” string from which to begin construction, and a mechanism for translating the generated strings into geometric structures.
◼
The first step is to create the alphabet:
In[95]:=
alphabet={"A","B"}
Out[95]=
{A,B}
◼
Then we define the substitution rules:
In[96]:=
rules={"A""AB","B""A"}
Out[96]=
{AAB,BA}
◼
Define the initial axiom:
In[97]:=
axiom="A"
Out[97]=
A
◼
The first generation of the system is, by definition, the axiom:
In[98]:=
LSystem[0,axiom_,rules_]:=axiom
◼
The following generations can be computed recursively:
In[99]:=
LSystem[generation_Integer,axiom_,rules_]:=StringReplace[LSystem[generation-1,axiom,rules],rules]
◼
Example for these rules:
In[100]:=
Manipulate[LSystem[n,axiom,rules],{n,0,8,1}]
Out[100]=
The result is a sequence of Fibonacci words.
◼
If we take the length of each string we obtain the Fibonacci sequence
In[101]:=
Manipulate[StringLength[LSystem[n,axiom,rules]],{n,0,16,1}]
Out[101]=
◼
The ratio B to A converges to the golden ratio
In[102]:=
Manipulate[N[Ratios[Map[StringCount[LSystem[n,axiom,rules],#]&,alphabet]][[1]]],{n,1,16,1}]
Out[102]=
Applications
Applications
The recursive nature of an L-system leads to self-similarity, hence fractal-like forms are easy to describe with L-systems.
Consider the Cantor set on a real line
Consider the Cantor set on a real line
◼
Create the alphabet:
In[103]:=
alphabetCantor={"1","0"}
Out[103]=
{1,0}
◼
Define the rules of substitution:
In[104]:=
rulesCantor={"1""101","0""000"}
Out[104]=
{1101,0000}
◼
Declare the axiom:
In[105]:=
axiomCantor="1"
Out[105]=
1
◼
We can now show how the system evolves:
In[106]:=
Manipulate[LSystem[n,axiomCantor,rulesCantor],{n,0,4,1}]
Out[106]=
This string can be turned into a plot by interpreting each variable as a graphic instruction
◼
If we interpret 1 as “draw” and 0 as “skip” then we find something like this:
In[107]:=
Manipulate[CantorMesh[n],{n,0,4,1}]
Out[107]=
Another famous fractal that can be expressed as an L-system is the Sierpiński triangle.
◼
In this case the alphabet is made up of four symbols:
In[108]:=
alphabetTriangle={"A","B","+","-"}
Out[108]=
{A,B,+,-}
◼
Only two of which have rules for substitution:
In[109]:=
rulesTriangle={"A""B-A-B","B""A+B+A"}
Out[109]=
{AB-A-B,BA+B+A}
◼
The axiom is:
In[110]:=
axiomTriangle="A"
Out[110]=
A
◼
By convention + means “turn left by angle”, − means “turn right by angle” and everything else means “draw forward”
In[111]:=
drawRules[angle_]:={"+"{0,angle},"-"{0,-angle},_String{1,0}}
◼
We can now convert a given system to a list of points:
In[112]:=
Geometry[system_,angle_]:=AnglePath[Characters[system]/.drawRules[angle]]
◼
And display these points:
In[113]:=
Manipulate[Graphics[Line[Geometry[LSystem[2*n,axiomTriangle,rulesTriangle],Pi/3]]],{n,0,5,1}]
Out[113]=
Usually the example used for L-systems is the dragon curve because of the simplicity of its model.
◼
The alphabet is made up of five symbols:
In[114]:=
alphabetDragon={"F","X","Y","+","-"}
Out[114]=
{F,X,Y,+,-}
◼
Of which only two have substitution rules:
In[115]:=
rulesDragon={"X""X+YF+","Y""-FX-Y"}
Out[115]=
{XX+YF+,Y-FX-Y}
◼
Finally, we define the axiom
◼
The angle is 90° so we can plot the evolution of the system:
Space-filling curves
Space-filling curves
Space-filling curves, namely Hilbert’s curve, can be modelled by a rewrite system.
◼
For the L-system representing Hilbert’s curve, the alphabet is again made up of five letters
◼
Each generation we substitute L and R the following way
◼
Since L and R shouldn’t be drawn, as their only scope is to control the evolution of the curve, we have to exclude them from out Geometry function
◼
Now we can draw Hilbert’s curve by starting with axiom “L” and angle 90°
Further Explorations
Iterated function system
Fractal
Cantor Set
Sierpiński Triangle
Dragon Curve
Hilbert curve
Authorship information
Alessio Sarti
06/23/2017
alessio.sarti99@gmail.com