Koch Snowflake and the Thue-Morse Sequence


When you first study recursion, you will invariably run into a “factorial” example. But if you are lucky, you will also run into a far more interesting algorithm – one that draws a fractal geometry construct called the “Koch snowflake”. This curve was discovered in 1904 by Swedish mathematician Helge von Koch [1]. Drawing this curve is straightforward, and we will do so using Python turtle graphics. But this curve also has a deeper connection with a mathematical sequence called the Thue-Morse sequence [2], which we will explore in a bit.


Koch Snowflake Construction


The Koch snowflake being a fractal, its structure can be defined in terms of itself. The math involved is shown in the figure below.


 


Once you know how to draw the line


A1P1P2P3B



you can draw the curve recursively as follows.



drawKoch(A, B):
if |AB| < delta:
draw A-P1-P2-P3-B
else:
drawKoch(A, P1)
drawKoch(P1, P2)
drawKoch(P2, PP3)
drawKoch(P3, B)


Now we are ready to draw this with turtle. The output is shown below. (Full code listing at the end of this article.)


 


Connection with the Thue-Morse Sequence


The Thue-Morse sequence is constructed as follows:


  1. Start with 0.
  2. Append the complement. You get 01.
  3. Repeat the previous step.

Here are the first five terms of the above procedure:


0
01
0110
01101001
0110100110010110


Now, consider the following drawing procedure.


Let t(n) be the Thue-Morse sequence.


  • If t(n) is 0, move forward by one unit.
  • If t(n) is 1, rotate (just change heading, don’t move) by 60 degrees anti-clockwise.

Keep repeating the above procedure, and guess what you get? Something astonishingly similar to the Koch snowflake! This idea has been explored by Jun Ma and Judy Holdener, in their 2005 paper “When Thue-Morse Meets Koch” [3]. The paper is not for the faint of heart, and although I am no mathematician, it looks like you need a background in Abstract Algebra and Topology to understand it. But you don’t need to know much to draw it. Here is what you get when you put turtle to task to draw the above.


 


I think this is mind-blowing, and this is why I love mathematics! 😉


Below is the full source code. Notice that we use a Python generator to create the Thue-Morse sequence.


To see the traditional Koch snowflake, run as:

$python koch.py


To see the Thue-Morse magic in action, run as:

$python koch.py --thue


 

"""
koch.py

Description:

A program that explores the Koch snowflake and the Thue-Morse sequence.

Author: Mahesh Venkitachalam
Website: electronut.in
"""

import time
import turtle
import math
import sys, argparse

# generate the Thue-Morse sequence
def genThueMorse():
    # initialize
    tms = '0'
    curr = 0
    while True:
        # generate next sequence
        if curr == len(tms):
            tmp = ''
            for i in range(len(tms)):
                if tms[i] is '0':
                    tmp += '1'
                else:
                    tmp += '0'
            tms += tmp
        yield tms[curr]
        curr +=1

# turtle graphics using Thue-Morse sequence
def drawTM(x, y):
    t = turtle.Turtle()
    t.hideturtle()
    t.up()
    t.setpos(x, y)
    t.down()
    tms = genThueMorse()
    delta = 4
    while True:
        a = next(tms)
        if a is '0':
            t.fd(delta)
        else:
            t.left(60)

# recursive koch snow flake
def kochSF(x1, y1, x2, y2, t):
    d = math.sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2))
    r = d/3.0
    h = r*math.sqrt(3)/2.0
    p3 = ((x1 + 2*x2)/3.0, (y1 + 2*y2)/3.0)
    p1 = ((2*x1 + x2)/3.0, (2*y1 + y2)/3.0)
    c = (0.5*(x1+x2), 0.5*(y1+y2))
    n = ((y1-y2)/d, (x2-x1)/d)
    p2 = (c[0]+h*n[0], c[1]+h*n[1])     
    if d > 10:
        # flake #1
        kochSF(x1, y1, p1[0], p1[1], t)
        # flake #2
        kochSF(p1[0], p1[1], p2[0], p2[1], t)
        # flake #3
        kochSF(p2[0], p2[1], p3[0], p3[1], t)
        # flake #4
        kochSF(p3[0], p3[1], x2, y2, t)
    else:
        # draw cone
        t.up()
        t.setpos(p1[0], p1[1])
        t.down()
        t.setpos(p2[0], p2[1])
        t.setpos(p3[0], p3[1])
        # draw sides
        t.up()
        t.setpos(x1, y1)
        t.down()
        t.setpos(p1[0], p1[1])
        t.up()
        t.setpos(p3[0], p3[1])
        t.down()
        t.setpos(x2, y2) 

# draw a koch snowflake
def drawKochSF(x1, y1, x2, y2):
    t = turtle.Turtle()
    t.hideturtle()
    kochSF(x1, y1, x2, y2, t)

# main() function
def main():
    print('Exploring the Koch Snowflake...')

    parser = argparse.ArgumentParser(description="Koch Snowflake")
    # add arguments
    parser.add_argument('--thue', action='store_true', required=False)
    args = parser.parse_args()

    if args.thue:
        drawTM(200, 200)
    else:
        drawKochSF(-100, 0, 100, 0)
        drawKochSF(0, -173.2, -100, 0)
        drawKochSF(100, 0, 0, -173.2)
        win = turtle.Screen()
        win.exitonclick()

# call main
if __name__ == '__main__':
    main()

References


  1. http://en.wikipedia.org/wiki/Koch_snowflake
  2. http://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence
  3. JUN MA AND JUDY HOLDENER, “When Thue-Morse meets Koch,” Fractals: Complex Geometry, Patterns, and Scaling in Nature and Society,13(2005) 191-206.