Sierpinski's triangle

A

Adiabat

Guest
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 by a moderator:

chance

predictably random
Forum Staff
Moderator
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:

 
A

Adiabat

Guest
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
 
A

Adiabat

Guest
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 by a moderator:

chance

predictably random
Forum Staff
Moderator
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: (snip)
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.
 
A

Adiabat

Guest
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.
 
Top