L-Systems

tags: Complex Systems

L-systems are string re-writing systems. They operate on an alphabet of symbols, rewriting symbols or patterns of symbols into new patterns according to a set of rules.

Examples

Fractal tree

A simple binary tree can be constructed with a L-system, using the rule (1 → 11), (0 → 1[0]0) and starting from a single 0.

This could be then drawn by a turtle drawer, where :

0 means “draw a leaf line of length a at the current position”
1 means “draw a line of length a at the current position”
[ means “store the current position, angle and length, turn by an angle alpha and reduce a by a factor l”
] means “retrieve latest position, angle and length, turn by an angle - alpha and reduce a by a factor l”

We start by defining a few helper functions that will help us manipulate the lines and generate children lines from parent lines with the correct rotations.

This could be coded in a recursive way, but since Python is not very suitable for this kind of programming anyways, we program it non-recursively. The drawing is not done like a turtle but line by line which was more convinient to implement.

""" This code generates a L-System tree fractal with chosen parameters.

In the following, a line is represented as a numpy array:
    [[x0, y0], [x1, y1]]
"""
import numpy as np
import matplotlib.pyplot as plt

def shorten(line: np.ndarray, length: float) -> np.ndarray:
    """ Shorten a line by some fixed amount (length is a number between
    0 and 1). Returns the shortened line.
    """
    return np.array([line[0], (1 - length) * line[0] + length * line[1]])


def rotate(line: np.ndarray, alpha: float):
    """ Rotate a line around its first point by an angle alpha (in radians).

    Returns the rotated line.
    """
    # Center line on origin
    origin_line = line - line[0]
    # Rotation matrix with angle alpha around origin
    rot_matrix = np.array(
        [[np.cos(alpha), -np.sin(alpha)],
         [np.sin(alpha), np.cos(alpha)]]
    )
    # Rotate just the second point since the first is origin.
    origin_line[1] = rot_matrix @ origin_line[1].T
    return origin_line + line[0]

def noise_factor(noise: float) -> float:
    """ Returns a factor of the form 1 + noise(). Noise amount can be
    scaled.
    """
    return 1 + noise * (2 * np.random.random() - 1)

def gen_new(line, alpha, length=0.5, noise=0.0):
    """ Generate a new pair of line from a base one. Lines are rotated
    and shortened according to `alpha` and `length`. Rotations and
    shortenings can be perturbed with the `noise` parameter.
    """
    short_line = (
        shorten(line, length * noise_factor(noise)) - line[0]
    )
    rot1 = (
        rotate(short_line, alpha * noise_factor(noise)) + line[1]
    )
    rot2 = (
        rotate(short_line, -alpha * noise_factor(noise)) + line[1]
    )
    return [rot1, rot2]

Now we can generate a beautiful tree and play with the parameters:

# Base line. Vertical, centered on x=0.5
x0 = np.array([[0.5, 0], [0.5, 0.5]])
lines = [ [x0] ]

# The angle can be changed
alpha = np.pi / 5

plt.figure(figsize=(5, 5))

# Number of generations can be tuned. Warning, exponential
# time in the number of gens.
n_generations = 11

for g in range(n_generations):
    new_lines = []
    base = lines[-1]
    for previous_line in base:
        # Tune parameters
        new_lines += gen_new(previous_line, alpha, 0.62, 0.5)
    lines.append(new_lines)

# Plot all the lines with decreasing width
for n in range(len(lines)):
    for l in lines[n]:
        plt.plot(
            *l.T,
            color="#43A6C6",
            linewidth=(0.92) ** n,
        )

plt.tight_layout()
plt.axis("off")
plt.savefig("l-system.svg")

This results in the following image:

Examples

Fractal tree

Comments