[Schooll_ĐHMT] 算法Breshenham画直线

十二月 16, 2014 nguyenvanquan7826 学校计算机图形学 19 回复

内容
1. 构建算法
2. 流程图算法
3. 代码插图
4. 所有病例码
阅读更多
1. 画直线的一般原则
2. DDA算法划清界线
3. 中点算法划清界线



1. 构建算法Breshenham

给 2 端点M1 (X1, Y1), M2(X2, Y2) 和油漆Ç.
在所有 画直线的一般原则 我们已经建立了表格的直线方程:

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 即单位 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) (我们乘 (X1-X2) 以消除在计算米的取代模式).
DX > 0 应该 P_{k} 只有在D1-D2依赖. 我有:
$胶乳
M = 压裂{Y2，Y1}{X2-X1} \\
\RIGHTARROW P_{到} = (X2-X1)(D1 – D2) \\
\缩进缩进= (X2-X1).\压裂{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)(2B-1) \\
\缩进缩进= 2x_{到}两 – 2Y_{到}.DX + Ç

\\
\RIGHTARROW P_{K 1} = 2(X_{到}+1)两 – 2Y_{K 1}DX + Ç, 到 : \左 (C = 2DY + (2B-1)DX 权 ) \\
\\
TH1: P_{到} \GEQ 0 \RIGHTARROW D1 D2 GEQ \\
\缩进缩进 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

Bresenham算法只对加法和乘法整数运算和计算 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他们完全重合