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

Inspiration

Japanese Daisugi

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→ABA\).

You can see how a self expanding sentence can be analogous to cell division in plants and other biological processes.

\[ axiom: AA \]

\[ Production ~ Rule: A --> ABA \]

\[ Iterations:\\\ 1. AA\\\ \]

\[ 2. ~\color{magenta}{A}~\color{Black}B~\color{magenta}{A}~~ ~\color{magenta}{A}~\color{Black}B~\color{magenta}{A}\\\ \] \[ 3.~\color{magenta}{ABA}~\color{Black}B~\color{magenta}{ABA} ~\color{magenta}{ABA}~\color{Black}B~\color{magenta}{ABA}\\\ \]

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.

All right, but how does this become a tree??

Two things need to be done:

• Each symbol in the language needs to be mapped to a left branch or a right branch. (with turn angle)
• At each application of the production rules, branch size is scaled down by a number.

Figure 1

Image Courtesy Christophe Eloy | University of Provence.

In the Figure 1, the RHS shows a typical figure generated by the L-system language. This figure shows both the LHS and RHS turns, and the fairly rapid reduction in the size of the branches.

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.

library(tidyverse)
###
library(LindenmayeR)
library(LearnGeom)
library(TurtleGraphics)
options(max.print = 20)

# 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     FF

Fractal 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. Make note of how the scaling factor works here.

Some suggestions!! Note the alphabet!!!

Col1	Col2
Pythagorean Tree: Axiom: [++!++!++!]xy Production Rules: x = [-[!++!++!++!]!xy y = [+![!++!++!++!]!xy - startAngle: 0 - turnAngle: 45.0 - growth : 1.408	! |
B. Krishna’s Anklets: Axiom: ++af-h-f+h - f ## h f++h++f-h-f++h++f-h-f++h Production Rules: f = f - h - f ++ h ++ f - h - f startAngle: 0 turnAngle: 45.0 growth:1.0	|

Design Principles for L-Systems

• Pick a set of symbols. i.e. our alphabet (say two or three letters of the alphabet)
• Map these to specific movements in the growth of the tree
• Decide on an axiom. It can include one or more of the symbols.
• Decide on a (set of) production rules. These should generate all the symbols in our alphabet. (Why?)
• Decide on a scaling factor
• Apply the production rules multiple times starting with the axiom, develop an extensive string using this recursion
• Plot the resulting string, scaling the individual recursions by the scaling factor.

Wait, But Why?

• By making use of “just sufficient randomness” in a few parameters, it is possible to generate very organic-looking trees
• These tree-like layouts can show up in a surprising number of places, such as transport networks, residential layouts.
• The multiple iterations generated from a few simple rules embody all the complexity of a language.
• Trees become a great metaphor for a diverse set of things and ideas.

References

1. Job Talle. Lindenmayer Systems https://jobtalle.com/lindenmayer_systems.html
2. C. J Jennings. L-systems. https://cgjennings.ca/articles/l-systems/
3. Joel Castellanos. Fractal Grower: Java Software for Growing Lindenmayer Substitution Fractals (L-systems). https://www.cs.unm.edu/~joel/PaperFoldingFractal/paper.html
4. Paul Bourke. L systems User Notes. https://paulbourke.net/fractals/lsys/
5. Przemysław Prusinkiewicz and Aristid Lindenmayer. The Algorithmic Beauty of Plants. Springer-Verlag, 1990.