Bài giảng Phân tích thiết kế giải thuật - Chương 35: Hình học tính toán

Chương 35: Hình học tính toán trong "Bài giảng Phân tích thiết kế giải thuật" giới thiệu đến bạn đọc những kiến thức giải thuật thô sơ, kỹ thuật quét, thứ tự có đoạn thẳng, tính đúng đắn. Hy vọng, đây là tài liệu tham khảo hữu ích dành cho các bạn.
Nội dung trích xuất từ tài liệu:
Bài giảng Phân tích thiết kế giải thuật - Chương 35: Hình học tính toán HìnhHọcTínhToán13.11.2004 1 35.2Xácđịnhcócặpđoạnthẳngnàocắtnhaukhông Bàitoán:Chotậpcácđoạnthẳngtrongmặtphẳng.Xácđịnhcócặp đoạnthẳngnàocắtnhauhaykhông.ª Đểđơngiản,giảsử: – Khôngcóđoạnthẳngnàolàthẳngđứng – Khôngcóbađoạnthẳngnàocắtnhautạimộtđiểmchung.13.11.2004 Chương35:Hìnhhọctínhtoán 2 Giảithuậtthôsơª Giảithuậtthôsơ:Kiểmtraxemmỗicặpđoạnthẳngcócắtnhauhay không.Thờigianchạylà (n2),vớinlàsốcácđoạnthẳng.13.11.2004 Chương35:Hìnhhọctínhtoán 3 Kỹthuậtquétª Giảithuậthữuhiệudùngkỷthuậtquét(sweeping): Dùngmộtđưòngthẳngthẳngđứngquéttừtráisangphảivàxemxét cácthayđổicủaphầngiaocủađườngthẳngquétvớicácđoạn thẳng. – Đườngthẳngquét(sweepline) ° Đườngthẳngquétthẳngđứng,vịtríhiệnthờilàtoạđộx x13.11.2004 Chương35:Hìnhhọctínhtoán 4 Thứtựcácđoạnthẳng ° Địnhnghĩamộtthứtựhoàntoàntrêncácđoạnthẳngcắtbởi đườngthẳngquét. – Haiđoạnthẳngs1vàs2khôngcắtnhaulàcóthểsosánh đượctạixnếuđườngthẳngquéttạivịtríxcắtcảhaiđoạn thẳngđó. s2 s1 – Nếus1vàs2làcóthểsosánhđượctạixvàgiaođiểmcủas1 vớiđườngthẳngquétởcaohơngiaođiểmcủas2vớicùng đườngthẳngquétđó,thìtanóis1ởtrêns2,kýhiệus1 xs2.13.11.2004 Chương35:Hìnhhọctínhtoán 5 Thứtựcácđoạnthẳng(tiế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 vfnhưngf we b t c Mọiđườngthẳngquétmàđiquavùng a t c xámđềucócácđoạnthẳngevàfởliênĐoạnthẳngdkhôngsosánhđượcvới tiếpnhautrongquanhệthứtựcủanócácđoạnthẳngkháctronghình(a).13.11.2004 Chương35:Hìnhhọctínhtoán 6 Cáccấutrúcdữliệutrongkỹthuậtquét – Đườngthẳngquét ° Khidichuyểnđườngthẳngquét,giảithuậttrữvàduytrìcác thôngtinsau – Tìnhtrạngcủađườngthẳngquét(sweeplinestatus):cho biếtthứtựgiữacácđốitượng(đoạnthẳng)bịcắtbởi đườngthẳngquétvớinhau – Lịchcủacácbiếncố(eventpointschedule):dãycáctọađộ x,sắptừtráisangphải,xácđịnhcácvịtrídừngcủađường thẳngquét.13.11.2004 Chương35:Hìnhhọctínhtoán 7 Cácthaotáclênsweeplinestatusª Chitiếtgiảithuậthữuhiệudùngkỷthuậtquét – Đườngthẳngquét ° Khidichuyểnđườngthẳngquét,giảithuậttrữvàduytrìcác thôngtinsau – Tìnhtrạngcủađườngthẳngquét(sweeplinestatus):Các thaotáclênT: ° INSERT(T,s):chènđoạnthẳngsvàoT ° DELETE(T,s):xoáđoạnthẳngskhỏiT ° ABOVE(T,s):trảvềđoạnthẳngởngaytrênstrongT ° BELOW(T,s):trảvềđoạnthẳngởngaydướistrongT.13.11.2004 Chương35:Hìnhhọctínhtoán 8 Eventpointschedule – Lịchcủacácbiếncố(eventpointschedule):dãycáctọađộ x,sắptừtráisangphải,xácđịnhcácvịtrídừngcủađường thẳngquét. ° Mỗiđiểmđầumútcủacácđoạnthẳng(củatậpinputS) làmộtđiểmbiếncố(eventpoint),làđiểmmàthứtựT thayđổi. ° Lịchcủacácbiếncốlàtĩnhvàđượcxâydựngbằng cáchsắpxếpcácđiểmđầumútcủacácđoạnthẳngtheo ...