Fractal curve — Koch snowflake

The Koch snowflake is a fractal curve that looks like a six-sided star. It is composed of three Koch curves turned 120 degrees from each other. A Koch curve can be described with a single production rule that substitutes a line with 4 smaller lines. The rule is (line –> line/3 turn_left_60 line/3 turn_right_60 turn_right_60 line/3 turn_left_60 line/3) where line/3 is a third as long as the original. To get a true Koch curve you have to keep substituting forever. The curve gets infinitely long, but it always ends up at the same place. In other words, the end point of the last line is always the same no matter how many expansions. Wikipedia has some nice illustrations.

A finite approximation of the curve is easy to describe in C++. Assume the following drawing methods:

// drawing functions
void draw_line( double distance);
void turn( int angle_in_degrees);

It is easy to describe the Koch curve recursively. The order param controls how much detail is shown. For a true Koch curve order would have to be infinity, but an order 5 or 6 curve looks pretty good until you zoom in close.

void koch_curve( unsigned order, double length)
{
    if ( 0 == order ) {
        draw_line( length);
    } else {
        order -= 1;
        length /= 3;

        koch_curve( order, length);
        turn( 60);
        koch_curve( order, length);
        turn( -120);
        koch_curve( order, length);
        turn( 60);
        koch_curve( order, length);
    }
}

void koch_snowflake( unsigned order, double length_of_side)
{
    koch_curve( order, length_of_side);
    turn( -120);
    koch_curve( order, length_of_side);
    turn( -120);
    koch_curve( order, length_of_side);
}

You can also describe the Koch curve and snowflake with template functions, which work if the drawing order is a constant known at compile time.

template< unsigned N >
void koch_curve( double length)
{
    koch_curve< N - 1 >( length / 3);
    turn( 60);
    koch_curve< N - 1 >( length / 3);
    turn( -120);
    koch_curve< N - 1 >( length / 3);
    turn( 60);
    koch_curve< N - 1 >( length / 3);
}

template<>
void koch_curve< 0 >( double length)
{
    draw_line( length);
}

template< unsigned N >
void koch_snowflake( double length_of_side)
{
    koch_curve< N >( length_of_side);
    turn( -120);
    koch_curve< N >( length_of_side);
    turn( -120);
    koch_curve< N >( length_of_side);
}

These functions are not optimized. The first thing to do is pre-calculate the length used by the leaf-level calls to draw_line(..).

The number of lines multiplies by 4 with every increment of the starting order. So koch_curve<0>() draws one line, and koch_curve<1>() draws 4 lines (and makes three turns). koch_curve<2>() draws 16 lines (and makes 15 turns), koch_curve<3>() draws 64 lines, etc. If the compiler inline-expanded koch_curve<6>() it would become 4096 calls to draw_line( ((((((length/3)/3)/3)/3)/3)/3)). It would also have 4095 calls to turn(..), turning right (-120 degrees) 1365 times and left (60 degrees) 2730 times.

Disclaimer: I’ve compiled these functions but have not run them.

August 28, 2008 | Filed Under C/C++, Code, Graphics, Programming

1 Comment 

Comments

One Response to “Fractal curve — Koch snowflake”

  1. Tom Riedl on October 1st, 2009 11:50 am

    Please send Kock Snowflake C code and executable if you can. Will give full credit.

    Thank you,
    Dr. Tom

Leave a Reply