Tài liệu Đồ họa máy tính tìm hiểu và cài đặt các thuật toán vẽ đường cho trường hợp tổng quát

ĐỒ HỌA MÁY TÍNH Tìm hiểu và cài đặt các thuật toán vẽ đường cho trường hợp tổng quát Input: (x1,y1)(x2,y2) Output : {(x1,y1)(x2,y2)….(xn,yn)} là những điểm sáng nằm trên đường thẳng. (x1,y1) (X2,y2) (x1,y1) (x2,y2) 1.Tăng chậm 2.Tăng nhanh 3. Giảm chậm ngược 4. Giảm nhanh ngược - Đối tượng mô tả trong hệ tọa độ thực là đối tượng liên tục, còn đối tượng trong hệ tọa độ thiết bị là đối tượng rời rạc. Nên cần thực hiện việc rời rạc hóa và việc nguyên hóa một cách tối uư nhất. Từ đó hình thành các thuật toán khác nhau với những uư thế riêng của nó để tối uư về mặt tốc độ và sự chính xác. Digital Differential Analyzer Để hiển thị trên lưới nguyên được liền nét các điểm có tọa độ (xi+1; yi+1) sẽ phải chọn 1 trong 8 điểm có tọa độ (xi + 1;yi + 1 ) 3 5 8 2 7 6 4 1 Thuật toán DDA là một thuật toán tính toán các điểm vẽ dọc theo đường thẳng dựa vào hệ số góc của phương trình đường thẳng y = mx + b Trường hợp 1 Đoạn thẳng tăng chậm với điểm đầu A(x1;y1) ở bên trái và điểm cuối B(xk; yk) ở bên phải và trường hợp đối xứng qua ox A B y = mx + b (0 < |m| <=1 ) m = (yk – y1)/(xk – x1) Bước 1: Xác định điểm đầu tiên x1 = x1 ; y1 =y1; Bước 2: Xác định những điểm tiếp theo Lặp x1 < xk ; xi+1 = xi +1 ; y = yi + m ; //đã cải tiến y yi+1 = Round(y); A B Lưu đồ thuật toán DDA vẽ đoạn thẳng qua 2 điểm (x1,y1) và (x2,y2) trong trương hợp 1 begin x end x=x+1; y=y+m; Putpixel(x,Round(y),c); m=Dy/Dx; x=x1; y=y1; Putpixel(x,y,c); NO yes Cài đặt thuật toán DDA trong trường hợp 1 #include #include #include #define Round(a) int(a+0.5) using namespace std; Void DDA_line1(int x1,int y1,int x1,int y2, Color c) { int Dx = x2-x1; Dy= y2-y1; float m = (float)Dy/Dx; if (abs(m) < 1) { int x = x1; float y = y1; putpixel(x, Round(y),c); while (x < x2) { x++; y = y+m; putpixel(x, Round(y), c); } } } Trường hợp 2 Đoạn thẳng tăng nhanh với điểm đầu A(x1;y1) ở bên trái và điểm cuối B(xk; yk) ở bên phải và trường hợp đối xứng qua oy A B y = mx + b (|m| > 1 ) m = (yk – y1)/(xk – x1) Bước 1: Xác định điểm đầu tiên x1 = x1 ; y1 =y1; Bước 2: Xác định những điểm tiếp theo Lặp y1 < yk ; x = xi +1/m; xi+1 = Round(x) ; yi+1 = yi +1; A B Lưu đồ thuật toán DDA vẽ đoạn thẳng qua 2 điểm (x1,y1) và (x2,y2) trong trường hợp 2 begin y end x=x+1/m; y=y+1; Putpixel(Round(x),y,c); m=Dy/Dx; x=x1; y=y1; Putpixel(x,y,c); NO yes Cài đặt thuật toán DDA trong trường hợp 2 #include #include #include #define Round(a) int(a+0.5) using namespace std; Void DDA_line1(int x1,int y1,int x1,int y2, Color c) { int Dx = x2-x1; Dy= y2-y1; float m = (float)Dy/Dx; if (abs(m) > 1) { float x = x1; int y = y1; putpixel(Round(x),y,c); while (y < y2) { x = x+1/m ; y ++; putpixel(Round(x), y, c); } } } Trường hợp 3 Đoạn thẳng giảm chậm với điểm đầu A(x1;y1) ở bên phải trên và điểm cuối B(xk; yk) ở bên trái dưới và đối xứng của nó qua ox y = mx + b (0 < |m| <=1 ) m = (yk – y1)/(xk – x1) Bước 1: Xác định điểm đầu tiên x1 = x1 ; y1 =y1; Bước 2: Xác định những điểm tiếp theo Lặp x1 > xk ; xi+1 = xi -1 ; y = yi - m ; yi+1 = Round(y); B A B A Lưu đồ thuật toán DDA vẽ đoạn thẳng qua 2 điểm (x1,y1) và (x2,y2) trong trường hợp 3 begin x >x2 end x=x-1; y=y-m; Putpixel(x,Round(y),c); m=Dy/Dx; x=x1; y=y1; Putpixel(x,y,c); NO yes Cài đặt thuật toán DDA trong trường hợp 3 #include #include #include #define Round(a) int(a+0.5) using namespace std; Void DDA_line1(int x1,int y1,int x1,int y2, Color c) { int Dx = x2-x1; Dy= y2-y1; float m = (float)Dy/Dx; if (abs(m) < 1) { int x = x1; float y = y1; putpixel(x, Round(y),c); while (x > x2) { x --; y = y - m; putpixel(x, Round(y), c); } } } Trường hợp 4 Đoạn thẳng giảm nhanh với điểm đầu A(x1;y1) ở bên phải và điểm cuối B(xk; yk) ở bên trái và đối xứng của nó qua oy A B y = mx + b (m > 1 ) m = (yk – y1)/(xk – x1) Bước 1: Xác định điểm đầu tiên x1 = x1 ; y1 =y1; Bước 2: Xác định những điểm tiếp theo Lặp y1 > yk ; x = xi -1/m; xi+1 = Round(x) ; yi+1 = yi -1; A B Lưu đồ thuật toán DDA vẽ đoạn thẳng qua 2 điểm (x1,y1) và (x2,y2) trong trường hợp 4 begin y > y2 end x=x-1/m; y=y-1; Putpixel(Round(x),y,c); m=Dy/Dx; x=x1; y=y1; Putpixel(x,y,c); NO yes Cài đặt thuật toán DDA trong trường hợp 4 #include #include #include #define Round(a) int(a+0.5) using namespace std; Void DDA_line1(int x1,int y1,int x1,int y2, Color c) { int Dx = x2-x1; Dy= y2-y1; float m = (float)Dy/Dx; if (abs(m) > 1) { float x = x1; int y = y1; putpixel(Round(x),y,c); while (y > y2) { x = x-1/m ; y --; putpixel(Round(x), y, c); } } } Luư đồ thuật toán DDA trong tất cả các trường hợp vẽ đường thẳng begin Dx = x2 – x1 Dy = y2 – y1 abs(Dx) > abs(Dy) xinc = Dx / step yinc = Dy / step x = x1; y = y1 putpixel (x, y,c ) end NO YES step = abs(Dx) step = abs(Dy) k<= step YES NO YES x = x + xinc y = y + yinc Putpixel(Round(x),Round(y),c) NO Cài đặt thuật toán DDA trong trường hợp Tổng quát #include #include #include #define Round(a) int(a+0.5) using namespace std; Void DDA_line1(int x1,int y1,int x1,int y2, Color color){ double x,y; int step; if(abs(x2-x1)>abs(y2-y1)) step=abs(x2-x1); else step=abs(y2-y1); x=(double)x1; y=(double)y1; putpixel(Round(x),Round(y),color); double m=(double)(x2-x1)/step; double n=(double)(y2-y1)/step; for(double i=1;i<=step;i++) { x+=m; y+=n; putpixel(Round(x),Round(y),color); } } Ví dụ Demo vẽ đường thẳng từ điểm A(2, 10) đến điểm B(21, 16) (0 < m < 1) điểm A(9, 1) đến điểm B(17,12) (m > 1) bằng thuật toán DDA. A (2, 10) đến B (21, 1) m= 6/19 = 0,316 < 1 i xi yi y 0 2 10 10 3 10 10,316 4 11 10,632 5 11 10,948 6 11 11,264 7 12 11,580 8 12 11,896 9 12 12,212 10 13 12,528 11 13 12,844 12 13 13,160 13 13 13,476 14 14 13,792 15 14 14,108 16 14 14,424 17 15 14,740 18 15 15,056 19 15 15,372 20 16 15,688 21 16 16,004 A ( 9,1 ) đến B (17 , 12 ) m= 11/8 = 1.375> 1 1/m = 0,73 i xi yi x 0919 10 2 9,73 10 3 10,46 11 4 11,19 12 5 11,92 13 6 12,65 13 7 13,38 14 8 14,11 15 9 14,84 16 10 15,57 16 11 16,30 17 12 17,03 Tất cả các trường hợp của đoạn thẳng còn lại được vẽ dựa trên thuật toán DDA bằng việc hoán đổi vị trí của điểm đầu và điểm cuối hoặc lấy đối xứng qua các trục tọa độ của 4 trường hợp trên. Việc sử dụng công thức để tính giá trị y tại mỗi bước đã giúp cho thuật toán DDA nhanh hơn hẳn so với cách tính y từ phương trình 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ẽ ra 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. Tuy đã khử được phép nhân số thực nhưng thuật toán DDA vẫn còn bị hạn chế về mặt tốc độ do vẫn còn phép toán cộng số thực và làm tròn. Có thể khắc phục thao tác cộng số thực m và làm tròn trong thuật toán bằng cách nhận xét m=Dy/Dx với Dy, Dx là các số nguyên. - Thuật toán Bresenham đưa ra cách chọn yi+1 là yi hay yi+1 theo một hướng khác sao cho có thể tối ưu hóa về mặt tốc độ so với thuật toán DDA. Vấn đề mấu chốt ở đây là làm thế nào để hạn chế tối đa các phép toán trên số thực trong thuật toán. - Ý tưởng chính của thuật toán Bresenham là việc so sánh khỏang cách giữa tọa độ y thực tại vị trí xi+1 với các tọa độ y nguyên trên và dưới nó. *** Phương pháp của thuật toán Bresenham Gọi (xi+1,y) là điểm thuộc đoạn thẳng thực. Ta có: y = m( xi+1) + b. (0 < m <1) Xét các hiệu khoảng cách của tung độ thực y so với các tung độ nguyên yi và yi+1 để chọn một điểm là S(xi +1, yi) hay P( xi + 1,yi + 1) gần với điểm thực nhất. Đặt d1 = y - yi d2 = ( yi+ 1) - y - Nếu d1- d2 < 0: Chọn điểm S, tức là yi+1=yi. - Nếu d1- d2 ≥ 0: Chọn điểm P, tức là yi+1 =yi + 1. Xây dựng pi Xét pi = Δx (d1 - d2) với Δx= x2- x1; Δy= y2 –y1; Ta có : d1 - d2 = 2 yi+1 - 2yi - 1 = 2m(xi+1) + 2b - 2yi - 1 => pi = Δx (d1 - d2) = Δx[2m(xi+1) + 2b - 2yi - 1] = Δx[2 Δy/Δx (xi+1) + 2b - 2yi - 1] = 2Δy(xi+1) - 2Δx.yi + Δx(2b - 1) = 2Δy.xi - 2Δx.yi+ 2Δy + Δx(2b - 1) Vậy C = 2Δy + Δx(2b - 1) = Const => pi= 2Δy.xi - 2Δx.yi+ C Nhận xét rằng nếu tại bước thứ i ta xác định được dấu của Pi thì xem như ta xác định được điểm cần chọn ở bước (i+1). Ta có : pi +1 - pi= (2Δy.xi+1 - 2Δx.yi+1+ C) - (2Δy.xi - 2Δx.yi+ C ) => Pi +1 = pi + 2Δy - 2Δx ( yi+1 - .yi) - Nếu pi< 0 : chọn điểm S, tức là yi +1= yi và pi +1 = pi + 2Δy. - Nếu pi≥ 0 : chọn điểm P, tức là yi +1= yi +1 và pi +1 = pi + 2Δy - 2Δx - Giá trị p0được tính từ điểm vẽ đầu tiên (x0,y0) theo công thức : P0= 2Δy.x0 - 2Δx.y0+ C Do (x0,y0) là điểm nguyên thuộc về đoạn thẳng nên ta có : y0 = m .x0+ b = Δy/Δx.x0 + b Thế vào phương trình trên ta được : p0= 2Δy - Δx Trường hợp 1 |Dy|<=|Dx| A B A B B A B A Các dạng đường thẳng thỏa |yB - yA| <= |xB – xA| Giải thuật trong trường hợp 1: |Dy|<=|Dx|; Bước 1: Xác định điểm đầu int Dx = x2 – x1, Dy = y2 – y1; int p = 2 * Dy – Dx; int const1 = 2 * Dy, const2 = 2 * (Dy-Dx); int x = x1, y = y1; putpixel(x, y, color); int dx =(Dx>0)? 1:-1; int dy=(Dy>0)? 1:-1; Bước 2: Xác định những điểm tiếp theo Lặp x!=x2 ; Nếu p<0: p+=const1; Nếu p>=0: p+=const2; y+=dy; x+=dx; Putpixel(x,y,color); Luư đồ thuật toán Bresenham trường hợp 1: |Dy|<=|Dx| begin p = 2Dy - Dx; const1=2Dy; const2=2(Dy-Dx); x = x1; y = y1; putpixel(x,y,color); dx = (Dx >0)? 1:-1; dy = (Dy > 0)?1:-1; x != x2 p+=const1; end NO YES p<0 p+=const2; y + = dy; x += dx; Putpixel(x, y,color); YES NO Cài đặt thuật tóan Bresenham trong trường hợp 1 #include #include #include using namespace std; Void Bresenham_line (int x1,int y1, int x2, int y2, Color color) { int Dx = x2 – x1, Dy = y2 – y1; int x = x1, y = y1; int p = 2 * Dy – Dx ; int const1 = 2 * Dy , const2 = 2 * (Dy-Dx); putpixel(x, y, color) ; int dx =(Dx>0)? 1:-1 ,dy=(Dy>0)? 1:-1; if(abs(Dy) <= abs(Dx)) { while(x != x2) { if ( p < 0) p+=const1; else { p+=const2; y += dy; } x += dx; putpixel(x,y,color); } } } A B A B B A A B Trường hợp 2 |Dy|<=|Dx| Các dạng đường thẳng thỏa |Dy| > |Dx| Giải thuật trong trường hợp 2 |Dy|>|Dx|; Bước 1: Xác định điểm đầu int Dx = x2 – x1, Dy = y2 – y1; int x = x1, y = y1; int p = 2 * Dx – Dy; int const1 = 2 * Dx, const2 = 2 * (Dx-Dy); putpixel(x, y, color); int dx =(Dx>0)? 1:-1; int dy=(Dy>0)? 1:-1; Bước 2: Xác định những điểm tiếp theo Lặp y!=y2 ; Nếu p<0: p+=const1; Nếu p>=0: p+=const2; x+=dx; y+=dy; Putpixel(x,y,color); Luư đồ thuật toán Bresenham trong trường hợp 2: |Dy|>|Dx| begin p = 2Dx - Dy; const1=2Dx; const2=2(Dx-Dy); x = x1; y = y1; putpixel(x,y,color); dx = (Dx >0)? 1:-1; dy = (Dy > 0)?1:-1; y != y2 p+=const1; end NO YES p<0 p+=const2; x+ = dx; y+= dy; Putpixel(x, y,color); YES NO Cài đặt thuật toán Bresenham trong trường hợp 2 #include #include #include using namespace std; Void Bresenham_line (int x1,int y1, int x2, int y2, Color color) { int Dx = x2 – x1, Dy = y2 – y1; int x = x1, y = y1; int p = 2 * Dx – Dy ; int const1 = 2 * Dx , const2 = 2 * (Dx-Dy); putpixel(x, y, color) ; int dx =(Dx>0)? 1:-1 ,dy=(Dy>0)? 1:-1; if(abs(Dy) > abs(Dx)) { while(y != y2) { if ( p < 0) p+=const1; else { p+=const2; x += dx; } y += dy; putpixel(x,y,color); } } } Ví dụ Demo vẽ đường thẳng bằng thuật toán Bresenham qua hai điểm A(5,8) và B(20,13) Ta có Dy=5, Dx=15; p=2Dy-Dx=-5 const1=2Dy=10, const2=2(Dy-Dx)=-20 Thuật toán Bresenham chỉ làm việc trên số nguyên và các thao tác trên số nguyên chỉ là phép cộng và phép dịch bit (phép nhân 2) đ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ằm ở chỗ xét dấu pi để quyết định điểm kế tiếp, và sử dụng công thức truy hồi pi+1- pi để tính pi bằng các phép toán đơn giản trên số nguyên. Tuy nhiên thuật toán Bresenham xây dựng phức tạp hơn thuật toán DDA. Thuật toán MidPoint đưa ra cách chọn yi+1 là yi hay yi +1 bằng cách so sánh điểm thực Q với điểm MidPoint là trung điểm của S và P. Ta có : Nếu điểm Q nằm dưới điểm MidPoint, ta chọn S. - Ngược lại nếu điểm Q nằm trên điểm MidPoint ta chọn P. Ta có dạng tổng quát của phương trình đường thẳng là : Ax + By + C = 0 Với A = y2 –y1; B = - (x2 – x1) ; C = x2y1 -x1y2 Đặt F(x,y)=Ax + By + C thì ta có nhận xét F(x,y) <0,nếu (x,y) nằm phía trên đường thẳng F(x,y) = 0 nếu (x,y) nằm thuộc đường thẳng F(x,y) > 0 nếu (x,y)nằm phía dưới đường thẳng Lúc này việc chọn điểm S hay P được đưa về việc xét dấu của pi = 2F(midpoint) = 2F(xi+1;yi+1/2) Xây dựng pi trong trường hợp 0<=m<=1, và Dx <0 Giống như một số thuật toán khác, ta không tính toán trực tiếp các giá trị pi để chọn điểm tiếp theo mà tính toán dựa trên kết quả của bước trước. Xét pi+1-pi=2F(xi+1+1,yi+1+1/2)-2F(xi+1,yi+1/2) Thay F(x,y)=Ax+By+C với A=Dy, B=-Dx vào ta được kết quả pi+1-pi=2Dy-2Dx(yi+1-yi) (1) Nhận xét: Khi yi+1=yi ta có (1) pi+1=pi+2Dy Khi yi+1=yi+1 ta có (1)  pi+1=pi+2Dy-2Dx=pi+2(Dy-Dx) Giá trị p0 ứng với điểm ban đầu được tính: p0=2F(xđầu+1, y đầu+1/2)=2[A(xđầu+1)+B(yđầu+1/2)+C] =2Dy-Dx Tóm tắt thuật toán: p0=2Dy-Dx yi+1= pi+1= yi nếu pi <0 yi+1 nếu pi >=0 pi+2Dy nếu pi <0 pi+2(Dy-Dx) nếu pi >=0 Trường hợp 1: |Dy|<=|Dx| A B A B B A B A Giải thuật bằng thuật toán Midpoint trong trường hợp 1 |Dy|<=|Dx|; . Bước 1: Xác định điểm đầu int Dx = x2 – x1, Dy = y2 – y1; int x = x1, y = y1; int p = 2 * Dy – Dx; int const1 = 2 * Dy, const2 = 2 * (Dy-Dx); putpixel(x, y, color); dx =(Dx>0)? 1:-1; dy=(Dy>0)? 1:-1; Bước 2: Xác định những điểm tiếp theo Lặp x!=x2 ; Nếu p<0: p+=const1; Nếu p>=0: p+=const2; y+=dy; x+=dx; Putpixel(x,y,color); Luư đồ thuật toán Midpoint trường hợp 1: |Dy|<=|Dx| begin p = 2Dy - Dx; const1=2Dy; const2=2(Dy-Dx); x = x1; y = y1; putpixel(x,y,color); dx = (Dx >0)? 1:-1; dy = (Dy > 0)?1:-1; x != x2 p+=const1; end NO YES p<0 p+=const2; y + = dy; x += dx; Putpixel(x, y,color); YES NO Cài đặt thuật tóan Midpoint trong trường hợp 1 #include #include #include using namespace std; Void Bresenham_line (int x1,int y1, int x2, int y2, Color color) { int Dx = x2 – x1, Dy = y2 – y1; int x = x1, y = y1; int p = 2 * Dy – Dx ; int const1 = 2 * Dy , const2 = 2 * (Dy-Dx); putpixel(x, y, color) ; int dx =(Dx>0)? 1:-1 ,dy=(Dy>0)? 1:-1; if(abs(Dy) <= abs(Dx)) { while(x != x2) { if ( p < 0) p+=const1; else { p+=const2; y += dy; } x += dx; putpixel(x,y,color); } } } A B A B B A A B Trường hợp 2 |Dy|<=|Dx| Các dạng đường thẳng thỏa |Dy| > |Dx| Giải thuật bằng thuật toán MidPoint trong trường hợp 2 |Dy|>|Dx|; Bước 1: Xác định điểm đầu int Dx = x2 – x1, Dy = y2 – y1; int x = x1, y = y1; int p = 2 * Dx – Dy; int const1 = 2 * Dx, const2 = 2 * (Dx-Dy); putpixel(x, y, color); int dx =(Dx>0)? 1:-1; int dy=(Dy>0)? 1:-1; Bước 2: Xác định những điểm tiếp theo Lặp y!=y2 ; Nếu p<0: p+=const1; Nếu p>=0: p+=const2; x+=dx; y+=dy; Putpixel(x,y,color); Luư đồ thuật toán Midpoint trong trường hợp 2: |Dy|>|Dx| begin p = 2Dx - Dy; const1=2Dx; const2=2(Dx-Dy); x = x1; y = y1; putpixel(x,y,color); dx = (Dx >0)? 1:-1; dy = (Dy > 0)?1:-1; y != y2 p+=const1; end NO YES p<0 p+=const2; x+ = dx; y+= dy; Putpixel(x, y,color); YES NO Cài đặt thuật toán Midpoint trong trường hợp 2 #include #include #include using namespace std; Void Bresenham_line (int x1,int y1, int x2, int y2, Color color) { int Dx = x2 – x1, Dy = y2 – y1; int x = x1, y = y1; int p = 2 * Dx – Dy ; int const1 = 2 * Dx , const2 = 2 * (Dx-Dy); putpixel(x, y, color) ; int dx =(Dx>0)? 1:-1 ,dy=(Dy>0)? 1:-1; if(abs(Dy) > abs(Dx)) { while(y != y2) { if ( p < 0) p+=const1; else { p+=const2; x += dx; } y += dy; putpixel(x,y,color); } } } Mở rộng thuật toán Midpoint trong các trường hợp vẽ đường thẳng với m bất kì ***Trường hợp đặc biệt m = : Đoạn thẳng song song trục tung nên rất đơn giản khi vẽ. ***Trường hợp -1<=m<=1 :Sử dụng các công thức của thuật toán vẽ trong trường hợp 0 < = m <=1, Dx >0 và thay đổi một số điểm sau: Nếu Dx < 0 thì bước nhảy của x sẽ thay bằng -1 tương tự nếu Dy <0, bước nhảy của y cũng sẽ là -1. Thay Dx bằng abs(Dx), Dy = abs(Dy) trong tất cả các công thức có chứa Dx,Dy *** Trường hợp m<= -1 hay m>=1 Thay đổi vai trò của x và y cho nhau, thay đổi vai trò của Dx và Dy cho nhau trong tất cả các công thức Thực hiện nguyên tắt về bước nhảy và thay đổi Dx, Dy như trong trường hợp -1< = m < =1 Dựa vào tính chất đối xứng của đường tròn ta có thể mở rộng các thuật toán Bresenham và Midpoint cho việc vẽ đường tròn y THUẬT TOÁN VẼ ĐƯỜNG TRÒN y (x,y) (y,x) (-y,x) (x,-y) (-x,-y) (-y,-x) (y,-x) (-x,y) x Trong hệ tọa độ Descartes, phương trình đường tròn bán kính R có dạng: Với tâm O(0,0) : x2 + y2 = R2 Với tâm C(xc,yc): (x - xc)2 + (y - yc)2 = R2 Trong hệ tọa độ cực : x = xc+ R.cosθ y = yc + Y.sinθ với θ thuộc [0, 2π]. - Do tính đối xứng của đường tròn C (xem hình 1.7) nên ta chỉ cần vẽ 1/8 cung tròn, - sau đó lấy đối xứng qua 2 trục tọa độ và 2 đường phân giác thì ta vẽ được cả đường tròn. THUẬT TOÁN VẼ ĐƯỜNG TRÒN BẰNG MIDPOINT Do tính đối xứng của đường tròn nên ta chỉ cần vẽ 1/8 cung tròn, sau đó lấy đối xứng là vẽ được cả đường tròn. Thuật toán MidPoint đưa ra cách chọn yi+1 là yi hay yi-1 bằng cách so sánh điểm thực Q(xi+1,y) với điểm giữa MidPoind là trung điểm của S1 vàS2. Chọn điểm bắt đầu để vẽ là (0,R). Giả sử (xi, yi) là điểm nguyên đã tìm được ở bước thứ i (xem hình 1.8), thì điểm (xi+1, yi+1) ở bước i+1 là sự lựa chọn giữa S1 và S2. Xi+1 = x + 1 yi+1= yi – 1 hoặc yi; THUẬT TOÁN VẼ ĐƯỜNG TRÒN BẰNG MIDPOINT Đặt F(x,y) = x2 + y2 - R2 , ta có : . F(x,y) < 0 , nếu điểm (x,y) nằm trong đường tròn. . F(x,y) = 0 , nếu điểm (x,y) nằm trên đường tròn. . F(x,y) > 0 , nếu điểm (x,y) nằm ngoài đường tròn. Xét Pi = F(MidPoint) = F(xi +1, yi - 1/2). Ta có : - Nếu Pi < 0 : điểm MidPoint nằm trong đường tròn. Khi đó, điểm thực Q gần với điểm S1 hơn nên ta chọn yi+1 = yi . - Nếu Pi>= 0 : điểm MidPoint nằm ngòai đường tròn. Khi đó, điểm thực Q gần với điểm S2 hơn nên ta chọn yi+1 = yi - 1. Mặt khác : Pi+1 - Pi = F(xi+1 +1, yi+1 - 1/2) - F(xi + 1, yi - 1/2) = [(xi+1 +1)2 + (yi+1 - 1/2)2 - R2 ] - [(xi +1)2 + (yi - 1/2)2 - R2 ] = 2xi + 3 + ((yi+1)2 + (yi)2 ) - (yi+1 - yi) Vậy : - Nếu Pi < 0 : chọn yi+1 = yi. Khi đó Pi+1 = Pi+ 2xi +3 - Nếu Pi >= 0 : chọn yi+1 = yi - 1. Khi đó Pi+1 = Pi+ 2xi - 2yi +5. - Piứng với điểm ban đầu ( x0 , y0 ) = (0,R) là: P0 = F(x0 + 1, y0 - 1/2) = F(1, R - 1/2) =5/4 -R XÂY DỰNG THUẬT TOÁN VẼ ĐƯỜNG TRÒN BẰNG MIDPOINT Q(xi+1,y) Midpoint S1 S2 yi yi-1 yi+1 (xi,yi) Luư đồ thuật toán Midpoint cho đường tròn begin P = 5/4 - R; x=0 ; y= R; Putpixel8(x,y,c); x P = P + 2*x + 3 end NO YES p<0 P = P + 2*(x-y)+5 y=y-1 x++; putpixel8(x,y,color) YES NO Cài đặt thuật toán Midpoint cho đường tròn void MidpointCircle(int a,int b,int r,Color c){ int x,y; x=0; y=r; put8pixel(x,y,a,b,c); int p=1-r; while(x if(p<0) { p+=2*x+3; } else { p+=2*(x-y)+5; y--; } x++; put8pixel(x,y,a,b,c); } } Ví dụ Demo đường tròn bằng thuật toán Midpoint Midpointcircle(15,16,13,Color(255,0,0)); Vẽ đường tròn bằng thuật toán Bresenham Tương tự thuật toán vẽ đường thẳng Bresenham, các vị trí ứng với các tọa độ nguyên nằm trên đường tròn có thể tính được bằng cách xác định một trong hai pixel gần nhất với đường tròn thực hơn trong mỗi bước