Nhờ việc sử dụng công thức y_sau=y_trước+m để tính giá trị y tại mỗi bước đã giúp thuật toán DDA  nhanh hơn hẳn so với cách tính y từ PT y=mx+b ( do khử được phép nhân trên số thực). Tuy nhiên, việc cộng dồn giá trị thực m vào y có thể sẽ tích lũy sai số làm cho hàm làm tròn có kết quả sai , dẫn tới việc xác định vị trí của điểm vẽ bị chệch hướng so với đường thẳng thực ( điều này chỉ xảy ra khi vẽ đoạn thẳng khá dài) . Hơn nữa, thuật toán DDA còn bị hạn chế về mặt tốc độ , do phép toán cộng dồn số thực và làm tròn. Để khắc phục những mặt hạn chế này,  cựu giáo sư Khoa học máy tính Jack Elton Bresenham  đã thiết kế thuật toán vẽ đường thẳng Bresenham vào năm 1962 tại công ty IBM.

1)Ý tưởng thuật toán Bresenham:

• Thay thế các phép toán trên số thực bằng các phép toán trên số nguyên.
• Giảm thời gian của thuật toán hơn so với DDA.
• Hạn chế phép toán được thực hiện để giảm tải thời gian.

2)Đặt vấn đề:

Cho 2 điểm A(x1,y1) và B(x2,y2) . Vẽ đường thẳng đi qua A,B .

3)Thuật giải :

Thuật toán Bresenham đưa ra cách chọn y_i+1 là y_i hay y_i+1 theo một hướng khác . Đó là so sánh khoảng cách giữa điểm thực y với 2 điểm gần kề nó nhất. Nếu điểm nào nằm gần điểm thực hơn thì sẽ được chọn làm điểm vẽ tiếp theo.

Xét trường hơp 0<m<1

Gọi y là giá trị thực (giá trị chính xác) của đường thẳng tại x ở bước thứ i+1 .

y = m(x_i  + 1)+b

Gọi d₁ là khoảng cách từ y đến y_{i .}

Gọi d₂ là khoảng cách từ y đến y_{i+1 .}

Ta có:

Dễ thấy  d1-d2 tồn tại phép toán với số thực m = dy/dx  .Và để tuân thủ theo đúng ý tưởng thuật toán chỉ thực hiện các phép toán trên số nguyên, ta khử phân số ( triệt tiêu mẫu số) bằng cách nhân 2 vế với dx :

Sau khi đi phân tích một hồi như ở trên, nhiều bạn sẽ có thắc mắc là “Sao lại đặt Pi=dx( d1-d2) , rồi tại sao lại đi tìm Pi+1 theo Pi ? Đầu tiên , hãy nhìn hình dưới đây:

chúng ta có thể hiểu như này cho dễ, giả sử khoảng cách từ điểm thực y_{i+1 .}so với y_i  là p. Do việc phải xét nên chọn điểm trên hay điểm dưới gần với điểm thực hơn , mà mỗi lần x tăng thêm 1 đơn vị thì khoảng cách p lại cộng thêm một giá trị c nào đó. Tuy nhiên , khoảng cách p không tăng lên một cách tuyến tính , nên chúng ta phải đi tìm công thức tổng quát cho các trường hợp , đó là

P_i+1 = ? P_i    

4)Lưu đồ thuật toán:

5)Code minh họa :

#include <winbgim.h>
#include<conio.h>
#define DELAY 10
int color = 2;
void Bresenham(int x1, int y1, int x2, int y2){
	int Dx = abs(x2 - x1);
	int Dy = abs(y2 - y1);
	int p = 2*Dy - Dx;
	int c1 = 2*Dy;
	int c2 = 2*(Dy-Dx);
	int x = x1;
	int 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 x1,y1,x2,y2;
	int gd,gm=VGAMAX; gd=DETECT;
	initgraph(&gd,&gm,NULL);
//	setbkcolor(4);
	Bresenham(50,150, 300, 200);
	delay(9000);
	return 0;
}

Ảnh minh họa:

Cảm ơn các bạn đã đọc bài viết . Mong bài viết giúp ích cho việc học tập của các bạn !