Trong giải thuật tô màu vùng đối tượng và trong những quá trình xử lý đồ họa khác, chúng
ta thường xuyên cần phải xác định vùng nằm bên trong đối tượng. Cho đến hiện tại thì
chúng ta cũng chỉ bàn đến việc tô màu cho các đa giác có hình dạng chuẩn. Tuy nhiên
trong hình học cơ bản, đa giác thường được định nghĩa theo dạng không có sự tự giao nhau
giữa các cạnh. Ví dụ như đa giác chỉ đơn giản là các tam giác, tứ giác, lục giác hay bát
giác. Các cạnh thành phần của các đối tương này chỉ giao nhau tại các đỉnh của đa giác và
không có điểm chung nào nữa. Sự nhận biết các vùng nằm bên trong các đa giác chuẩn là
một quá trình không mấy khó khăn. Nhưng trong phần lớn các ứng dụng đồ họa, chúng ta
có thể chỉ ra dãy liên tục các đỉnh của vùng tô màu kể cả các đỉnh là giao điểm của các
cạnh và như thế rất khó xác định đâu là các điểm nằm bên trong và đâu là các điểm nằm
bên ngoài đối tượng. Các phần mềm đồ họa thường dùng nguyên tắc chẵn lẻ hay nguyên
tắc hệ số xoắn khác không để nhận biết các vùng bên trong này.
Chúng ta sẽ sử dụng nguyên tắc tính chẳn lẽ bằng nguyên lý vẽ một đường thẳng từ
một điểm bất kỳ P đến một điểm cách xa nằm bên ngoài tọa độ đối tượng bằng cách đếm
số cạnh cắt ngang đường quét. Nếu số cạnh cắt ngang đường quét là số lẻ thì P là điểm
nằm bên trong, ngược lại thì P là điểm nằm bên ngoài. Để có thể đếm số cạnh chính xác,
chúng ta phải đảm bảo rằng đường thẳng mà chúng ta chọn không được đi qua bất kỳ đỉnh
nào của đa giác. Giải thuật tô màu theo phương pháp đường thẳng quét nói trên là một ví
dụ của giải thuật tô màu theo phương pháp chẵn lẻ.
117 trang |
Chia sẻ: netpro | Lượt xem: 1603 | Lượt tải: 3
Bạn đang xem trước 20 trang tài liệu Luận văn Đồ họa trong máy tính, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
1, 1
- Laàn thöù ba cuõng veõ laàn löôït nhöng moãi laàn veõ boû qua hai ñænh 1, 4, 7,…, N-2, 1
Cöù nhö theá, quaù trình ñöôïc laëp laïi vôùi (N-1)/2 laàn thì keát thuùc.
Cung C
Trong ñoà hoïa maùy tính, vôùi söï trôï giuùp cuûa maùy tính vaø caùc giaûi thuaät ñeä quy, thöïc teá
chuùng ta ñaõ taïo ra ñöôïc nhöõng hoï ñöôøng cong gaây ra söï loâi cuoán raát ñaëc bieät nhôø hieäu öùng
hình hoïc cuûa noù. Beân caïnh ñoù, vieäc xaây döïng caùc hoï ñöôøng cong naøy cuõng töông ñoái ñôn
giaûn vaø deã hieåu. Trong phaïm vi cuûa ñoà aùn thöïc taäp toát nghieäp naøy, chuùng ta seõ khaûo saùt hoï
ñöôøng cong C.
Ñöôøng cong C ñöôïc xaây döïng treân cô sôû thay theá moät ñoaïn thaúng baèng moät ñöôøng gaáp
khuùc taïo ra bôûi hai ñoaïn thaúng ngaén hôn hôïp vôùi nhau moät goùc laø π/2. Hai ñoaïn thaúng naøy
coù ñoä daøi baèng 1/√2 laàn ñoaïn thaúng caáp cha cuûa chuùng. Ñeã coù theå veõ ñöôïc caùc ñoaïn thaúng
caáp hai töø ñoaïn thaúng caáp moät, ta baét ñaàu ôû moät ñaàu ñoaïn thaúng caáp moät naøy veõ ñoaïn
thaúng caáp hai daøi baèng 1/√2 laàn ñoaïn thaúng caáp moät vaø hôïp vôùi ñoaïn thaúng caáp moät goùc
π/4, sau ñoù töø vò trí hieän haønh (ñaàu cuoái cuûa ñoaïn thaúng caáp hai thöù nhaát), ta veõ ñoaïn
thaúng thöù hai cuõng coù chieàu daøi töông töï vaø hôïp vôùi ñoaïn thaúng caáp hai vöaø veõ moät goùc -
(π/2). Cöù nhö theá töø vieäc thay theá 2 ñoaïn thaúng caáp n cho moãi ñoaïn thaúng caán n-1 ta ñöôïc
moät ñöôøng cong coù hình chöõ C raát ñeïp (soá caáp laø töø 15 trôû leân thì hình aûnh cung C hieän ra
raát roõ).
Cung Roàng
Töông töï nhö cung C, cung roàng laø vieäc thay theá moät ñoaïn thaúng cô sôû baèng hai ñoaïn
thaúng caáp con nhöng vieäc thay coù moät khaùc bieät ôû choã chieàu daøi cuûa ñoaïn thaúng thöø hai.
Luaän AÙn Toát Nghieäp Phaàn thuyeát minh
Sinh vieân thöïc hieän: Bieän Coâng Minh - Nguyeãn Xuaân Sôn Trang 40
Toùm Taét
Nhö vaäy, chuùng ta ñaõ laàn löôït tieán haønh khaûo saùt caùc cô sôû toaùn hoïc cuûa nhöõng ñoái töôïng
cô sôû trong ñoà hoïa maùy tính. Trong thöïc teá thì caùc ñöôøng gaáp khuùc, caùc ña giaùc, cung C,
cung roàng khoâng phaûi laø ñoái töôïng cô sôû cuûa ñoà hoïa, nhöng chuùng ta cuõng tieán haønh khaûo
saùt ôû ñaây bôûi vì chuùng laø nhöõng ñoái töôïng thöôøng xuyeân ñöôïc söû duïng ñeå taïo ra heä caùc
maãu veõ (patterns) laø heä maø chuùng ta seõ tieán haønh hieä thöïc baèng phaàn meàm.
Hôn nöõa, trong khi khaûo saùt lyù thuyeát, ñeã coù theå hieåu ñöôïc caën keõ baûn chaát cuûa caùc
giaûi thuaät, chuùng ta cuõng ñaõ tieán haønh khaûo saùt raát nhieàu caùc giaûi thuaät khaùc öùng vôùi töøng
loaïi ñoái töôïng moät, nhöng trong thöïc teá khi hieän thöïc baèng phaàn meàm, treân cô sôû caáu hình
heä thoáng maø chuùng ta ñang söû duïng, treân cô sôû quõy thôøi gian hieän coù cuûa chuùng ta vaø treân
cô sôû hieän thöïc cuûa ngoân ngöõ maø ta ñang söû duïng thì vieäc löïa choïn giaûi thuaät naøo hôïp lyù
nhaát laø tuøy thuoäc vaøo kyõ naêng cuûa ngöôøi laäp trình.
Luaän AÙn Toát Nghieäp Phaàn thuyeát minh
Sinh vieân thöïc hieän: Bieän Coâng Minh - Nguyeãn Xuaân Sôn Trang 41
Chöông 4 CAÙC GIAÛI THUAÄT TOÂ MAØU
Nhö chuùng ta ñaõ bieát, trong haàu heát taát caû caùc heä ñoà hoïa hieän nay thì beân caïnh vieäc veõ ra
ñöôïc caùc ñoái töôïng hình hoïc thì vieäc toâ maøu chuùng cuõng ñoùng moät vai troø quan troïng
khoâng keùm. Trong soá caùc ñoái töôïng caàn toâ maøu thì coù nhöõng nhoùm ñoái töôïng laø coù theå tieán
haønh toâ maøu ñöôïc vaø cuõng coù nhöõng ñoái töôïng khoâng theå toâ maøu do hình daïng phöùc taïp
cuûa noù, vaø trong taát caû caùc ñoái töôïng noùi treân thì vieäc toâ maøu moät ña giaùc coù leõ laø ñôn giaûn
hôn caû do caùc ñöôøng bao cuûa ña giaùc laø tuyeán tính.
Trong heä thoáng rôøi raïc, coù hai phöông thöùc ñöôïc duøng ñeå toâ maøu ñoái töôïng. Phöông
phaùp toâ maøu thöù nhaát laø xaùc ñònh phaàn truøng nhau giöõa dieän tích caàn toâ vaø ñöôøng thaúng
queùt qua phaàn dieän tích naøy. Moät phöông phaùp toâ maøu khaùc laø baét ñaàu töø moät vò trí beân
trong cho tröôùc, chuùng ta seõ toâ maøu töø ñieåm naøy veà phiaù ngoaøi cho ñeán khi ñuïng phaûi phaàn
ñöôøng bao cuûa ñoái töôïng ñang toâ.. Phöông phaùp toâ maøu duøng ñöông thaúng queùt thöôøng
ñöôïc ñi keøm vôùi haàu heát taát caû caùc goùi phaàn meàm ñoà hoïa thoâng thöôøng vaø noù ñöôïc aùp
duïng ñeå toâ maøu cho haàu heát caùc ñoái töôïng hình hoïc thoâng duïng nhö ña giaùc, hình troøn,
ellipse vaø nhöõng ñöôøng cong ñôn giaûn. Coøn phöông phaùp toâ maøu baèng vieäc baét ñaàu töø moät
ñieåm beân trong vaät theå caàn toâ tieán haønh toâ cho ñeán khi gaëp phaûi ñöôøng bao cuûa vaät theå thì
thöôøng ñöôïc söû duïng ñeå toâ maøu cho caùc ñoái töôïng hình hoïc phöùc taïp hay ñöôïc duøng trong
caùc heä thoáng hoäi hoïa.
Giaûi Thuaät Toâ Maøu Moät Ña Giaùc Baèng Ñöôøng Thaúng Queùt
Hình veõ 3-35 minh hoïa cho caùch thöùc toâ maøu baèng ñöôøng thaúng queùt.
ÖÙng vôùi moãi ñöôøng thaúng queùt qua ña giaùc,
giaûi thuaät toâ maøu seõ xaùc ñònh giao ñieåm giöõa
ñöôøng thaúng vaø ñöôøng bao cuûa ña giaùc. Nhöõng
giao ñieåm naøy sau ñoù seõ ñöôïc saép xeáp theo
thöù töï töø traùi sang phaûi, vaø moät vò trí töông öùng
trong vuøng ñeäm naèm giöõa moãi caëp giao ñieåm
seõ ñöôïc caøi ñaët giaù trò maøu seõ ñöôïc toâ. Trong
ví duï cuû hình veõ 3-35, vò trí cuûa boán giao ñieåm
vôùi ña giaùc ñònh nghóa neân hai khoaûng chöùa
caùc ñieåm naèm beân trong töø x = 10 ñeán x = 14
vaø töø x = 18 ñeán x = 24.
Trong moät vaøi tröôøng hôïp, tung ñoä cuûa caùc
giao ñieåm giöõa ñöôøng thaúng vaø ña giaùc cuõng
10 14 18 24
x
y
Luaän AÙn Toát Nghieäp Phaàn thuyeát minh
Sinh vieân thöïc hieän: Bieän Coâng Minh - Nguyeãn Xuaân Sôn Trang 42
caàn phaûi ñöôïc löu laïi moät caùch ñaëc bieät. Ví duï
nhö trong tröôøng hôïp
Hình 3-35 ñöôøng thaúng caét ngang ña giaùc taïi ñænh cuûa ña
giaùc
Caùc ñieåm beân trong khi thì vò trí naøy seõ phaûi ñöôïc löu laïi trong danh
saùch caùc
ñöôûng thaúng queùt qua phaàn ñieåm giao nhau ñeán hai laàn. Hình veõ 3-
36 chæ ra hai
dieän tích cuûa ña giaùc ñöôøng thaúng taïi hai vò trí y va y' caét ña
giaùc taïi caùc
ñænh cuûa ña giaùc. Ñöôøng thaèng y ñi qua 5 caïnh
cuûa ña giaùc. Tuy nhieân, ñöôøng thaúng y' laïi coù soá giao ñieåm vôùi ña giaùc laø soá chaün maëc daàu
noù cuõng ñi qua moät ñænh cuûa ña giaùc. Caùc giao ñieåm doïc theo ñöôøng thaúng y' coù theå nhaän
bieát ñöôïc deã daøng nhöõng ñieåm thuoäc beân trong ña giaùc nhöng vôùi ñöôøng thaúng y, chuùng ta
caàn phaûi laøm theâm moät soá coâng vieäc môùi coù theå xaùc ñònh caùc ñieåm naèm beân trong ña giaùc.
Söï khaùc bieät veà maët hình hoïc giöõa ñöôøng thaúng y vaø y' trong hình 3-36 seõ ñöôïc nhaän
bieát baèng caùch chuù yù ñeán caùc vò trí giao nhau giöõa caùc caïnh vaø caùc ñöôøng thaúng. Ñoái vôùi
ñöôøng y, hai caïnh giao vôùi ñöôøng thaúng coù chung moät ñænh naèm veà hai phiaù so vôùi ñöôøng
thaúng ñoù, nhöng vôùi ñöôøng thaúng y', hai caïnh giao nhau vôùi ñöôøng thaúng coù chung moät
ñænh laïi naèm cuøng veà moät phiaù so vôùi ñöôøngthaúng ñoù. Nhö theá, caùc ñænh ñoøi hoûi söï xöû lyù
theâm laø caùc ñænh coù caïnh noái ñeán noù giao vôùi ñöôøng thaúng naèm veà hai phiaù cuûa ñöôøng
thaúng ñoù. Chuùng ta coù theå phaùt hieän ra nhöõng ñænh naøy baèng caùch duyeät heát toaøn boä ña
giaùc hoaëc theo chieàu kim ñoàng hoà hoaëc ngöôïc chieàu kim ñoàng hoà vaø quan saùt söï thay ñoåi
töông öùng theo toïa ñoä y cuûa caùc ñænh khi chuùng ta di chuyeån töø caïnh naøy sang caïnh keá
tieáp. Neáu giaù trò y cuûa ñænh chung cho hai caïnh lieân tuïc laø taêng daàn hay giaûm daàn ñeàu thì
chuùng ta chæ caàn xem nhö ñænh naøy chæ laø moät giao ñieåm giöõa ñöôûng thaúng vaø ña giaùc.
Ngöôïc laïi, neáu ñænh chung laø cöïc ñieåm (cöïc ñaïi hay cöïc tieåu) trong vuøng laân caän cuûa
ñöôøng bao ña giaùc thì giao ñieåm giöõa hai caïnh vôùi ñöôøng thaúng thoâng qua ñieåm naøy seõ
ñöôïc theâm vaøo danh saùch giao ñieåm hai laàn.
Ñöôøng thaúng queùt y'
Ñöôøng thaúng queùt y
1
1
2 1
2 1 1
Luaän AÙn Toát Nghieäp Phaàn thuyeát minh
Sinh vieân thöïc hieän: Bieän Coâng Minh - Nguyeãn Xuaân Sôn Trang 43
Hình 3-36
Caùc giao ñieåm doïc theo ñöôøng thaúng
queùt giao vôùi ña giaùc taïi caùc ñænh cuûa
ña giaùc. Ñuôøng thaúng y coù soá giao ñieåm
laø soá chaün nhöng ñöôøng thaúng y’ coù soá
giao ñieåm laø leõ nhöng vaãn ñöôïc ñaùnh
daáu laø moät caëp ñeå xaùc ñònh ñuùng khoaûng
taäp caùc ñieåm naèm beân trong ña giaùc
Moät caùch ñeå coù theå traû lôøi chính xaùc caâu hoûi laø khi naøo thì chuùng ta ñeám moät ñænh laø
moät giao ñieåm vaø khi naøo ta ñeám ñænh laø hai giao ñieåm laø tieán haønh thu ngaén caùc caïnh cuûa
ña giaùc ñeå taùch nhöõng ñænh naøy thaønh caùc ñænh seõ ñöôïc ñeám chæ moät laàn. Chuùng ta tieán
haønh xöû lyù caùc caïnh khoâng naèm theo phöông ngang doïc theo ñöôøng bao ña giaùc theo moät
thöù töï naøo ñoù, hoaëc laø theo chieàu kim ñoàng hoà hoaëc laø ngöôïc chieàu kim ñoàng hoà. Vaø vôùi
moãi caïnh, chuùng ta seõ tieán haønh kieåm tra xem caïnh ñang xöû lyù vaø caïnh khoâng naèm theo
phöông ngang keá tieáp coù giaù trò toïa ñoä cuûa ñieåm chung theo truïc y laø taêng hay giaûm ñeàu
hay khoâng. Neáu coù thì caïnh thaáp hôn seõ ñöôïc thu ngaén ñeå ñaûm baûo laø chæ coù moät giao
ñieåm ñöôïc phaùt sinh cho ñöôøng thaúng queùt khi ñi qua ñænh chung cuûa hai caïnh.
Quaù trình tính toaùn ñöôïc trình baøy trong giaûi thuaät ñöôøng queùt cuõng nhö caùc giaûi thuaät
khaùc coù moät ñaëc ñieåm noåi baät laø tính chaët cheõ cuûa caùc lôùp ñöôïc hieån thò. Chuùng ta noùi tính
chaët cheõ laø nhö theá naøo? Ñôn giaûn laø ñaëc ñieåm cuûa moät phaàn thuoäc lôùp naøy seõ coù moái
quan heä maät thieát vôùi phaàn keá tieáp, do ñoù seõ giaûm ñöôïc khoái löôïng xöû lyù coâng vieäc. Caùc
phöông phaùp coù tính chaát chaët cheõ thöôøng ñöôïc söû duïng ñeå aùp duïng cho ñöôøng thaúng queùt
ñôn hay cho caùc ñöôøng thaúng queùt keá tieáp. Trong vieäc xaùc ñònh giao ñieåm vôùi caùc caïnh,
chuùng ta coù theå tính toaùn caùc toaï ñoä gia taêng doïc baát kyø caïnh naøo baèng caùch lôïi duïng tính
chaát laø heä soá goùc cuûa caùc caïnh laø khoâng ñoåi öùng vôùi baát kyø ñöôøng thaúng queùt naøo.
Hình 3-38
Hai ñöôøng thaúng keá nhau caét ñöôøng
bao cuûa ña giaùc
Ñöôøng thaúng queùt yk
Ñöôøng thaúng queùt yk+1(xk+1, yk+1)
(xk, yk)
Luaän AÙn Toát Nghieäp Phaàn thuyeát minh
Sinh vieân thöïc hieän: Bieän Coâng Minh - Nguyeãn Xuaân Sôn Trang 44
Hình 3-38 minh hoïa hai ñöôøng thaúng keá nhau caét moät caïnh beân traùi cuûa ña giaùc. Heä soá
goùc cuûa caïnh ñöôøng bao naøy seõ ñöôïc bieãu dieãn thoâng qua toïa ñoä cuûa caùc ñieåm caét nhö
sau:
yk+1 - yk
m = ------------- (58)
xk+1 - xk
Vì söï thay ñoåi giaù trò cuûa y giöõa hai ñöôøng thaúng ñôn giaûn laø
yk+1 - yk = 1 (59)
Nhö theá, giaù trò x cuûa giao ñieåm xk+1 thuoäc ñöôøng thaúng phiaù treân seõ ñöôïc tính thoâng
qua giaù trò x taïi giao ñieåm xk thuoäc ñöôøng thaúng beân döôùi nhö sau:
xk+1 = xk + 1/m (60)
Caùc giaù trò tieáp theo cuûa x coù theå ñöôïc tính baèng caùch coäng doàn giaù trò giaù trò nghòch
ñaûo cuûa heä soá goùc vaø laøm troøn ñeán giaù trò nguyeân gaàn nhaát.
Trong heä thoáng xöû lyù song song, vieäc thöïc thi giaûi thuaät toâ maøu coù theå ñöôïc tieán haønh
moät caùch song song baèng caùnh öùng vôùi moãi ñöôøng thaúng queùt caét ngang ña giaùc, ta seõ
chuyeån chuùng ñeán cho nhöõng quaù trình xöû lyù ñoäc laäp nhau. Quaù trình tính toaùn caùc giao
ñieåm caïnh sau ñoù seõ ñöôïc tính toaùn moät caùch ñoäc laäp. Vôùi moät caïnh coù heä soá goùc laø m, giaù
trò toïa ñoä theo truïc x laø xk öùng vôùi ñöôøng k naèm treân ñöôøng thaúng ban ñaàu coù theå tính nhö
sau:
xk = x0 + k/m (61)
Trong giaûi thuaät toâ maøu lieân tieáp, gia soá cuûa giaù trò x laø 1/m doïc theo caùc caïnh cho
ñeán khi keát thuùc chieàu daøi caïnh vôùi caùc pheùp toaùn treân soá nguyeân vaø cuõng neân chuù yù raèng,
heä soá goùc m laø tæ soá giöõa hai soá nguyeân
m = ∆x/∆y
trong ñoù ∆x, ∆y sai phaân cuûa toïa ñoä giao ñieåm theo truïc x vaø truïc y. Vaø nhö vaäy, giaù trò x
keá tieáp doïc theo caïnh laø:
xk+1 = xk + ∆x/∆y (62)
Söû duïng phöông trình naøy, chuùng ta coù theå tính ñöôïc giaù trò nguyeân cuûa x baèng caùch khôûi
taïo laïi bieán ñeám veà giaù trò 0 vaø sau ñoù taêng daàn bieán ñeám moät giaù trò laø ∆x öùng vôùi moãi
laàn di chuyeån ñeán ñöôøng thaúng queùt keá tieáp. Baát cöù khi naøo giaù trò bieán ñeám baèng hoaëc
Luaän AÙn Toát Nghieäp Phaàn thuyeát minh
Sinh vieân thöïc hieän: Bieän Coâng Minh - Nguyeãn Xuaân Sôn Trang 45
lôùn hôn ∆y, chuùng ta seõ taêng giaù trò cuûa x leân 1 vaø giaûm giaù trò bieán ñeám ∆y. Moät thuû tuïc
töông ñöông nhö theá naøy cuõng seõ ñöôïc söû duïng ñeå duy trì phaàn nguyeân vaø phaàn thaäp phaân
cuûa giaù trò x vaø taêng phaàn thaäp phaân cho ñeán khi chuùng ta ñaït ñöôïc giaù trò nguyeân keá tieáp.
Chuùng ta coù theå laøm troøn ñeán giaù trò x cuûa ñieåm gaàn nhaát thay vì caét boû ñeå ñaït ñeán giaù
trò nguyeân gaàn nhaát baèng caùch ñieàu chænh laïi giaùi thuaät, vaø so saùnh vôùi ∆y/2. Ñieàu naøy coù
theå thöïc hieän vôùi caùc soá nguyeân baèng caùch gia taêng bieán ñeám moät giaù trò laø 2∆x öùng vôùi
moãi böôùc tính vaø so saùnh vôùi ∆y. Khi söï gia taêng laø lôùn hôn hay baèng ∆y, chuùng ta taêng giaù
trò x leân 1 vaø giaûm bieán ñeám moät giaù trò laø 2∆y.
Ñeå laøm taêng tính hieäu quaû cuûa giaûi thuaät toâ maøu, tröôùc tieân chuùng ta caàn löu tröõ ñöôøng
bao cuûa ña giaùc vaøo baûng löu tröõ caùc caïnh laø nôi löu tröõ caùc giaù trò caàn thieát phuïc vuï cho
giaûi thuaät toâ maøu moät caùch hieäu quaû. Vieäc löu tröõ coù theå thöïc hieän theo chieàu kim ñoàng hoà
hay ngöôïc chieàu kim ñoàng hoà, chuùng ta coù theå söû duïng stack ñeå löu tröõ caùc caïnh ñoàng thôøi
cuõng caàn löu tröõ giaù trò nhoû nhaát cuûa y cho moãi caïnh töông öùng vôùi vò trí chính xaùc cuûa
ñöôøng thaúng queùt. Chæ coù caùc caïnh khoâng naèm theo phöông ngang môùi ñöôïc löu tröõ vaøo
baûng löu tröõ caùc caïnh. Vôùi caùc caïnh ñöôïc xöû lyù, chuùng ta coù theå thu ngaén caùc caïnh chính
xaùc ñeå giaûi quyeát baøi toaùn giao ñieåm laø caùc ñænh cuûa ña giaùc. Moåi laàn theâm vaøo baûng löu
tröõ caïnh töôùng öùng vôùi moät ñöôøng thaúng cuï theå naøo ñoù, chuùng ta cuõng caàn löu laïi giaù trò
lôùn nhaát cuûa y cho caïnh ñoù, löu tröõ giaù trò x cuûa ñænh thaáp hôn vaø nghòch ñaûo heä soá goùc.
ÖÙng vôùi moãi ñöôøng thaúng queùt, caùc caïnh seõ ñöôïc saép xeáp theo thöù töï töø traùi sang phaûi.
Tieáp theo, chuùng ta seõ tieán haønh xöû lyù caùc caïnh theo thöù töï töø döôùi leân treân, ta caàn taïo
ra moät danh saùch caùc caïnh kích hoaït cho moãi ñöôøng thaúng queùt qua ña giaùc. Moãi danh
saùch töông öùng cho moät ñöôøng kích hoaït seõ chöùa taát caû caùc caïnh maø ñöôøng thaúng ñi qua
vaø caùc pheùp toaùn lieân quan ñeå coù theå tính ñöôïc caïnh giao.
Vieäc thöïc hieän caùc pheùp tính caùc caïnh giao cuõng coù theå thuaän tieän hôn neáu chuùng ta
löu caùc giaù trò ∆x vaø ∆y vaøo baûng löu. Vaø cuõng vaäy, ñeå baûo ñaûm raèng chuùng ta chæ toâ maøu
caùc ñieåm naèm beân trong ña giaùc thì öùng vôùi moãi ñöôøng thaúng queùt, chuùng ta chæ tieán haønh
toâ caùc ñieåm naèm trong khoaûng caùc caëp giao ñieåm x baét ñaàu töø ñieåm beân traùi nhaát vaø keát
thuùc ôû ñieåm beân phaûi nhaát.
Giaûi Thuaät Kieåm Tra Beân Trong Vaø Beân Ngoaøi
Trong giaûi thuaät toâ maøu vuøng ñoái töôïng vaø trong nhöõng quaù trình xöû lyù ñoà hoïa khaùc, chuùng
ta thöôøng xuyeân caàn phaûi xaùc ñònh vuøng naèm beân trong ñoái töôïng. Cho ñeán hieän taïi thì
chuùng ta cuõng chæ baøn ñeán vieäc toâ maøu cho caùc ña giaùc coù hình daïng chuaån. Tuy nhieân
trong hình hoïc cô baûn, ña giaùc thöôøng ñöôïc ñònh nghóa theo daïng khoâng coù söï töï giao nhau
giöõa caùc caïnh. Ví duï nhö ña giaùc chæ ñôn giaûn laø caùc tam giaùc, töù giaùc, luïc giaùc hay baùt
giaùc. Caùc caïnh thaønh phaàn cuûa caùc ñoái töông naøy chæ giao nhau taïi caùc ñænh cuûa ña giaùc vaø
khoâng coù ñieåm chung naøo nöõa. Söï nhaän bieát caùc vuøng naèm beân trong caùc ña giaùc chuaån laø
moät quaù trình khoâng maáy khoù khaên. Nhöng trong phaàn lôùn caùc öùng duïng ñoà hoïa, chuùng ta
coù theå chæ ra daõy lieân tuïc caùc ñænh cuûa vuøng toâ maøu keå caû caùc ñænh laø giao ñieåm cuûa caùc
caïnh vaø nhö theá raát khoù xaùc ñònh ñaâu laø caùc ñieåm naèm beân trong vaø ñaâu laø caùc ñieåm naèm
Luaän AÙn Toát Nghieäp Phaàn thuyeát minh
Sinh vieân thöïc hieän: Bieän Coâng Minh - Nguyeãn Xuaân Sôn Trang 46
beân ngoaøi ñoái töôïng. Caùc phaàn meàm ñoà hoïa thöôøng duøng nguyeân taéc chaün leû hay nguyeân
taéc heä soá xoaén khaùc khoâng ñeå nhaän bieát caùc vuøng beân trong naøy.
Chuùng ta seõ söû duïng nguyeân taéc tính chaún leõ baèng nguyeân lyù veõ moät ñöôøng thaúng töø
moät ñieåm baát kyø P ñeán moät ñieåm caùch xa naèm beân ngoaøi toïa ñoä ñoái töôïng baèng caùch ñeám
soá caïnh caét ngang ñöôøng queùt. Neáu soá caïnh caét ngang ñöôøng queùt laø soá leû thì P laø ñieåm
naèm beân trong, ngöôïc laïi thì P laø ñieåm naèm beân ngoaøi. Ñeå coù theå ñeám soá caïnh chính xaùc,
chuùng ta phaûi ñaûm baûo raèng ñöôøng thaúng maø chuùng ta choïn khoâng ñöôïc ñi qua baát kyø ñænh
naøo cuûa ña giaùc. Giaûi thuaät toâ maøu theo phöông phaùp ñöôøng thaúng queùt noùi treân laø moät ví
duï cuûa giaûi thuaät toâ maøu theo phöông phaùp chaün leû.
Moät phöông phaùp khaùc coù theå xaùc ñònh moät ñieåm naèm beân trong hay beân ngoaøi ñoái
töôïng laø phöông phaùp duøng nguyeân taéc ñeám soá ñieåm xoaén khaùc khoâng laø nguyeân taéc ñeám
soá laàn caùc caïnh cuûa ña giaùc uoán quanh moät ñieåm theo chieàu ngöôïc chieàu kim ñoàng hoà. Soá
ñeám naøy ñöôïc goïi laø heä soá xoaén vaø moät ñieåm naèm beân trong ñoái töôïng hai chieàu ñöôïc
ñònh nghóa laø nhöõng ñieåm coù heä soá xoaén khaùc khoâng. Chuùng ta aùp duïng nguyeân taéc heä soá
xoaén khaùc khoâng naøy vaøo moät ña giaùc baèng caùch khôûi taïo heä soá xoaén baèng khoâng vaø moät
laàn nöõa hình dung laø ñöôøng thaúng ñi qua ñieåm P baát kyø noái vôùi moät ñieåm caùch xa beân
ngoaøi toïa ñoä cuûa ñoái töôïng. Vaø ñöôøng thaúng chuùng ta choïn khoâng ñi qua baát kyø moät ñænh
naøo cuûa ña giaùc. Nhö vaäy chuùng ta seõ ñi doïc theo ñöôøng thaúng baét ñaàu töø ñieåm P ñeán ñieåm
caùch xa ñoái töôïng vaø ñeám soá caïnh caét ñöôøng thaúng öùng vôùi moãi chieàu. Chuùng ta seõ coäng
theâm moät vaøo heä soá xoaén neáu caïnh ña giaùc caét ñöôøng thaúng töø phaûi sang traùi vaø tröø moät ra
khoûi heä soá xoaén neáu caïnh ña giaùc caét ñöôøng thaúng töø traùi sang phaûi. Giaù trò cuoái cuøng cuûa
heä soá xoaén sau khi caùc caïnh caét ngang ñöôøng thaúng ñaõ ñöôïc ñeám heát seõ quyeát ñònh vò trí
töông öùng cuûa P. Neáu heä soá xoaén laø khaùc khoâng thì P laø moät ñieåm naèm beân trong ñoái
töôïng. Ngöôïc laïi thì P laø moät ñieåm thuoäc beân ngoaøi ñoái töôïng. Ñoái vôùi caùc ña giaùc vaø caùc
ñoái töôïng coù daïng hình hoïc chuaån thì caû hai phöông phaùp chaün leû vaø heä soá xoaén khaùc
khoâng ñeàu cho ra cuøng moät keát quaû. Nhöng ñoái vôùi caùc ñoái töôïng coù daïng hình hoïc phöùc
taïp thì hai phöông phaùp treân coù theå xaùc ñònh ra ñöôïc caùc vuøng naèm beân trong vaø beân ngoaøi
moät ñoái töôïng laø khaùc nhau.
Moät caùch ñeå coù theå xaùc ñònh chieàu cuûa caùc caïnh laø xaùc ñònh moät vector toång cuûa hai
vector - moät doïc theo chieàu ñöôøng thaúng ñi qua P ra ñieåm xa voâ cuøng vaø moät vector caïnh
E töông öùng vôùi moãi caïnh bò caét. Neáu thaønh phaàn z cuûa vector cheùo u x E cho moät caïnh cuï
theå naøo ñoù laø döông thì chieàu cuûa caïnh caét ngang ñöôøng thaúng ñöôïc xem laø töø phaûi qua
traùi vaø chuùng ta seõ coäng 1 vaøo heä soá xoaén. Ngöôïc laïi, caïnh seõ caét ñöôøng thaúng theo chieàu
töø traùi sang phaûi vaø chuùng ta seõ tröø 1 töø heä soá xoaén. Vector caïnh coù theå ñöôïc tính toaùn
baèng caùch tröø giaù trò toïa ñoä cuûa vò trí ñaàu cho vò trí cuoái.
Moät vaøi phaàn meàm ñoà hoïa duøng phöông phaùp heä soá xoaén ñeå xaùc ñònh vuøng toâ maøu
thay vì duøng phöông phaùp chaün leû vì phöông phaùp heä soá xoaén toû ra linh hoaït hôn. Trong
tröôøng hôïp toång quaùt, ñoái töôïng coù theå ñöôïc ñònh nghóa baèng taäp caùc ñænh phöùc taïp khoâng
lieân thoâng hoaëc moät taäp caùc ñöôøng cong rôøi raïc vaø chieàu ñöôïc chæ ra trong caùc taäp naøy seõ
ñöôïc duøng ñeå xaùc ñònh vuøng naèm beân trong ñoái töôïng.
Luaän AÙn Toát Nghieäp Phaàn thuyeát minh
Sinh vieân thöïc hieän: Bieän Coâng Minh - Nguyeãn Xuaân Sôn Trang 47
Giaûi Thuaät Toâ Maøu Theo Caùc Ñöôøng Bieân
Moät phöông caùch khaùc cuõng coù theå ñöôïc duøng ñeå toâ maøu ñoái töôïng laø baét ñaàu töø moät vò trí
naèm beân trong ñoái töôïng, chuùng ta seõ tieán haønh toâ theo chieàu höôùng ra caùc ñöôøng bieân.
Neáu caùc ñöôøng bieân ñöôïc ñònh nghóa baèng caùc maøu ñôn saéc thì giaûi thuaät seõ tieán haønh toâ
maøu caùc ñieåm theo xu höôùng höôùng ra ñöôøng bieân vaø döøng laïi khi ñuïng phaûi maøu cuûa
ñöôøng bieân. Phöông phaùp naøy - coøn ñöôïc goïi laø giaûi thuaät toâ maøu theo ñöôøng bieân - ñaëc
bieät raát höõu hieäu trong caùc phaàn meàm veõ hình nôi maø caùc vuøng thuoäc beân trong ñoái töôïng
laø deã daøng xaùc ñònh. Söû duïng taám baûn veõ hay caùc thieát bò ñeå veõ khaùc, ngöôøi söû duïng coù
theå phaùc hoïa ra ñöôïc ñoái töôïng mình caàn veõ, choïn maøu saéc töø caùc baûng maøu vaø toâ maøu
cho caùc vuøng naèm beân trong ñoái töôïng. Thuû tuïc toâ maøu theo caùc ñöôøng bieân coù caùc giaù trò
ñaàu vaøo laø toïa ñoä cuûa ñieåm naèm beân trong ñoái töôïng (x, y), maøu saéc seõ ñöôïc toâ vaø maøu
saéc cuûa ñöôøng bieân. Baét ñaàu töø vò trí (x,y), thuû tuïc naøy seõ tieán haønh xem xeùt caùc ñieåm laân
caän vaø xem chuùng coù phaûi laø caùc ñieåm thuoäc ñöôøng bieân hay khoâng? Neáu khoâng, chuùng ta
seõ tieán haønh toâ maøu vaø tieáp tuïc xeùt tieáp ñeán caùc ñieåm laân caän vôùi ñieåm vöøa môùi ñöôïc toâ
maøu. Quaù trình naøy cöù nhö theá tieáp tuïc cho ñeán khi taát caû caùc ñieåm töø vò trí (x, y) cho ñeán
caùc ñieåm naèm treân ñöôøng bieân ñeàu ñöôïc kieåm tra.
Sau ñaây laø moät thuû tuïc minh hoïa cho phöông phaùp ñeä quy duøng ñeå toâ maøu söû duïng
vieäc kieåm tra boán ñieåm laân caän vôùi maøu saéc seõ toâ cho caùc ñieåm ñöôïc xaùc ñònh trong tham
soá fill vaø maøu saéc cuûa ñöôøng bieân ñöôïc cho trong tham soá boundary.Thuû tuïc naøy cuõng coù
theå söû duïng ñeå toâ maøu cho vieäc kieåm tra taùm ñieåm laân caän.
void boundaryFill4 (int x, int y, int fill, int boundary)
{
int current;
current = getPixel(x ,y);
if ((current != boundary) && (current != fill)
{
setColor (fill);
setPixel(x, y);
boundaryfill4(x+1, y, fill, boundary);
boundaryfill4(x-1, y, fill, boundary);
boundaryfill4(x, y+1, fill, boundary);
boundaryfill4(x, y-1, fill, boundary);
}
}
Giaûi thuaät toâ maøu theo ñöôøng bieân ñeä theo phöông phaùp ñeä quy coù theå seõ khoâng toâ
maøu caùc vuøng moät caùch chính xaùc neáu nhö coù moät vaøi ñieåm trong vuøng ñöôïc toâ ñaõ coù maøu
saéc truøng vôùi maøu ñöôïc toâ. Ñieàu naøy laø do thuû tuïc ñaõ kieåm tra ñieåm keá tieáp treân caû hai
tham soá laø maøu ñöôøng bieân vaø maøu toâ. Neáu phaùt hieän ra moät ñieåm coù maøu saéc hieän haønh
Luaän AÙn Toát Nghieäp Phaàn thuyeát minh
Sinh vieân thöïc hieän: Bieän Coâng Minh - Nguyeãn Xuaân Sôn Trang 48
laø truøng vôùi maøu ñöôïc toâ, giaûi thuaät seõ döøng trong khi coù moät soá ñieåm khaùc vaãn chöa ñöôïc
toâ. Ñeå giaûi quyeát vaán ñeà naøy chuùng ta coù theå thay ñoåi maøu saéc cho taát caû caùc ñieåm vôùi
maøu laø khaùc vôùi maøu ñöôïc toâ vaø maøu ñöôøng bieân tröôùc khi chuùng ta aùp duïng thuû tuïc naøy.
Giaûi Thuaät Veát Daàu Loang
Ñoâi khi chuùng ta cuõng coù theå tieán haønh toâ maøu caùc ñoái töôïng coù maøu saéc ñöôøng bieân
khoâng phaûi laø moät maøu nhaát ñònh cho tröôùc. Trong nhöõng tröôøng hôïp nhö theá, chuùng ta coù
theå tieán haønh toâ maøu theo caùch thay theá maøu saéc cho caùc ñieåm beân trong thay vì laø kieåm
tra giaù trò maøu saéc cuûa ñöôøng bieân. Vieäc laøm naøy seõ cho chuùng ta giaûi thuaät toâ maøu môùi
goïi laø giaûi thuaät veát daàu loang. Chuùng ta seõ baét ñaàu töø moät vò trí beân trong (x, y) vaø tieán
haønh thay theá giaù trò maøu cho taát caû caùc ñieåm - nhöõng ñieåm ñang mang nhöõng maøu cuï theå
- moät giaù trò maøu môùi laø maøu chuùng ta caàn toâ. Neáu vuøng caàn toâ coù nhieåu maøu saéc khaùc
nhau thì tröôùc tieân chuùng ta seõ laøm cho caùc ñieåm naøy coù cuøng chung moät maøu saéc. Söû duïng
hoaëc 4 hoaëc 8 ñieåm laân caän, chuùng ta seõ laàn löôït toâ cho ñeán khi taát caû caùc ñieåm ñeàu ñöôïc
toâ baèng maøu môùi. Sau ñaây laø thuû tuïc minh hoïa cho giaûi thuaät veát daàu loang.
void floatFill4 (int x, int y, int fillColor, int oldColor)
{
if (getPixel (x, y) == oldColor)
{
setColor(fillColor);
setPixel(x, y);
floodFill4(x+1, y, fillColor, oldColor);
floodFill4(x-1, y, fillColor, oldColor);
floodFill4(x, y+1, fillColor, oldColor);
floodFill4(x, y-1, fillColor, oldColor);
}
}
Toùm Taét
Trong haàu heát caùc phaàn meàm ñoà hoïa, nguyeân thuûy cuûa vieäc toâ maøu laø toâ
Các file đính kèm theo tài liệu này:
- Cơ sở toán học trong đồ hoạ máy tính.pdf