Fractal curve — Sierpinski arrowhead

Yesterday I wrote about the Koch curve, and today I’m writing about the Sierpinski arrowhead curve. The two fractal curves have a lot in common.

Wikipedia has some good illustrations.

The Sierpinski arrowhead curve draws an equilateral triangle with a bunch of triangular holes in it. It can be described with two substituting production rules: (A –> B-A-B) and (B –> A+B+A). A and B recurse and at the bottom do the same thing — draw a line. Plus and minus (+ and -) mean turn 60 degrees either left or right. The terminating point of the Sierpinski arrowhead curve is always the same provided you recurse an even number of times and you halve the length of the line at each recursion. If you recurse to an odd depth (order is odd) then you end up turned 60 degrees, at a different point in the triangle.

This is easy to describe in code. Given these drawing functions:

void draw_line( double distance);
void turn( int angle_in_degrees);

The code to draw an (approximate) Sierpinski arrowhead curve looks like this.

void curve( unsigned order, double length, int angle)
{
    if ( 0 == order ) {
        draw_line( length);
    } else {
        curve( order - 1, length / 2, - angle);
        turn( + angle);
        curve( order - 1, length / 2, + angle);
        turn( + angle);
        curve( order - 1, length / 2, - angle);
    }
}

void sierpinski_arrowhead_curve( unsigned order, double length)
{
    // If order is even we can just draw the curve.
    if ( 0 == (order & 1) ) {
        curve( order, length, +60);
    }
    else /* order is odd */ {
        turn( +60);
        curve( order, length, -60);
        turn( +60);
    }
}

The number of line segments is (3 ** order), and there is exactly one turn between any two adjacent lines. If you negate the starting angle you flip the triangle upside down.

You can also make a star or a hexagon.

void sierpinski_arrowhead_star( unsigned order, double length)
{
    sierpinski_arrowhead_curve( order, length);
    turn( -60);
    sierpinski_arrowhead_curve( order, length);
    turn( -60);
    sierpinski_arrowhead_curve( order, length);
    turn( -60);
    sierpinski_arrowhead_curve( order, length);
    turn( -60);
    sierpinski_arrowhead_curve( order, length);
    turn( -60);
    sierpinski_arrowhead_curve( order, length);
    turn( -60); /* full circle, back where we started */
}

void sierpinski_arrowhead_hexagon( unsigned order, double length)
{
    sierpinski_arrowhead_curve( order, length);
    turn( +60);
    sierpinski_arrowhead_curve( order, length);
    turn( +60);
    sierpinski_arrowhead_curve( order, length);
    turn( +60);
    sierpinski_arrowhead_curve( order, length);
    turn( +60);
    sierpinski_arrowhead_curve( order, length);
    turn( +60);
    sierpinski_arrowhead_curve( order, length);
    turn( +60); /* full circle, back where we started */
}

Disclaimer: I haven’t tested these functions. I’m just coding into the wild blue here.

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.