[Shool_DHMT] 線を引くためのDDAアルゴリズム

12月 16, 2014 nguyenvanquan7826 学校コンピューターグラフィックス 8 回答

コンテンツ
1. 構成アルゴリズム
2. フローチャートアルゴリズム
3. コー​​ドイラスト
4. すべてのケースのためのコード
続きを読む
1. 直線を描くの一般原則
2. アルゴリズムBreshenhamは直線を引く
3. 線を引くための中間点アルゴリズム



1. 建設DDAアルゴリズム (デジタルDifferentialAnalyzer)

与える 2 エンドポイントM1 (X1, Y1), M2(X2, Y2) とCを描く.
全部で 直線を描くの一般原則 我々は、フォームの直線方程式を構築しています:

y = mx + b. \text{ Trong do: } \begin{cases} m = \frac{y2 - y1}{x2-x1} = \frac{Dy}{Dx} \\ b = y1 - m.x1 \end{cases}

アルゴリズムを簡略化するために、我々は行を考える m in [0,1] , Dx > 0
Xが増加するため、各ステップ1で、 1 すなわちユニット x_{i + 1} = x_{i} + 1 \Rightarrow y_{i+1} = y_{i} + m

* mが望むべきである実数であるため、 y_{i + 1} それは、画面を作るための座標を取得する前に、丸め整数でなければなりません.
* 直線mと > 1 私は、各ステップで私たちが持っているという意味で、変数y、xの反対を行います y_{i + 1} = y_{i} + 1 \Rightarrow x_{i+1} = x_{i} + frac{1}{m}
* Dxを持つ直線で <0 それは減少するのではなく、Xが増加します.

2. DDAアルゴリズムのフローチャート
DDAアルゴリズム


3. コー​​ドは、アルゴリズムを説明

/* Program create in Linux OS
 * nguyenvanquan7826 
 */

#include <graphics.h>
#define Round(a) (int)(a+0.5)	// lam tron so
#define DELAY 10
int color = RED;

void lineDDA(int x1, int y1, int x2, int y2){		// thuat toan DDA
	int x_unit = 1, Dx = x2 - x1, Dy = y2 - y1;		// Khoi tao cac gia tri ban dau
	int x = x1;
	float y = y1;
	float m = (float)Dy/Dx;		// he so goc m
	putpixel(x, Round(y), color);
	
	while(x < x2){
		delay(10);	// thoi gian tre khi ve 1 diem anh
		x += x_unit;
		y += m;
		putpixel(x,Round(y), color);
	}
}
int main(){
	int gd,gm=VGAMAX; gd=DETECT;
    initgraph(&gd,&gm,NULL);		// khoi tao cua so do hoa
	setbkcolor(WHITE);
	lineDDA(50,150, 300, 200);		// ve duong thang
	getchar();
	return 0;
}

結果は示している


4. すべてのケースのためのコード
次のコードは、描画されます 8 下のセグメント 8 方向, 中心点から始まる.

/* Program create in Linux OS
 * nguyenvanquan7826 
 */

#include <graphics.h>
#include <stdio.h>
#define Round(a) (int)(a+0.5)
#define DELAY 10
int color = RED;
struct point		// diem gom tung do x va hoanh do y
{
	int x, y;
};

void lineDDA(int x1, int y1, int x2, int y2)		// DDA algorithm
{			
	int x_unit = 1, Dx = x2 - x1, Dy = y2 - y1;	// Init first value
	int x = x1;
	float y = y1;
	float y_unit = 1;
	
	if (Dx < 0)			
		x_unit = -1;
	if (Dy < 0)
		y_unit = -1;
		
	if (x1 == x2)	// duong thang dung
	{
		while (y != y2)
		{
			delay(DELAY);
			y += y_unit;
			putpixel(x, Round(y), color);
		}	
	}
	else if (y1 == y2)	// duong ngang
	{
		while (x != x2)
		{
			delay(DELAY);
			x += x_unit;
			putpixel(x, Round(y), color);
		}
	}
	else if (x1 != x2 && y1 != y2)// duong xien
	{
		float m = (float) abs(Dy) / abs(Dx);
		x_unit = 1;
		y_unit = m;
		x = x1;
		y = y1;
		
		if (Dx < 0)			
			x_unit = -1;		// ve x giam
		if (Dy < 0)
			y_unit = -m;		// ve y giam
		
		putpixel(x, Round(y), color);
		while(x != x2)
		{
			delay(10);	// thoi gian tre khi ve 1 diem anh
			x += x_unit;
			y += y_unit;
			putpixel(x, Round(y), 1);
		}
	}
}
int main(){
	int gd,gm=VGAMAX; gd=DETECT;
	initgraph(&gd,&gm,NULL);
	setbkcolor(2);
	int x = 200, y = 100;
	char s[] = "nguyenvanquan7826";
	outtextxy(250,100, s);
	point A[9] = {{getmaxx()/2, getmaxy()/2}, 
					{A[0].x-x, A[0].y-y},
					{A[0].x-x, A[0].y+y},
					{A[0].x+x, A[0].y+y},
					{A[0].x+x, A[0].y-y},
					{A[0].x, A[0].y-y},
					{A[0].x-x, A[0].y},
					{A[0].x, A[0].y+y},
					{A[0].x+x, A[0].y},
				};
	for (int i=1; i<9; i++)
	{
		lineDDA(A[0].x, A[0].y, A[i].x, A[i].y);
	}
	getchar();
	return 0;
}

結果は示している