Koch Snowflake

The Koch curve is a curve defined by a very simple process. Starting with a straight line segment having length L:

1. divide the line segment into 3 equal parts of length L/3
2. replace the middle part from step 1 with an equilateral triangle having sides of length L/3
3. erase the base of the triangle from step 2

At the end of step 3, you now have a curve made up of 4 equal line segments where the original middle segment has been replaced by a trianglar bump. If you repeat the steps with each line segment over and over again (an infinite number of times) you get the Koch curve (discovered by Swedish mathematician Helge von Koch in 1904). The Koch curve is mathematically interesting because it is an infinitely long curve that occupies a finite area. It was one of the earliest fractal curves to be described.

The Koch snowflake is made up of three Koch curves joined together.

It is surprisingly easy to use the Turtle class to generate the Koch curve.

1. move the turtle forward a distance of L/3
2. turn left 60 degrees (to start the middle triangular bump)
3. move the turtle forward a distance of L/3
4. turn right 120 degrees
5. move the turtle forward a distance of L/3 (to finish the middle triangular bump)
6. turn left 60 degrees
7. move the turtle forward a distance of L/3

If everytime the turtle moves forward you repeat the above steps then you will generate the Koch curve. The key to making this work is to encapsulate the above steps in a method, and have the method call itself. Such a method is called a recursive method, and we will be studying these in greater detail later in the course. For now, use the program below to test your Turtle class. You should get the following output:

The main method of the program creates 6 Turtle objects (5 of them using a copy construtor). Each turtle is responsible for drawing one Koch snowflake. The important method in this program is the the drawKoch method which draws a Koch curve for each turtle it is given. The method implements the algorithm described above except that every move forward step is replaced with another invocation of drawKoch. We cannot do this forever without running out of memory, so an additional method parameter (depth) is used to control the number of times we recursively invoke drawKoch. By decreasing depth each time we invoke drawKoch we eventually reach the case where depth == 0 at which point we finally tell the turtle to move forward and draw the line.

package lab.turtle;

import java.util.ArrayList;
import java.util.List;

public class KochSnowflake {

  private static void drawKochSnowflake(List<Turtle> turtles) {
    
      drawKoch(turtles, 0.87, 4);
      for (Turtle t : turtles) {
        t.turn(-120.0);
      }
      drawKoch(turtles, 0.87, 4);
      for (Turtle t : turtles) {
        t.turn(-120.0);
      }
      drawKoch(turtles, 0.87, 4);
  }

  private static void drawKoch(List<Turtle> turtles, double length, int depth) {
    if (depth == 0) {
      for (Turtle t : turtles) {
        t.move(length);
      }
    } else {
      length /= 3.0;
      drawKoch(turtles, length, depth - 1);
      for (Turtle t : turtles) {
        t.turn(60.0);
      }
      drawKoch(turtles, length, depth - 1);
      for (Turtle t : turtles) {
        t.turn(-120.0);
      }
      drawKoch(turtles, length, depth - 1);
      for (Turtle t : turtles) {
        t.turn(60.0);
      }
      drawKoch(turtles, length, depth - 1);
    }
  }

  public static void main(String[] args) {
    StdDraw.circle(0, 0, 1.01);
  
    List<Turtle> turtles = new ArrayList<Turtle>();
    Turtle t = new Turtle();
    turtles.add(t);
    for (int i = 1; i < 6; i++) {
      Turtle ti = new Turtle(turtles.get(i - 1));
      ti.turn(60.0);
      turtles.add(ti);
    }    
    drawKochSnowflake(turtles);
  }
}