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

Tháng Mười Hai 16, 2014 nguyenvanquan7826 School Đồ họa máy tính 8 responses

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 Breshenham 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 DDA (Digital DifferentialAnalyzer)

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:

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

Để đơn giản hóa giải thuật ta xét đường thẳng với m in [0,1] , Dx > 0
Tại mỗi bước ta cho x tăng lên 1 đơn vị tức là x_{i + 1} = x_{i} + 1 \Rightarrow y_{i+1} = y_{i} + m

* Do m là số thực nên muốn y_{i + 1} là số nguyên ta phải làm tròn trước khi truy xuất tọa độ để đưa ra màn hình.
* Với đường thẳng có m > 1 ta sẽ làm ngược lại cho y biến thiên và tính x theo y nghĩa là tại mỗi bước ta có y_{i + 1} = y_{i} + 1 \Rightarrow x_{i+1} = x_{i} + frac{1}{m}
* Với các đoạn thẳng có Dx <0 ta sẽ cho x giảm xuống chứ không tăng.

2. Lưu đồ thuật toán DDA
thuật toán DDA


3. Code minh họa giải thuật

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

Kết quả minh họa


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

Kết quả minh họa