[Schooll_ĐHMT] Thuật toán Breshenham vẽ đoạn thẳng

Nội dung
1. Xây dựng thuật toán
2. Lưu đồ thuật toán
3. Code minh họa
4. Code cho mọi trường hợp
Đọc thêm
1. Nguyên lý chung vẽ đoạn thẳng
2. Thuật toán DDA vẽ đoạn thẳng
3. Thuật toán Midpoint vẽ đoạn thẳng

1. Xây dựng thuật toán Breshenham

Cho 2 điểm đầu mút M1 (x1, y1), M2(x2, y2) và màu vẽ C.
Trong bài nguyên lý chung vẽ đoạn thẳng chúng ta đã xây dựng phương trình đường thẳng có dạng:

Để đơn giản hóa giải thuật ta xét đường thẳng với
Tại mỗi bước ta cho x tăng lên 1 đơn vị tức là . Bước tiếp theo là ta tính nhưng ta sẽ không làm giống thuật toán DDA vì nó phải xử lỹ dữ liệu trên số thực và làm tròn số dẫn tới mất thời gian. Ta sẽ tìm các tính theo các số nguyên.

Giả sử tại bước thứ k ta có được hình vẽ như sau:

Gọi y là tung độ chính xác của . Ta sẽ lấy giá trị y là giá trị gần nhất với hay . Để làm việc này ta xét d1 và d2.

Nếu d1 > d2 khi đó
Nếu d1 < d2 khi đó
Do đó nếu ta xác định được dấu của d1 – d2 thì ta sẽ biết được giá trị của . Ta xét hằng số (Ta nhân với (x1-x2) để triệt tiêu được mẫu khi thay m vào khi tính toán).
Do Dx > 0 nên chỉ phụ thuộc vào d1 -d2. Ta có:
$latex
m = frac{y2-y1}{x2-x1} \
Rightarrow P_{k} = (x2-x1)(d1 – d2) \
indent indent= (x2-x1).frac{2(y2-y1)(x_{k}+1) +(x2-x1)(-2y_{k} + 2b – 1)}{x2-x1} \
indent indent = 2(y2-y1)x_{k} – 2(x2-x1)y_{k} + 2(y2-y1) + (x2-x1)(2b-1) \
indent indent = 2x_{k}Dy – 2y_{k}.Dx + c

\
Rightarrow P_{k+1} = 2(x_{k}+1)Dy – 2y_{k+1}Dx + c, voi : left (c= 2Dy + (2b-1)Dx ight ) \
\
TH1: P_{k} geq 0 Rightarrow d1 geq d2 \
indent indent Rightarrow y_{k+1} = y_{k} + 1 \
indent indent Rightarrow P_{k+1} = 2(x_{k}+1)Dy – 2(y_{k} + 1)Dx + c = P_{k} + 2(Dy – Dx) \
\
TH2: P_{k} 2. Lưu đồ thuật toán

Thuật toán Bresenham chỉ thao tác trên số nguyên và chỉ tính toán trên phép cộng và phép nhân 2 (phép dịch bit). Điều này là một cải tiến làm tăng tốc độ đáng kể so với thuật toán DDA. Ý tưởng chính của thuật toán này là ở chỗ xét dấu P i để quyết định điểm kế tiếp.

3. Code minh họa

/* 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. Code cho mọi trường hợp
Code sau sẽ vẽ 8 đoạn thẳng theo 8 hướng, điểm bắt đầu từ tâm.

/* 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;
}

Tuy nhiên do lý do làm tròn liên tục y và giá trị làm tròn đó lại được lưu lại để tính toán tiếp nên đường thẳng vẽ bằng thuật toán này không chính xác. Ta có thể quan sát sự khác biệt giữa thuật toán này và DDA với cùng 1 hệ các đường thẳng.

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}
}

Các đường thẳng màu xanh là của Breshenham, màu hồng là của DDA. (DDA chính xác hơn). Các đường ngang và dọc thì chúng khớp hoàn toàn với nhau. Và dưới đây là đoạn code cho thuật toán Breshenham cải tiến.

// 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);
		}
	}
}

Khi chạy bằng đoạn code này so với DDA thì chúng hoàn toàn trùng khớp