Sierpinski's triangle

Discussion in 'Advanced Programming Discussion' started by Adiabat, Apr 30, 2017.

  1. Adiabat

    Adiabat Member

    Joined:
    Sep 17, 2016
    Posts:
    26
    Hi all,

    A recent episode of Numberphile (www.youtube.com/watch?v=kbKtFN71Lfs), describes a really simple and unexpected way (to me in any case) of generating Sierpinski's triangle (or gasket): essentially you move from a random point half way towards one of three (noncollinear) points with one third probability each, draw another point and repeat. Quite amazingly this generates the famous fractal pattern. Thought people here might get a kick out of it.

    edit: maybe I put this in the wrong forum, pls move if so.

    Some (terrible) code below and examples:

    Code:
    // Generate Sierpinski triangle - move some fraction of distance to one of 3 points according to
    // randomly sampled integer from 1 to 3.
    
    //room size 1920 x 1200
    
    if keyboard_check_pressed(ord("R")) room_restart();
    
    NumberOfPoints = 10000;
    
    if can_choose = true
    {
    // triangle vertex coordinates and radius of circles drawn at those coordinates
    vertex_x1 = 900;
    vertex_y1 = 100;
    
    vertex_x2 = 1700;
    vertex_y2 = 1100;
    
    vertex_x3 = 100;
    vertex_y3 = 1100;
    
    vertex_radius_1 = 10;
    vertex_radius_2 = 10;
    vertex_radius_3 = 10;
    vertex_radius_4 = 10;
    
    
    // Use these lines to randomize shape of starting triangle. No guarantee won't be colinear.
    /*vertex_x1 = irandom_range(100,1800);
    vertex_y1 = irandom_range(100,1100);
    vertex_radius_1 = 10;
    
    vertex_x2 = irandom_range(100,1800);
    vertex_y2 = irandom_range(100,1100);
    vertex_radius_2 = 10;
    
    vertex_x3 = irandom_range(100,1800);
    vertex_y3 = irandom_range(100,1100);
    vertex_radius_3 = 10;*/
    
    
    // fraction in original example was 0.5. Here mutiplied by separate scale for
    // each of three vertexes
    fraction = 0.5;
    
    /*scale1x = 1;
    scale2x = 1;
    scale3x = 1;
    scale1y = 1;
    scale2y = 1;
    scale3y = 1;*/
    
    scale1x = random_range(0.5,1.5);
    scale2x = random_range(0.5,1.5);
    scale3x = random_range(0.5,1.5);
    scale1y = random_range(0.5,1.5);
    scale2y = random_range(0.5,1.5);
    scale3y = random_range(0.5,1.5);
    
    
    // starting position and radius of circle drawn at starting position
    start_x = irandom_range(100,1800);
    start_y = irandom_range(100,1100);
    start_radius = 10;
    
    // generate array of random integers with values from 1 to 3
    for (i=0; i<NumberOfPoints+1; i+=1)
    {
    direct[i] = choose(1,2,3);
    }
    }
    
    // draw vertexes
    /*draw_circle_colour(vertex_x1,vertex_y1,vertex_radius_1,c_red,c_red,false);
    draw_circle_colour(vertex_x2,vertex_y2,vertex_radius_2,c_red,c_red,false);
    draw_circle_colour(vertex_x3,vertex_y3,vertex_radius_3,c_red,c_red,false);*/
    
    // draw starting point
    draw_circle_colour(start_x,start_y,start_radius,c_green,c_green,false);
    
    // state fraction*scales
    draw_text_colour(100,150,fraction*scale1x,c_yellow,c_yellow,c_yellow,c_yellow,1);
    draw_text_colour(100,200,fraction*scale2x,c_yellow,c_yellow,c_yellow,c_yellow,1);
    draw_text_colour(100,250,fraction*scale3x,c_yellow,c_yellow,c_yellow,c_yellow,1);
    draw_text_colour(100,300,fraction*scale1y,c_yellow,c_yellow,c_yellow,c_yellow,1);
    draw_text_colour(100,350,fraction*scale2y,c_yellow,c_yellow,c_yellow,c_yellow,1);
    draw_text_colour(100,400,fraction*scale3y,c_yellow,c_yellow,c_yellow,c_yellow,1);
    
    
    
    // generate new point coordinates
    current_x[0] = start_x;
    current_y[0] = start_y;
    
    for (i = 0; i < NumberOfPoints+1; i += 1)
    {
      if direct[i] == 1
       {
       current_x[i+1] = current_x[i] + sign(vertex_x1 - current_x[i])*fraction*scale1x*abs(vertex_x1 - current_x[i]);
       current_y[i+1] = current_y[i] + sign(vertex_y1 - current_y[i])*fraction*scale1y*abs(vertex_y1 - current_y[i]);
       }
      if direct[i] == 2
       {
       current_x[i+1] = current_x[i] + sign(vertex_x2 - current_x[i])*fraction*scale2x*abs(vertex_x2 - current_x[i]);
       current_y[i+1] = current_y[i] + sign(vertex_y2 - current_y[i])*fraction*scale2y*abs(vertex_y2 - current_y[i]);
       }
      if direct[i] == 3
       {
       current_x[i+1] = current_x[i] + sign(vertex_x3 - current_x[i])*fraction*scale3x*abs(vertex_x3 - current_x[i]);
       current_y[i+1] = current_y[i] + sign(vertex_y3 - current_y[i])*fraction*scale3y*abs(vertex_y3 - current_y[i]);
       }
    }
    // use these lines to draw all points simultaneously
    for (i=1; i < NumberOfPoints+1; i += 1)
    {
    if i mod 2 = 0
    draw_circle_colour(current_x[i],current_y[i],start_radius,c_yellow,c_black,false);
    if i mod 2 != 0
    draw_circle_colour(current_x[i],current_y[i],start_radius,c_blue,c_black,false);
    }
    
    
    // use these lines to plot points one by one
    // press space to plot points
    /*if keyboard_check(vk_space)
    {
    for (m = 1; m < j+1; m += 1)
    {
    if m mod 2 = 0
    draw_circle_colour(current_x[m],current_y[m],start_radius,c_yellow,c_black,false);
    if m mod 2 != 0
    draw_circle_colour(current_x[m],current_y[m],start_radius,c_blue,c_black,false);
    }
    if (j < NumberOfPoints+1)
    j += 1;
    }
    */
    can_choose = false;
    

    Here's an example of the classic triangle with scale factors equal to 0.5. The green circle is the starting point:

    Runner_170429_2111056 (1280x800).jpg

    I then played around with distorting the scale factors:

    Runner_170429_2139028 (1280x800).jpg

    Runner_170429_2138476 (1280x800).jpg
     
    Last edited: Apr 30, 2017
    renex, Wraithious, hippyman and 6 others like this.
  2. chance

    chance predictably random Forum Staff Moderator

    Joined:
    Apr 22, 2016
    Posts:
    774
    That's an interesting algorithm. I've always used cellular automata algorithms to draw these, one line at a time. This sub-division approach is one I haven't seen. Although reading about it, I guess it's fairly common. Not immediately intuitive, though.

    Fun to watch this evolve step-by-step. Just takes a few lines in DRAW:

    Code:
    var old_x = new_x; // swap point
    var old_y = new_y;
    
    var index = choose(0,1,2); // draw new point
    new_x = old_x + (vert_x[index] - old_x)/2;
    new_y = old_y + (vert_y[index] - old_y)/2;
    
    surface_set_target(surf); // update surface
    draw_point(new_x,new_y);
    surface_reset_target();
    
    draw_surface(surf,0,0); // draw the surface
    
    The surface is initialized in the Create event, of course. Along with the three vertices and starting values for new_x/y. With room_speed at 9999, it takes <10 sec to get a detailed gasket:

    [​IMG]
     
    renex, Adiabat, joqlepecheur and 3 others like this.
  3. Adiabat

    Adiabat Member

    Joined:
    Sep 17, 2016
    Posts:
    26
    Thanks Chance! That's code from someone who actually knows what they're doing. Also I had no idea rooms could run that fast.

    Took your code and had some more fun.

    Two triangles:

    Runner_170430_1527496 (1280x769).jpg

    Letting scaling factor vary in one triangle:

    Runner_170430_1510144 (1280x769).jpg

    Regular hexagon, scale = 0.7 (instead of 0.5):

    Runner_170430_1621548 (1280x769).jpg

    Regular hexagon, scale = 0.6 (less than that, starts to look like noise):

    Runner_170430_1625395 (1280x769).jpg
     
    Rivo likes this.
  4. Adiabat

    Adiabat Member

    Joined:
    Sep 17, 2016
    Posts:
    26
    I thought the Barnsley fern they mentioned looked great so I did that too, plus the variation described in the corresponding Wikipedia article. Classic on left, variation on right:

    Runner_170430_1820304 (1280x769).jpg

    Here's the code (modified version of chance's code):

    Code:
    // Barnsley fern and variation
    
    var old_x = new_x; // swap points
    var old_y = new_y;
    
    var old_x2 = new_x2;
    var old_y2 = new_y2;
    
    // classic fern
    part = irandom_range(1,100)
    
    if (part == 1)
     {
      new_x = 0;
      new_y = 0.16*old_y;
     }
    if (part <= 86) and (part != 1)
     {
      new_x = 0.85*old_x + 0.04*old_y;
      new_y = -0.04*old_x + 0.85*old_y + 1.6;
     }
    if (part >= 87) and (part <= 93)
     {
      new_x = 0.2*old_x - 0.26*old_y;
      new_y = 0.23*old_x + 0.22*old_y + 1.6;
     }
    if (part >= 94)
     {
      new_x = -0.15*old_x + 0.28*old_y;
      new_y = 0.26*old_x + 0.24*old_y + 0.44;
     }
    
    // variation
    part2 = irandom_range(1,100);
    
    if (part2 == 1) or (part2 == 2)
     {
      new_x2 = 0;
      new_y2 = 0.25*old_y2 - 0.4;
     }
    if (part2 <= 86) and (part2 >= 3)
     {
      new_x2 = 0.95*old_x2 + 0.005*old_y2 - 0.002;
      new_y2 = -0.005*old_x2 + 0.93*old_y2 + 0.5;
     }
    if (part2 >= 87) and (part2 <= 93)
     {
      new_x2 = 0.035*old_x2 - 0.20*old_y2 - 0.09;
      new_y2 = 0.16*old_x2 + 0.04*old_y2 + 0.02;
     }
    if (part2 >= 94)
     {
      new_x2 = -0.04*old_x2 + 0.20*old_y2 + 0.083;
      new_y2 = 0.16*old_x2 + 0.04*old_y2 + 0.12;
     }
    
    surface_set_target(surf); // update surface
    draw_set_colour(c_green);
    draw_point(new_x*100+500,1100-new_y*100);
    draw_set_colour(c_lime);
    draw_point(1500-new_x2*150,1100-new_y2*150);
    
    surface_reset_target();
    
    draw_surface(surf,0,0); // draw the surface
    
    if keyboard_check_pressed(ord("R")) room_restart();
     
    Last edited: May 1, 2017
    Snayff, Kenjiro, Simon Gust and 9 others like this.
  5. chance

    chance predictably random Forum Staff Moderator

    Joined:
    Apr 22, 2016
    Posts:
    774
    Very nice. I love to see iteration used to create fractal organic shapes. Reminds me of the earliest programs I ever wrote.

    Your other examples with Sierpinski triangles using different divisors got me thinking. So I made an animation to see it "evolve" as the divisor was varied over time.

    Here's an HTML5 example. It uses two surfaces: one to display the last result, while the other surface is being updated. Then they get swapped every step. Even with 20,000 iterations per step, it still runs quickly since the calculation is very simple.

    Just click to play in browser:
    http://dotcom-games.com/sierpinski/

    Interesting "fireball" effect at the end. With the divisor very large, the points just dance around a central location after the first update.
     
    Bentley, Dragon47, renex and 2 others like this.
  6. Adiabat

    Adiabat Member

    Joined:
    Sep 17, 2016
    Posts:
    26
    Very cool! I like how it progresses from noise to recognizable pattern repeatedly as the divisor increases.

    Also, sorry for delayed response - I have to wait for weekends.
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice