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

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