L-system
L-system (L system, Lindenmayer system) is the algorithm that I describe the structure of various natural objects which assumed the growth process of the plant the beginning with a kind of the formal grammar and can express. When I generate pro-repetition function (Iterated Function System; IFS) so-called self-resemblance figure and fractal figure of the natural object, I am used. L-System made a theory biologist of the Utrecht University of Hungary in 1968, and I was proposed by Alice Ted Linden Mayer (Aristid Lindenmayer) who was a botanist and developed.
Table of contents
Origin
Linden Mayer studied the growth pattern of various creatures including the alga such as Anabaena catenula of yeast and a filamentous fungus and the blue-green alga as a biologist. Originally L-system was developed to describe the mutual relations of the cell of the neighborhood in a growth style and the plant cell of such a unicellular organism or the simple multicellular organism of the system. L-system accomplishes development as a tool to describe the form of the higher plant and complicated divergence structure later.
Structure of L-system
The basics of L-system can easily describe the shape such as the self-resemblance figure and fractal figure in recurrence characteristics. A plant and other appearances can easily define the natural creature structure equally, and structure does "growth" by increasing the number of times of the recurrence summons and seems to become complicated. L-system is used for generation of the artificial life well.
(→ Chomsky hierarchy) where the grammar of L-system is similar to a thing of en:Unrestricted grammar. I am often defined now by four following groups.
- G = {V, S,ω, P},
Each element,
- V (letter): The set of the variable rearranged sequentially by a substituted rule (later P). When a recursive repetition calculation of L-system advances, it is character string consisting of elements of this V that make "growth" as a thing.
- S ： A set of the fixed number not to change even if a calculation advances.
- ω ： The character string consisting of elements of V indicating the initial state of the system.
- P ： The set of the substituted rule changing V. Each element is described, for example, like (A → AB) by a combination of (substituted object) character string and character string after the substitution before substitution.
When a substituted object is only an independent letter in substituted rule P, L-system is context-free language. On the other hand, L-system is a context-sensitive language when a substituted rule considers it to the mutual relations with the letter of the neighborhood. In addition, it is said, "it is deterministic", and L-system is called D0L-system (deterministic context-free L-system) when substituted rule P is applied for each letter surely every time. On the contrary, "it is probabilistic" and is called L-system when the application of the substituted rule depends on the probability.
When you apply L-system to graphics, you must convert the character string that L-system generates into the figure on the screen in one way or another. For example, by the program (cf. outside link of the end of a sentence) called FractInt, I generate graphics using a turtle such as LOGO. In other words, a program translates character string of L-system into the control order of the turtle and lets a figure paint pictures.
Example of L-systems
It is alga example 1
The example which describes the algal growth that was an opportunity of the L-system birth.
- V ： A, B
- S ： Unavailable
- ω: A
- P ： (A → AB) (B → A)
The character string grows up as follows when I calculate sequentially.
- n = 0 ： A
- n = 1 ： AB
- n = 2 ： ABA
- n = 3 ： ABAAB
- n = 4 ： ABAABABA
In this example, (A → AB) expresses what normal cell A and unripe cell B produce by unequal cell division in substituted rule P and expresses that (B → A) matures to cell A which unripe cell B grows up, and can be divided. Because a figure does this character string (e.g., I replace B with the figures of the small cell a cell of the branching type each in A), I can get the picture such as the algal colony which unfolded on the agar nutrient medium.
It is Fibonacci series example 2
- V ： A, B
- S ： Unavailable
- ω: A
- P ： (A → B) (B → AB)
It becomes the following character string when I push forward a calculation.
- n = 0 ： A
- n = 1 ： B
- n = 2 ： AB
- n = 3 ： BAB
- n = 4 ： ABBAB
- n = 5 ： BABABBAB
- n = 6 ： ABBABBABABBAB
- n = 7 ： BABABBABABBABBABABBAB
When count the number of each letter of this character string sequentially from n=0; Fibonacci series (1 1 2 3 5 8 13 21 34 55 89 …It becomes). Because the contents of the character string do not matter, and they pay attention only to length in this example, I can get similar progression even if, for example, I rearrange (B → AB) of the substitution rule in (B → BA).
It is Cantor meeting example 3
- V ： A, B
- S ： Unavailable
- ω: A
- P ： (A → ABA) (B → BBB)
It becomes the following character string when I push forward a calculation.
- n = 0 ： A
- n = 1 ： ABA
- n = 2 ： ABABBBABA
- n = 3 ： ABABBBABABBBBBBBBBABABBBABA
The figure such as the bottom is provided when I replace A of this character string with the part that B was pulled out for a line. I am equivalent to operation that (A → ABA) of the substituted rule divides (closed interval) for a line into 3 parts and pulls out the center. (B → BBB) means that a removed section does not return once. Specifically, Cantor set (Cantor set) is referred to
It is Koch curve example 4
A drawing example of the Koch curve to be comprised of a right angle.
- V ： F
- S ： +, -,
- ω: F
- P ： (F → F+F-F-F+F)
In the above, in F, in drawing, + of the straight line by the turtle, - means that 90 degrees turns to the right a 90 degrees turn in a turtle in the same way to the left. The following figures are provided when I calculate this sequentially.
- n = 0 ：
F
- n = 1 ：
F+F-F-F+F
- n = 2 ：
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 ：
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
It is Penrose tile example 5
Using L-system, I can generate the plane filling design such as the chart below. Specifically, I refer to Penrose tile and Roger Penrose.
It is the triangle of the shell pin ski example 6
The example which draws a figure of the triangle of the shell pin ski in L-system.
- V ： A, B
- S ： +, -
- ω: A
- P ： (A → B-A-B) (B → A+B+A)
In the above, in A and B, in drawing, + of the straight line by the turtle, - means that 60 degrees turns to the right a 60 degrees turn in a turtle in the same way to the left. There are other substituted rules representing similar figure, but, in the case of this rule, will begin to draw the turtle from the triangular lower left.
The figure which is drawn at the time of n = 2, n = 4, n = 6, n = 8 each. At the time of n →∞, I equal in the triangle of the shell pin ski.
It is transformation of the Koch curve example 7
Kind of the fractal figure which painted pictures while making the change of the periodic angle to normal Koch curve.
Graphics using other L-system
- Lichen or bryophytes:
 |  |
- A herbaceous drawing figures example:
 |  |  |
- A drawing figures example of Kimoto:
 |  |  |  |
- Including the protozoan:
 |  |  | 
|
Known problem
A lot of problems about L-system exist, but it is difficult for the prime example to follow L-system adversely. Specifically, it is difficult parameter to generate the structure and to find a substituted rule when a certain structure was shown. This is remarkable in a figure formed after the process when it is complicated (the repetition number of times there is many) such as the natural object.
Kind of L-system
L-system in the true progression:
L-system in the plane:
- Plane filling curve, figure (Space-filling curve) others:
L-system in the space:
- Natural object
Probabilistic L-system
Probabilistic (Stochastic) L-system expanded L-system and allowed you to diverge stochastically. Because probabilistic L-system does not have a standard, grammar varies according to software.
It is an example every implementation of probabilistic diverging L-system as follows.
| Implementation of Tong Lin (1996) | Houdini (L-system SOP) | Cinema 4D (Turtle of MoSpline) |
|---|---|---|
A=(0.5)FA A=(0.25)+F-A A=(0.25) -F+A | A=FA: 0.5 A=+F-A: 0.25 A=-F+A: 0.25 | A: (rnd(1)<0.5)=FA A: (rnd(1)<0.75)=+F-A A: (rnd(1)>0.75)=-F+A |
Context-dependent L-system
Context-dependent (Context-sensitive) L-system expanded L-system, and pattern matching allows divergence depending on context. For the thing which implemented context-dependent L-system, implementation of Tong Lin exists.
Allied item
References
- Przemyslaw Prusinkiewicz - en:The Algorithmic Beauty of Plants PDF version available here for free
Outside link
- David J. Wright's article on L-systems
- Algorithmic Botany at the University of Calgary
- Branching: Java applet (English) which simulates the growth of the tree using L-system Tree L-system
- Fractint L-System True Fractals
- "An introduction to Lindenmayer systems", by Gabriela Ochoa. Brief description of L-systems and how the strings they generate can be interpreted by computer.
- "powerPlant" an open-source landscape modelling software
- Fractint home page
- "L-system in Falk arts" The FORMA commurative issue of the conference ISKFA06
- A simple L-systems generator (Windows)
- Lyndyhop: another simple L-systems generator (Windows & Mac)
- An evolutionary L-systems generator (anyos*)
- L-systems gallery – a tribute to Fractint
- "LsystemComposition". Page at Pawfal ("poor artists working for a living") about using L-systems and genetic algorithms to generate music.
- eXtended L-Systems (XL), Relational Growth Grammars, and open-source software platform GroIMP.
- A JAVA applet with many fractal figures generated by L-systems.
- L-systems in Architecture; genetic housing.
- L-systems in Plant Growth,Simulation and Visualization (PlantVR).
- Musical L-systems: Theory and applications about using L-systems to generate musical structures, from waveforms to macro-forms.
- LSys/JS - Interactive L-System interpreter using the Canvas HTML element.
This article is taken from the Japanese Wikipedia L-system
This article is distributed by cc-by-sa or GFDL license in accordance with the provisions of Wikipedia.
In addition, Tranpedia is simply not responsible for any show is only by translating the writings of foreign licenses that are compatible with CC-BY-SA license information.
0 개의 댓글:
댓글 쓰기