Visualizing Lindenmayer system#


A Lindenmayer system or L-system is a mathematical system that can be used to describe growth process such as the growth of plants. Formally, it is a symbol expansion system whereby rewrite rules are applies iteratively to generate a longer string of symbols starting from a simple initial state. In this notebook, we will see how various types of fractal, including plant-like ones can be generated with L-systems and visualized with HoloViews.

import holoviews as hv
from holoviews import opts
import numpy as np

This notebook makes extensive use of the Path element and we will want to keep equal aspects and suppress the axes:

opts.defaults(opts.Path(xaxis=None, yaxis=None, show_title=False, color='black'))

Some simple patterns#

In this notebook, we will be drawing paths relative to an agent, in the spirit of turtle graphics. For this we define a simple agent class that has a path property to show us the path travelled from the point of initialization:

class SimpleAgent(object):
    def __init__(self, x=0,y=0, heading=0):
        self.x, self.y = x,y
        self.heading = heading
        self.trace = [(self.x, self.y)]
    def forward(self, distance):
        self.x += np.cos(2*np.pi * self.heading/360.0)
        self.y += np.sin(2*np.pi * self.heading/360.0)
    def rotate(self, angle):
        self.heading += angle
    def back(self, distance):
        self.heading += 180
        self.heading += 180
    def path(self):
        return hv.Path([self.trace])

We can now test our SimpleAgent by drawing some spirographs:

def pattern(angle= 5):
    agent = SimpleAgent()
    for i in range(360//angle):
        for i in range(4):
    return agent
(pattern(20).path + pattern(10).path + pattern(5).path
 + pattern(5).path * pattern(10).path * pattern(20).path).cols(2)

We can also draw some pretty rose patterns, adapted from these equations:

def roses(l,n,k):
    agent = SimpleAgent()
    n * 10
    x = (2.0 * k -n) / (2.0 * n)
    for i in range(360*n):
        agent.rotate(i + x)
    return agent

roses(5, 7, 3).path + roses(5, 12, 5).path

Following rules#

We now want to the capabilites of our agent with the ability to read instructions, telling it which path to follow. Let’s define the meaning of the following symbols:

F: Move forward by a pre-specified distance.
B: Move backwards by a pre-specified distance.
+: Rotate anti-clockwise by a pre-specified angle.
-: Rotate clockwise by a pre-specified angle.

Here is an agent class that can read strings of such symbols to draw the corresponding pattern:

class Agent(SimpleAgent):
    "An upgraded agent that can follow some rules"
    default_rules = {'F': lambda t,d,a: t.forward(d),
                     'B': lambda t,d,a: t.back(d),
                     '+': lambda t,d,a: t.rotate(-a),
                     '-': lambda t,d,a: t.rotate(a)}
    def __init__(self, x=0,y=0, instructions=None, heading=0,  
                 distance=5, angle=60, rules=default_rules):
        super(Agent,self).__init__(x,y, heading)
        self.distance = distance
        self.angle = angle
        self.rules = rules
        if instructions: self.process(instructions, self.distance, self.angle)
    def process(self, instructions, distance, angle):
        for i in instructions:          
            self.rules[i](self, distance, angle)

Defining L-Systems#

L-systems are defined with a rewrite system, making use of a set of production rules. What this means is that L-systems can generate instructions for our agent to follow, and therefore generate paths.

Now we define the expand_rules function which can process some expansion rules to repeatedly substitute an initial set of symbols with new symbols:

def expand_rules(initial, iterations, productions):
    "Expand an initial symbol with the given production rules"
    expansion = initial
    for i in range(iterations):
        intermediate = ""
        for ch in expansion:
            intermediate = intermediate + productions.get(ch,ch)
        expansion = intermediate
    return expansion

Koch curve and snowflake#

To demonstrate expand_rules, let’s define two different rules:

koch_curve = {'F':'F+F-F-F+F'}     # Replace 'F' with 'F+F-F-F+F'
koch_snowflake = {'F':'F-F++F-F'}  # Replace 'F' with 'F-F++F-F'

Here are the first three steps using the first rule:

for i in range(3):
    print('%d: %s' % (i, expand_rules('F', i, koch_curve)))
0: F
1: F+F-F-F+F
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

Note that these are instructions our agent can follow!

k1 = Agent(-200, 0, expand_rules('F', 4, koch_curve), angle=90).path
k2 = Agent(-200, 0, expand_rules('F', 4, koch_snowflake)).path
(k1 + k2 + (k1 * k2)).opts(opts.Path(color=hv.Cycle()))

This shows two variants of the Koch snowflake where koch_curve is a variant that uses right angles.

Sierpinski triangle#

The following example introduces a mutual relationship between two symbols, ‘A’ and ‘B’, instead of just the single symbol ‘F’ used above:

sierpinski_triangle = {'A':'B-A-B', 'B':'A+B+A'}
for i in range(3):
    print('%d: %s' % (i, expand_rules('A', i,sierpinski_triangle)))
0: A
1: B-A-B
2: A+B+A-B-A-B-A+B+A

Once again we can use these instructions to draw an interesting shape although we also need to define what these symbols mean to our agent:

sierpinski_rules = {'A': lambda t,d,a: t.forward(d),
         'B': lambda t,d,a: t.forward(d),
         '+': lambda t,d,a: t.rotate(-a),
         '-': lambda t,d,a: t.rotate(a)}

instructions = expand_rules('A', 9,sierpinski_triangle)
Agent(x=-200, y=0, rules=sierpinski_rules, instructions=instructions, angle=60).path.opts(opts.Path(color='green'))

We see that with our L-system expansion in terms of ‘A’ and ‘B’, we have defined the famous Sierpinski_triangle fractal.

The Dragon curve#

Now for another famous fractal:

dragon_curve = {'X':'X+YF+', 'Y':'-FX-Y'}

We now have two new symbols ‘X’ and ‘Y’ which we need to define in addition to ‘F’, ‘+’ and ‘-’ which we used before:

dragon_rules = dict(Agent.default_rules, X=lambda t,d,a: None, Y=lambda t,d,a: None)

Note that ‘X’ and ‘Y’ don’t actual do anything directly! These symbols are important in the expansion process but have no meaning to the agent. This time, let’s use a HoloMap to view the expansion:

def pad_extents(path):
    "Add 5% padding around the path"
    minx, maxx = path.range('x')
    miny, maxy = path.range('y')
    xpadding = ((maxx-minx) * 0.1)/2
    ypadding = ((maxy-miny) * 0.1)/2
    path.extents = (minx-xpadding, miny-ypadding, maxx+xpadding, maxy+ypadding)
    return path
hmap = hv.HoloMap(kdims='Iteration')
for i in range(7,17):
    path = Agent(-200, 0, expand_rules('FX', i, dragon_curve), rules=dragon_rules, angle=90).path
    hmap[i] = pad_extents(path)