Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 35

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 35 có nội dung trình bày về hình học tính toán, giải thuật thô sơ, kỹ thuật quét, cấu trúc dữ liệu trong kỹ thuật quét, các thao tác lên sweep-line status, tính đúng đắn,... Mời các bạn cùng tham khảo chi tiết nội dung bài giảng!
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 35 Hình Hoïc Tính Toaùn13.11.2004 1 35.2 Xaùc ñònh coù caëp ñoaïn thaúng naøo caét nhau khoâng Baøi toaùn: Cho taäp caùc ñoaïn thaúng trong maët phaúng. Xaùc ñònh coù caëp ñoaïn thaúng naøo caét nhau hay khoâng.ª Ñeå ñôn giaûn, giaû söû: – Khoâng coù ñoaïn thaúng naøo laø thaúng ñöùng – Khoâng coù ba ñoaïn thaúng naøo caét nhau taïi moät ñieåm chung.13.11.2004 Chöông 35: Hình hoïc tính toaùn 2 Giaûi thuaät thoâ sôª Giaûi thuaät thoâ sô: Kieåm tra xem moãi caëp ñoaïn thaúng coù caét nhau hay khoâng. Thôøi gian chaïy laø (n2), vôùi n laø soá caùc ñoaïn thaúng.13.11.2004 Chöông 35: Hình hoïc tính toaùn 3 Kyõ thuaät queùtª Giaûi thuaät höõu hieäu duøng kyû thuaät queùt (sweeping): Duøng moät ñöoøng thaúng thaúng ñöùng queùt töø traùi sang phaûi vaø xem xeùt caùc thay ñoåi cuûa phaàn giao cuûa ñöôøng thaúng queùt vôùi caùc ñoaïn thaúng. – Ñöôøng thaúng queùt (sweep line) ° Ñöôøng thaúng queùt thaúng ñöùng, vò trí hieän thôøi laø toaï ñoä x x13.11.2004 Chöông 35: Hình hoïc tính toaùn 4 Thöù töï caùc ñoaïn thaúng ° Ñònh nghóa moät thöù töï hoaøn toaøn treân caùc ñoaïn thaúng caét bôûi ñöôøng thaúng queùt. – Hai ñoaïn thaúng s1 vaø s2 khoâng caét nhau laø coù theå so saùnh ñöôïc taïi x neáu ñöôøng thaúng queùt taïi vò trí x caét caû hai ñoaïn thaúng ñoù. s2 s1 – Neáu s1 vaø s2 laø coù theå so saùnh ñöôïc taïi x vaø giao ñieåm cuûa s1 vôùi ñöôøng thaúng queùt ôû cao hôn giao ñieåm cuûa s2 vôùi cuøng ñöôøng thaúng queùt ñoù, thì ta noùi s1 ôû treân s2 , kyù hieäu s1 > x s2 .13.11.2004 Chöông 35: Hình hoïc tính toaùn 5 Thöù töï caùc ñoaïn thaúng (tieáp) e d g a i b h c f r t u v z w (a) (b) a >r c a >t b b >u c e >v f nhöng f >w e b >t c Moïi ñöôøng thaúng queùt maø ñi qua vuøng a >t c xaùm ñeàu coù caùc ñoaïn thaúng e vaø f ôû lieân tieáp nhau trong quan heä thöù töï cuûaÑoaïn thaúng d khoâng so saùnh ñöôïc vôùi noùcaùc ñoaïn thaúng khaùc trong hình (a).13.11.2004 Chöông 35: Hình hoïc tính toaùn 6 Caùc caáu truùc döõ lieäu trong kyõ thuaät queùt – Ñöôøng thaúng queùt ° Khi di chuyeån ñöôøng thaúng queùt, giaûi thuaät tröõ vaø duy trì caùc thoâng tin sau – Tình traïng cuûa ñöôøng thaúng queùt (sweep-line status): cho bieát thöù töï giöõa caùc ñoái töôïng (ñoaïn thaúng) bò caét bôûi ñöôøng thaúng queùt vôùi nhau – Lòch cuûa caùc bieán coá (event-point schedule): daõy caùc toïa ñoä x, saép töø traùi sang phaûi, xaùc ñònh caùc vò trí döøng cuûa ñöôøng thaúng queùt.13.11.2004 Chöông 35: Hình hoïc tính toaùn 7 Caùc thao taùc leân sweep-line statusª Chi tieát giaûi thuaät höõu hieäu duøng kyû thuaät queùt – Ñöôøng thaúng queùt ° Khi di chuyeån ñöôøng thaúng queùt, giaûi thuaät tröõ vaø duy trì caùc thoâng tin sau – Tình traïng cuûa ñöôøng thaúng queùt (sweep-line status): Caùc thao taùc leân T: ° INSERT(T, s): cheøn ñoaïn thaúng s vaøo T ° DELETE(T, s): xoaù ñoaïn thaúng s khoûi T ° ABOVE(T, s): traû veà ñoaïn thaúng ôû ngay treân s trong T ° BELOW(T, s): traû veà ñoaïn thaúng ôû ngay döôùi s trong T.13.11.2004 Chöông 35: Hình hoïc tính toaùn 8 Event-point schedule – Lòch cuûa caùc bieán coá (event-point schedule): daõy caùc toïa ñoä x, saép töø traùi sang phaûi, xaùc ñònh caùc vò trí döøng cuûa ñöôøng thaúng queùt. ° Moãi ñieåm ñaàu muùt cuûa caùc ñoaïn thaúng (cuûa taäp input S) laø moät ñieåm bieán coá (event point), laø ñieåm maø thöù töï T thay ñoåi. ° Lòch cuûa caùc bieán coá laø tónh vaø ñöôïc xaây döïng baèng caùch saép xeáp caùc ñieåm ñaàu muùt cuûa caùc ñoaïn thaúng theo thöù töï töø traùi qua phaûi.13.11.2004 Chöông 35: Hình hoïc tính toaùn 9 Xaùc ñònh coù caëp ñoaïn thaúng naøo caét nhau khoâng ANY-SEGMENTS-INTERSECT(S) 1 T 2 Saép caùc ñieåm ñaàu muùt cuûa caùc ñoaïn thaúng trong S theo thöù töï töø traùi sang phaûi, breaking ties... 3 for moåi ñieåm p trong danh saùch saép xeáp cuûa caùc ñieåm ñaàu muùt 4 do if p laø ñieåm ñaàu muùt beân traùi cuûa ñoaïn t ...