Title: Use L-systems to draw fractals in Python

$[A Hilbert curve fractal]$

The following posts show how you can draw some fractals.

Those programs use methods that draw a series of lines to create fractal shapes. You can make other similar programs to draw other fractals, but there's also a way that you can generalize the process by using an L-system.

L-Systems

In 1968 the Hungarian biologist Aristid Lindenmayer developed a technique called an L-system or Lindenmayer system that lets you specify how this kind of fractal works. An L-system has at least three parts: an alphabet of symbols that it uses, a set of production rules, and an "axiom" that gives the system's starting point.

For a given desired depth of complexity, the program repeatedly applies the rules to the axiom. When it is finished, the program uses the resulting script to draw the fractal.

Koch Snowflake

$[A Koch snowflake fractal]$ For example, consider the Koch snowflake on the right. The example generated it by using the following L-system.

Alphabet: F, -, +
Rules: F: F+F--F+F
Axiom: F--F--F

The rule F: F+F--F+F means you replace the letter F (on the left) with the string F+F--F+F. For example, if you apply the rule to the axiom F--F--F you get F+F--F+F--F+F--F+F--F+F--F+F.

Note that you apply all rules simultaneously. For example, if there are two rules, then you apply each rule to every character in the axiom at the same time, you don't apply one rule and then apply the second rule to the result. (This will be easier to understand when you see the code that does it.)

When you've evaluated the rules as many times as desired, you use the resulting script to draw the fractal.

In most cases, the - symbol means "turn left," the + symbol means "turn right," and other symbols mean "draw forward." The angle through which you turn depends on the fractal. (It's 60° for the Koch snowflake.)

You can probably calculate the distance you need to draw to make the result appear in a designated target area, but it's easier to just calculate the points and then scale the result to fit.

Python Code

The following get_l_system_points method processes an L-system and returns a list of points.

def get_l_system_points(depth, theta, axiom, ignore, rules, dtheta): '''Apply an L-system.''' # Build the final script. script = axiom for i in range(depth): new_script = '' for ch in script: if ch in rules: new_script += rules[ch] else: new_script += ch script = new_script # print(script) # Create the points. p1 = (0, 0) length = 100 points = [p1] for ch in script: if ch in ignore: pass elif ch == '-': theta -= dtheta elif ch == '+': theta += dtheta else: x = p1[0] + length * math.cos(theta) y = p1[1] + length * math.sin(theta) p1 = (x, y) points.append(p1) # Return the points. return points

The method takes the following inputs:

depth - The number of times it should apply the rules.
theta - The initial angle toward which the points should move.
axiom - The axiom.
ignore - A list of characters to ignore when drawing. (Some rules use symbols to produce a final script that are not used when drawing.)
rules - The dictionary of rules. The keys are the rule names as in F and the values are the replacements as in F+F--F+F.
dtheta - The angle through which the drawing should turn for the - and + characters.

The code starts by copying the axiom into variable script. It then loops through the desired number of iterations.

For each iteration, the code loops through the script's characters. If a character is a key in the rules dictionary (like F, the code adds its value to the new script that it is building. If the character is not a rule key (like - or +), the program adds it unchanged to the new script.

After it has finished its pass through the script, it copies the new script into variable script.

Once it has finished applying the rules the desired number of times, the code generates the curve's points. It makes a points list containing the point (0, 0). It then iterates through the script.

When it finds a script character in the ignore list, the code skips it.

When it finds a - or + character, the code subtracts or adds dtheta to theta.

When it finds any other character, the method moves distance length in direction theta, calculates the new point's location, and adds it to the points list.

After it finishes processing the script, the method returns the points list.

Scaling Results

The get_l_system_points method generates points, but they start at the point (0, 0) and it's not clear where they end up. The example program uses the following fit_to_canvas method to scale the points so they are centered on a canvas widget.

def fit_to_canvas(canvas, curve, margin): '''Scale a curve to fit a canvas.''' # Get the canvas's dimensions. canvas_wid = canvas.winfo_width() - 2 * margin canvas_hgt = canvas.winfo_height() - 2 * margin # Get the curve's dimensions. x1, y1, x2, y2 = canvas.bbox(curve) curve_wid = x2 - x1 curve_hgt = y2 - y1 # Calculate the scale factor. x_scale = (canvas_wid - 2 * margin) / curve_wid y_scale = (canvas_hgt - 2 * margin) / curve_hgt scale = min(x_scale, y_scale) # Scale the curve. canvas.scale(curve, 0, 0, scale, scale) # Center the curve. x1, y1, x2, y2 = canvas.bbox(curve) cx = (x1 + x2) / 2 cy = (y1 + y2) / 2 xmin = cx - canvas_wid / 2 xmax = cx + canvas_wid / 2 ymin = cy - canvas_hgt / 2 ymax = cy + canvas_hgt / 2 canvas.config(scrollregion=(xmin, ymin, xmax, ymax))

This method first uses winfo_width and winfo_height to get the canvas's dimensions minus a margin. It then uses the canvas widget's bbox method to get a bounding box for the points and uses that to get the curve's dimensions.

Next, the code calculates a scale factor that will make the curve fit within the canvas's dimensions. It then calls the canvas widget's scale method to scale the points.

The code then finds the center of the curve's bounding box and uses it to calculate a rectangle the size of the canvas and centered on the curve. It sets the canvas's scroll region to that rectangle so the canvas draws the curve in its center.

Conclusion

$[A Peano-Gosper curve fractal]$ The main program builds a list of L-systems. For example, the Peano-Gosper curve on the right uses the following data.

'Peano-Gosper Curve': ( {'X': 'X+YF++YF-FX--FXFX-YF+', 'Y': '-FX+YFYF++YF+FX--FX-Y'}, 'FX', '', 60, 7),

This curve has two rules (one for the symbol X and one for Y), axiom FX, ignores no characters (that's the empty set of quotes), and turns 60° when it turns. The final value 7 is the maximum depth of recursion the program allows for this curve because values larger than that make the screen completely black.

When you select a curve from the program's dropdown list, the code looks up the corresponding L-system and draws it.

Download the example to experiment with it. In another post (probably my next), I'll add another feature commonly implemented by L-systems that lets the program draw disconnected curves.

For more information on L-systems, look online, for example on Wikipedia.

$[A Gosper boundary fractal]$ $[A Sierpi?ski curve fractal]$