ĐỒ HỌA RASTER
ĐỒ HỌA RASTER
CÁC THUẬT TOÁN
CÁC THUẬT TOÁN
VẼ ĐƯỜNG THẲNG
VẼ ĐƯỜNG THẲNG
Giảng viên : Bùi Tiến Lên
Trang
Trang
2
2
Bài toán vẽ đường thẳng
Bài toán vẽ đường thẳng
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
( X 1 , Y 1 )
( X 2 , Y 2 )
Baứi toaựn veừ ủửụứng thaỳng
Baứi toaựn veừ ủửụứng thaỳng
Trang
Trang
3
3
Trang
Trang
4
4
Một số công thức cơ bản của đường thẳng
Một số công thức cơ bản của đường thẳng

2
, Y
2
)
Trang
Trang
5
5
Phân loại đường thẳng
Phân loại đường thẳng
Tăng chậm Tăng nhanh
Giảm chậm Giảm nhanh
Trang
Trang
6
6
Giaỷi quyeỏt
Giaỷi quyeỏt
Thuaọt toaựn DDA
Thuaọt toaựn Bresenham
Thuaät toaùn DDA
Thuaät toaùn DDA
Thuaät toaùn DDA
Thuaät toaùn DDA
Trang
Trang
8
8
Trang
Trang

, y
cũ
)
(x
i+1
, y
mới
)
y đầu là Y
1
y
mới
= y
cũ
+ m
Trang
Trang
11
11
Trường hợp 2
Trường hợp 2
Đoạn thẳng tăng nhanh và điểm đầu ở bên dưới.
Thuật toán
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 yi < Y2
yi+1 = yi + 1
x = yi+1/m – b/m

12
YY
XX
k
−
−
=
Thuaät toaùn Bresenham
Thuaät toaùn Bresenham
Trang
Trang
14
14
Trường hợp 1
Trường hợp 1
Dự đoán điểm sáng thứ i+1
i A
B
Trang
Trang
15
15
Trửụứng hụùp 1
Trửụứng hụùp 1
Xaõy dửùng bieỏn pi
y = m(xi+1) + b
d1 = y - yi
d2 = yi + 1 - y
pi = x(d1 - d2)
i A

+ 2∆xY
1
– 2∆yX
1
+ 2∆y – ∆x
Trang
Trang
17
17
Trường hợp 1
Trường hợp 1
Đoạn thẳng tăng chậm và điểm đầu ở bên trái.
Thuật toán
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 xi < X2
pi = …
pi < 0
xi+1 = xi + 1
yi+1 = yi
pi >= 0
xi+1 = xi + 1
yi+1 = yi + 1
Trang
Trang
18
18
Trửụứng hụùp 1

20
20
Trửụứng hụùp 2
Trửụứng hụùp 2
i
A B
x
i
x
i
+1
y
i
+1
y
i
x
C
d
2
d
1
( )
21i
i2
i1
i
i
ddyp
x1xd

+ 2∆x
p
i
>= 0 :
p
i+1
= pi + 2∆x - 2∆y
Trang
Trang
22
22
Trường hợp 2
Trường hợp 2
Thuật toán
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 xi < X2
pi < 0
xi+1 = xi
yi+1 = yi + 1
pi >= 0
xi+1 = xi + 1
yi+1 = yi + 1