Trong đồ họa máy tính, khi muốn vẽ đường Elip , ngoài việc áp dụng thuật toán Bresenham (như bài 6), chúng ta còn có thể áp dụng một thuật toán nữa – đó chính là thuật toán Midpoint. Và thuật toán Midpoint , chúng ta cũng đã tìm hiểu khi dùng để vẽ đường thẳng ( tại bài 5) . Nếu bạn nào chưa  đọc thì hãy vào xem phần này nha !

Đặt vấn đề

Vẽ elip bằng thuật toán Midpoint.

Giải thuật

Để đơn giản, chúng ta sẽ chọn vẽ hình Elip có tâm ở gốc tọa độ.

Phương trình của đường Elip:

f(x,y) = b²x² + a²y²  – a²b²    

• < 0 nếu (x,y) nằm bên trong elip.
• = 0 nếu (x,y) nằm trên elip.
• > 0 nếu (x,y) nằm bên ngoài elip.

*Ý tưởng và phân tích giải thuật:

• Chia Elip làm 2 phần tại điểm Q nơi có hệ số góc của tiếp tuyến với Elip bằng -1 (véc tơ gradient bằng 1) ( lý do tại sao lại phải chia làm 2 phần thì bài 6 mình đã giải thích rồi nhé). Tại vùng thứ nhất, x biến thiên nhanh hơn y và tại vùng thứ hai , y biến thiên nhanh hơn x. Nhớ lại công thức hệ số góc của đường cong :

dx/dy = fx/fy = (2b²x) /( 2a²y)

trong đó: fx và fy là đạo hàm riêng phần của f(x,y) theo x, theo y.

• Trong phần thứ nhất:

Giả sử đã vẽ được điểm (x_i,y_i) , điểm tiếp theo trên elip được chọn trong bước nhảy i+1 là T hoặc S.  Trung điểm I của TS sẽ quyết định điểm nào được chọn. Giá trị của f(x,y) tại điểm I:

d_i = f(x_i + 1, y_i – ½) = b²(x_i + 1)² + a²(y_i – ½)² – a²b²

+Nếu d_i ≥ 0 thì trung điểm I nằm ngoài đường elip  => điểm được chọn là S.

+Nếu d_i < 0 thì trung điểm I nằm trong đường elip =>  điểm được chọn là T.

Ta lại có:

d_i+1 = f(x_i+1 + 1, y_i+1 – ½) = b²(x_i+1 +1)² + a²(y_i+1 – ½)² – a²b²

Suy ra:

d_i+1 – d_i = b²[(x_i+1 +1)² – (x_i +1)²] +a²[(y_i+1 – ½)² – (y_i – ½)²]

Vì x_i+1 = x_i+1 nên

d_i+1 – d_i = 2b²x_i+1 + b² + a²[(y_i+1 – ½)² – (y_i – ½)²]

+ Nếu điểm được chọn là T (d_i < 0) thì y_i+1 = y_{i .} 

Ta có :

d_i+1 = d_i + 2b²x_i+1 + b² (= d_i + fx + b²)

= d_i + 2b² (x_i + 1) + b²

= d_i + b² (2x_i + 3)

+ Nếu điểm được chọn là S (d_i ≥ 0) thì y_i+1 = y_i – 1

Ta có:

d_i+1 = d_i + 2b²x_i+1 + b² – 2a²y_i+1 (= d_i + fx + b² – fy)

       = d_i + 2b² (x_i + 1) + b² – 2a² (y_i – 1)

= d_i + b² (2x_i + 3) + a² (-2y_i + 2)

Với điểm đầu tiên (0,b) ta có:

d₁ = f(0,b) = b² + a²(b – ½)² – a²b² = b² ─ a²b + a²/4

• Trong phần thứ hai:

Chúng ta tính toán như phần 1. Giả sử ta phải xác định điểm  (x_j+1,y_j+1) tiếp theo trên elip  trong bước j+1. Điểm được chọn là U hoặc V. Trung điểm K của UV sẽ quyết định việc chọn điểm U hay điểm V. Giá trị của f(x,y) tại điểm K:

e_j = f(x_j + ½, y_j – 1) = b²(x_j + ½)² + a²(y_j – 1)² – a²b²

+ Nếu e_j ≥ 0 điểm được chọn là U.

+ Nếu e_j < 0 điểm được chọn là V.

Ta lại có:

e_j+1 = f(x_j+1 + ½, y_j+1 – 1) = b²(x_j+1 + ½)² + a²(y_j+1 – 1)² – a²b²

Suy ra:

e_j+1 – e_j = b²[(x_j+1 + ½)² – (x_j + ½)²] + a²[(y_j+1 – 1)² – (y_j – 1)²]

= b²[(x_j+1 + ½)² – (x_j + ½)²] – 2a²y_j+1 + a²  

(Chú ý : y_j+1 = y_i – 1)

+ Nếu điểm được chọn là U (tức e_j ≥ 0) thì x_j+1 = x_j

Ta có:

e_j+1 = e_j – 2a²y_j+1 + a² (= e_j – fy + a²)

= e_j – 2a²(y_j -1) + a²

= e_j – a²(3 – 2y_j)

+ Nếu điểm được chọn là V (tức e_j < 0 )thì x_j+1 = x_j+1

Ta có:

e_j+1 = e_j + 2b²x_j+1 – 2a²y_j+1 + a² (= e_j + fx – fy + a²)

= e_j + 2b²(x_j + 1)– 2a²(y_j -1) + a²

= e_j + b²(2x_j + 2)+ a²(3 -2y_j )

Giá trị khởi tạo ban đầu trong phần 2 phụ thuộc vào vị trí cuối cùng của phần 1 , giả sử là (x_k,y_k). Khi đó:

e₁ = f(x_k + ½, y_k – 1) = b²(x_k + ½) + a²(y_k – 1)² – a²b²

Lưu đồ thuật toán

*Q: Tại sao lại so sánh  2A²y < 0 ???

=> A:  Do ở phần ý tưởng thuật toán, chúng ta chia elip làm 2 phần để vẽ và lấy điểm Q có hệ số góc của tiếp tuyến với elip bằng -1 làm giao điểm. Theo công thức hệ số đã nêu ở trên:  dx/dy = fx/fy = (2b²x) /( 2a²y). Tại điểm đầu tiên có tọa độ  (0,b), chúng ta thay x=0 và y=b vào công thức trên được hệ số góc= 0/( 2a²b) lớn hơn -1 . Nên ta chọn vẽ theo nhánh 1 . Như vậy, việc so sánh  2A²y < 0 là để chọn nhánh vẽ elip thôi.

Code minh họa

#include<graphics.h>
#include<conio.h>//de dung man hinh dô hoa
#include<iostream>
#define ROUND(a) (int)(a+0.5)
using namespace std;

void plot(int xc, int yc, int x, int y, int color)
{
	putpixel(xc+x, yc+y, color);
	putpixel(xc-x, yc+y, color);
	putpixel(xc+x, yc-y, color);
	putpixel(xc-x, yc-y, color);
}
void elipMidpoint(int xc,int yc, int a, int b, int color)
{
	int x, y, fx, fy, a2, b2, p;
	x = 0;
	y = b;
	a2 = a*a;
	b2 = b*b;
	fx = 0;
	fy = 2 * a2 * y;
	plot(xc, yc, x, y, color);
	p = ROUND(b2 -(a2*b) + (0.25*a2));//p=b2 - a2*b +a2/4
	while(fx<fy)
	{
		x++;
		fx += 2*b2;
		delay(50);
		if(p<0)
		{
			p += b2*(2*x + 3);//p=p + b2*(2x +3)
		}
		else
		{
			y--;
			p += b2*(2*x +3) + a2*(2- 2*y);//p=p +b2(2x +3) +a2(2-2y)
			fy -= 2*a2;
		}
		plot(xc, yc, x, y, color);
	}
	p = ROUND(b2*(x +0.5)*(x +0.5) + a2*(y-1)*(y-1) - a2*b2);
	//
	while(y>0)
	{
		y--;
		fy -= 2*a2;
		delay(50);
		if(p >=0)
		{
			p += a2*(3-2*y); //p=p +a2(3-2y)
		}
		else
		{
			x++;
			fx += 2*b2;
			p += b2*(2*x +2) +a2*(3- 2*y);//p=p+ b2(2x +2) + a2(3-2y)
		}
		plot(xc, yc, x, y, color);
	}
}
int main()
{
	int gd=DETECT, gm;
	initgraph(&gd,&gm,"");
	elipMidpoint(getmaxx()/2, getmaxy()/2,150,80,15);
	getch();
	closegraph();
	return 0;
}
	

Hì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 !