[Schooll_ĐHMT] アルゴリズムBreshenhamは直線を引く

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

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



1. 建設アルゴリズムBreshenham

与える 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_{k + 1} = x_{k} + 1 . 次のステップは、私たちが計算され y_{k + 1} 私たちは同じことを行うことはありません DDAアルゴリズム それが失われた時間に実数と丸めリード上のデータを扱う必要があるため、. 私たちは、整数に応じてプロパティを見つけることができます.

ステップkで、我々は以下の画像を取得したと:
アルゴリズムBreshenham
コー​​ルメディカルは精度を立ち上げる y_{k + 1}. 私は、yの値が最も近い値であるがかかります y_{k} + 1 がある y_{k}. これを行うには、d1とd2を検討.
d1 = y - y_{k} = m(x_{i} + 1) + b - y_{k} \\ d2 = y_{k} + 1 - y = y_{k} + 1 - m(x_{i}+1) - b \\ => d1 - d2 = 2m(x_{i} +1) - 2y_{k} + 2b - 1
D1の場合 > 一方、D2 y_{k + 1} = y_{k} + 1
D1の場合 < 一方、D2 y_{k + 1} = y_{k}
したがって、我々はD1の兆候を識別する場合 – D2、我々はの価値を知っている y_{k+1} . 定数を考慮してください P_{k} = (x1-x2)(d1-d2) (私たちは、乗算 (×1、×2) 計算mにおける置換パターンを除去する).
Dxは > 0 すべきである P_{k} 唯一のD1 -d2に依存. 私が持っている:
$ラテックス
メートル= FRAC{Y2-Y1}{X2-X1} \\
\RIGHTARROW P_{へ} = (X2-X1)(D1 – D2) \\
\インデントインデント= (X2-X1).\FRAC{2(Y2-Y1)(X_{へ}+1) +(X2-X1)(-2Y_{へ} + 2B – 1)}{X2-X1} \\
\インデントインデント= 2(Y2-Y1)X_{へ} – 2(X2-X1)Y_{へ} + 2(Y2-Y1) + (X2-X1)(2のb 1) \\
\インデントインデント= 2x_{へ}二つ – 2Y_{へ}.Dxは + ℃

\\
\RIGHTARROW P_{のk 1} = 2(X_{へ}+1)二つ – 2Y_{のk 1}Dxは + ℃, へ : \左 (C = 2Dy + (2のb 1)DX 権 ) \\
\\
TH1: P_{へ} \GEQ 0 \RIGHTARROW D1 GEQ D2 \\
\インデントインデント RIGHTARROW Y_{のk 1} = Y_{へ} + 1 \\
\インデントインデント RIGHTARROW P_{のk 1} = 2(X_{へ}+1)二つ – 2(Y_{へ} + 1)Dxは + C = P_{へ} + 2(二つ – Dxは) \\
\\
TH2: P_{へ} < 0 \Rightarrow d1 < d2 \\ \indent \indent \Rightarrow y_{k+1} = y_{k} \\ \indent \indent \Rightarrow P_{k+1} = 2(x_{k}+1)Dy - 2y_{k}Dx + c = P_{k} + 2Dy \\ $ Tính P1, ta có: $latex y1 = m.x1 + b = \frac{Dy}{Dx}x1 + b\\ P_{1} = 2x1.Dy - 2y1.Dx + c = 2x1.Dy - 2\left ( \frac{Dy}{Dx}x1 + b \right )Dx + 2Dy + (2b - 1)Dx\\ = 2Dy - Dx $
2. フローチャートアルゴリズム
Breshenham

唯一の加算と乗算に整数演算と計算上のブレゼンハムアルゴリズム 2 (翻訳ビットを可能にする). これは速度向上が大幅に増加DDAアルゴリズムです. このアルゴリズムの主な考え方は、次の決定点にポイントでP I.

3. コー​​ドイラスト

/* Program create in Linux OS
 * nguyenvanquan7826
 */

#include <graphics.h>
#define DELAY 10
int color = RED;

void Bresenham(int x1, int y1, int x2, int y2){
	int x, y, Dx, Dy, p, c1, c2;
	Dx = abs(x2 - x1);
	Dy = abs(y2 - y1);
	p = 2*Dy - Dx;
	c1 = 2*Dy;
	c2 = 2*(Dy-Dx);
	x = x1;
	y = y1;

	int x_unit = 1, y_unit = 1;

	putpixel(x,y,color);
	while(x != x2){
		delay(DELAY);
		if (p<0) p += c1;
		else{
			p += c2;
			y += y_unit;
		}
		x += x_unit;
		putpixel(x, y, color);
	}
}

int main(){
	int gd,gm=VGAMAX; gd=DETECT;
	initgraph(&gd,&gm,NULL);
	setbkcolor(WHITE);
	Bresenham(50,150, 300, 200);		// ve duong thang
	getchar();
	return 0;
}


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

/* Program create in Linux OS
 * nguyenvanquan7826
 */
#include <graphics.h>
#define DELAY 10
int colorRedBlue = BLUE;
struct point
{
	int x, y;
};
void lineBresenham(int x1, int y1, int x2, int y2){
	int x, y, Dx, Dy, p, c1, c2;
	Dx = abs(x2 - x1);
	Dy = abs(y2 - y1);
	p = 2*Dy - Dx;
	c1 = 2*Dy;
	c2 = 2*(Dy-Dx);
	x = x1;
	y = y1;

	int x_unit = 1, y_unit = 1;

	if (x2 - x1 < 0)
		x_unit = -x_unit;
	if (y2 - y1 < 0)
		y_unit = -y_unit;

	if (x1 == x2)	// duong thang dung
	{
		while (y != y2+1)
		{
			delay(DELAY);
			y += y_unit;
			putpixel(x, y, colorRedBlue);
		}
	}

	else if (y1 == y2)	// duong ngang
	{
		while (x != x2+1)
		{
			delay(DELAY);
			x += x_unit;
			putpixel(x, y, colorRedBlue);
		}
	}
	else{
		putpixel(x, y, colorRedBlue);
		while(x != x2){
			delay(DELAY);
			if (p<0) p += c1;
			else{
				p += c2;
				y += y_unit;
			}
			x += x_unit;
			putpixel(x, y, colorRedBlue);
		}
	}
}

int main(){
	int gd,gm=VGAMAX; gd=DETECT;
	initgraph(&gd,&gm,NULL);
	setbkcolor(WHITE);
	int x = 100, y = 200;
	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++)
	{
		lineBresenham(A[0].x, A[0].y, A[i].x, A[i].y);
	}

	getchar();
	return 0;
}

しかし、このアルゴリズムによって描かれるラインを計算するために保存された値を丸め、丸めによるケアの継続性に間違っています. 私たちは同じで、このアルゴリズムとDDAとの違いを観察することができます 1 ラインにお問い合わせください.

A[] = {
	{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}
}

BreshenhamとDDAを比較
青い線はBreshenhamです, ピンクはDDAです. (DDAより正確な). 水平線と垂直線は、それらが一緒に完璧にフィット. そして、ここでアルゴリズムの改善のためのコードだBreshenham.

// Ve duong thang Bresenham Cai tien
void lineBresenham_1(int x1, int y1, int x2, int y2) 
{ 
	int c2, c, Dx, Dy, x, y;
	Dx = abs(x2 - x1);
	Dy = abs(y2 - y1);
	c = Dx - Dy;
	c2 = 2*c;
	x = x1;
	y = y1;
	
	int x_unit = 1, y_unit = 1;
	
	if (x2 - x1 < 0)
		x_unit = -x_unit;
	if (y2 - y1 < 0)
		y_unit = -y_unit;

	putpixel(x, y, colorGreen);
	
	if (x1 == x2)	// duong thang dung
	{
		while (y != y2)
		{
			delay(DELAY);
			y += y_unit;
			putpixel(x, y, colorGreen);
		}
	}
	
	else if (y1 == y2)	// duong ngang
	{
		while (x != x2)
		{
			delay(DELAY);
			x += x_unit;
			putpixel(x, y, colorGreen);
		}
	}
	
	else if (x1 != x2 && y1 != y2)	// duong xien
	{
		while(x != x2+1)
		{
			delay(DELAY);
			c2 =2*c;
			if (c2 > -Dy)	
			{
				c = c - Dy;	
				x = x + x_unit;
			}
			if (c2 < Dx)	
			{
				c = c + Dx;	
				y = y + y_unit; 
			}
			putpixel(x, y, colorGreen);
		}
	}
}

あなたはDDAよりも、このコードを実行すると、彼らは完全に一致している