Working With Shape: L-Systems
Trees
“I think that I shall never see
A poem lovely as a tree.
A tree whose hungry mouth is prest
Against the earth’s sweet flowing breast;
A tree that looks at God all day,
And lifts her leafy arms to pray;
A tree that may in Summer wear
A nest of robins in her hair;
Upon whose bosom snow has lain;
Who intimately lives with rain.
Poems are made by fools like me,
But only God can make a tree."
— Joyce Kilmer, 1915
Introduction
Trees are fractal in nature, meaning that patterns created by the large structures, such as the main branches, repeat themselves in smaller structures, such as smaller branches…. a universal growth pattern first observed by Leonardo da Vinci 500 years ago: a simple yet startling relationship that always holds between the size of a tree’s trunk and sizes of its branches.
An Introduction to L-Systems
From Job Talle’s Website:
Lindenmayer systems were originally conceived by Hungarian biologist Aristid Lindenmayer while studying algae growth. He developed L-systems as a way to describe the growth process of algae and simple plants. The result was a type of language in which the recursive and self similar properties of organism growth can be expressed. Indeed, L-systems can be used to generate natural patterns, but well known mathematical patterns can also be written as an L-system. In this article, I will explain different flavors of L-systems, and I will demonstrate them by rendering 2D Lindenmayer systems and 3D Lindenmayer systems using turtle graphics.
The language is very simple. It consists of symbols (the alphabet) and production rules. The first state of the sentence is called the axiom. The production rules can be applied repeatedly on this axiom to evolve or grow the system. A simple example would be a system with the axiom AA, and the rule A→ABAA→ABA. After the first iteration (the first time the rule is applied), the sentence will be changed to ABAABA. After the second iteration, the sentence will be ABABABAABABABA and so forth. You can see how a self expanding sentence can be analogous to cell division in plants and other biological processes.
L-system Structures thus develop through a process of string rewriting. A string of letters is transformed into a new string of letters using simple rules called productions. The process is repeated indefinitely, each time using the string that was just produced as the source for the next string. Because the strings tend to grow with each rewrite, an L-system can become arbitrarily complex, but always guided by a simple process dictated by a fixed set of simple rules.
In this respect, L-systems are a manifestation of Complexity Phenomena.
(Image Courtesy Christophe Eloy | University of Provence).
Let us see how we can create “Algorithmic Trees”.
Creating Trees using L-systems
Using p5.js
Using R
We will use the package LindenmayerR to create our tree.
# Lindemayer tree
## Dictionary of Symbols
dictionary <- data.frame(
symbol = c("F", "f", "+", "-", "[", "]"), # symbol column
action = c("F", "f", "+", "-", "[", "]"), # action column
stringsAsFactors = FALSE
)
## Axioms to start and morph
tree_morph_rules <- data.frame(
inp = c("F"), # starting axiom
out = c("F[+F][-F]"), # Morphing Rule
stringsAsFactors = FALSE
)
## Build the Tree with commands
Ltree <- Lsys(
init = "F",
rules = tree_morph_rules,
n = 2,
verbose = 0, # No progress messages please...
retAll = FALSE # One Vector output at the end only
)[[1]]
start end
[1,] 1 1
[[1]]
start end insert
1 1 1 F[+F][-F]
[[1]]
start end
[1,] 1 1
[2,] 4 4
[3,] 8 8
[[1]]
start end insert
1 1 1 F[+F][-F]
2 4 4 F[+F][-F]
3 8 8 F[+F][-F]## Now draw the tree
drawLsys(
string = Ltree,
drules = dictionary,
stepSize = 10, shrinkFactor = 1.2, # integers shrink!
ang = 12,
st = c(50, 10, 90) # Root Position x, y, angle from bottom-left
)
A more complex, and more botanical-looking, tree or seaweed:
## Define Axiom and Mutation Rules
fractal_tree_rules <- data.frame(
inp = c("X", "F"),
out = c("F-[[X]+X]+F[+FX]-X", "FF"),
stringsAsFactors = FALSE
)
## Create the Algorithmic Tree
fractal_tree <- Lsys(
init = "X", # Axiom
rules = fractal_tree_rules,
n = 4,
verbose = 0,
retAll = FALSE
)
## Now draw the tree
drawLsys(
string = fractal_tree,
drules = dictionary,
stepSize = 2, # Shrink by half each time
ang = runif(n = 1, min = 3, max = 30),
st = c(50, 5, 90), # Origin of tree
gp = gpar(col = "chocolate4", fill = "honeydew")
)
grid.text("Fractal Seaweed (n = 4)", 0.25, 0.25)
[[1]]
start end
[1,] 1 1
[[1]]
start end insert
1 1 1 F-[[X]+X]+F[+FX]-X
[[1]]
start end
[1,] 5 5
[2,] 8 8
[3,] 15 15
[4,] 18 18
[[2]]
start end
[1,] 1 1
[2,] 11 11
[3,] 14 14
[[1]]
start end insert
1 5 5 F-[[X]+X]+F[+FX]-X
2 8 8 F-[[X]+X]+F[+FX]-X
3 15 15 F-[[X]+X]+F[+FX]-X
4 18 18 F-[[X]+X]+F[+FX]-X
[[2]]
start end insert
1 1 1 FF
2 11 11 FF
3 14 14 FF
[[1]]
start end
[1,] 10 10
[2,] 13 13
[3,] 20 20
[4,] 23 23
[5,] 30 30
[6,] 33 33
[7,] 40 40
[8,] 43 43
[9,] 56 56
[10,] 59 59
[11,] 66 66
[12,] 69 69
[13,] 76 76
[14,] 79 79
[15,] 86 86
[16,] 89 89
[[2]]
start end
[1,] 1 1
[2,] 2 2
[3,] 6 6
[4,] 16 16
[5,] 19 19
[6,] 26 26
[7,] 36 36
[8,] 39 39
[9,] 46 46
[10,] 47 47
[11,] 50 50
[12,] 51 51
[13,] 52 52
[14,] 62 62
[15,] 65 65
[16,] 72 72
[17,] 82 82
[18,] 85 85
[[1]]
start end insert
1 10 10 F-[[X]+X]+F[+FX]-X
2 13 13 F-[[X]+X]+F[+FX]-X
3 20 20 F-[[X]+X]+F[+FX]-X
4 23 23 F-[[X]+X]+F[+FX]-X
5 30 30 F-[[X]+X]+F[+FX]-X
6 33 33 F-[[X]+X]+F[+FX]-X
7 40 40 F-[[X]+X]+F[+FX]-X
8 43 43 F-[[X]+X]+F[+FX]-X
9 56 56 F-[[X]+X]+F[+FX]-X
10 59 59 F-[[X]+X]+F[+FX]-X
11 66 66 F-[[X]+X]+F[+FX]-X
12 69 69 F-[[X]+X]+F[+FX]-X
13 76 76 F-[[X]+X]+F[+FX]-X
14 79 79 F-[[X]+X]+F[+FX]-X
15 86 86 F-[[X]+X]+F[+FX]-X
16 89 89 F-[[X]+X]+F[+FX]-X
[[2]]
start end insert
1 1 1 FF
2 2 2 FF
3 6 6 FF
4 16 16 FF
5 19 19 FF
6 26 26 FF
7 36 36 FF
8 39 39 FF
9 46 46 FF
10 47 47 FF
11 50 50 FF
12 51 51 FF
13 52 52 FF
14 62 62 FF
15 65 65 FF
16 72 72 FF
17 82 82 FF
18 85 85 FF
[[1]]
start end
[1,] 17 17
[2,] 20 20
[3,] 27 27
[4,] 30 30
[5,] 37 37
[6,] 40 40
[7,] 47 47
[8,] 50 50
[9,] 63 63
[10,] 66 66
[11,] 73 73
[12,] 76 76
[13,] 83 83
[14,] 86 86
[15,] 93 93
[16,] 96 96
[17,] 108 108
[18,] 111 111
[19,] 118 118
[20,] 121 121
[21,] 128 128
[22,] 131 131
[23,] 138 138
[24,] 141 141
[25,] 154 154
[26,] 157 157
[27,] 164 164
[28,] 167 167
[29,] 174 174
[30,] 177 177
[31,] 184 184
[32,] 187 187
[33,] 209 209
[34,] 212 212
[35,] 219 219
[36,] 222 222
[37,] 229 229
[38,] 232 232
[39,] 239 239
[40,] 242 242
[41,] 255 255
[42,] 258 258
[43,] 265 265
[44,] 268 268
[45,] 275 275
[46,] 278 278
[47,] 285 285
[48,] 288 288
[49,] 300 300
[50,] 303 303
[51,] 310 310
[52,] 313 313
[53,] 320 320
[54,] 323 323
[55,] 330 330
[56,] 333 333
[57,] 346 346
[58,] 349 349
[59,] 356 356
[60,] 359 359
[61,] 366 366
[62,] 369 369
[63,] 376 376
[64,] 379 379
[[2]]
start end
[1,] 1 1
[2,] 2 2
[3,] 3 3
[4,] 4 4
[5,] 8 8
[6,] 9 9
[7,] 13 13
[8,] 23 23
[9,] 26 26
[10,] 33 33
[11,] 43 43
[12,] 46 46
[13,] 53 53
[14,] 54 54
[15,] 57 57
[16,] 58 58
[17,] 59 59
[18,] 69 69
[19,] 72 72
[20,] 79 79
[21,] 89 89
[22,] 92 92
[23,] 99 99
[24,] 100 100
[25,] 104 104
[26,] 114 114
[27,] 117 117
[28,] 124 124
[29,] 134 134
[30,] 137 137
[31,] 144 144
[32,] 145 145
[33,] 148 148
[34,] 149 149
[35,] 150 150
[36,] 160 160
[37,] 163 163
[38,] 170 170
[39,] 180 180
[40,] 183 183
[41,] 190 190
[42,] 191 191
[43,] 192 192
[44,] 193 193
[45,] 196 196
[46,] 197 197
[47,] 198 198
[48,] 199 199
[49,] 200 200
[50,] 201 201
[51,] 205 205
[52,] 215 215
[53,] 218 218
[54,] 225 225
[55,] 235 235
[56,] 238 238
[57,] 245 245
[58,] 246 246
[59,] 249 249
[60,] 250 250
[61,] 251 251
[62,] 261 261
[63,] 264 264
[64,] 271 271
[65,] 281 281
[66,] 284 284
[67,] 291 291
[68,] 292 292
[69,] 296 296
[70,] 306 306
[71,] 309 309
[72,] 316 316
[73,] 326 326
[74,] 329 329
[75,] 336 336
[76,] 337 337
[77,] 340 340
[78,] 341 341
[79,] 342 342
[80,] 352 352
[81,] 355 355
[82,] 362 362
[83,] 372 372
[84,] 375 375
[[1]]
start end insert
1 17 17 F-[[X]+X]+F[+FX]-X
2 20 20 F-[[X]+X]+F[+FX]-X
3 27 27 F-[[X]+X]+F[+FX]-X
4 30 30 F-[[X]+X]+F[+FX]-X
5 37 37 F-[[X]+X]+F[+FX]-X
6 40 40 F-[[X]+X]+F[+FX]-X
7 47 47 F-[[X]+X]+F[+FX]-X
8 50 50 F-[[X]+X]+F[+FX]-X
9 63 63 F-[[X]+X]+F[+FX]-X
10 66 66 F-[[X]+X]+F[+FX]-X
11 73 73 F-[[X]+X]+F[+FX]-X
12 76 76 F-[[X]+X]+F[+FX]-X
13 83 83 F-[[X]+X]+F[+FX]-X
14 86 86 F-[[X]+X]+F[+FX]-X
15 93 93 F-[[X]+X]+F[+FX]-X
16 96 96 F-[[X]+X]+F[+FX]-X
17 108 108 F-[[X]+X]+F[+FX]-X
18 111 111 F-[[X]+X]+F[+FX]-X
19 118 118 F-[[X]+X]+F[+FX]-X
20 121 121 F-[[X]+X]+F[+FX]-X
21 128 128 F-[[X]+X]+F[+FX]-X
22 131 131 F-[[X]+X]+F[+FX]-X
23 138 138 F-[[X]+X]+F[+FX]-X
24 141 141 F-[[X]+X]+F[+FX]-X
25 154 154 F-[[X]+X]+F[+FX]-X
26 157 157 F-[[X]+X]+F[+FX]-X
27 164 164 F-[[X]+X]+F[+FX]-X
28 167 167 F-[[X]+X]+F[+FX]-X
29 174 174 F-[[X]+X]+F[+FX]-X
30 177 177 F-[[X]+X]+F[+FX]-X
31 184 184 F-[[X]+X]+F[+FX]-X
32 187 187 F-[[X]+X]+F[+FX]-X
33 209 209 F-[[X]+X]+F[+FX]-X
34 212 212 F-[[X]+X]+F[+FX]-X
35 219 219 F-[[X]+X]+F[+FX]-X
36 222 222 F-[[X]+X]+F[+FX]-X
37 229 229 F-[[X]+X]+F[+FX]-X
38 232 232 F-[[X]+X]+F[+FX]-X
39 239 239 F-[[X]+X]+F[+FX]-X
40 242 242 F-[[X]+X]+F[+FX]-X
41 255 255 F-[[X]+X]+F[+FX]-X
42 258 258 F-[[X]+X]+F[+FX]-X
43 265 265 F-[[X]+X]+F[+FX]-X
44 268 268 F-[[X]+X]+F[+FX]-X
45 275 275 F-[[X]+X]+F[+FX]-X
46 278 278 F-[[X]+X]+F[+FX]-X
47 285 285 F-[[X]+X]+F[+FX]-X
48 288 288 F-[[X]+X]+F[+FX]-X
49 300 300 F-[[X]+X]+F[+FX]-X
50 303 303 F-[[X]+X]+F[+FX]-X
51 310 310 F-[[X]+X]+F[+FX]-X
52 313 313 F-[[X]+X]+F[+FX]-X
53 320 320 F-[[X]+X]+F[+FX]-X
54 323 323 F-[[X]+X]+F[+FX]-X
55 330 330 F-[[X]+X]+F[+FX]-X
56 333 333 F-[[X]+X]+F[+FX]-X
57 346 346 F-[[X]+X]+F[+FX]-X
58 349 349 F-[[X]+X]+F[+FX]-X
59 356 356 F-[[X]+X]+F[+FX]-X
60 359 359 F-[[X]+X]+F[+FX]-X
61 366 366 F-[[X]+X]+F[+FX]-X
62 369 369 F-[[X]+X]+F[+FX]-X
63 376 376 F-[[X]+X]+F[+FX]-X
64 379 379 F-[[X]+X]+F[+FX]-X
[[2]]
start end insert
1 1 1 FF
2 2 2 FF
3 3 3 FF
4 4 4 FF
5 8 8 FF
6 9 9 FF
7 13 13 FF
8 23 23 FF
9 26 26 FF
10 33 33 FF
11 43 43 FF
12 46 46 FF
13 53 53 FF
14 54 54 FF
15 57 57 FF
16 58 58 FF
17 59 59 FF
18 69 69 FF
19 72 72 FF
20 79 79 FF
21 89 89 FF
22 92 92 FF
23 99 99 FF
24 100 100 FF
25 104 104 FF
26 114 114 FF
27 117 117 FF
28 124 124 FF
29 134 134 FF
30 137 137 FF
31 144 144 FF
32 145 145 FF
33 148 148 FF
34 149 149 FF
35 150 150 FF
36 160 160 FF
37 163 163 FF
38 170 170 FF
39 180 180 FF
40 183 183 FF
41 190 190 FF
42 191 191 FF
43 192 192 FF
44 193 193 FF
45 196 196 FF
46 197 197 FF
47 198 198 FF
48 199 199 FF
49 200 200 FF
50 201 201 FF
51 205 205 FF
52 215 215 FF
53 218 218 FF
54 225 225 FF
55 235 235 FF
56 238 238 FF
57 245 245 FF
58 246 246 FF
59 249 249 FF
60 250 250 FF
61 251 251 FF
62 261 261 FF
63 264 264 FF
64 271 271 FF
65 281 281 FF
66 284 284 FF
67 291 291 FF
68 292 292 FF
69 296 296 FF
70 306 306 FF
71 309 309 FF
72 316 316 FF
73 326 326 FF
74 329 329 FF
75 336 336 FF
76 337 337 FF
77 340 340 FF
78 341 341 FF
79 342 342 FF
80 352 352 FF
81 355 355 FF
82 362 362 FF
83 372 372 FF
84 375 375 FFFractal Grower
Head off to https://www.cs.unm.edu/~joel/PaperFoldingFractal/paper.html. Download the .jar file and save it say in your Documents folder. Open and play. Instructions are on the website.
Job Talle. Lindenmayer Systems https://jobtalle.com/lindenmayer_systems.html
C. J Jennings. L-systems. https://cgjennings.ca/articles/l-systems/
Przemysław Prusinkiewicz and Aristid Lindenmayer. The Algorithmic Beauty of Plants. Springer-Verlag, 1990.