Blog

August 03, 2014 | Python |

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 $$A_{1}-P_{1}-P_{2}-P_{3}-B$$ 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

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.

Questions/Comments

We love hearing from our readers. Email us at info@electronut.in for questions or comments on this article. If you found this article useful, please support us by buying some of our Open Source hardware products - like ZeroDriver - an Arduino Zero compatible motor driver for robotics. ZeroDriver is crowdfunding right now. Please click here to support our campaign. and bring this product to market!


Please sign up for updates

Once in a while, we will send you an email update on the latest Electronut Labs projects and products. Your email address will never be shared or abused, ever.

2016 Electronut Labs. All rights reserved.