Giáo trình Đồ họa trong Pascal - Chương 1: Màn hình của máy tính - Bài 3: Các thuật toán vẽ đoạn thẳng, đường tròn

$3. CÁC THUẬT TOÁN VẼ ĐOẠN THẲNG, ĐƯỜNG TRÒN
I. VẼ ĐOẠN THẲNG :
Giả sử ta cần vẽ đoạn thẳng đi qua 2 điểm (x1, y1) và (x2, y2), thì hệ số góc của nó là m=dy/dx, trong đó dy=y2-y1; dx=x2-x1 và phương trình đường thẳng sẽ là y=m.x+b với b=y1-m.x1;
1. Vẽ đoạn thẳng bằng cách làm tròn số :
a. Trường hợp x1=x2 :
trong trường hợp này đoạn thẳng là đường song song với trục tung
b. Trường hợp y1=y2 :
trong trường hợp này đoạn thẳng là đường song song với trục hoành
c. Trong trường hợp 0<|m|<=1 :
Trường hợp này là trường hợp giá trị tuyệt đối của hệ số góc nhỏ hơn 1 thì ta vẽ đoạn thẳng bằng cách cho x chạy từ x1 đến x2 tính y=Round(m.x+b) và vẽ điểm (x,y) 
d. Trong trường hợp |m|>1 :
Trường hợp này là trường hợp giá trị tuyệt đối của hệ số góc lớn hơn 1 ta viết lại phương trình đường để cho giá trị tuyệt đối của hệ số góc nhỏ hơn 1 : x=(1/m)y-b/m thì ta vẽ đoạn thẳng bằng cách cho y chạy từ y1 đến y2 tính x=Round((1/m)y-b/m) và vẽ điểm (x,y)
Chương trình trên chạy chậm vì phải tính toán với các số thực.
Bài tập : Lập chương trình vẽ đoạn thẳng theo thuật toán trên
2. Thuật toán vẽ đoạn thẳng của Bresanham
Ta bắt đầu bằng cách xét đường thẳng có hệ số góc nằm trong khoảng (0,1] vì các điểm trên màn hình được biểu diễn bởi các toạ độ nguyên nên ta cho x tăng theo bước nhảy đơn vị từ x1 đến x2. Giả sử trên hình vẽ điểm (x[i],y[i]) là điểm nằm trên đoạn thẳng đã được vẽ và cho x[i] tăng thêm 1 để vẽ điểm tiếp theo và giá trị của y ứng với x[i]+1 ta nên chọn là y[i] hay y[i]+1, giá trị đúng của y=m(x[i]+1)+b như vậy ta sẽ tuỳ xem y[i] hay y[i]+1 gần y(=m(x[i]+1)+b) hơn thì ta sẽ chọn giá trị đó. Ta xét các khoảng cách :
Khoảng cách giữa y và y[i] : 	d1=y-y[i]=m(x[i]+1)+b-y[i]
Khoảng cách giữa y[i]+1 và y : 	d2=y[i]+1-y=y[i]+1-m(x[i]+1)-b
Hiệu giữa hai khoảng cách này là : d1-d2=2m(x[i]+1)-2y[i]+2b-1
thay m=dy/dx ta có d1-d2=2(dy/dx)(x[i]+1)-2y[i]+2b-1
nên p[i]=dx(d1-d2)=2dy.x[i]+2dy-2dx.y[i]+2dx.b-dx
=2dy.x[i]-2dx.y[i]+2dy+dx(2b-1)
Hay p[i]=2dy.x[i]-2dx.y[i]+c với c=2dy+dx(2b-1) 	(1)
thay i=1 ta có p[1]=2dy.x1-2dy.y1+c=2dy-dx
Nếu p[i]<0 nghĩa là y[i] gần đường thẳng hơn y[i]+1 và ta chọn y[i+1]=y[i] ngược lại ta chọn y[i+1]=y[i]+1
Công thức (1) có thể được giản lược bằng cách liên hệ với điểm 
(x[i+1],y[i+1]) tiếp theo, khi đó p[i+1]=2dy.x[i+1]-2dx.y[i+1]+c (2)
Trừ (2) cho (1) ta có :
p[i+1]-p[i]=2dy(x[i+1]-x[i])-2dx(y[i+1]-y[i]) mà x[i+1]=x[i]+1 nên
p[i+1]=p[i]+2dy-2dx(y[i+1]-y[i])
Mà nếu p[i]<0 thì y[i+1] tiếp theo sẽ được chọn là y[i], nghĩa là y[i+1]=y[i] nên p[i+1]=p[i]+2dy=p[i]+const1 với const1=2dy ngược lại chọn y[i+1]=y[i]+1 nên p[i+1]=p[i]+2(dy-dx)=p[i]+const2 với const2=2(dy-dx)
Và thuật toán vẽ đường thẳng của Presenham trong trường hợp hệ số góc nằm trong khoảng (0,1] như sau :
1. Nếu x1>x2 Thì ta hoán vị 2 điểm (x1,y1) và (x2,y2)
2. Đặt dx:=Abs(x2-x1); dy:=Abs(y2-y1);
 p:=2*dy-dx; const1:=2*dy; const2:=2*(dy-dx);
3. Đặt x:=x1; y:=y1; 
4. vẽ điểm(x,y);
5. Tăng x lên 1 đơn vị
6. Nếu p<0 Thì p:=p+const1 và giữ nguyên y
 ngược lại p:=p+const2 va tăng y lên 1 đơn vị;
7. Kiểm tra xem x còn <= x2 không nếu còn quay lên bước 4 ngược lại kết thúc
8. Kết thúc
Và thủ tục vẽ đường thẳng là :
Procedure Line_(x1,y1,x2,y2 : Integer);
Var
 x,y,tg,dx,dy,const1,const2,p : Integer;
 mau : Byte;
Begin
 If x1>x2 Then
 Begin
 tg:=x1; x1:=x2; x2:=tg; 
 tg:=y1; y1:=y2; y2:=tg;
 End;
 dx:=Abs(x2-x1); dy:=Abs(y2-y1);
 p:=2*dy-dx; const1:=2*dy;
 const2:=2*(dy-dx);
 mau:=GetColor;
 x:=x1; y:=y1;
 While x<=x2 Do
 Begin
 Putpixel(x,y,mau);
 Inc(x);
 If p<0 Then p:=p+const1
 Else
 Begin Inc(y); p:=p+const2; End;
 End;
End;
Bài tập :
1. Vẽ sơ đồ khối minh hoạ thuật toán vẽ đoạn thẳng của Bresenham
2. Hoàn thiện chương trình vẽ đoạn thẳng theo thuật toán của Bresenham trong tất cả các trường hợp trường hợp 
II. VẼ ĐƯỜNG TRÒN :
Để vẽ đường tròn chúng ta cũng phải tiến hành chọn những điểm có toạ độ nguyên để vẽ mà điểm đó nằm gần đường tròn thực nhất
Giả sử đường tròn cần phải vẽ có phương trình là x2+y2=R2, ở đây để đơn giản ta xét tâm của đường tròn là tại gốc toạ độ sau đó để vẽ đường tròn ta chi cần tịnh tiến theo vector (x0,y0) là tâm
Có thể tham số hoá chương trình trên thành x=R*cos(T); y=R*sin(T)
với 0<=T<=2*pi
Như vậy ta có thể vẽ đường tròn bằng cách cho góc T chạy từ 0 cho đến 2*pi với bước tăng là 1/R để lấy x:=Round(R*cos(T)) y:=Round(R*sin(T)) và vẽ điểm (x,y) nhưng làm như vậy lại phải tính sin và cos và do đó chương trình sẽ không chạy nhanh nên ta sẽ cải tiến bằng các phương pháp sau :
1. Vẽ đường tròn bằng phương pháp xấp xỉ :
như ta biết x=R*cos(T); y=R*sin(T), lấy đạo hàm theo T ta có :
x'=-R*sin(T)=-y; y'=R*cos(T)=x 	(1)
cho T chạy từ 0 đến 2*pi với bước là h=1/R thì điểm thứ i sẽ có toạ độ là
x[ih]=R*cos(ih); y[ih]=R*sin(ih)
Theo 1 ta có :
-y[ih]=x'[ih] bằng đạo hàm trái tại điểm T=ih xấp xỉ (x[(i+1)h]-x[ih])/h (h càng nhỏ thì độ chính xác càng lớn), nên -h.y[ih]=x[(i+1)h]-x[ih] =>
x[(i+1)h]=x[ih]-h.y[ih] 	(2) 
Và x[(i+1)h]=y'[(i+1)h] bằng đạo hàm phải tại điểm T=(i+1)h xấp xỉ (y[ih]-y[(i+1)h])/-h (h càng nhỏ thì độ chính xác càng lớn), nên
-h.x[(i+1)h]=y[ih]-y[(i+1)h] => y[(i+1)h]=h.x[(i+1)h]+y[ih] 	 (3)
Từ (2) và (3) ta có
x[(i+1)h]=x[ih]-h.y[ih] 
y[(i+1)h]=h.x[(i+1)h]+y[ih] 
Với giá trị ban đầu khi T=0 là x0=R.cos(0)=R, y0:=R.sin(0)=0;
Ta có thể viết gọn lại với bước h=1/R :
x[i+1]=x[i]-hy.[i]
y[i+1]=h.x[i+1]+y[i]
Với giá trị ban đầu là x0=R, y0=0
Và thủ tục để vẽ đường tròn theo phương pháp này là :
Procedure Circle_(x1,y1,r : Integer);
Var
 mau : Byte;
 d: LongInt;
 x,y,h: Real;
Begin
 mau:=GetColor;
 h:=1/r; d:=0;
 x:=r; y:=0;
 Repeat
 Putpixel(x1+Round(x),y1+Round(y),mau);
 x:=x-h*y;
 y:=h*x+y;
 Inc(d);
 Until d*h>2*pi;
End;
2. Thuật toán vẽ đường tròn của Bresenham
Thuật toán trên vẽ đường tròn vẫn còn chậm vì phải tính toán liên quan với các số thực. Tương tự như với đường thẳng, thuật toán vẽ đường tròn của Bresanham chỉ thực hiện trên các số nguyên nên chạy nhanh hơn rất nhiều :
Cũng như trên ta xét tâm ở gốc toạ độ, với chú ý rằng cứ một điểm thuộc đường tròn thì bằng cách đối xứng qua các trục toạ độ, qua các đường chéo ta có thể xác định được 8 điểm thuộc đường tròn (như hình vẽ). Do đó ta chỉ cần xét 1/8 cung tròn bắt đầu từ x=0,y=R và kết thúc khi x=y.
Ta viết lại phương trình đường tròn thành y2=R2-x2
Giả sử điểm (x[i], y[i]) là điểm thuộc đường tròn, vị trí của điểm kế tiếp cần vẽ sẽ là (x[i]+1,y[i]) hoặc (x[i]+1,y[i]-1) và giá trị đúng của y sẽ được xét bằng phương trình y2=R2-(x[i+1])2
Ta xét 2 độ dài : 	d1=(y[i])2-y2=(y[i])2-R2+(x[i]+1)2
Và 	d2=y2-(y[i]-1)2=R2-(x[i]+1)2-(y[i]-1)2
Do đó hiệu giữa d1 và d2 là : p[i]=d1-d2=2(x[i]+1)2+(y[i])2+(y[i]-1)2-2R2
Cũng giống như đoạn thẳng nếu p[i] âm ta chọn y[i], 
ngược lại chọn y[i]-1
Tăng i lên 1 đơn vị ta có
p[i+1]=d1-d2=2(x[i+1]+1)2+(y[i+1])2+(y[i+1]-1)2-2R2
Nên p[i+1]=p[i]+4x[i]+6+2((y[i+1])2-(y[i])2)-2(y[i+1]-y[i])
mà y[i+1] hoặc bằng y[i] hoặc bằng y[i]-1
Nếu y[i+1]=y[i] thì p[i+1]=p[i]+4x[i]+6
Nếu y[i+1]=y[i]-1 thì p[i+1]=p[i]+4(x[i]-y[i])+10
Có thể tóm tắt các bước như sau :
1. Đặt x:=0; y:=r; p:=3-2*r;
2. Nếu x>y kết thúc nếu không thực hiện bước 3
3. Vẽ 8 điểm (x, y); (-x, y); (x, -y); (-x, -y); (y, x); (-y, x); (y, -x); (-y, -x);
4. Nếu p<0 thì p:=p+4*x+6
 Ngươc lại p:=p+4*(x-y)+10; và giảm y 1 đơn vị
5. Tăng x lên 1 đơn vị
6. Quay lại bước 2
Và thủ tục để vẽ đường tròn theo thuật toán Bresenham là :
Procedure Circle_(x1,y1,r : Integer);
Var
 mau : Byte;
 x,y,p: Integer;
 Procedure Put_Pixels(x,y: Integer);
 Begin
 Putpixel(x1+x,y1+y,mau);
 Putpixel(x1-x,y1+y,mau);
 Putpixel(x1+x,y1-y,mau);
 Putpixel(x1-x,y1-y,mau);
 Putpixel(x1+y,y1+x,mau);
 Putpixel(x1-y,y1+x,mau);
 Putpixel(x1+y,y1-x,mau);
 Putpixel(x1-y,y1-x,mau);
 End;
Begin
 mau:=GetColor;
 x:=0; y:=r; p:=3-2*r;
 While x<=y Do
 Begin
 Put_pixels(x,y);
 If p<0 Then p:=p+4*x+6
 Else
 Begin
 p:=p+4*(x-y)+10;
 Dec(y);
 End;
 Inc(x);
 End;
End;
Bài tập :
1. Lập chương trình vẽ đường tròn theo phương pháp xấp xỉ
2. Lập thiện chương trình vẽ đường tròn theo thuật toán của Bresenham
3. Lập chương trình vẽ đường tròn theo tham số
4. Lập chương trình vẽ Elip theo tham số
5. Tương tự như vẽ đường tròn lập chương trình vẽ Elip theo thuật toán của Bresenham