Nhằm giúp các bạn có thêm tài liệu phục vụ nhu cầu học tập và nghiên cứu về Công nghệ thông tin, mời các bạn cùng tham khảo nội dung "Bài giảng Chương 11: Giao điểm của hai đoạn thẳng" dưới đây. Nội dung bài giảng cung cấp cho các bạn những kiến thức về tính chất của đoạn thẳng, tính chéo, xác định hai đoạn thẳng có cắt nhau không.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Chương 11: Giao điểm của hai đoạn thẳng
- Giao điểm của hai đoạn thẳng
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 p1 (x1,y1) và p2 (x2 ,y2)
là một điểm p3 (x3 ,y3) sao cho
x3 x1 (1 a) x2
y3 y1 (1 a) y2
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 p1 p2 .
25.9.2004 Chương 11: Giao điểm của hai đoạn 2
thẳng
- Tích chéo
ª Định nghĩa Tích chéo của hai vectors p1 (x1,y1) và p2 (x2 ,y2) là
x1 x2
p1 p2 det
y1 y2
x1 y2 x2 y1
ª Nhận xét
– Nếu p1 p2 0 thì vectơ p1 nằm theo chiều kim đồng hồ từ vectơ
p2
p2 đối với (0, 0) (0,0)
p1
– Nếu p1 p2 0 thì vectơ p1 nằm ngược chiều kim đồng hồ từ
p1
vectơ p2 đối với (0, 0)
(0,0) p2
– Nếu p1 p2 = 0 thì O, p1 và p2 thẳng hàng.
25.9.2004 Chương 11: Giao điểm của hai đoạn 3
thẳng
- Tích chéo (tiếp)
y
y vectơ nằm ngược chiều p
p2 kim đồng hồ từ p
(0,0)
p1 x
(0,0) x 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 4
thẳng
- Tích chéo (tiếp)
ª Nhận xét
Cho hai đoạn thẳng có hướng p0 p1 và p0 p2 . Dùng phép tịnh tiến mà
vectơ tịnh tiến là p0 , ta thấy
– Nếu (p1 p0) (p2 p0) 0 thì p0 p1 nằm theo chiều kim đồng hồ
từ p0 p2
– Nếu (p1 p0) (p2 p0) 0 thì p0 p1 nằm ngược chiều kim đồng
hồ từ p0 p2 .
p2 p2
p1 p1
ngược chiều theo chiều
kim đồng hồ kim đồng hồ
p0 p0
25.9.2004 Chương 11: Giao điểm của hai đoạn 5
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 p1p2 và p3p4 . 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 6
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 p1p2 nằm hai bên (“straddle”) một
đường thẳng nếu p1 và p2 nằm ở hai bên khác nhau của đường
thẳng. (Trường hợp biên: p1 hay p2 nằm trên đường thẳng.)
L p2 L
p1
p2
p1
đt p1p2 nằm hai bên
đường thẳng L
L
đt p1p2 không nằm hai bên
p1 đường thẳng L
p2
25.9.2004 Chương 11: Giao điểm của hai đoạn 7
thẳng
- 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.
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
a hai bên đường thẳng chứa a
25.9.2004 Chương 11: Giao điểm của hai đoạn 8
thẳng
- Xác định hai đoạn thẳng có cắt nhau không (tiếp)
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.
p2
p3 Các tích chéo (p3 p1) (p2 p1)
p4 và (p4 p1) (p2 p1) có dấu khác
nhau, do đó đt p3 p4 nằm hai bên
(p3 p1) (p2 p1) 0 đường thẳng chứa đt p1 p2 (và
p1 ngược lại)
(p4 p1) (p2 p1) 0
p4
Các tích chéo (p3 p1) (p2 p1)
p3
và (p4 p1) (p2 p1) có cùng
p2
dấu, do đó đt p3 p4 không nằm hai
bên đường thẳng chứa đt p1 p2 (và
p1 (p3 p1) (p2 p1) 0 ngược lại)
(p4 p1) (p2 p1) 0
25.9.2004 Chương 11: Giao điểm của hai đoạn 9
thẳng
- Xác định hai đoạn thẳng có cắt nhau không (tiếp)
p3
p2
(p3 p1) (p2 p1) 0
p4 (p4 p1) (p2 p1) 0
p1
p4
p4
(p4 p1) (p2 p1) 0 p2
p3 p3
p2 (p3 p1) (p2 p1) 0
p1
p1
25.9.2004 Chương 11: Giao điểm của hai đoạn 10
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 p1p2 và p3p4 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.
SEGMENTSINTERSECT(p1, p2, p3, p4)
1 d1 DIRECTION(p3, p4, p1)
2 d2 DIRECTION(p3, p4, p2)
3 d3 DIRECTION(p1, p2, p3)
4 d4 DIRECTION(p1, p2, p4)
5 if ((d1 > 0 and d2 0 and d4
- Xác định hai đoạn thẳng có cắt nhau không (tiếp)
(tiếp)
7 elseif d1 = 0 and ONSEGMENT(p3, p4, p1)
8 then return TRUE
9 elseif d2 = 0 and ONSEGMENT(p3, p4, p2)
10 then return TRUE
11 elseif d3 = 0 and ONSEGMENT(p1, p2, p3)
12 then return TRUE
13 elseif d4 = 0 and ONSEGMENT(p1, p2, p4)
14 then return TRUE
15 else return FALSE
25.9.2004 Chương 11: Giao điểm của hai đoạn 12
thẳng
- Xác định hai đoạn thẳng có cắt nhau không (tiếp)
Thủ tục ONSEGMENT
Input: pi , pj , pk , mà pk thẳng hàng với đoạn pi pj
Output: TRUE nếu pk nằm trên đoạn pi pj
FALSE nếu pk nằm ngoài đoạn pi pj
DIRECTION(pi , pj , pk )
1 return (pk pi ) (pj pi )
ONSEGMENT(pi , pj , pk )
1 if min(xi , xj ) xk max(xi , xj ) and min(yi , yj ) yk max(yi ,
yj )
2 then return TRUE
3 else return FALSE
25.9.2004 Chương 11: Giao điểm của hai đoạn 13
thẳng
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
