Bài giảng Giải thuật - Chương 11, Phần 1: Hình học tính toán
ª Tính chất của đoạn thẳng
ª Định nghĩa
– Một tổ hợp lồi của hai điểm khác nhau p1 = (x1,y1) và p2 = (x2 ,y2) là một điểm p3 = (x3 ,y3) sao cho
x3 = a x1 + (1 - a) x2
y3 = a y1 + (1 - a) y2
0 a 1 .
– Đoạn thẳng p1p2 là tập mọi tổ hợp lồi của p1 và p2 , ký hiệu đt p1p2
– Các điểm đầu mút của đoạn thẳng p1p2 là p1 và p2
– Đoạn thẳng có hướng p1p2 là đoạn thẳng p1p2 được định hướng từ p1 đến p2 , ký hiệu p1p2 .
Bạn đang xem nội dung tài liệu Bài giảng Giải thuật - Chương 11, Phần 1: Hình học tính toán, để tải tài liệu về máy bạn click vào nút TẢI VỀ ở trên
Hình Học Tính Toán 25.9.2004 1 Tính chất của đoạn thẳng Định nghĩa Một tổ hợp lồi của hai điểm khác nhau p 1 = ( x 1 , y 1 ) và p 2 = ( x 2 , y 2 ) là một điểm p 3 = ( x 3 ,y 3 ) sao cho x 3 = a x 1 + (1 - a ) x 2 y 3 = a y 1 + (1 - a ) y 2 0 a 1 . Đoạn thẳng p 1 p 2 là tập mọi tổ hợp lồi của p 1 và p 2 , ký hiệu đt p 1 p 2 Các điểm đầu mút của đoạn thẳng p 1 p 2 là p 1 và p 2 Đoạn thẳng có hướng p 1 p 2 là đoạn thẳng p 1 p 2 được định hướng từ p 1 đến p 2 , ký hiệu p 1 p 2 . 25.9.2004 2 Chương 11: Giao điểm của hai đoạn thẳng Tích chéo Định nghĩa Tích chéo của hai vectors p 1 = ( x 1 ,y 1 ) và p 2 = ( x 2 ,y 2 ) là Nhận xét Nếu p 1 p 2 > 0 thì vectơ p 1 nằm theo chiều kim đồng hồ từ vectơ p 2 đối với (0, 0) Nếu p 1 p 2 < 0 thì vectơ p 1 nằm ngược chiều kim đồng hồ từ vectơ p 2 đối với (0, 0) Nếu p 1 p 2 = 0 thì O , p 1 và p 2 thẳng hàng. p 1 p 2 (0,0) p 1 p 2 (0,0) 25.9.2004 3 Chương 11: Giao điểm của hai đoạn thẳng Tích chéo (tiếp) x y p 1 p 2 (0,0) p x y (0,0) vectơ nằm ngược chiều kim đồng hồ từ p vectơ nằm theo chiều kim đồng hồ từ p p 1 p 2 là diện tích của hình bình hành 25.9.2004 4 Chương 11: Giao điểm của hai đoạn thẳng Tích chéo (tiếp) Nhận xét Cho hai đoạn thẳng có hướng p 0 p 1 và p 0 p 2 . Dùng phép tịnh tiến mà vectơ tịnh tiến là - p 0 , ta thấy Nếu ( p 1 - p 0 ) ( p 2 - p 0 ) > 0 thì p 0 p 1 nằm theo chiều kim đồng hồ từ p 0 p 2 Nếu ( p 1 - p 0 ) ( p 2 - p 0 ) < 0 thì p 0 p 1 nằm ngược chiều kim đồng hồ từ p 0 p 2 . p 0 p 1 p 2 p 0 p 1 p 2 ngược chiều kim đồng hồ theo chiều kim đồng hồ 25.9.2004 5 Chương 11: Giao điểm của hai đoạn thẳng Xác định hai đoạn thẳng có cắt nhau không Bài toán Cho hai đoạn thẳng p 1 p 2 và p 3 p 4 . Hỏi: Hai đoạn thẳng có cắt nhau không? Hai cách giải quyết Cách giải 1: giải hệ thống phương trình bậc nhất để tìm tọa độ của điểm cắt (nếu có). Cách giải này cần dùng phép chia nên không chính xác khi tử số gần bằng 0. Cách giải 2: không cần dùng phép chia (xem slide tới). 25.9.2004 6 Chương 11: Giao điểm của hai đoạn thẳng Xác định hai đoạn thẳng có cắt nhau không (tiếp) Định nghĩa: Một đoạn thẳng p 1 p 2 nằm hai bên (“straddle”) một đường thẳng nếu p 1 và p 2 nằm ở hai bên khác nhau của đường thẳng. (Trường hợp biên: p 1 hay p 2 nằm trên đường thẳng.) p 2 p 1 p 2 p 1 đt p 1 p 2 nằm hai bên đường thẳng L đt p 1 p 2 không nằm hai bên đường thẳng L p 2 p 1 L L L 25.9.2004 7 Chương 11: Giao điểm của hai đoạn thẳng Xác định hai đoạn thẳng có cắt nhau không (tiếp) Định ly ù: Hai đoạn thẳng cắt nhau nếu và chỉ nếu một trong các điều kiện sau (hoặc cả hai) là đúng. 1. Mỗi đoạn thẳng nằm hai bên đường thẳng chứa đoạn thẳng kia. 2. Một điểm đầu mút (điểm cuối) của đoạn thẳng này nằm trên đoạn thẳng kia. a b Đoạn thẳng a nằm hai bên đường thẳng chứa b , và đoạn thẳng b nằm hai bên đường thẳng chứa a 25.9.2004 8 Chương 11: Giao điểm của hai đoạn thẳng Xác định hai đoạn thẳng có cắt nhau không (tiếp) p 2 p 1 p 3 p 4 ( p 4 p 1 ) ( p 2 p 1 ) 0 ( p 3 p 1 ) ( p 2 p 1 ) < 0 p 4 p 1 p 3 p 2 ( p 4 p 1 ) ( p 2 p 1 ) < 0 ( p 3 p 1 ) ( p 2 p 1 ) < 0 Các tích chéo ( p 3 p 1 ) ( p 2 p 1 ) và ( p 4 p 1 ) ( p 2 p 1 ) có dấu khác nhau, do đó đt p 3 p 4 nằm hai bên đường thẳng chứa đt p 1 p 2 (và ngược lại) Các tích chéo ( p 3 p 1 ) ( p 2 p 1 ) và ( p 4 p 1 ) ( p 2 p 1 ) có cùng dấu, do đó đt p 3 p 4 không nằm hai bên đường thẳng chứa đt p 1 p 2 (và ngược lại) Dùng tích chéo để xác định một đoạn thẳng có nằm hai bên một đường thẳng hay không. 25.9.2004 9 Chương 11: Giao điểm của hai đoạn thẳng Xác định hai đoạn thẳng có cắt nhau không (tiếp) p 1 p 3 p 4 p 2 ( p 4 p 1 ) ( p 2 p 1 ) = 0 ( p 3 p 1 ) ( p 2 p 1 ) < 0 ( p 4 p 1 ) ( p 2 p 1 ) = 0 ( p 3 p 1 ) ( p 2 p 1 ) = 0 p 1 p 3 p 2 p 4 p 1 p 2 p 3 p 4 25.9.2004 10 Chương 11: Giao điểm của hai đoạn thẳng Xác định hai đoạn thẳng có cắt nhau không (tiếp) Thủ tục để kiểm tra hai đoạn thẳng p 1 p 2 và p 3 p 4 có cắt nhau không (mã giả). Thủ tục trả về TRUE nếu hai đoạn thẳng cắt nhau và trả về FALSE nếu chúng không cắt nhau. S EGMENTS -I NTERSECT ( p 1 , p 2 , p 3 , p 4 ) 1 d 1 D IRECTION ( p 3 , p 4 , p 1 ) 2 d 2 D IRECTION ( p 3 , p 4 , p 2 ) 3 d 3 D IRECTION ( p 1 , p 2 , p 3 ) 4 d 4 D IRECTION ( p 1 , p 2 , p 4 ) 5 if (( d 1 > 0 and d 2 0)) and (( d 3 > 0 and d 4 0)) 6 then return TRUE (xem tiếp slide tới) 25.9.2004 11 Chương 11: Giao điểm của hai đoạn thẳng Xác định hai đoạn thẳng có cắt nhau không (tiếp) (tiếp) 7 elseif d 1 = 0 and O N -S EGMENT ( p 3 , p 4 , p 1 ) 8 then return TRUE 9 elseif d 2 = 0 and O N -S EGMENT ( p 3 , p 4 , p 2 ) 10 then return TRUE 11 elseif d 3 = 0 and O N -S EGMENT ( p 1 , p 2 , p 3 ) 12 then return TRUE 13 elseif d 4 = 0 and O N -S EGMENT ( p 1 , p 2 , p 4 ) 14 then return TRUE 15 else return FALSE 25.9.2004 12 Chương 11: Giao điểm của hai đoạn thẳng Xác định hai đoạn thẳng có cắt nhau không (tiếp) Thủ tục O N -S EGMENT Input: p i , p j , p k , mà p k thẳng hàng với đoạn p i p j Output: TRUE nếu p k nằm trên đoạn p i p j FALSE nếu p k nằm ngoài đoạn p i p j D IRECTION ( p i , p j , p k ) 1 return ( p k - p i ) ( p j - p i ) O N -S EGMENT ( p i , p j , p k ) 1 if min( x i , x j ) x k max( x i , x j ) and min( y i , y j ) y k max( y i , y j ) 2 then return TRUE 3 else return FALSE 25.9.2004 13 Chương 11: Giao điểm của hai đoạn thẳng
File đính kèm:
bai_giang_giai_thuat_chuong_11_phan_1_hinh_hoc_tinh_toan.ppt
