The Koch snowflake

Jordan2R · July 2014

Hi there everyone!

// beginning of the intro, don't need to read it if you want

In the last weeks, I got really interested in Fractals and Procedural Content Generation (PCG for short). I started to study PCG before finding out about this class. I didn't study it much though, I was playing with dungeon creation in Unity with a very simple algorithm.

Now, with this course, I thought in learning about Fractals, how they work and how could I create them. I don't want any code ready, but I want to start from the very beginning. I thought the Koch snowflake was a good one to start over and use it as my first assignment here. Actually, to be honest, I was going to do another thing as my first assignment, but setFilter() and ramp() aren't working on Java mode and I'm having problems in putting my code to work in Javascript mode, so I gave up on my code and started doing this Fractal.

// end of the intro, beginning of the problem itself

Well, I've done this code right here:

  class Segment
  {
    float x1, x2, y1, y2;
    public Segment[] subd = new Segment[5];

    public Segment(float x1, float y1, float x2, float y2)
    {
      this.x1 = x1;
      this.x2 = x2;
      this.y1 = y1;
      this.y2 = y2;
    }

    void drawSegment()
    {
      pushMatrix();
      translate(x1, y1);
      line(0,0, x2-x1, y2-y1);
      popMatrix();
    }

    void subdivision()
    {
        float distX = (x2-x1)/3.0;
        float distY = (y2-y1)/3.0;

        for(int i = 0; i < 3; ++i)
          this.subd[i] = new Segment(x1 + i*distX, y1 + i*distY, x1 + (i+1)*distX, y1 + (i+1)*distY);

      this.subd[3] = new Segment(0, 0, x2 - x1, y2 - y1);
      this.subd[4] = new Segment(0, 0, x1 - x2, y1 - y2);
    }

    void triangleCreation()
    {    
      pushMatrix();
      translate(x1,y1);
      rotate(PI/3.0);
      this.subd[3].drawSegment();
      popMatrix();

      pushMatrix();
      translate(x2,y2);
      rotate(-PI/3.0);
      this.subd[4].drawSegment();
      popMatrix();
    }

    void finalDraw()
    {
      this.subdivision();
      this.subd[0].drawSegment();
      this.subd[2].drawSegment();
      this.subd[1].subdivision();
      this.subd[1].triangleCreation();

      Segment temp = subd[1];
      subd[1] = subd[4];
      subd[4] = temp;
    }
  }

  void setup()
  {
    size(600,600);
    background(255);

    Segment supra = new Segment(150,250,350,250);

    supra.finalDraw();
    for(int i = 0; i < 4; i++)
    {
      Segment[] vect = supra.subd;
      vect[i].finalDraw();

      for(int j = 0; j < 4; j++)
        vect[i].subd[j].finalDraw();
    }

  }

In Wikipedia (this link: http://en.wikipedia.org/wiki/Koch_snowflake), says that in order to create Koch snowflake I should:

Create a line segment (I made one, in this case called supra)
Draw an equillateral triangle using the middle segment
Remove the middle segment (I've done these last two steps with triangleCreation).

Then for each segment remained, do the same steps.

So I've created a class called Segment and within that class I created an attribute (or internal variable, as you wish), which is from trype Segmment[] (it's actually an array of Segment's). Then I use the finalDraw() function to do the three steps above. They work for the first line segment (supra, in this case). But the algorithm doesn't work for the 4 segments created from it (from supra).

Why's that? What am I doing wrong? What I am thinking wrong? Does anyone know a good (I mean, very good) online tutorial or series that teach about Fractals in a way that's not very hard to understand? Because the ones I find people write it in a very formal or scientific way that makes it hard or boring to read. I want something easy and that teaches everything I need to know.

I really would appreciate some help with this code. Thank you guys!

Jordan2R · July 2014

I'm not understanding why the code is being chopped like that. I already tried to fix it, but I couldn't. If you prefer, I've posted the same question on another forum (the forum's course that I'm doing actually) and you can read the code clearly:

https://class.coursera.org/digitalmedia-002/forum/thread?thread_id=572

GoToLoop · July 2014

I'm not understanding why the code is being chopped like that.

In order for the forum's code formatting to kick in, the code block needs at least 4 margin spaces!
Just highlight your code block and hit CTRL+K and those 4 spaces are automatically inserted!

Jordan2R · July 2014

I had put 4 spaces within Processing. So I didn't try CTRL+K as the post for beginners said because I thought it would have had the same effect. But that did the trick, thanks mate!

asimes · July 2014

I played with your code a bit, although what I have works, it really needs to be made recursive. You can already see that iterating subdivisions in draw() is quite painful and this only subdivides three times.

What I did was make the subdivision calculate the 5 points of the 4 new line segments (the first point is trivial). I made a diagram in the comments to try to show this.

Also there is a Processing example of a Koch Snowflake: http://processing.org/examples/koch.html

float sixtyDegrees;
Segment supra;

void setup() {
  size(600, 600);
  sixtyDegrees = PI/3.0;
  supra = new Segment(0.0, 200, 300, 400, 300);
  noLoop();
}

void draw() {
  background(255);

  // Iteration 1
  supra.subdivision();

  // Iteration 2
  for (int i = 0; i < 4; i++)
    supra.subd[i].subdivision();

  // Iteration 3
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++)
      supra.subd[i].subd[j].subdivision();

  // Only draw the last iteration
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++)
      supra.subd[i].subd[j].display();
}

class Segment {
  float ang, x1, x2, y1, y2;
  Segment[] subd = new Segment[4];

  Segment(float inAng, float inX1, float inY1, float inX2, float inY2) {
    ang = inAng;
    x1 = inX1;
    y1 = inY1;
    x2 = inX2;
    y2 = inY2;
  }

  void drawSegment() {
    line(x1, y1, x2, y2);
  }

  void subdivision() {
    float deltaX = (x2-x1)/3.0;
    float deltaY = (y2-y1)/3.0;
    float dist = sqrt(deltaX*deltaX+deltaY*deltaY);

    // Calculate the new points once
    // Imagine that they look like this:
    // .................
    // ....... 3 .......
    // ...... / \ ......
    // 1 --- 2   4 --- 5
    // .................

    float newX1 = x1;
    float newY1 = y1;
    float newX2 = newX1+deltaX;
    float newY2 = newY1+deltaY;
    float newX3 = newX2+cos(ang-sixtyDegrees)*dist;
    float newY3 = newY2+sin(ang-sixtyDegrees)*dist;
    float newX4 = newX3+cos(ang+sixtyDegrees)*dist;
    float newY4 = newY3+sin(ang+sixtyDegrees)*dist;
    float newX5 = newX4+deltaX;
    float newY5 = newY4+deltaY;

    subd[0] = new Segment(ang, newX1, newY1, newX2, newY2);
    subd[1] = new Segment(ang-sixtyDegrees, newX2, newY2, newX3, newY3);
    subd[2] = new Segment(ang+sixtyDegrees, newX3, newY3, newX4, newY4);
    subd[3] = new Segment(ang, newX4, newY4, newX5, newY5);
  }

  void display() {
    for (int i = 0; i < 4; i++) subd[i].drawSegment();
  }
}

Jordan2R · July 2014

Hey the asimes. First of all, I thank you from the bottom of my heart for spending some of your time to help me out!

Second, I understood everything of the code you wrote, except the ang variable. Could explain to me, please? I've changed 0.0 to PI and HALF_PI to see what would happend, and weird stuff happened man hahahahah.

Third, couldn't I change:

float newX4 = newX3+cos(ang+sixtyDegrees)*dist;
float newY4 = newY3+sin(ang+sixtyDegrees)*dist;

to:

float newX4 = newX2+ deltaX;
float newY4 = newY2+ deltaY;

??

Thanks for the link, I was trying to do without seeing any, but I'll just see it. I still don't understand what was wrong with my code, but again, thanks a lot buddy!

asimes · July 2014

@Jordan2R, The ang variable is short for angle. By default, angle 0.0 (such as x = cos(0.0) and y = sin(0.0)) points to the right which is problematic because newly generated lines are not always horizontal. To deal with this problem each line stores its current angle so that the triangle line segments can be placed relative to that angle.

I did just try plugging in PI instead of 0.0 to supra's constructor, the result was pretty funny. When I wrote this I assumed that the initial line was being drawn from left to right. It can be changed by playing with the arguments, here is a top to bottom one:

supra = new Segment(HALF_PI, 300, 100, 300, 500);

Here is an upside-down one:

supra = new Segment(PI, 500, 300, 100, 300);

Actually your suggestion (placing newX4 and newY4 based on newX2 and newY2) does seem to work for me (all I did was copy / paste the code I posted and replace the two lines of code). I didn't do that in my code to make it clear I was positioning each point based on the previous one, but it is more efficient to do it your way.

As far as your own code goes, I became confused with the extra line segment generated which has index 1 (you have 5 line segments instead of 4):

for(int i = 0; i < 3; ++i)
        this.subd[i] = new Segment(x1 + i*distX, y1 + i*distY, x1 + (i+1)*distX, y1 + (i+1)*distY);

It seems that this extra line segment would complete the triangle yet it is used in your finalDraw() function. Combining logic for drawing and subdividing in the same function also confused me so I separated them.

Jordan2R · July 2014

@asimes, I see man, now I've understood everything. I'm really appreciated for your time and help. When you need help too, tell me and I'll try to help you with everything I can!

asimes · July 2014

@Jordan2R, no problem, glad it made sense. I ended up playing with it again later and tried this out to finish the snowflake:

float sixtyDegrees;

void setup() {
  size(600, 600);
  sixtyDegrees = PI/3.0;
  noLoop();
}

void draw() {
  background(255);

  float[] x = new float[3];
  float[] y = new float[3];
  for (int i = 0; i < 3; i++) {
    x[i] = width/2+cos(sixtyDegrees*i*2.0)*200.0;
    y[i] = height/2+sin(sixtyDegrees*i*2.0)*200.0;
  }

  Segment[] snowflake = new Segment[3];
  for (int i = 0; i < 3; i++) {
    float ang = sixtyDegrees*i*2.0+sixtyDegrees*2.5;
    snowflake[i] = new Segment(ang, x[i], y[i], x[(i+1)%3], y[(i+1)%3]);
  }

  for (int i = 0; i < 3; i++) {
    snowflake[i].subdivision();
    for (int j = 0; j < 4; j++) {
      snowflake[i].subd[j].subdivision();
      for (int k = 0; k < 4; k++) {
        snowflake[i].subd[j].subd[k].subdivision();
        for (int l = 0; l < 4; l++) {
          snowflake[i].subd[j].subd[k].subd[l].subdivision();
          for (int m = 0; m < 4; m++)
            snowflake[i].subd[j].subd[k].subd[l].subd[m].subdivision();
        }
      }
    }
  }

  for (int i = 0; i < 3; i++) {
    //line(x[i], y[i], x[(i+1)%3], y[(i+1)%3]);
    //snowflake[i].display();
    for (int j = 0; j < 4; j++) {
      //snowflake[i].subd[j].display();
      for (int k = 0; k < 4; k++) {
        //snowflake[i].subd[j].subd[k].display();
        for (int l = 0; l < 4; l++) {
          //snowflake[i].subd[j].subd[k].subd[l].display();
          for (int m = 0; m < 4; m++)
            snowflake[i].subd[j].subd[k].subd[l].subd[m].display();
        }
      }
    }
  }
}

class Segment {
  float ang, x1, x2, y1, y2;
  Segment[] subd = new Segment[4];

  Segment(float inAng, float inX1, float inY1, float inX2, float inY2) {
    ang = inAng;
    x1 = inX1;
    y1 = inY1;
    x2 = inX2;
    y2 = inY2;
  }

  void drawSegment() {
    line(x1, y1, x2, y2);
  }

  void subdivision() {
    float deltaX = (x2-x1)/3.0;
    float deltaY = (y2-y1)/3.0;
    float dist = sqrt(deltaX*deltaX+deltaY*deltaY);

    // Calculate the new points once
    // Imagine that they look like this:
    // .................
    // ....... 3 .......
    // ...... / \ ......
    // 1 --- 2   4 --- 5
    // .................

    float newX1 = x1;
    float newY1 = y1;
    float newX2 = newX1+deltaX;
    float newY2 = newY1+deltaY;
    float newX3 = newX2+cos(ang-sixtyDegrees)*dist;
    float newY3 = newY2+sin(ang-sixtyDegrees)*dist;
    float newX4 = newX2+deltaX;
    float newY4 = newY2+deltaY;
    float newX5 = newX4+deltaX;
    float newY5 = newY4+deltaY;

    subd[0] = new Segment(ang, newX1, newY1, newX2, newY2);
    subd[1] = new Segment(ang-sixtyDegrees, newX2, newY2, newX3, newY3);
    subd[2] = new Segment(ang+sixtyDegrees, newX3, newY3, newX4, newY4);
    subd[3] = new Segment(ang, newX4, newY4, newX5, newY5);
  }

  void display() {
    for (int i = 0; i < 4; i++) subd[i].drawSegment();
  }
}

Jordan2R · July 2014

Hey there @asimes! It got really nice man, great job! I have one question and one comment.

The comment: instead of using 5 for's, one inside another, wouldn't it be better to use an ArrayList, Queue or something like that? In terms of speed, it won't be better, but with that it will be easier to choose how many iterations you want.

Question: I didn't get much what these lines work, could you explain me please what you were thinking when you choose these calculations:

for (int i = 0; i < 3; i++) {
    x[i] = width/2+cos(sixtyDegrees*i*2.0)*200.0;
    y[i] = height/2+sin(sixtyDegrees*i*2.0)*200.0;
  }

 for (int i = 0; i < 3; i++) {
    float ang = sixtyDegrees*i*2.0+sixtyDegrees*2.5;
    snowflake[i] = new Segment(ang, x[i], y[i], x[(i+1)%3], y[(i+1)%3]);
  }

asimes · July 2014

@Jordan2R, As far as I know, a for loop is needed per iteration due to it not having been written as recursive. It would be a good idea to make your next version recursive, I'm not sure how an ArrayList would avoid that syntax.

Admittedly I compacted those lines because the code was long when written out similarly to how newX1, newY1, newX2, etc. were written. This would be the equivalent:

  // A triangle that points to the right
  // These points define the initial line segments
  float[] x = new float[3];
  float[] y = new float[3];
  x[0] = width/2+cos(radians(0.0))*200.0;
  y[0] = height/2+sin(radians(0.0))*200.0;
  x[1] = width/2+cos(radians(120.0))*200.0;
  y[1] = height/2+sin(radians(120.0))*200.0;
  x[2] = width/2+cos(radians(240.0))*200.0;
  y[2] = height/2+sin(radians(240.0))*200.0;

  // To see the triangle
  for (int i = 0; i < 3; i++)
    line(x[i], y[i], x[(i+1)%3], y[(i+1)%3]);

  // These Segments use the triangle points
  // However, their angles must be set because they are not horizontal
  Segment[] snowflake = new Segment[3];
  snowflake[0] = new Segment(radians(150.0), x[0], y[0], x[1], y[1]);
  snowflake[1] = new Segment(radians(270.0), x[1], y[1], x[2], y[2]);
  snowflake[2] = new Segment(radians(30.0), x[2], y[2], x[0], y[0]);

The first part describes the three points of a triangle which is pointing to the right. Because the Segments use these points but they describe lines which are not horizontal, the angles have to be set.

Howdy, Stranger!

Categories

In this Discussion

The Koch snowflake

Best Answers

Answers