2420.sagews

We are going to generate a Sierpinski Triangle using an "L-system" method. An L-system can use a string of characters (which we will call the "genome") as instructions for drawing a picture. It starts out with a simple string (we call it the "start"), which is composed of some of the available instructions, and then uses a set of rules to modify the string over a series of iterations.

For example, if our instructions are "A" and "B" (where each letter draws something different), and our starting string is "AB" and we have one rule which specifies that each time we see the letter "B" we replace it with the string "BA," then after one iteration, "AB" will become "ABA". After another iteration, it will become "ABAA", since it replaces the "B" in "ABA" with "BA".

For our purposes, we will first set up the following instructions for use in the L-system calculations:

• F means "draw forward."
• G means "draw forward" as well. We need a separate letter for it because one of our replacement rules makes a distinction between F and G.
• + means "turn left by angle."
• - means "turn right by angle."

We will also use an angle of 60°.

(which we will call the "genome")

ANGLE = 60

F = "F"
G = "G"
P = "+"
M = "-"

For convenience, let's define which of the instructions are constants (are never replaced by any rule), and which are variables (are sometimes replaced by a rule):

convenience

CONSTS = (P, M)
VARS = (F, G)

Next, we define the generator rules.

For each tuple, the first value is the pattern to replace, and the second value is the pattern to replace it with.

The comment after the line should make the replacement clearer. It is of the form:

PATTERN_TO_REPLACE -> REPLACEMENT_PATTERN

rules = (
    (F, G + M + F + M + G), # F -> G-F-G
    (G, F + P + G + P + F)) # G -> F+G+F

Finally, we define the start state. In our case, it's just going to be a simple "go forward" instruction:

start = F

Before going any further, let's define the drawing algorithm and test it using the starting state.

update_angle will take one of the angle movement instructions and modify which direction the line is drawn based on instruction.

next_point takes the current angle and the current point, and uses that to draw the next point. Note that we have to a) convert from polar to rectangular coords (hence the trig functions), and also from degrees to radians (hence the math.pi / 180).

generate_lines parses the instructions in the genome and converts them into points and lines.

def update_angle(c, angle):
    if c == P:
        angle = angle + ANGLE
    if c == M:
        angle = angle - ANGLE
    return angle
    
def next_point(point, angle):
    x = point[0] + math.cos(angle * (math.pi / 180))
    y = point[1] + math.sin(angle * (math.pi / 180))
    return (x, y)

def generate_lines(genome):
    angle = 0
    point = (0, 0)
    points = [point]
    
    for c in genome:
        if c in CONSTS:
            angle = update_angle(c, angle)
        if c in VARS:
            point = next_point(point, angle)
            points.append(point)
    return line(points)

lines = generate_lines(start)
lines.plot()

Our starting instruction does nothing but go forward, so that looks about right.

Next, let's define the function that does the actual replacements:

def replace(genome, rules):
    new_genome = ""
    for c in genome:
        replacement_made = False
        for rule in rules:
            if rule[0] == c:
                new_genome = new_genome + rule[1]
                replacement_made = True
        if (not replacement_made):
            new_genome = new_genome + c
    return new_genome
    
def test_replace():
    expected = "G-F-G";
    print "Expected Result: " + expected
    actual = replace(start, rules)
    print "Actual Result: " + actual
    if expected == actual:
        print "The replacement algorithm seems to be working."
    else:
        print "Something's wrong with the replacement algorithm."

test_replace()

Expected Result: G-F-G Actual Result: G-F-G The replacement algorithm seems to be working.

Ok, so now that that's working, we just need to apply the replacement rules to the genome for an arbitrary number of iterations.

def l_generate(start, rules, iterations):
    genome = start
    for i in range(0, iterations):
        genome = replace(genome, rules)
    return genome

Now that everything's set up, let's plot the Sierpinski Triangles generated by a few different iteration values. We'll use 2, 4, 6, and 8. Note that the odd-numbered iterations don't actually generate the triangles: they are just steps to get to the even numbered iterations.

10 iterations creates a very smooth triangle, but it takes a while to calculate.

genome = l_generate(start, rules, 2)
lines = generate_lines(genome)
lines.plot()

genome = l_generate(start, rules, 4)
lines = generate_lines(genome)
lines.plot()

genome = l_generate(start, rules, 6)
lines = generate_lines(genome)
lines.plot()

genome = l_generate(start, rules, 8)
lines = generate_lines(genome)
lines.plot()