Bài giảng Phân tích và thiết kế giải thuật - Chương 11: Giao điểm của hai đoạn thẳng (Phần 1)

25.9.2004 1 Hình Học Tính Toán 25.9.2004 Chương 11: Giao điểm của hai đoạn thẳng 2 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 Chương 11: Giao điểm của hai đoạn thẳng 3 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) 1221 21 21 21 det yxyx yy xx pp -=       = 25.9.2004 Chương 11: Giao điểm của hai đoạn thẳng 4 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 p1  p2 là diện tích của hình bình hành 25.9.2004 Chương 11: Giao điểm của hai đoạn thẳng 5 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 . p0 p1 p2 p0 p1 p2 ngược chiều kim đồng hồ theo chiều kim đồng hồ 25.9.2004 Chương 11: Giao điểm của hai đoạn thẳng 6 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 Chương 11: Giao điểm của hai đoạn thẳng 7 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.) p2 p1 p2 p1 đ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 p2 p1 L L L 25.9.2004 Chương 11: Giao điểm của hai đoạn thẳng 8 Xác định hai đoạn thẳng có cắt nhau không (tiếp) – Định lý: 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 Chương 11: Giao điểm của hai đoạn thẳng 9 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 Chương 11: Giao điểm của hai đoạn thẳng 10 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 Chương 11: Giao điểm của hai đoạn thẳng 11 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. SEGMENTS-INTERSECT(p 1 , p 2 , p 3 , p 4 ) 1 d 1  DIRECTION(p 3 , p 4 , p 1 ) 2 d 2  DIRECTION(p 3 , p 4 , p 2 ) 3 d 3  DIRECTION(p 1 , p 2 , p 3 ) 4 d 4  DIRECTION(p 1 , p 2 , p 4 ) 5 if ((d 1 > 0 and d 2 < 0) or (d 1 < 0 and d 2 > 0)) and ((d 3 > 0 and d 4 < 0) or (d 3 < 0 and d 4 > 0)) 6 then return TRUE (xem tiếp slide tới) 25.9.2004 Chương 11: Giao điểm của hai đoạn thẳng 12 Xác định hai đoạn thẳng có cắt nhau không (tiếp) (tiếp) 7 elseif d 1 = 0 and ON-SEGMENT(p 3 , p 4 , p 1 ) 8 then return TRUE 9 elseif d 2 = 0 and ON-SEGMENT(p 3 , p 4 , p 2 ) 10 then return TRUE 11 elseif d 3 = 0 and ON-SEGMENT(p 1 , p 2 , p 3 ) 12 then return TRUE 13 elseif d 4 = 0 and ON-SEGMENT(p 1 , p 2 , p 4 ) 14 then return TRUE 15 else return FALSE 25.9.2004 Chương 11: Giao điểm của hai đoạn thẳng 13 Xác định hai đoạn thẳng có cắt nhau không (tiếp) Thủ tục ON-SEGMENT 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 DIRECTION(p i , p j , p k ) 1 return (p k - p i )  (p j - p i ) ON-SEGMENT(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