Surprising where following something can lead. I saw a reference in a YouTube video to something, wondered what it was, and eventually ended up discovering L-trees.
Lindenmayer Trees, or L-Systems, or L-trees, are forms created by using a set of rules and axioms related to ‘formal grammars’. They are extremely useful for producing lifelike imitations of biological trees.
The surprising thing about L-trees is that they rely on a grammar. That is, you can set up a set of symbols, say letters of the alphabet, ‘rewritable’ letter by letter into a new ‘string’ of symbols.
Imagine our set of symbols, an ‘alphabet’ V (I like to think V for vocabulary), a starting string of symbols, which we will call an axiom or initiator. Finally, we have a set P of production rules, rules for pumping out new strings based on the old. The way this is normally expressed is in the equation
G = (V, w, P)
Basically, the idea is that we have a set of rules that expands a string, which may contain generated substrings, the string and substrings can represent branches and structures.
The following is from the Wikipedia article, which I used as a starting point.
Example 1: The Wikipedia article names this example Algae
The example defines some of the above entities that we will use.
variable: A B
constants: none
axiom: A this is the starter string
rules: (A -> AB), (B -> A)
The rules basically state that: if you see an A turn into AB, if you see a B turn it into an A. Best to write the result into a separate string so as not to confuse.
Here is a simple python program that demonstrates
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
def process_rules(s): res = "" for c in s: # rule 1 if c == 'A': res += 'AB' elif c == 'B': res += 'A' return res axiom = 'A' s = axiom for i in range(7): s = process_rules(s) print("%d (%d) : %s" % ((i+1), (len(s)), s)) |
This produces this output:
1 (2) : AB
2 (3) : ABA
3 (5) : ABAAB
4 (8) : ABAABABA
5 (13) : ABAABABAABAAB
6 (21) : ABAABABAABAABABAABABA
7 (34) : ABAABABAABAABABAABABAABAABABAABAAB
Note that the length of the resulting strings, in parentheses, follows the Fibonacci Sequence. For completeness we should add the axiom with length 1 to the top of the list.
We can dramatically change the behaviour of the evolving string if we introduce symbols that create substrings demarked by special characters, say ().
Example 2: A branching tree.
This example is taken from this video from IIT (Indian Institute of Technology). The video is a bit advanced for me, because I haven’t studied this stuff in many years, forgotten most of it, and I am jumping late into a course. Still after wading through the abstractions you can find some interesting stuff. Note: this subject I have always found to be interesting even though it often makes my head hurt, I wouldn’t mind some time looking at these lectures from Lecture 1 onwards rather than jumping in to lecture 39.
Here’s the example Professor Kamala Krithivasan introduces in the video at 9:50.
The rules in P are represented by the following table, first row is LHS of the rule, second row is what it is transformed into by the RHS (righ hand side) of a production rule.
1 2 3 4 5 6 7 8 ( ) # 0
2#3 2 2#4 504 6 7 8(1) 8 ( ) # 0
The axiom, or starting string, P0 is ‘1’.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
# Using a dictionary makes this so much easier. rules = { '1':'2#3', '2':'2', '3':'2#4', '4':'504', '5':'6', '6':'7', '7':'8(1)', '8':'8', '(':'(', ')':')', '#':'#', '0':'0'} def process_rules(s): res = "" for ch in s: res += rules[ch] return res axiom = '1' s = axiom print("0 : %s" % (s)) for i in range(1, 11): s = process_rules(s) print("%d : %s" % (i, s)) |
The output for the first 10 productions (not including the axiom, which is rule 0):
0 : 1
1 : 2#3
2 : 2#2#4
3 : 2#2#504
4 : 2#2#60504
5 : 2#2#7060504
6 : 2#2#8(1)07060504
7 : 2#2#8(2#3)08(1)07060504
8 : 2#2#8(2#2#4)08(2#3)08(1)07060504
9 : 2#2#8(2#2#504)08(2#2#4)08(2#3)08(1)07060504
10 : 2#2#8(2#2#60504)08(2#2#504)08(2#2#4)08(2#3)08(1)07060504
Notice the substrings, in bold, that are contained within the parentheses. These substrings are subtrees. In fact, if you define a graphical representation of these strings so that the parenthetical sections project independently from the main track at some angle, then they represent branches both logically and visually. This allows us to construct more organic visual structures. One can add a rule which determines which way the branches are displayed in visual space so as to make the visual form more natural.
Applying these ideas to computer graphics enables us to make more realistic trees but more importantly, as far as I am concerned, it gives us a window into why the world looks the way it does. The amazing thing about mathematics is that it reveals surprising unity in the apparent disorder of Nature, which inevitably reveals further order below that.
Here is a video of some graphics using L-trees.
I can’t resist posting a link to one of my favourite YouTube channels, exemplified here by a brilliant explanation of why the Golden Ratio / Fibonacci Sequence appears in plants. Follow it all the way through to part 3. Each clip is quite short but condenses a lot of information, the kicker comes in the final video.
It was a lot of fun skimming this topic. Now back to slightly less abstract stuff.
Peter
(NOTE: this is a repost of an earlier post of mine, on a different hosting site, now gone. I still like it and thought it worth reposting.)