Luận văn Đồ họa trong máy tính

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â