L-Systems - Theory

Well, the correct name for this fractal type should be deterministic contextfree Lindenmayer systems.

Deterministic, because there is nothing randomly chosen as opposed to perhaps IFS.

Contextfree, because all rules are applied regardless of the context, i.e. rules of the form 'character <c> has to be replaced by the string <string>'. Contextsensitive rules are of the form '<string1> has to be replaced by the string <string2>'.

Lindenmayer, because Mr. Lindenmayer examined those systems...

System, because there can be many rules.

An L-system consists of an axiom - which simply is a string - and a set of rules: All of them are of the form character <c> has to be replaced by the string <string>. In order to calculate an LSystem, one starts with the axiom as the initial string.

Then the first character of the initial string is examined. If a rule exists, which says, that this character should be replaced by a string, then it should be replaced by that string. If no rule for this character exists, then just leave the character as it is. Then have a look at the second character, replace it by a string, if a rule exists, or simply do nothing, if no rule exists. Continue this way, until the end of the string is reached.

Then the first iteration is finished. The result is most likely a string, which is quite a bit longer that the string before starting the iteration.

Now the second iteration is started: The resulting string from the first iteration is taken: One again starts at the first character, replaces, continues with the second character, the third, etc. until the end of the string has been reached, then goes on to the next iteration, starts again at the first character, etc., the 4th iteration, the 5th, etc. until the maximum number of iterations is reached.

As you can imagine, values of less than 10 for MaxIt are very popular, because the string will grow exponentially...

At the end one has a huge string, which doesn't look like a fractal. But now the magic starts: The whole string is interpreted as a series of drawing commands. A drawing command normally consists of a single character, like 'F', which simply draws a line. The resulting image is a fractal, at least, if one would iterate infinitely often.

The Lindenmayer-systems are of importance in conjunction with computer generated natural objects, because the results show some similarities to objects, which appear in nature, mostly plants. Unfortunately these deterministic contextfree systems aren't that powerful. It's very difficult to create realistic plants with them. If one wants to create such plants, one has to specify a huge amount of rules to describe simple plants. Due to this, there exist some enhancements to DOL-systems, which then are contextsensitive and additionally not deterministic.

But not lets give an example of an L-system, just to make clear, how it all works:

Well, lets define the Koch-curve: It's ideal for creation via L-systems:

Keep in mind some drawing commands:

F, which draws a line of given lenght into the current direction.

+, which changes the current direction, say about 60 degree counter clockwise.

-, which changes the current direction, say about 60 degree clockwise.

Lets start with the axiom: F

Now lets define one single rule: F has to be replaced by F-F++F-F

This is exactly the definition of the Koch-curve: Every line (F) has to be replaced by an object, which is the line, but the middle third part of the line is replaced by a triangle. Just draw this F-F++F-F, and you will see this replacement. It is obvious, that this very simple L-system creates the Koch-curve.

Generally the interpretation of the drawing commands is very similar to turtle-graphics: One has to imagine a virtual turtle on the screen, which can do some actions. It can move forward a specified length, draw forward a specified length, it can rotate itself, it can change the drawing color, etc.

For an explanation of all the drawing commands see chapter about the L-system formula editor.





Last update on Nov 26 2002.