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 Hoïc Tính Toaùn
25.9.2004
1
Tính chaát cuûa ñoaïn thaúng
ª Ñònh nghóa
– Moät toå hôïp loài cuûa hai ñieåm khaùc nhau p1 = (x1,y1) vaø p2 = (x2 ,y2)
laø moät ñieåm p3 = (x3 ,y3) sao cho
x3 = a x1 + (1 - a) x2
y3 = a y1 + (1 - a) y2
0 a 1 .
– Ñoaïn thaúng p1p2 laø taäp moïi toå hôïp loài cuûa p1 vaø p2 , kyù hieäu ñt p1p2
– Caùc ñieåm ñaàu muùt cuûa ñoaïn thaúng p1p2 laø p1 vaø p2
– Ñoaïn thaúng coù höôùng p1p2 laø ñoaïn thaúng p1p2 ñöôïc ñònh höôùng töø
→
p1 ñeán p2 , kyù hieäu p1 p2 .
25.9.2004
2
Chöông 11: Giao ñieåm cuûa hai ñoaïn
thaúng
Tích cheùo
ª Ñònh nghóa Tích cheùo cuûa hai vectors p1 = (x1,y1) vaø p2 = (x2 ,y2) laø
x x
1
2
p1 p2 = det
y y2
1
= x1y2 - x2 y1
ª Nhaän xeùt
– Neáu p1 p2 > 0 thì vectô p1 naèm theo chieàu kim ñoàng hoà töø vectô
p2
p2 ñoái vôùi (0, 0)
(0,0)
p1
– Neáu p1 p2 < 0 thì vectô p1 naèm ngöôïc chieàu kim ñoàng hoà töø
vectô p2 ñoái vôùi (0, 0)
p1
(0,0)
p2
– Neáu p1 p2 = 0 thì O, p1 vaø p2 thaúng haøng.
25.9.2004
3
Chöông 11: Giao ñieåm cuûa hai ñoaïn
thaúng
Tích cheùo (tieáp)
y
y
vectô naèm ngöôïc chieàu
kim ñoàng hoà töø p
(0,0)
p
p2
x
p1
x
vectô naèm theo chieàu
kim ñoàng hoà töø p
(0,0)
p1 p2 laø dieän tích cuûa hình bình haønh
25.9.2004
4
Chöông 11: Giao ñieåm cuûa hai ñoaïn
thaúng
Tích cheùo (tieáp)
ª Nhaän xeùt
→
→
Cho hai ñoaïn thaúng coù höôùng p0 p1 vaø p0 p2 . Duøng pheùp tònh tieán
maø vectô tònh tieán laø - p0 , ta thaáy
→
– Neáu (p1 - p0) (p2 - p0) > 0 thì p0 p1 naèm theo chieàu kim ñoàng hoà
→
töø p0 p2
→
– Neáu (p1 - p0) (p2 - p0) < 0 thì p0 p1 naèm ngöôïc chieàu kim ñoàng
→
hoà töø p0 p2 .
p2
p2
p1
p1
ngöôïc chieàu
kim ñoàng hoà
theo chieàu
kim ñoàng hoà
p0
p0
25.9.2004
5
Chöông 11: Giao ñieåm cuûa hai ñoaïn
thaúng
Xaùc ñònh hai ñoaïn thaúng coù caét nhau khoâng
ª Baøi toaùn
Cho hai ñoaïn thaúng p1p2 vaø p3p4 . Hoûi: Hai ñoaïn thaúng coù caét nhau
khoâng?
Hai caùch giaûi quyeát
ª Caùch giaûi 1: giaûi heä thoáng phöông trình baäc nhaát ñeå tìm toïa ñoä cuûa
ñieåm caét (neáu coù). Caùch giaûi naøy caàn duøng pheùp chia neân khoâng
chính xaùc khi töû soá gaàn baèng 0.
ª Caùch giaûi 2: khoâng caàn duøng pheùp chia (xem slide tôùi).
25.9.2004
6
Chöông 11: Giao ñieåm cuûa hai ñoaïn
thaúng
Xaùc ñònh hai ñoaïn thaúng coù caét nhau khoâng (tieáp)
– Ñònh nghóa: Moät ñoaïn thaúng p1p2 naèm hai beân (“straddle”) moät
ñöôøng thaúng neáu p1 vaø p2 naèm ôû hai beân khaùc nhau cuûa ñöôøng
thaúng. (Tröôøng hôïp bieân: p1 hay p2 naèm treân ñöôøng thaúng.)
L
L
p2
p1
p2
p1
ñt p1p2 naèm hai beân
ñöôøng thaúng L
L
ñt p1p2 khoâng naèm hai beân
ñöôøng thaúng L
p1
p2
25.9.2004
7
Chöông 11: Giao ñieåm cuûa hai ñoaïn
thaúng
Xaùc ñònh hai ñoaïn thaúng coù caét nhau khoâng (tieáp)
– Ñònh lyù: Hai ñoaïn thaúng caét nhau neáu vaø chæ neáu moät trong caùc
ñieàu kieän sau (hoaëc caû hai) laø ñuùng.
ª
1. Moãi ñoaïn thaúng naèm hai beân ñöôøng thaúng chöùa ñoaïn thaúng
kia.
ª
2. Moät ñieåm ñaàu muùt (ñieåm cuoái) cuûa ñoaïn thaúng naøy naèm
treân ñoaïn thaúng kia.
b
Ñoaïn thaúng a naèm hai beân ñöôøng
thaúng chöùa b, vaø ñoaïn thaúng b naèm
hai beân ñöôøng thaúng chöùa a
a
25.9.2004
8
Chöông 11: Giao ñieåm cuûa hai ñoaïn
thaúng
Xaùc ñònh hai ñoaïn thaúng coù caét nhau khoâng (tieáp)
Duøng tích cheùo ñeå xaùc ñònh moät ñoaïn thaúng coù naèm hai beân moät ñöôøng
thaúng hay khoâng.
p2
p3
Caùc tích cheùo (p3 - p1) (p2 - p1)
vaø (p4 - p1) (p2 - p1) coù daáu
khaùc nhau, do ñoù ñt p3 p4 naèm hai
beân ñöôøng thaúng chöùa ñt p1 p2
(vaø ngöôïc laïi)
p4
(p3 - p1) (p2 - p1) < 0
(p4 - p1) (p2 - p1) > 0
p1
p4
p2
Caùc tích cheùo (p3 - p1) (p2 - p1)
vaø (p4 - p1) (p2 - p1) coù cuøng
daáu, do ñoù ñt p3 p4 khoâng naèm hai
beân ñöôøng thaúng chöùa ñt p1 p2
(vaø ngöôïc laïi)
p3
(p3 - p1) (p2 - p1) < 0
(p4 - p1) (p2 - p1) < 0
p1
25.9.2004
9
Chöông 11: Giao ñieåm cuûa hai ñoaïn
thaúng
Xaùc ñònh hai ñoaïn thaúng coù caét nhau khoâng (tieáp)
p3
p2
(p3 - p1) (p2 - p1) < 0
(p4 - p1) (p2 - p1) = 0
p4
p1
p4
p4
(p4 - p1) (p2 - p1) = 0
(p3 - p1) (p2 - p1) = 0
p2
p3
p3
p2
p1
p1
25.9.2004
10
Chöông 11: Giao ñieåm cuûa hai ñoaïn
thaúng
Xaùc ñònh hai ñoaïn thaúng coù caét nhau khoâng (tieáp)
– Thuû tuïc ñeå kieåm tra hai ñoaïn thaúng p1p2 vaø p3p4 coù caét nhau
khoâng (maõ giaû). Thuû tuïc traû veà TRUE neáu hai ñoaïn thaúng caét nhau
vaø traû veà FALSE neáu chuùng khoâng caét nhau.
SEGMENTS-INTERSECT(p1, p2, p3, p4)
1
2
3
4
5
d1 DIRECTION(p3, p4, p1)
d2 DIRECTION(p3, p4, p2)
d3 DIRECTION(p1, p2, p3)
d4 DIRECTION(p1, p2, p4)
if ((d1 > 0 and d2 < 0) or (d1 < 0 and d2 > 0)) and
((d3 > 0 and d4 < 0) or (d3 < 0 and d4 > 0))
then return TRUE
6
(xem tieáp slide tôùi)
25.9.2004
11
Chöông 11: Giao ñieåm cuûa hai ñoaïn
thaúng
Xaùc ñònh hai ñoaïn thaúng coù caét nhau khoâng (tieáp)
(tieáp)
7
8
elseif d1 = 0 and ON-SEGMENT(p3, p4, p1)
then return TRUE
9
elseif d2 = 0 and ON-SEGMENT(p3, p4, p2)
then return TRUE
10
11
12
13
14
15
elseif d3 = 0 and ON-SEGMENT(p1, p2, p3)
then return TRUE
elseif d4 = 0 and ON-SEGMENT(p1, p2, p4)
then return TRUE
else return FALSE
25.9.2004
12
Chöông 11: Giao ñieåm cuûa hai ñoaïn
thaúng
Xaùc ñònh hai ñoaïn thaúng coù caét nhau khoâng (tieáp)
Thuû tuïc ON-SEGMENT
Input: pi , pj , pk , maø pk thaúng haøng vôùi ñoaïn pi pj
Output: TRUE neáu pk naèm treân ñoaïn pi pj
FALSE neáu pk naèm ngoaøi ñoaïn pi pj
DIRECTION(pi , pj , pk )
1 return (pk - pi ) (pj - pi )
ON-SEGMENT(pi , pj , pk )
1 if min(xi , xj ) xk max(xi , xj ) and min(yi , yj ) yk max(yi , yj )
2
3
then return TRUE
else return FALSE
25.9.2004
13
Chöông 11: Giao ñieåm cuûa hai ñoaïn
thaúng
13 trang
09/05/2022
2580
Bạn đang xem tài liệu "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", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_phan_tich_thiet_ke_giai_thuat_chuong_11_giao_diem.ppt
