Just another WordPress.com site

Algorithm

Implementation of L-System on Java Language

Introduction

Last time, I have explained the basic of Fractal and L-System. Basically L-System is a one of many techniques that used to generate fractal geometries. In this article, I will focus on creating l-system using java. This is not the only way to implement l-system using java. You can find another way or you can create your own way. Before I begin with the code, I will explain about the l-system parts that we’re about to create.

L-System Parts

We will divide the system into 6 classes. They are Module, ModuleString, ConditionEvaluator, ParameterModifier, Production, and ProductionManager.

Module will represent one character on our string. It can also contain another parameters which can affect the process of generating new string and affect how the interpreter will draw each character on our string. The parameter can be in any type you want. You can make it generic by using Object as the type of the parameters. I will use my own class as the parameters.

ModuleString will represent our string or the sequence of Module. Actually, this ModuleString class is just a mere wrapper class for the list of Module. I create it to make it easier for us to manage the string.

ConditionEvaluator is just an interface. We will use ConditionEvaluator to evaluate the condition before the string replacement occurs. ParameterModifier is also an interface. It is used to modify each Module’s paramaters after the string replacement occurs.

Production will represent one production rule that exists in the current l-system. This class will store the predecessor and successor string of each production rule. It also store the required condition needed by the rule to replace the string and also how the production should modify the parameters after replacement.

The last one is ProductionManager. This class will manage all the production in one l-system. It also have to apply each the production to each Module on the predecessor string.

Module

This class will have an ID, which is the character that represented by the Module. We will use the ID to compare whether two compared Modules are equal or not. And I will also make an array of Dbl to contain the other parameters. Dbl is only a wrapper class for double type. I make it myself so of course you can’t use that type on your code. You can either create one for yourself or Change it to another type. It’s fine as long as it can store your parameters. Here is my code.

ModuleString

As I said before, this class is basically only a wrapper for the list of Modules. Just make sure when you put a new Module to this ModuleString, you have to put a copy of the Module, not the real one. It is because later we have to modify the parameters of the Modules. If we don’t store the copy, it will store the referenced instance of the Module which means if we change the parameters, all of the other instance that refer to it will also change. To make a copy, I use copy constructor from Module class. This class s quite straightforward. I’m sure you can easily understand what I write here.

ConditionEvaluator and ParameterModifier

Since both of them are just interfaces, these classes will look like this

ConditionEvaluator will take the ModuleString and the index of Module that will be checked. It should return true if the condition fulfilled and vice versa. As for ParameterModifier, it will take both predecessor and successor string because we usually get the values of modified parameter from the predecessor string’s parameters. The implementation of those two interfaces is depend on the l-system. For example, if we only want to create a simple l-system(I mean the one that I used to explain l-system on the previous article), we won’t need any condition to be evaluated or any parameters to be modified.

Production

This class is the most complex in this l-system implementation. It has to store the predecessor and successor string in the rule. It also has to store left and right context on the predecessor string. They are the string that placed on the left and the right side of the predecessor string. Before the rule is applied to the string, it has to check if the left and right context of the checked character match the rule’s left and right context. This class also has to store the implementation of ConditionEvaluator and ParameterModifier that apply to this rule. This is the code

You can see the code, if we don’t need ConditionEvaluator and ParameterModifier, the default will be assigned. On the applyAtIndex() method, first we have to check if the character at the specified index match the rule’s predecessor string. If it match, then check the left and right context and also the condition. After we make sure all the required condition fulfilled, we can start to replace the string with the successor string. After the replacement occur, we can apply the parameter modifier to the string.

ProductionManager

This class is the one that manage all the production rules we have on our l-system. It stores the list of the production rules. Its task is very simple, to apply each production rule to every character on the string.

Basically, after we define the production rules on our application, we only need to call apply() method on this class to rewrite entire string to the new string.

Now let’s create a test. We will write a simple implementation of the codes we have written. I will use the simple l-system on the previous article. The notation of that l-system is:

ω: b

p1: a → ab

p2: b → a

The l-system above should produce the strings below after 5 iteration

a

ab

aba

abaab

abaababa

Here is the code:

If you do it correctly, you should get the same result as listed above.

Advertisements

Understanding Fractal and L-System

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.