Giáo viên phụ trách môn học: Nguyễn Hoài Anh Khoa Công nghệ thông tin - HVKTQS
(cid:1) Thuật toán vẽ đường thẳng (cid:1) Thuật toán vẽ đường tròn (cid:1) Thuật toán vẽ Elip
(cid:1) Ý tưởng
(cid:1) Giả sử tọa độ nguyên các điểm sau khi xấp xỉ đối
tượng thực lần lượt là (xi,yi) với i=0,... vẽ các điểm này chúng ta sẽ được một đường xấp xỉ của đối này chúng ta sẽ được một đường xấp xỉ của đối tượng cần vẽ.
(cid:1) Giả sử đã biết được (xi,yi) là tọa độ nguyên xác
định ở bước thứ i, điểm nguyên tiếp theo (xi+1,yi+1) sẽ được xác định như thế nào?
(cid:1) Ý tưởng
(cid:1) Nhận xét
▪ Để đối tượng hiển thị trên lưới nguyên được liền nét, các điểm mà (xi+1,yi+1) có thể chọn chỉ là một trong tám điểm điểm mà (xi+1,yi+1) có thể chọn chỉ là một trong tám điểm được đánh số từ 1 đến 8
▪ Giải thích: điểm đen chính là (xi,yi). ▪ Nói cách khác : (xi+1,yi+1) = (xi+/-1,yi+/-1).
(cid:1) Thuật toán
(cid:1) Giả thiết 0
định được ở bước thứ i
(cid:1) thì điểm cần chọn (xi+1,yi+1) ở bước thứ i+1 sẽ là một
trong hai trường hợp 1 hoặc 2
(cid:1) Tại bước i+1 ta xác định được: xi+1 = xi+1 và yi+1 = yi hoặc yi+1. Vấn đề còn lại là cách chọn một trong hai điểm trên như thế nào để có thể tối ưu về mặt tốc độ.
(cid:1) Thuật toán DDA (Digital Differential Analyzer)
(cid:1) Việc quyết định chọn yi+1 là yi hay yi+1, dựa vào
phương trình của đoạn thẳng y=mx+b
(cid:1) Tính y rồi làm tròn số và gán giá trị đó cho yi+1. i+1 (cid:1) Như vậy
yi+1 = Round(m xi+1 + b) = Round(m (xi+1)+b)
Sơ đồ khối thuật toán DDA
Cài đặt thuật toán DDA
Procedure DDA ( x1, y1, x2, y2, color : integer ); Var dx, dy, step : integer; X_inc, y_inc , x, y : real ; Begin dx:=x2-x1;
dy:=y2-y1;
if abs(dx)>abs(dy) then steps:=abs(dx) else steps:=abs(dy); x_inc:=dx/steps; x_inc:=dx/steps; y_inc:=dy/steps; x:=x1; y:=y1;
putpixel(round(x),round(y), color); for k:=1 to steps do begin
x:=x+x_inc; y:=y+y_inc; putpi xel(round(x),round(y), color);
end;
end;
(cid:1) Thuật toán Bresenham
(cid:1) Đư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. thuật toán DDA.
(cid:1) 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.
Sơ đồ khối thuật toán Bresenham
Cài đặt thuật toán Bresenham
Procedure Bres_Line (x1,y1,x2,y2: integer); Var dx, dy, x, y, P, const1, const2 : integer; Begin
dx : = x2- x1; dy : = y2- y1; P : = 2*dy - dx; Const1 : = 2*dy ; const2: = 2*(dy - dx) ; x:= x1; y:=y1; Putpixel ( x, y, Color); while (x < x -2 ) do
begin begin
x : = x +1 ; if (P < 0) then P : = P + const1 else
begin y : = y+1 ; P : = P + const2
end ; putpixel (x, y, color) ;
end ;
End ;
(cid:1) Trong hệ tọa độ Decac. Phương trình đường
tròn có dạng: (cid:1) Với tâm O(0,0): x2 + y2 = R2. (cid:1) Với tâm C(xc,yc): (x-xc)2 + (y-yc)2 = R2 (cid:1) Với tâm C(x ,y ): (x-x )2 + (y-y )2 = R2
(cid:1) Trong hệ tọa độ cực
(cid:1) Do tính đối xứng của đường tròn C 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. giác thì ta vẽ được cả đường tròn.
(cid:1) Ý tưởng
Cài đặt thuật toán vẽ đường tròn
Procedure Circle (xc, yc, R : integer) ; Var x, y : integer ; Procedure DOIXUNG; Begin
putpixel (xc + x , yc +y, color) ; putpixel (xc - x , yc + y, color) ; putpixel (xc + x , yc - y, color) ; putpixel (xc - x , yc- y, color) ; putpixel (xc + y , yc + x, color) ; putpixel (xc - y , yc + x, color) ; putpixel (xc - y , yc + x, color) ; putpixel (xc + y , yc - x, color) ; putpixel (xc - y , yc - x, color) ;
End ; Begin
For x : = 0 to round(R*Sqrt(2)/2) do Begin
y : = round(Sqrt(R*R - x*x)) ; DOIXUNG;
End ;
End ;
(cid:1) Thuật toán MidPoint (xét điểm giữa)
(cid:1) 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)
(cid:1) với điểm MidPoint là trung điểm của S và P theo (cid:1) với điểm MidPoint là trung điểm của S và P theo
nguyên tắ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.
(cid:1) Thuật toán MidPoint (xét điểm giữa)
Sơ đồ khối thuật toán MidPoint
Cài đặt thuật toán MidPoint
Procedure DTR(xc, yc, r, mau : integer);
var x, y, p : integer ; begin
x:=0 ; y:=r; p:=1 - r; while ( y > x) do
begin
doi_xung; if (p<0) then p:=p+2*x+3 else begin else begin
p:=p+2*(x-y)+5 ; y:=y-1;
end;
x:=x+1; end; {while}
end;
(cid:1) Thuật toán Bresenham
(cid:1) Tương tự thuật toán vẽ đường thẳng, 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 1 trong 2 có thể tính được bằng cách xác định 1 trong 2 pixel gần nhất với đường tròn thực hơn trong mỗi bước
Cài đặt thuật toán Bresenham
Procedure DTR _BRES (xc,yc,r,mau : integer);
var x ,y ,p :integer; begin
x :=0 ; y :=r;
p := 3 – 2 * r ;
while (x begin doi_ xung ;
doi_ xung ;
if (p <0) then p := p + 4* x + 6
else begin p := p + 4 * (x -y ) + 1 0 ;
y := y -1 ; end ; x :=x + 1 ;
end ;{w h ile} end ; (cid:1) Xét elip có tâm tại gốc tọa độ, bán kính trục X là 2 2 2 2 (cid:1) Do elip đối xứng nên chỉ cần vẽ cung ¼, các cung (cid:1) Triển khai các thuật toán trên ngôn ngữ lập trìnha, bán kính trụcY là b. Phương trình elip có dạng:
=
=
1
1
x
a
+ y
+
b
(cid:2) b2x2+a2y2 – a2b2 =0 = F(x,y)
còn lại lấy đối xứng qua các trục X vàY.
và môi trường đồ họa phù hợp
