ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán tô màu 1/16
C
CC
C
C
CC
C
a
aa
a
a
aa
a
ù
ùù
ù
ù
ùù
ù
c
cc
c
c
cc
c
ä
t
tt
t
t
tt
t
t
tt
t
t
tt
t
o
oo
o
o
oo
o
a
aa
a
a
aa

o
â
ââ
â
â
ââ
â
m
mm
m
m
mm
m
a
aa
a
a
aa
a
ø
øø
ø
ø
øø

• Có hai dạng vùng tô thường gặp : tô bằng một màu
thuần nhất (solid fill) và tô theo một mẫu tô (fill-
pattern) nào đó.
• Việc tô màu thường được chia làm hai công đoạn :
♦ Xác đònh vò trí các điểm cần tô màu.
♦ Quyết đònh tô các điểm trên bằng màu nào. Công đoạn
này thực sự phức tạp khi ta cần tô theo một mẫu tô nào
đó chứ không phải tô thuần một màu.
• Có hai cách tiếp cận chính : tô màu theo dòng quét
và tô màu dựa theo đường biên.
♦ Phương pháp tô màu dựa theo dòng quét sẽ xác đònh
phần giao của các dòng quét kế tiếp nhau với đường biên
của vùng tô, sau đó sẽ tiến hành tô màu các điểm thuộc
phần giao này. Cách này thường được dùng để tô màu đa
giác, đường tròn, ellipse và một số đường cong đơn giản
khác.
♦ Phương pháp tô màu dựa theo đường biên sẽ bắt đầu từ
một điểm bên trong vùng tô và từ đó loang dần ra cho
đến khi gặp điểm biên. Cách này thường được dùng cho
các dạng đường biên phức tạp.
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán tô màu 2/16
T
TT
T
T
TT
T
h
hht
tt
t
t
tt
t
o
oo
o
o
oo
o
a
aa
a
a
aa
a
ù
ùù
ù
ù
ùù
ù
n
nnt
tt
t
t
tt
t
h
hh
h
h
hh
h
e
ee
e
e
ee
e
o
oo
o
o
oo
o
g
g
gg
g
q
qq
q
q
qq
q
u
uu
u
u
uu
u
e
ee
e
e
ee
e
ù
ùù

t
t
a
a
é
é
t
tc
c
a
a
ù
ù
c
cb
b
ư
ư
ơ
ơ
ù
ù
c
c

a
a
ä
ä
t
tt
t
o
o
a
a
ù
ù
n
n
• Tìm
top
y
,
bottom
y
lần lượt là giá trò lớn nhất, nhỏ
nhất của tập các tung độ của các đỉnh của đa giác đã
cho:
(){}
Pyxyy
iiitop

y
=
lần lượt
được giới hạn bởi các cặp
()()( )
1222110
,, ,,,,
+kk
x
x
x
x
x
x
.
O
y
0123
x
y
bottom
y
top
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán tô màu 3/16
C
C
a
a
ù

tr
r
a
a
• Hạn chế được số cạnh cần tìm giao điểm ứng với mỗi
dòng quét vì ứng với mỗi dòng quét, không phải lúc
nào tất cả các cạnh của đa giác cũng tham gia cắt
dòng quét.
• Xác đònh nhanh hoành độ giao điểm vì nếu lặp lại
thao tác tìm giao điểm của cạnh đa giác với mỗi
dòng quét bằng cách giải hệ phương trình sẽ tốn rất
nhiều thời gian.
• Giải quyết trường hợp số giao điểm ứng với trường
hợp dòng quét đi ngang qua đỉnh : Nếu số giao điểm
tìm được giữa các cạnh đa giác và dòng quét là lẻ thì
việc nhóm từng cặp giao điểm kế tiếp nhau để hình
thành các đoạn tô có thể sẽ không chính xác. Điều
này chỉ xảy ra khi dòng quét đi ngang qua các đỉnh
của đa giác.
• Ngoài ra, việc tìm giao điểm của dòng quét với các
cạnh nằm ngang là một trường hợp đặc biệt cần
phải có cách xử lí thích hợp
y=k
1
y=k
2
0 1,2

á
u
ut
t
r
r
u
u
ù
ù
c
cd
d
ư
ư
õ
õl
l
i
i
e

t
o
o
a
a
ù
ù
n
n
• Danh sách các cạnh (Edge Table – ET) : chứa toàn
bộ các cạnh của đa giác (đã loại đi các cạnh nằm
ngang) được sắp theo thứ tự tăng dần của
Min
y
.
• Danh sách các cạnh kích hoạt (Active Edge Table –
AET) : chứa các cạnh của đa giác có thể cắt ứng với
dòng quét hiện hành, các cạnh này được sắp theo
thứ tự tăng dần của hoành độ giao điểm giữa cạnh
và dòng quét.
• Khi dòng quét đi từ bottom đến top, các cạnh thỏa
điều kiện sẽ được di chuyển từ ET sang AET:
♦ Khi dòng quét
k
y
=
bắt đầu cắt một cạnh, nghóa là
Min
yk ≥
, cạnh này sẽ được chuyển từ ET sang AET.

y=k
x
k
x
k+1