Tutorials‎ > ‎

Understanding Fractal and L-System

posted Dec 29, 2011, 12:06 AM by William Salim   [ updated Aug 15, 2016, 11:38 PM by Surya Wang ]

Introduction

Fractal and L-system have been around for many years. Some of them are very simple and easy to create, and the others can be very complex. This article will explain the basic about both of them.

Fractal

Fractal is a geometric shape that is considered as infinitely complex object that can be scaled infinitely without reducing its complexity on all level. The common feature of fractal is self-similarity which means every part of the fractal is similar to the whole fractal. The famous example of the fractal object are Mandelbrot set and Koch snowflake.

Mandelbrot set is a fractal that is generated by using a recurrence relation of each point in the space. Because of that, the self-similarity of this fractal is only an approximation of the whole fractal or we can call it quasi-self-similarity. If a part of Mandelbrot set is zoomed, the result will not exactly the same as the whole Mandelbrot set but still similar to the whole Mandelbrot set.

As you can see at the pictures above, when the Mandelbrot set is zoomed 2000 times, it still has the same complexity as the original Mandelbrot set. Although the shape of the zoomed version is different that the normal sized, it still has similar characteristics.

Koch Snowflake, on the other hand, is generated using geometric replacement rule that applied iteratively to the initial geometric shape. In case of Koch Snowflake, the initial shape is a triangle which consist of 3 individual straight lines. Each of those lines will be replaced by another form of shape (we can call it generator). The process will be iterated some times to generate more detailed object. This kind of fractal can be also scaled up infinitely.

Usually, the fractal generated using iterated function will be exactly-self-similar. Another famous examples of this fractal type are Cantor set, Peano curve, dragon curve, and Menger sponge.

L-System

L-system was proposed by Astrid Lindenmayer. It is a system string rewriting system. In general, rewriting is a technique to define a complex object by changing the object’s parts, which are originally the more simple parts, into the more complex parts consecutively by using a set of rewriting rules and productions. It is very similar to the iterated function fractal explained above. Actually L-system itself is a kind of iterated function fractal that operates on a sequence of string.

As it is easier to study the rewriting system by using string than a graphical representation, there were several concepts of rewriting system appearing, including Chomsky grammar and L-system. The main difference is how the productions are applied to the existing string. While Chomsky grammar replace the string with the production sequentially, L-system replace all the string simultaneously in parallel.

The simplest class of L-System which are deterministic and context free, called DOL-System. For example, assume that a string is formed by two letter, a and b, which can appear multiple times in a string. Every letter has its own rewriting rule. The rule a → ab means that every letter a will be replaced by string ab, and the rule b → a means that every letter b will be replaced by string a. The rewriting process starts from a distinguished string called axiom. Assume that the axiom contains the letter b. In the first rewriting phase, axiom b is replaced by a using production b → a. In the second derivation, a is replaced with ab from the production a → ab. String ab has two letters, both of them will be replaced simultaneously and it will produce aba. Using the same method, aba will produce abaab, then it will become abaababa, then abaababaabaab, and so on.

You can think it like the picture below.

Assume that V is an alphabet, V* is a set of every words of V, and V+ is a set of non-empty words of V. A string in OL-system is an ordered triplet G = {V,ω,P} where V is the alphabet, ω ∈ V+ is a non-empty word which is called axiom, and P ⊂ V × V* is a finite set of productions. A production (a, χ) ∈ P written as a → χ. The letter a is a predecessor and the letter χ is the successor of the production. It is assumed that for any letter a ∈ V, there should be at least one word χ ∈ V* such as a → χ. If there is no production specified for a given predecessor a ∈ V, the identity production of a → a is assumed as the part of production P. An OL-system is deterministic (noted DOL-system) if and only if for each a ∈ V there is exactly one χ ∈ V* such that a → χ.

Let μ = a1 … am be an arbitrary word over V. The word ν = χ1 … χm ∈  V* is directly derived (or generated by) μ, noted μ ⇒ ν, if and only if ai → χi for i = 1,…, m. A word ν is generated by G in a derivation of length n if there exists a developmental sequence of words μ0,  μ1,…, μn such that μ0 = ω, μn = ν and μ0 ⇒ μ1 ⇒ … ⇒ μn.

L-system can be used to visualize the structures by embedding graphical symbols in the string that can be used later to render it. Turtle commands can be used to describe and visualize a wide range of L-systems including Koch’s snowflake, plants and branching structures. The concept behind Turtle Graphics is that the ‘turtle’ is given instructions relative to its current position and as it moves it leaves a pen line mark behind it. By using turtle graphics, shapes, drawing and structures can be defined in the terms of a L-system. Using a bracket extension to Turtle Graphics, L-systems can support the branching structures such as trees that are predominant in nature.

The picture above is an example of L-system that is rendered by using turtle graphics. It can be used to produce natural forms quite nicely. Lindenmayer himself use this system to produce realistic looking 3 dimensional representation of various plants.

The pictures above are the examples of generated plants using L-system.

Maybe that’s all I can explain about fractal and l-system for now. The area of research that involve fractal and l-system is very large so it’s impossible for me to explain it here. You can find many books that explain about fractal in detail. For the next article, I will explain how to implement l-system by using java.