ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 1/22
C
C
a
a
ù
ù
c
ct
t
h
h
u
u
a
a
ä
ä
t
tt
t
o
o
a

a
ã
ã
n
nn
n
h
h
a
a
ä
ä
p
p
• Giả sử tọa độ các điểm nguyên sau khi xấp xỉ đối
tượng thực lần lượt là
( )
,...0,, =iyx
ii
. Đây là các điểm
nguyên sẽ được hiển thò trên màn hình.
• Bài toán đặt ra là nếu biết được
( )
ii
yx ,
là tọa độ
nguyên xác đònh ở bước thứ i, điểm nguyên tiếp theo

xét tới vấn đề tối ưu tốc độ.
1
23
876
5
4
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 2/22
T
T
h
h
u
u
a
a
ä
ä
t
tt
t
o
o
a
a
ù
ù

a
a
ú
ú
n
n
g
g
• Xét đoạn thẳng có hệ số góc
10 << m
và
0>Dx
.
• Với các đoạn thẳng dạng này, nếu
( )
ii
yx ,
là điểm
đã xác đònh được ở bước thứ i (điểm màu đen) thì
điểm cần chọn
( )
11
,
++ ii
yx
ở bước thứ (i+1) sẽ là một
trong hai trường hợp như hình vẽ sau :
{ }



i
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 3/22
T
T
h
h
u
u
a
a
ä
ä
t
tt
t
o
o
a
a
ù
ù
n
nD

f
f
f
e
e
r
r
e
e
n
n
t
t
i
i
a
a
l
lA
A
n
n
a
a
l
l
y

1+i
y
sẽ là giá trò sau khi làm
tròn giá trò tung độ y.
• Như vậy :
( )
( )
yRoundy
bxmy
i
i
=
++=
+1
1
• Nếu tính trực tiếp giá trò thực y ở mỗi bước từ
phương trình
bmxy +=
thì phải cần một phép toán
nhân và một phép toán cộng số thực. Để cải thiện
tốc độ, người ta tính giá trò thực của y ở mỗi bước
theo cách sau để khử phép tính nhân trên số thực :
• Nhận xét rằng :
( )
bxmbmxy
iisau
++=+=
+
1
1

putpixel(x, Round(y),c);
End
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 5/22
• Ví dụ : Cho A(12, 20) và B(22, 27), ta có m= 0.7
i
i
x
x
i
i
y
y
i
i
y
y
0
0
1
1
2
2
2
2
0
0
2
2
0

2
1
1
.
.
4
4
3
3
1
1
5
5
2
2
2
2
2
2
2
2
.
.
1
1
4
4
1
1
6

1
1
1
0
0
2
2
2
2
2
2
7
7
• Cài đặt minh họa thuật toán DDA
#define Round(a) int(a+0.5)
int Color = GREEN;
void LineDDA (int x1, int y1, int x2, int y2)
{
int x = x1;
float y = y1;
float m = float(y2-y1)/(x2-x1);
putpixel(x, Round(y), Color);
for(int i=x1; i<x2; i++)
{
x++;
y +=m;
putpixel(x, Round(y), Color);
}
} // LineDDA
ĐỒ HỌA MÁY TÍNH

r
e
e
s
s
e
e
n
n
h
h
a
a
m
m
• Gọi
( )
yx
i
,1+
là điểm thuộc đoạn thẳng. Ta có:
( )
bxmy
i
++= 1
.
• Đặt
( )
yyd
yyd

0
21
<− dd
, ta sẽ chọn điểm S, tức là
ii
yy =
+1
.
♦ Ngược lại, nếu
0
21
≥− dd
, ta sẽ chọn điểm P, tức là
1
1
+=
+ ii
yy
• Xét
( ) ( )
122
21
−−=−=
ii
yyDxddDxp
( )( )
[ ]
1212 −−++=⇒
iii
ybxmDxp

, với
( )
DxbDyc 122 −+=
.
• Nhận xét rằng nếu tại bước thứ i ta xác đònh được
dấu của
i
p
thì xem như ta xác đònh được điểm cần
chọn ở bước (i+1).
• Ta có :
( ) ( )
cDxyDyxcDxyDyxpp
iiiiii
+−−+−=−
+++
2222
111
( ) ( )
iiiiii
yyDxxxDypp −−−=−⇔
+++ 111
22
( )
1 do ,22
111
+=−−=−⇔
+++ iiiiii
xxyyDxDypp
• Từ đây ta có thể suy ra cách tính

1
−+=
+
, do
ta chọn
1
1
+=
+ ii
yy
.
• Giá trò
0
p
được tính từ điểm vẽ đầu tiên
( )
00
, yx
theo công thức :
( )
DxbDyDxyDyxcDxyDyxp 1222222
00000
−−+−=+−=
• Do
( )
00
, yx
là điểm nguyên thuộc về đoạn thẳng
nên ta có
bx

End