Saturday 12 March 2011

Examples of L-systems

Example 1: Algae

Lindenmayer's original L-system for modelling the growth of algae.

    variables : A B
    constants : none
    start  : A
    rules  : (A → AB), (B → A)

which produces:

    n = 0 : A
    n = 1 : AB
    n = 2 : ABA
    n = 3 : ABAAB
    n = 4 : ABAABABA
    n = 5 : ABAABABAABAAB
    n = 6 : ABAABABAABAABABAABABA
    n = 7 : ABAABABAABAABABAABABAABAABABAABAAB

 Example 1: Algae, explained

n=0:         A           start (axiom/initiator)
            / \
n=1:       A   B         the initial single A spawned into AB by rule (A → AB), rule (B → A) couldn't be applied
          /|    \
n=2:     A B     A       former string AB with all rules applied, A spawned into AB again, former B turned into A
        /| |     |\
n=3:   A B A     A B     note all A's producing a copy of themselves in the first place, then a B, which turns ...
      /| | |\    |\ \
n=4: A B A A B   A B A   ... into an A one generation later, starting to spawn/repeat/recurse then

 Example 2: Fibonacci numbers

If we define the following simple grammar:

    variables : A B
    constants : none
    start  : A
    rules  : (A → B), (B → AB)

then this L-system produces the following sequence of strings:

    n = 0 : A
    n = 1 : B
    n = 2 : AB
    n = 3 : BAB
    n = 4 : ABBAB
    n = 5 : BABABBAB
    n = 6 : ABBABBABABBAB
    n = 7 : BABABBABABBABBABABBAB

These are the mirror images of the strings from the first example, with A and B interchanged. Once again, each string is the concatenation of the preceding two, but in the reversed order.

In either example, if we count the length of each string, we obtain the famous Fibonacci sequence of numbers:

    1 1 2 3 5 8 13 21 34 55 89 ...

For n>0, if we count the kth position from the invariant end of the string (left in Example 1 or right in Example 2), the value is determined by whether a multiple of the golden mean falls within the interval (k-1,k). The ratio of A to B likewise converges to the golden mean.

This example yields the same result (in terms of the length of each string, not the sequence of As and Bs) if the rule (B → AB) is replaced with (B → BA).

This sequence is a locally catenative sequence because G(n) = G(n-2)G(n-1) where G(n) is the nth generation.
 Example 3: Cantor dust
Cantor set in seven iterations.svg

    variables : A B
    constants : none
    start  : A {starting character string}
    rules  : (A → ABA), (B → BBB)

Let A mean "draw forward" and B mean "move forward".

This produces the famous Cantor's fractal set on a real straight line R.
 Example 4: Koch curve

A variant of the Koch curve which uses only right-angles.

    variables : F
    constants : + −
    start  : F
    rules  : (F → F+F−F−F+F)

Here, F means "draw forward", + means "turn left 90°", and - means "turn right 90°" (see turtle graphics).

    n = 0: Koch Square - 0 iterations

        F

    n = 1: Koch Square - 1 iterations

        F+F-F-F+F

    n = 2: Koch Square - 2 iterations

        F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F

    n = 3: Koch Square - 3 iterations

        F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F+ F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F- F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F- F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F+ F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F

 Example 5: Penrose tilings

The following images were generated by an L-system. They are related and very similar to Penrose tilings, invented by Roger Penrose.
Penam01c.gif
Penam02c.gif

As an L-system these tilings are called Penrose's rhombuses and Penrose's tiles. The above pictures were generated for n = 6 as an L-system. If we properly superimpose Penrose tiles as an L-system we get next tiling:
Pend05c.gif

otherwise we get patterns which do not cover an infinite surface completely:
Pendx05c.gif
 Example 6: Sierpinski triangle

The Sierpinski triangle drawn using an L-system.

    variables : A B
    constants : + −
    start  : A
    rules  : (A → B−A−B), (B → A+B+A)
    angle  : 60°

Here, A and B both mean "draw forward", + means "turn left by angle", and − means "turn right by angle" (see turtle graphics). The angle changes sign at each iteration so that the base of the triangular shapes are always in the bottom (they would be in the top and bottom, alternatively, otherwise).
Serpinski Lsystem.svg

Evolution for n = 2, n = 4, n = 6, n = 8

There is another way to draw the Sierpinski triangle using an L-system.

    variables : F G
    constants : + −
    start  : F−G−G
    rules  : (F → F−G+F+G−F), (G → GG)
    angle  : 120°

Here, F and G both mean "draw forward", + means "turn left by angle", and − means "turn right by angle".
 Example 7: Dragon curve

The dragon curve drawn using an L-system.

    variables : X Y
    constants : F + −
    start  : FX
    rules  : (X → X+YF), (Y → FX-Y)
    angle  : 90°

Here, F means "draw forward", - means "turn left 90°", and + means "turn right 90°". X and Y do not correspond to any drawing action and are only used to control the evolution of the curve.
Dragon curve L-system.svg

Dragon curve for n = 10
 Example 8: Fractal plant

    variables : X F
    constants : + −
    start  : X
    rules  : (X → F-[[X]+X]+F[+FX]-X), (F → FF)
    angle  : 25°

Here, F means "draw forward", - means "turn left 25°", and + means "turn right 25°". X does not correspond to any drawing action and is used to control the evolution of the curve. [ corresponds to saving the current values for position and angle, which are restored when the corresponding ] is executed.
Fractal-plant.svg

Fractal plant for n = 6
 Example 9: Modified Koch L-system

A fractal figure drawn introducing a periodic change of angle sign in the iteration of the usual Koch curve L-system.

No comments:

Post a Comment