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! | Hình Hoïc Tính Toaùn 1 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. 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. 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 x 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 gt x s2 . 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 gt r c a gt t b b gt u c e gt v f nhöng f gt w e b gt t c Moïi ñöôøng thaúng queùt maø ñi qua vuøng a gt 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 . 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 .
