›
›

Bài giảng Phân tích thiết kế giải thuật - Chương 11: Hình học tính toán

Download
Hình Hoïc Tính Toaùn  
13.11.2004  
1
35.2 Xaùc ñònh coù caëp ñoaïn thaúng naøo caét nhau khoâng  
Baøi toaùn: Cho taäp caùc ñoaïn thaúng trong maët phaúng. Xaùc ñònh coù caëp  
ñoaïn thaúng naøo caét nhau hay khoâng.  
ª Ñeå ñôn giaûn, giaû söû:  
– Khoâng coù ñoaïn thaúng naøo laø thaúng ñöùng  
– Khoâng coù ba ñoaïn thaúng naøo caét nhau taïi moät ñieåm chung.  
13.11.2004  
2
Chöông 35: Hình hoïc tính toaùn  
Giaûi thuaät thoâ sô  
ª Giaûi thuaät thoâ sô: Kieåm tra xem moãi caëp ñoaïn thaúng coù caét nhau hay  
khoâng. Thôøi gian chaïy laø (n2), vôùi n laø soá caùc ñoaïn thaúng.  
13.11.2004  
3
Chöông 35: Hình hoïc tính toaùn  
Kyõ thuaät queùt  
ª Giaûi thuaät höõu hieäu duøng kyû thuaät queùt (sweeping):  
Duøng moät ñöoøng thaúng thaúng ñöùng queùt töø traùi sang phaûi vaø xem xeùt  
caùc thay ñoåi cuûa phaàn giao cuûa ñöôøng thaúng queùt vôùi caùc ñoaïn thaúng.  
– Ñöôøng thaúng queùt (sweep line)  
°
Ñöôøng thaúng queùt thaúng ñöùng, vò trí hieän thôøi laø toaï ñoä x  
x
13.11.2004  
4
Chöông 35: Hình hoïc tính toaùn  
Thöù töï caùc ñoaïn thaúng  
°
Ñònh nghóa moät thöù töï hoaøn toaøn treân caùc ñoaïn thaúng caét bôûi  
ñöôøng thaúng queùt.  
– Hai ñoaïn thaúng s1 vaø s2 khoâng caét nhau laø coù theå so saùnh  
ñöôïc taïi x neáu ñöôøng thaúng queùt taïi vò trí x caét caû hai ñoaïn  
thaúng ñoù.  
s1  
s2  
– Neáu s1 vaø s2 laø coù theå so saùnh ñöôïc taïi x vaø giao ñieåm cuûa  
s1 vôùi ñöôøng thaúng queùt ôû cao hôn giao ñieåm cuûa s2 vôùi  
cuøng ñöôøng thaúng queùt ñoù, thì ta noùi s1 ôû treân s2 , kyù hieäu s1  
>x s2 .  
13.11.2004  
5
Chöông 35: Hình hoïc tính toaùn  
Thöù töï caùc ñoaïn thaúng (tieáp)  
e
d
g
a
i
b
h
c
f
r
t u  
v z  
w
(b)  
(a)  
b >u c  
e >v f nhöng f > e  
a >t b  
b >t c  
a >t c  
a >r c  
Moïi ñöôøng thaúng queùtwmaø ñi qua vuøng  
xaùm ñeàu coù caùc ñoaïn thaúng e vaø f ôû  
lieân tieáp nhau trong quan heä thöù töï cuûa  
noù  
Ñoaïn thaúng d khoâng so saùnh ñöôïc vôùi  
caùc ñoaïn thaúng khaùc trong hình (a).  
13.11.2004  
6
Chöông 35: Hình hoïc tính toaùn  
Caùc caáu truùc döõ lieäu trong kyõ thuaät queùt  
– Ñöôøng thaúng queùt  
°
Khi di chuyeån ñöôøng thaúng queùt, giaûi thuaät tröõ vaø duy trì caùc  
thoâng tin sau  
– Tình traïng cuûa ñöôøng thaúng queùt (sweep-line status): cho  
bieát thöù töï giöõa caùc ñoái töôïng (ñoaïn thaúng) bò caét bôûi ñöôøng  
thaúng queùt vôùi nhau  
– Lòch cuûa caùc bieán coá (event-point schedule): daõy caùc toïa ñoä  
x, saép töø traùi sang phaûi, xaùc ñònh caùc vò trí döøng cuûa ñöôøng  
thaúng queùt.  
13.11.2004  
7
Chöông 35: Hình hoïc tính toaùn  
Caùc thao taùc leân sweep-line status  
ª Chi tieát giaûi thuaät höõu hieäu duøng kyû thuaät queùt  
– Ñöôøng thaúng queùt  
°
Khi di chuyeån ñöôøng thaúng queùt, giaûi thuaät tröõ vaø duy trì caùc  
thoâng tin sau  
– Tình traïng cuûa ñöôøng thaúng queùt (sweep-line status): Caùc  
thao taùc leân T:  
°
°
°
°
INSERT(T, s): cheøn ñoaïn thaúng s vaøo T  
DELETE(T, s): xoaù ñoaïn thaúng s khoûi T  
ABOVE(T, s): traû veà ñoaïn thaúng ôû ngay treân s trong T  
BELOW(T, s): traû veà ñoaïn thaúng ôû ngay döôùi s trong T.  
13.11.2004  
8
Chöông 35: Hình hoïc tính toaùn  
Event-point schedule  
– Lòch cuûa caùc bieán coá (event-point schedule): daõy caùc toïa ñoä  
x, saép töø traùi sang phaûi, xaùc ñònh caùc vò trí döøng cuûa ñöôøng  
thaúng queùt.  
°
Moãi ñieåm ñaàu muùt cuûa caùc ñoaïn thaúng (cuûa taäp input S)  
laø moät ñieåm bieán coá (event point), laø ñieåm maø thöù töï T  
thay ñoåi.  
°
Lòch cuûa caùc bieán coá laø tónh vaø ñöôïc xaây döïng baèng  
caùch saép xeáp caùc ñieåm ñaàu muùt cuûa caùc ñoaïn thaúng theo  
thöù töï töø traùi qua phaûi.  
13.11.2004  
9
Chöông 35: Hình hoïc tính toaùn  
Xaùc ñònh coù caëp ñoaïn thaúng naøo caét nhau khoâng  
ANY-SEGMENTS-INTERSECT(S)  
1 T    
2 Saép caùc ñieåm ñaàu muùt cuûa caùc ñoaïn thaúng trong S theo  
thöù töï töø traùi sang phaûi, breaking ties...  
3 for moåi ñieåm p trong danh saùch saép xeáp cuûa caùc ñieåm ñaàu muùt  
4
5
6
do if p laø ñieåm ñaàu muùt beân traùi cuûa ñoaïn thaúng s  
then INSERT(T, s)  
if (ABOVE(T, s) toàn taïi vaø caét s)  
hay (BELOW(T, s) toàn taïi vaø caét s)  
then return TRUE  
7
8
9
if p laø ñieåm ñaàu muùt beân phaûi cuûa ñoaïn thaúng s  
then if caû hai ABOVE(T, s) vaø BELOW(T, s) ñeàu toàn taïi  
vaø ABOVE(T, s) caét BELOW(T, s)  
then return TRUE  
10  
11  
DELETE(T, s)  
12 return FALSE  
13.11.2004  
10  
Chöông 35: Hình hoïc tính toaùn  
Thöïc thi ANY-SEGMENTS-INTERSECT  
e
d
a
c
f
b
a
a
b
a
c
b
d
a
c
b
d
c
b
e
d
c
b
e
d
b
thôøi gian  
13.11.2004  
11  
Chöông 35: Hình hoïc tính toaùn  
Breaking ties  
ª Neáu khi saép xeáp caùc ñieåm ñaàu muùt cuûa caùc ñoaïn thaúng trong S töø traùi  
sang phaûi maø coù nhieàu ñieåm coù cuøng toïa ñoä x thì breaking ties nhö  
sau  
– Caùc ñieåm ñaàu muùt beân traùi ñöôïc xeáp tröôùc caùc ñieåm ñaàu muùt beân  
phaûi.  
a
b
q
p
p ñöôïc xeáp tröôùc q khi saép xeáp caùc ñieåm ñaàu muùt  
ôû doøng 2 cuûa ANY-SEGMENTS-INTERSECT  
13.11.2004  
12  
Chöông 35: Hình hoïc tính toaùn  
Tính ñuùng ñaén  
ª Theorem 35.1 (Tính ñuùng ñaén)  
Giaûi thuaät ANY-SEGMENTS-INTERSECT chaïy treân taäp S traû veà TRUE  
neáu vaø chæ neáu coù caét nhau giöûa caùc ñoaïn thaúng.  
ª Chöùng minh  
“”: xem maõ ta thaáy ANY-SEGMENTS-INTERSECT traû veà TRUE chæ khi  
naøo noù tìm thaáy hai ñoaïn thaúng caét nhau.  
“”: Seõ chöùng minh raèng neáu toàn taïi hai ñoaïn thaúng caét nhau thì  
ANY-SEGMENTS-INTERSECT traû veà TRUE.  
13.11.2004  
13  
Chöông 35: Hình hoïc tính toaùn  
Tính ñuùng ñaén (tieáp)  
Giaû söû toàn taïi moät giao ñieåm.  
Goïi p laø giao ñieåm beân traùi nhaát, goïi a vaø b laø caùc ñoaïn thaúng caét  
nhau taïi p.  
Toàn taïi ñöôøng queùt z maø taïi ñoù a vaø b trôû neân lieân tieáp nhau trong thöù  
töï toaøn phaàn.  
Toàn taïi ñieåm ñaàu muùt q maø laø event point ñeå cho a vaø b trôû neân lieân  
tieáp nhau trong thöù töï toaøn phaàn.  
a
p
b
z
Coù 2 tröôøng hôïp: A) giaûi thuaät xöû lyù q vaø B) giaûi thuaät khoâng xöû lyù q.  
13.11.2004  
14  
Chöông 35: Hình hoïc tính toaùn  
Tính ñuùng ñaén (tieáp)  
A)  
Tröôøng hôïp 1: ñoaïn thaúng a hay b ñöôïc cheøn vaøo T, vaø ñoaïn thaúng  
kia ôû treân hay döôùi noù. Caùc doøng 4-7 tìm thaáy tröôøng hôïp naøy.  
q
q
p
q
p
p
z
z
z
p
p
q
p
q
q
z
z
z
13.11.2004  
15  
Chöông 35: Hình hoïc tính toaùn  
Tính ñuùng ñaén (tieáp)  
Tröôøng hôïp 2: caùc ñoaïn thaúng a vaø b ñang trong T, vaø moät ñoaïn  
thaúng ôû giöõa chuùng ñöôïc xoùa. Caùc doøng 8-11 tìm thaáy tröôøng hôïp  
naøy.  
p
q
z
Trong caû hai tröôøng hôïp, giaûi thuaät tìm thaáy p vaø traû veà TRUE.  
B)  
Neáu q khoâng ñöôïc giaûi thuaät xöû lyù, thì coù nghóa laø giaûi thuaät ñaõ quay  
veà tröôùc khi xöû lyù xong taát caû caùc event points. Vaäy giaûi thuaät ñaõ tìm  
thaáy moät giao ñieåm vaø traû veà TRUE.  
13.11.2004  
16  
Chöông 35: Hình hoïc tính toaùn  
Phaân tích ANY-SEGMENTS-INTERSECT  
ª Thôøi gian chaïy  
– Giaû söû taäp ñoaïn thaúng S goàm coù n ñoaïn thaúng. Duøng caáu truùc döõ  
lieäu thích hôïp (ví duï: döïa treân caây nhò phaân caân baèng) ñeå hieän  
thöïc T sao cho caùc thao taùc leân T ñeàu toán O(lg n) thôøi gian.  
– Thôøi gian chaïy cuûa giaûi thuaät ANY-SEGMENTS-INTERSECT goàm  
°
°
°
Doøng 1: O(1) thôøi gian  
Doøng 2: O(n lg n) thôøi gian  
Voøng laëp for: O(n lg n) thôøi gian  
Vaäy thôøi gian chaïy toång coäng cuûa giaûi thuaät laø O(n lg n).  
13.11.2004  
17  
Chöông 35: Hình hoïc tính toaùn  
35.4 Tìm bao loài  
ª Töï ñoïc.  
13.11.2004  
18  
Chöông 35: Hình hoïc tính toaùn  
35.4 Tìm caëp ñieåm gaàn nhau nhaát  
ª Töï ñoïc.  
13.11.2004  
19  
Chöông 35: Hình hoïc tính toaùn  
ppt 19 trang baolam 09/05/2022 2220
Download
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: Hình học tính toán", để 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:

  • pptbai_giang_phan_tich_thiet_ke_giai_thuat_chuong_11_hinh_hoc_t.ppt