• 文章
  • 科赫分形 - 最簡單的演算法之一
作者：
釋出於 2015 年 10 月 1 日（最後更新：2015 年 10 月 13 日）

科赫分形 - 最簡單的圖形學演算法之一

評分：4.2/5（349 次投票）
*****

什麼是科赫分形？

科赫分形是一種簡單的演算法，它能從一個三角形生成雪花。其背後的概念是，將一條線段分成三段，去掉中間一段，然後以去掉的線段為底，向外作一個等邊三角形，保留兩條邊。然後對所有線段重複這個過程！

實現

首先，你應該瞭解 C++ 基礎知識，以及一點 SDL2 和基本的三角函式知識，才能理解它。
我們將使用 SDL2 來實現一些圖形效果。我們只會使用它的一些基本圖元繪製方法來畫線。因此，我們只需要包含 SDL2 標頭檔案。我們還會包含 list.h 以便使用線段列表。
1
2
 
#include <list>
#include <SDL2/SDL.h> // or #include <SDL.h>

現在，我們需要一個 SDL_Window*、一個 SDL_Renderer* 和一個 SDL_Event 例項，以便在螢幕上顯示影像並處理事件。
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


前面我說過會有一個線段列表。這意味著我們需要將線段定義為一個結構體或一個類。你也可以使用結構體，但我這裡用的是類。
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
	}
};

現在，我們需要一個線段列表。
 
 
std::list<Line*> lines; //Note that we do not take Line, we take Line*

最後是科赫演算法的實現，全部在一個函式中完成，該函式接收一個 Line* 列表作為引數。
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);
	}
}

呼！實現程式碼可真夠長的！現在，是時候在 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;
}

結果！

以下圖片展示了結果。它是在移動裝置上使用 C4Droid（一個在安卓上執行 C++ 程式的應用）執行的。

我希望這能激發你對更多程式設計、演算法和分形的興趣。想要了解更多類似內容，請訪問我的部落格 bacprogramming.wordpress.com。