Click here to Skip to main content
Licence 
First Posted 24 Dec 2005
Views 63,934
Bookmarked 33 times

The Koch Curve - Snowflake!

By | 24 Dec 2005 | Article
Using the Koch curve, a fractal, to draw a snowflake.

A merry Christmas to all CPians!

Introduction

This program is written in VS2005, however, it would be very easy to convert to VS2003 and .NET 1.1.

The Koch curve is a simple fractal that creates a pretty snowflake-like object. The iteration algorithm is very simple:

  1. Start with a straight line:

  2. Trisect the line into three segments:

  3. Form an equilateral triangle rising out of the middle segment:

  4. Repeat, with newly formed segment.

    If you start with an equilateral triangle instead of a line, you get the lovely image shown at the top of the article after a few iterations.

The program

The program is very simple. There are some constants that define the screen area, scaling and the offset of the initial snowflake, and the angle that we use to construct the equilateral triangle out of the middle segment:

private const int width = 400;
private const int height = 300;
private const double scale = 0.5;
private const int xoffset = width / 4;
private const int yoffset = height / 6;
private const double rangle = -60 * Math.PI / 180.0;
private const int maxFlakes=2;

While running, the program draws several snowflakes in random positions and in random colors. After a set limit (which in the demo I have set to 2), the first snowflake in the list is removed (rendering starts to really bog down if we keep all the snowflakes).

Initialization

public Form1()
{
  InitializeComponent();
  rand=new Random((int)DateTime.Now.Ticks);
  FormBorderStyle = FormBorderStyle.None;
  StartPosition = FormStartPosition.CenterScreen;
  ClientSize = new Size(width, height);
  backBrush = new SolidBrush(Color.LightBlue);
  pens = new List<Pen>(new Pen[] {new Pen(Color.White), 
               new Pen(Color.Red), new Pen(Color.Green)});
  segPen = pens[0];
  windowRect = new Rectangle(0, 0, width, height);
  SetStyle(ControlStyles.DoubleBuffer | ControlStyles.UserPaint | 
                        ControlStyles.AllPaintingInWmPaint, true);
  segments = new List<Segment>();
  flakes = new List<Flake>();
  segments.Add(new Segment(0, height, width/2, 0));
  segments.Add(new Segment(width/2, 0, width, height));
  segments.Add(new Segment(width, height, 0, height));
  timer = new Timer();
  timer.Interval = 100;
  timer.Tick += new EventHandler(OnTick);
  timer.Start();
}

Three pens are initialized and the starting equilateral triangle is constructed. The timer event will generate the next iteration. Also, the "working" snowflake segment collection is initialized, as well as the completed snowflake collection. You'll also note the SetStyle call, which enables double buffering and owner-draw painting of the form.

Painting

During painting, both the "working" snowflake and the completed snowflakes are drawn:

protected override void OnPaint(PaintEventArgs e)
{
  foreach (Segment seg in segments)
  {
    e.Graphics.DrawLine(segPen, Adjust(seg.P1), Adjust(seg.P2));
  }

  foreach (Flake flake in flakes)
  {
    flake.Draw(e.Graphics);
  }
}

You'll note that the Adjust method, which scales and offsets the coordinates, is used so as to preserve the accuracy of the snowflake's coordinates during iteration.

Iteration

When the timer event fires, the snowflake iterates to the next step, following the algorithm I described above:

void OnTick(object sender, EventArgs e)
{
  List<Segment> newSegments = new List<Segment>();

  foreach (Segment seg in segments)
  {
    double length=seg.Length/3;
    double a = Math.Atan2(seg.Height, seg.Width);
    a = a + rangle;
    Point p1 = new Point(seg.P1.X + seg.Width / 3, 
                         seg.P1.Y + seg.Height / 3);
    Point p2 = new Point(seg.P1.X + seg.Width * 2 / 3, 
                         seg.P1.Y + seg.Height * 2 / 3);
    Segment cutSeg = new Segment(p1.X, p1.Y, p2.X, p2.Y);
    Point p = new Point((int)(cutSeg.P1.X + length * Math.Cos(a)), 
                        (int)(cutSeg.P1.Y + length * Math.Sin(a)));
    newSegments.Add(new Segment(seg.P1.X, seg.P1.Y, p1.X, p1.Y));
    newSegments.Add(new Segment(p1.X, p1.Y, p.X, p.Y));
    newSegments.Add(new Segment(p.X, p.Y, p2.X, p2.Y));
    newSegments.Add(new Segment(p2.X, p2.Y, seg.P2.X, seg.P2.Y));
  }

The segment is split into three pieces, where p1 is used to construct the first third and p2 is used to construct the last third. The segment cutSeg is the middle segment, which is cut out and used to build the new equilateral triangle. The third point, p, of the triangle is determined, and the new segments are added to the collection.

Next:

  if (segments[0].Length <= 1)
  {
    foreach (Segment seg in newSegments)
    {
    seg.P1 = Adjust(seg.P1);
    seg.P2 = Adjust(seg.P2);
    }

    flakes.Add(new Flake(segPen, newSegments));

If the first segment's length is 1 or less, then any further iteration is pointless, so the "working" snowflake is added to the completed snowflake collection. The segment locations are scaled and offset one final time, since we don't need to work with them anymore.

Also:

    if (flakes.Count == maxFlakes)
    {
      flakes.RemoveAt(0);
    }

this code removes the first snowflake from the collection after a set number of snowflakes have been drawn.

Finally:

    segments.Clear();

    int rndX = rand.Next(width);
    int rndY = rand.Next(height/2)+height/2;
    int rndW = rand.Next(width - rndX);

    double a = rangle;
    Point p = new Point((int)(rndX + rndW * Math.Cos(a)), 
                        (int)(rndY + rndW * Math.Sin(a)));

    segments.Add(new Segment(rndX, rndY, p.X, p.Y));
    segments.Add(new Segment(p.X, p.Y, rndX + rndW, rndY));
    segments.Add(new Segment(rndX + rndW, rndY, rndX, rndY));
    segPen = pens[rand.Next(3)];
    }
  else
  {
    segments = newSegments;
  }

  Invalidate();
}

The working snowflake segment collection is cleared and a new pen and starting point for the next snowflake is randomly determined. At the very end of the timer, the form is invalidated so that the OnPaint is called.

Conclusion

The Koch curve is fun because you can do many things with it, such as creating random but interesting looking coastlines and continents. If you're ever in San Diego, I have (well, last time I looked) a permanent exhibit on fractals at the Reuben H. Fleet Science Center which illustrates this.

Further reading

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

About the Author

Marc Clifton



United States United States

Member

Marc is the creator of two open source projets, MyXaml, a declarative (XML) instantiation engine and the Advanced Unit Testing framework, and Interacx, a commercial n-tier RAD application suite.  Visit his website, www.marcclifton.com, where you will find many of his articles and his blog.
 
Marc lives in Philmont, NY with his son Ian.

Sign Up to vote   Poor Excellent
Add a reason or comment to your vote: x
Votes of 3 or less require a comment

Comments and Discussions

 
You must Sign In to use this message board. (secure sign-in)
 
Search this forum  
 FAQ
    Noise  Layout  Per page   
  Refresh
GeneralHere's another cool algorithm... Pinmemberfuzzylintman12:34 28 Dec '05  
GeneralRe: Here's another cool algorithm... PinmemberLuc Pattyn3:27 14 Jul '07  
GeneralFor those who do not have C# or VS2005 PinmemberPJ Arends22:59 24 Dec '05  
Hi Marc, I thought your idea was pretty neat, but unfortunately I do not have VS2005 or the .NET 2.0 runtime so it did not work on my machine. I slapped together a win32 c++ version but I did not think it deserved an article of it's own so I am posting the source here for anyone who wants it.
 
Hope you don't mind;)
 
Merry Christmas!
 
// Flakes.cpp : Defines the entry point for the application.
//
 
#define WIN32_LEAN_AND_MEAN		// Exclude rarely-used stuff from Windows headers
 
#include <windows.h>
 
#include <math.h>
#include <time.h>
#include <list>
using namespace std;
 
const double rangle = 0.0 - 60.0 * 3.1415926535897932384626433832795 / 180.0;
const int ScreenWidth = GetSystemMetrics(SM_CXSCREEN);
const int ScreenHeight = GetSystemMetrics(SM_CYSCREEN);
const int step = 1;
 
HWND MainWindow = NULL;
 
HDC DC1, DC2;
HBITMAP bmp1, bmp2;
 
class DPOINT
{
public:
    DPOINT() { x = 0.0; y = 0.0; }
    DPOINT(double a, double b) { x = a; y = b; }
    double x;
    double y;
 
    operator POINT() { POINT pt; pt.x = (int)x; pt.y = (int)y; return pt; }
    DPOINT &operator =(const DPOINT &pt) { x = pt.x; y = pt.y; return *this; }
};
 
list<DPOINT> Split(DPOINT one, DPOINT two)
{
    list<DPOINT> pts;
    double originalheight = two.y - one.y;
    double originalwidth = two.x - one.x;
    double originallength = sqrt((originalheight * originalheight) + (originalwidth * originalwidth));
 
    if (originallength >= 5.0)
    {
        double length = originallength / 3;
        double angle = atan2(originalheight, originalwidth) + rangle;
 
        DPOINT p1 (one.x + originalwidth / 3, one.y + originalheight / 3);
        DPOINT p2 (p1.x + length * cos(angle), p1.y + length * sin(angle));
        DPOINT p3 (one.x + originalwidth * 2 / 3, one.y + originalheight * 2 / 3);
 
        pts.push_back(p1);
        pts.push_back(p2);
        pts.push_back(p3);
    }
 
    return pts;
}
 
class Flake
{
public:
    Flake() { PenColour = RGB(0, 0, 0); }
    void Create()
    {
        DPOINT Point1, Point2;
        do {
            Point1 = DPOINT(0, 0);
            Point2 = DPOINT(rand() % 300, rand() % 300);
            points = Split(Point1, Point2);
        } while (points.empty());
 
        list<DPOINT> temp;
        bool Continue = true;
        list<DPOINT>::iterator it = points.begin();
 
        while (Continue)
        {
            Point1 = *it++;
            if (points.end() == it)
                it = points.begin();
            Point2 = *it;
            temp = Split(Point1, Point2);
            Continue = !temp.empty();
            points.splice(it, temp);
        }
 
        PenColour = RGB(rand() % 256, rand() % 256, rand() % 256);
    }
 
    void Draw(HDC DC, POINT pt)
    {
        point.x = pt.x;
        point.y = pt.y;
        int s = SaveDC(DC);
        HPEN Pen = CreatePen(PS_SOLID, 1, PenColour);
        SelectObject(DC, Pen);
        SetROP2(DC, R2_XORPEN);
 
        MoveToEx(DC, pt.x + points.front().x, pt.y + points.front().y, NULL);
        for (list<DPOINT>::iterator it = points.begin(); it != points.end(); ++it)
            LineTo(DC, pt.x + (*it).x, pt.y + (*it).y);
        LineTo(DC, pt.x + points.front().x, pt.y + points.front().y);
 
        RestoreDC(DC, s);
        DeleteObject(Pen);
    }
 
    void Erase(HDC DC)
    {
        Draw(DC, point);
    }
 
protected:
    list<DPOINT> points;
    COLORREF PenColour;
    POINT point;
};
 
LRESULT CALLBACK WndProc(HWND hWnd,
                         UINT nMsg,
                         WPARAM wp,
                         LPARAM lp)
{
    switch (nMsg)
    {
    case WM_SETCURSOR:
        ShowCursor(FALSE);;
        break;
 
    case WM_CREATE:
        {
            HDC ScreenDC = GetDC(NULL);
            DC1 = CreateCompatibleDC(ScreenDC);
            DC2 = CreateCompatibleDC(ScreenDC);
            bmp1 = CreateCompatibleBitmap(ScreenDC, ScreenWidth, ScreenHeight + 400);
            bmp2 = CreateCompatibleBitmap(ScreenDC, ScreenWidth, ScreenHeight + 400);
            ReleaseDC(NULL, ScreenDC);
            SelectObject(DC1, bmp1);
            SelectObject(DC2, bmp2);
            RECT rc = {0, 0, ScreenWidth, ScreenHeight + 400};
            HBRUSH br = CreateSolidBrush(RGB(0, 255, 255));
            FillRect(DC1, &rc, br);
            DeleteObject(br);
        }
        break;
 
    case WM_TIMER:
        {
            static int counter = 0;
            if (wp == 1)
            {
                HBRUSH br = CreateSolidBrush(RGB(0, 255, 255));
                RECT rc = {0, 0, ScreenWidth, step * counter};
                FillRect(DC1, &rc, br);
                DeleteObject(br);
                BitBlt(DC1, 0, 0, ScreenWidth, ScreenHeight + 400, DC2, 0, 0, SRCCOPY);
                Flake f;
                f.Create();
                POINT pt = { rand() % ScreenWidth, 200 };
                f.Draw(DC1, pt);
                counter = 0;
            }
            else if (wp == 2)
            {
                BitBlt(DC2, 0, step * counter++, ScreenWidth, ScreenHeight + 400, DC1, 0, 0, SRCCOPY);
                RedrawWindow(MainWindow, NULL, NULL, RDW_INVALIDATE | RDW_NOERASE);
            }
        }
        break;
 
    case WM_PAINT:
        {
            PAINTSTRUCT ps = {0};
            HDC DC = BeginPaint(MainWindow, &ps);
            if (DC)
            {
                BitBlt(DC,
                       0,
                       0,
                       ScreenWidth,
                       ScreenHeight,
                       DC2,
                       0,
                       400,
                       SRCCOPY);
                EndPaint(MainWindow, &ps);
            }
        }
        break;
 
    default:
        return DefWindowProc(hWnd, nMsg, wp, lp);
    }
    return 0;
}
 
int APIENTRY WinMain(HINSTANCE hInstance,
                     HINSTANCE hPrevInstance,
                     LPSTR     lpCmdLine,
                     int       nCmdShow)
{
    HBRUSH bkBrush = CreateSolidBrush(RGB(0, 255, 255));
    WNDCLASS WndClass = {0};
    WndClass.hInstance = hInstance;
    WndClass.lpfnWndProc = WndProc;
    WndClass.hbrBackground = bkBrush;
    WndClass.lpszClassName = "SnowFlake";
 
    if (!RegisterClass(&WndClass))
        throw ("Failed to register main window class");
 
    MainWindow = CreateWindowEx(0,//WS_EX_TOPMOST,
                                "SnowFlake",
                                "SnowFlake",
                                WS_POPUP | WS_VISIBLE,
                                0, 0, ScreenWidth, ScreenHeight,
                                NULL,
                                NULL,
                                hInstance,
                                NULL);
 
    if (MainWindow == NULL)
        throw ("Failed create main window");
 
    ShowWindow(MainWindow, SW_SHOW);
 
    SetTimer(MainWindow, 1, 1500, NULL);
    SetTimer(MainWindow, 2, 10, NULL);
 
    MSG msg = {0};
    while (GetMessage(&msg, MainWindow, 0, 0) > 0)
    {
        TranslateMessage(&msg);
        DispatchMessage(&msg);
    }
     return msg.wParam;
}

 
-- modified at 5:03 Sunday 25th December, 2005
fixed where html mangled code


"You're obviously a superstar." - Christian Graus about me - 12 Feb '03
 
"Obviously ???  You're definitely a superstar!!!" - mYkel - 21 Jun '04
 
"There's not enough blatant self-congratulatory backslapping in the world today..." - HumblePie - 21 Jun '05
 
Within you lies the power for good - Use it!

GeneralRe: For those who do not have C# or VS2005 PinprotectorMarc Clifton4:13 25 Dec '05  
GeneralRe: For those who do not have C# or VS2005 Pinmembergeoyar15:13 27 Dec '05  
GeneralJust as a side note PinmemberRobert Rohde22:51 24 Dec '05  
GeneralRe: Just as a side note PinprotectorMarc Clifton4:04 25 Dec '05  
GeneralVery cool... PinmemberRay Cassick10:24 24 Dec '05  
GeneralRe: Very cool... PinprotectorMarc Clifton10:59 24 Dec '05  
GeneralNice! PinmemberVertyg010:20 24 Dec '05  
GeneralRe: Nice! Pinmemberpeterchen0:10 25 Dec '05  

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Mobile
Web04 | 2.5.120528.1 | Last Updated 24 Dec 2005
Article Copyright 2005 by Marc Clifton
Everything else Copyright © CodeProject, 1999-2012
Terms of Use
Layout: fixed | fluid