Dù thuật toán Bresenham đã có bước chuyển mình thành công , đó là cải tiến việc tính toán trên số thực  phức tạp của thuật toán DDA thành chỉ thao tác trên số nguyên, trên phép cộng và nhân , làm tăng tốc thuật toán đáng kể . Nhưng việc xây dựng trường hợp tổng quát cho thuật toán Bresenham có vẻ phức tạp hơn nhiều so với thuật toán DDA. Vì vậy , vào năm 1967 , Pitteway đã công bố thuật toán MidPoint (được phát triển dựa trên thuật toán Bresenham) ,sau đó vào năm 1984  được Van Aken cải tiến. Thuật toán Midpoint cho kết quả hoàn toàn giống với thuật toán Bresenham , nhưng cách xây dựng thì “max simple” đơn giản hơn rất nhiều. Chúng ta cùng đi vào tìm hiểu thuật toán Midpoint nha!

1) Đặt vấn đề:

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

2)Giải thuật:

Xét 0<hệ số góc<1

Thuật toán Midpoint đưa ra cách chọn điểm y_i+1 là y_i hay y_i+1 bằng cách so sánh điểm thực Q(x_i+1 , y) với điểm Midpoint là trung điểm của S và P.

Nếu điểm Q nằm dưới điểm Midpoint thì ta chọn điểm S là điểm vẽ tiếp theo. Ngược lại , nếu điểm Q nằm trên điểm Midpoint thì ta chọn P.

Ta có dạng tổng quát của PT đường thẳng :

Ax + By +C=0

Với A= y_o –y₁ ; B= -(x₂ –x₁) ; C=x₂y₁ –x₁y₂

Đặt F(x,y)= Ax+ By +C

Ta có nhận xét:

Vị trí tương đối của điểm Midpoint (x,y) với đường thẳng:

•                             _{< 0 nếu (x,y) nằm phía trên đường thẳng}
•         _{F( x, y )      = 0 nếu (x,y) thuộc về đường thẳng}
•                            _{> 0 nếu (x,y) nằm phía dưới đường thẳng}

Lúc này việc chọn các điểm S, P ở trên được đưa về việc xét dấu của

p_i = 2F(Midpoint) = 2F(x_i +1 , y_i +1/2)

• Nếu pi < 0 ⇒ Midpoint nằm phía trên đường thẳng ⇒Lúc này điểm thực Q nằm phía dưới điểm Midpoint  ⇒ Chọn S(xi+1,yi) .

• Nếu pi >= 0 ⇒ Midpoint nằm phía dưới đường thẳng ⇒ Lúc này điểm thực Q nằm trên điểm Midpoint ⇒ Chọn P(xi+1,yi+1).

Mặt khác:

p_i+1 –p_i = 2F(x_i+1 +1 , y_i+1 +1/2) – 2F(x_i +1 , y_i +1/2)

⇒ p_i+1 –p_i =2[A(x_i+1  +1) + B(y_i+1  +1/2) +C] – 2[A(x_i +1) + B(y_i+1/2) +C]

⇒ p_i+1 –p_i = 2A + 2B(y_i+1   – y_i)

⇒ p_i+1 –p_i = 2Dy  – 2Dx(y_i+1   – y_i)

Vậy

p_i+1 =p_i + 2Dy  nếu p_i <0 do ta chọn y_i+1 =y_i

p_i+1 =p_i + 2Dy  – 2Dx nếu p_i >=0 do ta chọn  y_i+1 =y_i  +1

Ta tính giá trị p₁  ứng với điểm ban đầu (x₁, y₁) với nhận xét rằng điểm (x₁, y₁) là điểm thuộc đường thẳng, tức là có Ax₁ + By₁ + C =0.

p₁ = 2F(x₁ +1, y₁ +1/2) = 2[A(x₁ +1) +B(y₁ +1/2) +C]

⇒ p₁ = 2(Ax₁ + By₁ +C) +2A +B

⇒ p₁ = 2A + B

⇒ p₁ = 2Dy-Dx

Ta thấy kết quả của thuật toán Midpoint tương tự thuật toán Bresenham như đã nói ở trên.

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

Giống của thuật toán Bresenham

4) Code minh họa:

#include<iostream>
#include<winbgim.h>
#include<math.h>
using namespace std;

void midpoint(int x1,int y1,int x2, int y2,int color){
	//Truong hop 0<m<1 && x1<x2 && y1<y2
	int a,b,pi,x,y,p;
	a=y2-y1;
	b=-(x2-x1);
	y=y1;
	x=x1;
	putpixel(x,y,color);	//Ve diem pixel dau tien
	p=2*a+b;		//tinh vi tri tuong doi cua diem Midpoint so voi duong thang
	while(x < x2){
		if(p < 0){	
			p+=2*a; // ta chon chon diem yi
		}else{		
			y++;
			p+=2*(a+b);//ta chon diem yi +1
		}
		x++;
		cout<<"Pixel (x,y) midpoint = ("<<x<<", "<<y<<")\n";
		putpixel(x,y,color);
		delay(10);
	}
}


int main(){
	initwindow(800,600);
	//khoi tao window có chieu rong	x=400 và chieu cao y = 500
	setwindowtitle("Thuat toan Line Midpoint");	 
      //thiet	lap	tieu	de	cho	windows
	midpoint(10,10,400,400,15);
	getch();
}

Ả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 !