tailieunhanh - 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. | Hình Học Tính Toán Chương 35: Hình học tính toán Xác định có cặp đoạn thẳng nào cắt nhau không Bài toán: Cho tập các đoạn thẳng trong mặt phẳng. Xác định có cặp đoạn thẳng nào cắt nhau hay không. Để đơn giản, giả sử: Không có đoạn thẳng nào là thẳng đứng Không có ba đoạn thẳng nào cắt nhau tại một điểm chung. Chương 35: Hình học tính toán Giải thuật thô sơ Giải thuật thô sơ: Kiểm tra xem mỗi cặp đoạn thẳng có cắt nhau hay không. Thời gian chạy là (n2), với n là số các đoạn thẳng. Chương 35: Hình học tính toán Kỹ thuật quét Giải thuật hữu hiệu dùng kỷ thuật quét (sweeping): Dùng một đưòng thẳng thẳng đứng quét từ trái sang phải và xem xét các thay đổi của phần giao của đường thẳng quét với các đoạn thẳng. Đường thẳng quét (sweep line) Đường thẳng quét thẳng đứng, vị trí hiện thời là toạ độ x x Chương 35: Hình học tính toán Thứ tự các đoạn thẳng Định nghĩa một thứ tự hoàn toàn trên các đoạn thẳng cắt bởi đường thẳng quét. Hai đoạn thẳng s1 và s2 không cắt nhau là có thể so sánh được tại x nếu đường thẳng quét tại vị trí x cắt cả hai đoạn thẳng đó. Nếu s1 và s2 là có thể so sánh được tại x và giao điểm của s1 với đường thẳng quét ở cao hơn giao điểm của s2 với cùng đường thẳng quét đó, thì ta nói s1 ở trên s2 , ký hiệu s1 >x s2 . s2 s1 Chương 35: Hình học tính toán a b c d e g h f i r t u v z w (a) (b) a >r c a >t b b >t c a >t c b >u c Đoạn thẳng d không so sánh được với các đoạn thẳng khác trong hình (a). e >v f nhưng f >w e Mọi đường thẳng quét mà đi qua vùng xám đều có các đoạn thẳng e và f ở liên tiếp nhau trong quan hệ thứ tự của nó Thứ tự các đoạn thẳng (tiếp) Chương 35: Hình học tính toán Các cấu trúc dữ liệu trong kỹ thuật quét Đường thẳng quét Khi di chuyển đường thẳng quét, giải thuật trữ và duy trì các thông tin sau Tình trạng của đường thẳng quét (sweep-line status): cho biết thứ tự giữa các đối tượng (đoạn thẳng) bị cắt bởi đường thẳng quét | Hình Học Tính Toán Chương 35: Hình học tính toán Xác định có cặp đoạn thẳng nào cắt nhau không Bài toán: Cho tập các đoạn thẳng trong mặt phẳng. Xác định có cặp đoạn thẳng nào cắt nhau hay không. Để đơn giản, giả sử: Không có đoạn thẳng nào là thẳng đứng Không có ba đoạn thẳng nào cắt nhau tại một điểm chung. Chương 35: Hình học tính toán Giải thuật thô sơ Giải thuật thô sơ: Kiểm tra xem mỗi cặp đoạn thẳng có cắt nhau hay không. Thời gian chạy là (n2), với n là số các đoạn thẳng. Chương 35: Hình học tính toán Kỹ thuật quét Giải thuật hữu hiệu dùng kỷ thuật quét (sweeping): Dùng một đưòng thẳng thẳng đứng quét từ trái sang phải và xem xét các thay đổi của phần giao của đường thẳng quét với các đoạn thẳng. Đường thẳng quét (sweep line) Đường thẳng quét thẳng đứng, vị trí hiện thời là toạ độ x x Chương 35: Hình học tính toán Thứ tự các đoạn thẳng Định nghĩa một thứ tự hoàn toàn trên các đoạn thẳng cắt .