What is Koch Fractal?
Koch Fractal is a simple algorithm which produces snowflake from a triangle. The concept behind this, is to break a line into two while leaving one third of the space between them where we fit two more lines forming an equilateral triangle without the base. This process is, then repeated to all lines again and again!
The Implementation
First thing, you should know basics of C++ as well as a bit of SDL2 and basic trigonometry to understand it.
We are going to use
SDL2 to have some graphics. We will only use some of its basic primitive drawing methods for drawing lines. So, we are going to include only SDL2 header. We are also going to include list.h to have a list of lines.
1
2
| #include <list> #include <SDL2/SDL.h> // or #include <SDL.h>
|
Now, we need an
SDL_Window*, an
SDL_Renderer* and an
SDL_Event instance to have the image on screen and to handle events.
1
2
3
4
5
6
7
| SDL_Window* window = NULL; SDL_Renderer* renderer = NULL; bool quit = false; SDL_Event in; const int SCR_W = 640; // Width of the window const int SCR_H = 480; // Height of the window
|
Previously, I said that there will be a list of lines. That means, we need to define line as a struct or a class. You can use struct as well but I am using class for that.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Line { public: double x, y, length, angle; // Members Line(double x, double y, double length, double angle) : x(x), y(y), length(length), angle(angle) {} double getX2() // Getting the second x coordinate based on the angle and length { return x+cos(angle*(M_PI/180.0))*length; } double getY2() // Getting the second y coordinate based on the angle and length { return y+sin(angle*(M_PI/180.0))*length; } void draw() { SDL_SetRenderDrawColor(renderer, 100,255,100,255); // Setting the color of the line SDL_RenderDrawLine(renderer,x,y, getX2(),getY2()); // Drawing the line SDL_SetRenderDrawColor(renderer, 0,0,0,255); // Resetting the color } };
|
Now, we need to have a list of lines.
| std::list<Line*> lines; //Note that we do not take Line, we take Line*
|
Finally, the Koch algorithm implementation, all in one function which takes list of Line* as a parameter.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| //Worth noting: It's a heavy function! void kochFractal( std::list<Line*> & lines ) { std::list<Line*> newLines; //For getting new Line*(s) std::list<Line*> delLines; //For getting Line*(s) to be deleted for(auto itr = lines.begin(); itr != lines.end(); itr++) { double x_l1 = (*itr)->x; double y_l1 = (*itr)->y; double len_l1 = (*itr)->length/3; double ang_l1 = (*itr)->angle; double x_l2 = (*itr)->x + (cos((*itr)->angle*(M_PI/180.0))*(*itr)->length/1.5); double y_l2 = (*itr)->y + (sin((*itr)->angle*(M_PI/180.0))*(*itr)->length/1.5); double len_l2 = (*itr)->length/3; double ang_l2 = (*itr)->angle; double x_l3 = (*itr)->x + (cos((*itr)->angle*(M_PI/180.0))*(*itr)->length/3.0); double y_l3 = (*itr)->y + (sin((*itr)->angle*(M_PI/180.0))*(*itr)->length/3.0); double len_l3 = (*itr)->length/3.0; double ang_l3 = (*itr)->angle - 300.0; double x_l4 = (*itr)->x + (cos((*itr)->angle*(M_PI/180.0))*((*itr)->length/1.5)); double y_l4 = (*itr)->y + (sin((*itr)->angle*(M_PI/180.0))*((*itr)->length/1.5)); double len_l4 = (*itr)->length/3.0; double ang_l4 = (*itr)->angle - 240.0; //All four lines properties are setted above! //Fixing bug - Changing Triangle Forming Orientation x_l4 = x_l4 + cos(ang_l4*(M_PI/180.0))*len_l4; y_l4 = y_l4 + sin(ang_l4*(M_PI/180.0))*len_l4; ang_l4 -= 180.0; //Each line forms four new lines... newLines.push_back( new Line( x_l1, y_l1, len_l1, ang_l1 ) ); newLines.push_back( new Line( x_l2, y_l2, len_l2, ang_l2 ) ); newLines.push_back( new Line( x_l3, y_l3, len_l3, ang_l3 ) ); newLines.push_back( new Line( x_l4, y_l4, len_l4, ang_l4 ) ); //...for deleting itself! delLines.push_back( (*itr) ); } for(auto itr = newLines.begin(); itr != newLines.end(); itr++) lines.push_back( (*itr) ); //Adding new Line*(s) for(auto itr = delLines.begin(); itr != delLines.end(); itr++) { lines.remove( (*itr) ); //Deleting new Line*(s) delete (*itr); } }
|
Phew! A big implementation really! Now, time for the action in the
int main():
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| int main( int argc, char** args ) { SDL_Init(SDL_INIT_EVERYTHING); //Initializing SDL2 window = SDL_CreateWindow( "Koch Fractal", SDL_WINDOWPOS_UNDEFINED, SDL_WINDOWPOS_UNDEFINED, SCR_W, SCR_H, SDL_WINDOW_SHOWN ); //Creating window renderer = SDL_CreateRenderer( window, -1, SDL_RENDERER_ACCELERATED ); //Creating renderer SDL_SetRenderDrawColor(renderer,0,0,0,255); //Setting default screen color //Horizontal line //lines.push_back( new Line(SCR_W-10,SCR_H/2.0, SCR_W-20,180.0) ); //Vertical line //lines.push_back( new Line(SCR_W/1.5,10, SCR_H-20,90.0) ); //Equilateral Triangle for forming Koch Snowflake lines.push_back( new Line( SCR_W-100, 150, SCR_W-200, 180.0) ); lines.push_back( new Line( 100, 150, SCR_W-200, 60.0) ); Line* lineS = new Line( SCR_W-100, 150, SCR_W-200, 120.0); lineS->x += cos(lineS->angle *(M_PI/180.0))*lineS->length; lineS->y += sin(lineS->angle *(M_PI/180.0))*lineS->length; lineS->angle -= 180.0; lines.push_back( lineS ); while(!quit) //The loop { while(SDL_PollEvent(&in)) //Polling Events { if(in.type == SDL_QUIT) quit = true; } SDL_RenderClear(renderer); //Clearing renderer for(auto itr = lines.begin(); itr != lines.end(); itr++) (*itr)->draw(); //Drawing all lines SDL_RenderPresent(renderer); //Updating screen SDL_Delay(2500); //Delay to show each iteration kochFractal(lines); //Applying Koch Fractal } for(auto itr = lines.begin(); itr != lines.end(); itr++) delete (*itr); //Deleting all lines at the end of a program SDL_DestroyRenderer(renderer); SDL_DestroyWindow(window); SDL_Quit(); //Clearing all SDL resources return 0; }
|
The Results!
Following images show the result. It was executed on a mobile device using C4Droid, a program for running C++ programs on Android.
I hope that this excites you for more programming, algorithms and fractals. For more such things, visit my blog
bacprogramming.wordpress.com.
