Đ H A RASTER Đ H A RASTER
Ồ Ọ Ồ Ọ
CÁC THU T TOÁN Ậ CÁC THU T TOÁN Ậ NG TH NG V ĐẼV ĐẼ ƯƯ NG TH NG
Ờ Ờ
Ẳ Ẳ
Gi ng viên : Bùi Ti n Lên ế ả
ng th ng Bài toán v ẽ đưđư ng th ng Bài toán v ẽ
ờ ờ
ẳ ẳ
Input
(X1, Y1) (X2, Y2)
Output
“n m trên” ể ằ {(x1, y1) (x2, y2) … (xn, yn)} là nh ng ữ đi m sáng
( X 2 , Y 2 )
( X 1 , Y 1 )
đư ng th ng ẳ ờ
Trang 22 Trang
ng th ng Bài toán v ẽ đưđư ng th ng Bài toán v ẽ
ờ ờ
ẳ ẳ
Trang 33 Trang
M t s công th c c M t s công th c c
ộ ố ộ ố
ả ủ đưđư ng th ng ng th ng b n c a ờ ứ ơơ b n c a ờ ả ủ ứ
ẳ ẳ
(X2, Y2)
= y
= - x
2
D - = = m D - y x
- + bmx b y m m Y Y 2 1 X X 1 = Yb mX 1 1
(X1, Y1)
Trang 44 Trang
ng th ng Phân lo i ạ đưđư ng th ng Phân lo i ạ
ờ ờ
ẳ ẳ
Tăng nhanh Tăng ch mậ
Gi m ch m Gi m nhanh ả ậ ả
Trang 55 Trang
Gi Gi
ả ả
i quy t ế i quy t ế
Thu t toán DDA Thu t toán Bresenham ậ ậ
Trang 66 Trang
ậ
ậThu t toán DDA Thu t toán DDA
ậ
ậThu t toán DDA Thu t toán DDA
Trang 88 Trang
ợng h p 1 TrTrưư ng h p 1 ợ
ờ ờ
bên trái. ăng ch m và ậ đi m ể đ u ầ ở ạ ẳ
đi m ể đ u tiên ầ Đo n th ng t Thu t toán ậ Bư c 1ớ Xác đ nh 1
2 3 ị x1 = X1 y1 = Y1 ị ữ đi m ti p theo ể ế n…
i < X2 xi+1 = xi + 1 y = mxi+1 + b yi+1 = Round(y)
Bư c 2ớ Xác đ nh nh ng L p xặ
Trang 99 Trang
ợng h p 1 TrTrưư ng h p 1 ợ
ờ ờ
ả ế
C i ti n tính y Xét hai đi m sáng liên ti p nhau ể ế
i (xi, ycũ)
i+1 (xi+1, ym iớ )
Công th c liên h ứ ệ
ầ
y đ u là Y 1 ym i ớ = ycũ + m
Trang 1010 Trang
ợng h p 2 TrTrưư ng h p 2 ợ
ờ ờ
bên d ăng nhanh và đi m ể đ u ầ ở ư i.ớ ẳ ạ
đi m ể đ u tiên ầ Đo n th ng t Thu t toán ậ Bư c 1ớ Xác đ nh
ị x1 = X1 y1 = Y1 ị ữ đi m ti p theo ế ể
i < Y2 yi+1 = yi + 1 x = yi+1/m – b/m xi+1 = Round(x)
Bư c 2ớ Xác đ nh nh ng L p yặ
Trang 1111 Trang
ợng h p 2 TrTrưư ng h p 2 ợ
ờ ờ
ả ế
C i ti n tính x Xét hai đi m sáng liên ti p nhau ế ể
i (xc, yi)
i+1 (xm iớ , yi+1)
Công th c liên h ứ ệ
=
k
-
X 2 Y 2
X 1 Y 1
-
ầ
x đ u là X 1 xm i ớ = xcũ + k
Trang 1212 Trang
ậ
ậThu t toán Bresenham Thu t toán Bresenham
ợng h p 1 TrTrưư ng h p 1 ợ
ờ ờ
D ự đoán đi m sáng th i+1 ứ ể
B
A i
Trang 1414 Trang
ợng h p 1 TrTrưư ng h p 1 ợ
ờ ờ
Xây d ngự bi n pế i
B yi+1
d2
y
C
d1 y = m(xi+1) + b d1 = y - yi d2 = yi + 1 - y pi = D x(d1 - d2)
yi i A
xi xi+1
Trang 1515 Trang
ợng h p 1 TrTrưư ng h p 1 ợ
ờ ờ
Cách tính pi
pi = 2D yxi – 2D xyi + 2D xY1 – 2D yX1 + 2D y – D x
Trang 1616 Trang
ợng h p 1 TrTrưư ng h p 1 ợ
ờ ờ
bên trái.
ăng ch m và ậ
đi m ể đ u
ầ ở
ạ
ẳ
Đo n th ng t Thu t toán ậ Bư c 1ớ Xác đ nh
đi m ể đ u tiên ầ
ữ đi m ti p theo
ế
ể
ị x1 = X1 y1 = Y1 Bư c 2ớ Xác đ nh nh ng ị L p xặ
i < X2
pi = … pi < 0
xi+1 = xi + 1 yi+1 = yi
pi >= 0
xi+1 = xi + 1 yi+1 = yi + 1
Trang 1717 Trang
ợng h p 1 TrTrưư ng h p 1 ợ
ờ ờ
Cách tính pi c i ti n ả ế
p1 = 2D y - D x pi < 0 :
pi+1 = pi + 2D y
pi >= 0 :
pi+1 = pi + 2D y - 2D x
Trang 1818 Trang
ợng h p 2 TrTrưư ng h p 2 ợ
ờ ờ
D ự đoán đi m sáng th i+1 ứ ể
B A
i
Trang 1919 Trang
ợng h p 2 TrTrưư ng h p 2 ợ
ờ ờ
C Xaây A B yi+1
= - x
b m
= - d2 d1
=
)
D= - döïng bieán p i + 1y i m xx i -+ x1x i ( ddy 1 2 d 1 d 2 p i
yi i
x xi xi+1
Trang 2020 Trang
ợng h p 2 TrTrưư ng h p 2 ợ
ờ ờ
Cách tính pi
p1 = 2D x - D y pi < 0 :
pi+1 = pi + 2D x
pi >= 0 :
pi+1 = pi + 2D x - 2D y
Trang 2121 Trang
ợng h p 2 TrTrưư ng h p 2 ợ
ờ ờ
Thu t toán ậ Bư c 1ớ Xác đ nh đi m ể đ u tiên ầ
ữ đi m ti p theo ế ể ị x1 = X1 y1 = Y1 ị
i < X2 pi < 0
Bư c 2ớ Xác đ nh nh ng L p xặ
xi+1 = xi yi+1 = yi + 1
pi >= 0
xi+1 = xi + 1 yi+1 = yi + 1
