Z´apadoˇcesk´a univerzita v Plzni Fakulta aplikovan´ych vˇed Katedra matematiky
´ ´I NEJKRATSˇ´ICH CEST HLEDAN ´ ´IKOVYCH ´ NA TROJUHELN S´IT´ICH Semestr´aln´ı pr´ace z pˇredmˇetu Matematick´e modelov´an´ı
Martina Smitkov´a, A06117
[email protected] Matematick´e inˇzen´yrstv´ı 1. u´nora 2007
1
´ Uvod — motivace hled´ an´ı nejkratˇ s´ı cesty
Hled´an´ı nejkratˇs´ıch cest je intenzivnˇe diskutovanou ot´azkou zejm´ena pˇri ˇreˇsen´ı navigaˇcn´ıch u ´loh – at’ uˇz m´ame na mysli historickou moˇreplavbu ˇci modern´ı navigaci pomoc´ı glob´aln´ıho polohov´eho syst´emu GPS. Odjakˇziva bylo potˇreba dostat se z v´ ychoz´ıho do c´ılov´eho m´ısta co nejrychleji a s co nejmenˇs´ımi n´aklady na cestu a tyto d˚ uvody podnˇecovaly a st´ale podnˇecuj´ı z´ajem o problematiku nejkratˇs´ıch cest. V geod´ezii se tento probl´em ˇreˇs´ı jiˇz velice dlouho a je zn´am´ y pod n´azvem druh´ a z´akladn´ı geodetick´ au ´loha – ze zadan´ ych souˇradnic koncov´ ych bod˚ u je u ´kolem vypoˇc´ıtat d´elku geodetick´e kˇrivky mezi tˇemito dvˇema body a azimuty kˇrivky v koncov´ ych bodech. Na klasick´ ych referenˇcn´ıch ploch´ach je tato u ´loha jednoduˇse ˇreˇsiteln´a – v rovinˇe pˇrevodem kart´ezsk´ ych souˇradnic na pol´arn´ı, na kulov´e ploˇse pomoc´ı apar´atu sf´erick´e trigonometrie a na rotaˇcn´ım elipsoidu numerick´ ym ˇreˇsen´ım soustavy obyˇcejn´ ych diferenci´aln´ıch rovnic.
2
TIN — model zemsk´ eho povrchu
Abychom mohli nejkratˇs´ı cesty hledat co nejpˇresnˇeji, pouˇzijeme lok´aln´ı vektorov´ y model zemsk´eho povrchu – nepravidelnou troj´ uheln´ıkovou s´ıt’ neboli TIN (z anglick´eho Triangular Irregular Network). TIN reprezentuje povrch jako soubor troj´ uheln´ık˚ u, z nichˇz kaˇzd´ y je definov´an tˇremi vrcholy – body o zn´am´ ych prostorov´ ych souˇradnic´ıch. Kaˇzd´a hrana v TIN (s v´ yjimkou ob” vodu“ TIN) je sd´ılena pr´avˇe dvˇema sousedn´ımi troj´ uheln´ıky. V´ yhodou tohoto modelu je vˇern´ y a pˇresn´ y popis tvar˚ u zemsk´eho povrchu a optimalizace uloˇzen´ı dat, jeho nev´ yhodou je sloˇzitost datov´e struktury a t´ım i algoritm˚ u s n´ı pracuj´ıc´ıch.
1
Obr´azek 1: Pˇr´ıklad TIN.
3
Hled´ an´ı nejkratˇ s´ı cesty na TIN
Vstupem u ´lohy hled´an´ı nejkratˇs´ı cesty na TIN je TIN a dva r˚ uzn´e body na TIN – v´ ychoz´ı bod a c´ılov´ y bod, v´ ystupem je nejkratˇs´ı cesta po TIN mezi tˇemito dvˇema body. Nepovinn´ ym vstupem m˚ uˇze b´ yt v´ahov´a funkce F , kter´a pro kaˇzd´ y vrchol TIN definuje moˇznou rychlost pohybu v tomto vrcholu (napˇr´ıklad v z´avislosti na prostupnosti ter´enu). V´ ystupem pak je nejkratˇs´ı v´aˇzen´a cesta, kter´a minimalizuje celkov´ y ˇcas cesty mezi dan´ ymi dvˇema body. Ve sv´e pr´aci probl´em hled´an´ı nejkratˇs´ı cesty na TIN ˇreˇs´ım ve dvou kroc´ıch: 1. V´ ypoˇcet ˇcasov´e funkce T , kter´a pro kaˇzd´ y vrchol TIN ud´av´a minim´aln´ı ˇcas cesty do v´ ychoz´ıho bodu. 2. Vlastn´ı v´ ypoˇcet nejkratˇs´ı cesty – n´avrat“ z c´ılov´eho do v´ ychoz´ıho ” bodu pod´el z´apornˇe vzat´eho gradientu funkce T – gradient ud´av´a smˇer nejvˇetˇs´ı zmˇeny funkce T a tedy i lok´aln´ı smˇer nejkratˇs´ı cesty.
3.1 3.1.1
V´ ypoˇ cet ˇ casov´ e funkce T Formulace u ´ lohy
ˇ Uvaˇzujme rovinu xy. Casov´ a funkce T (x, y) pro kaˇzd´ y bod (x, y) ud´av´a nejkratˇs´ı ˇcas, ve kter´em je moˇzn´e se dostat z v´ ychoz´ıho bodu do tohoto bodu. Odvod´ıme nyn´ı rovnici pro funkci T . Pouˇzijeme-li zn´am´ y vztah, ˇze vzd´ alenost = rychlostסcas, pak v jednorozmˇern´em pˇr´ıpadˇe dost´av´ame 2
dT = 1. (1) dx Ve v´ıce dimenz´ıch plat´ı, ˇze ∇T je ortogon´aln´ı k hladin´am funkce T a podobnˇe F
jako v pˇredchoz´ım pˇr´ıpadˇe je jeho velikost nepˇr´ımo u ´mˇern´a rychlosti, tedy |∇T | F = 1,
T = 0 v A,
(2)
kde A je v´ ychoz´ı bod. Rovnici |∇T | F = 1 se ˇr´ık´a eikonalov´ a rovnice. Budeme ji numericky ˇreˇsit na TIN. 3.1.2
Sch´ ema pro jednoduchou troj´ uheln´ıkovou s´ıt’
Uvaˇzujme jednoduchou troj´ uheln´ıkou s´ıt’ jako na obr´azku 2.
D
A
B
X
C
Obr´azek 2: Jednoduch´a troj´ uheln´ıkov´a s´ıt’. Zamˇeˇrme se na troj´ uheln´ık tvoˇren´ y body X, A a C s hodnotami TX , TA a TC a pˇredpokl´adejme, ˇze hodnoty TA a TC jsou zn´am´e a ˇze hodnotu TX chceme urˇcit. Pˇredstavme si, ˇze hodnoty T v tˇechto tˇrech bodech definuj´ı jakousi rovinu, kart´ezsk´ y souˇradnicov´ y syst´em m´a poˇca´tek v bodˇe X a plat´ı |AX| = |CX| = h. Rovnice roviny vyj´adˇren´e jako funkce dvou promˇenn´ ych pak je µ
TX − TA h
¶
µ x+
TX − TC h 3
¶ y + TX = T (x, y).
(3)
Gradient t´eto funkce je µ ∇T =
TX − TA TX − TC , h h
¶ .
(4)
ˇ s´ıme eikonalovou diferenci´aln´ı rovnici |∇T | F = 1, mus´ı tedy platit Reˇ µ
¶2 µ ¶2 TX − TA TX − TC 1 + = 2. (5) h h F Lze ˇr´ıci, ˇze hledanou hodnotou TX ≥ TA , TC zdvih´ame rovinu tak, aby velikost gradientu byla rovna 1/F . 3.1.3
Sch´ ema pro ostro´ uhlou TIN
Ostro´ uhlou TIN rozumˇejme TIN, jej´ıˇz troj´ uheln´ıky nejsou tupo´ uhl´e. Uvaˇzujme troj´ uheln´ıkovou s´ıt’ jako na obr´azku 3.
X
Obr´azek 3: Skupina troj´ uheln´ık˚ u okolo spoleˇcn´eho centr´aln´ıho bodu X. V obecnˇejˇs´ım pˇr´ıpadˇe ostro´ uhl´e TIN m˚ uˇze velk´e mnoˇzstv´ı troj´ uheln´ık˚ u sd´ılet centr´aln´ı bod (viz bod X na obr´azku 3). Pomoc´ı n´asleduj´ıc´ıho postupu, inspirovan´eho jednoduchou troj´ uheln´ıkovou s´ıt´ı z pˇredchoz´ı ˇca´sti, se pokouˇs´ıme vypoˇc´ıtat vhodnou hodnotu T pro centr´aln´ı bod z kaˇzd´eho troj´ uheln´ıku, kter´ y m´a vrchol v tomto centr´aln´ım bodˇe. M˚ uˇze ovˇsem doj´ıt k situaci, ˇze z r˚ uzn´ ych troj´ uheln´ık˚ u obdrˇz´ıme v´ıce r˚ uzn´ ych pˇr´ıpustn´ ych hodnot T a mus´ıme tedy jednu z nich vybrat – v tomto pˇr´ıpadˇe vol´ıme minimum z moˇzn´ ych hodnot T .
4
Uvaˇzujme netupo´ uhl´ y troj´ uheln´ık ABC (viz obr´azek 4), ve kter´em chceme urˇcit T (C). Pˇredpokl´adejme, ˇze T (B) > T (A) a u = T (B) − T (A). Pro T (C) plat´ı T (C) = T (A) + t. E I u B t
Ö
B H
a G è
G
h
C
b
D
A
h D
A
C
Obr´azek 4: Odvozen´ı vztahu pro v´ ypoˇcet funkce T na troj´ uheln´ıku. Obr´azek vlevo – rovinn´ y pohled na troj´ uheln´ık ABC, oznaˇcen´ı nˇekter´ ych bod˚ u, u ´seˇcek a u ´hl˚ u. Obr´azek vpravo – prostorov´ y pohled na troj´ uheln´ık ABC, oznaˇcen´ı dalˇs´ıch bod˚ u a u ´seˇcek. Plat´ı t = |CE| = T (C) − T (A) a u = |BI| = T (B) − T (A). Body A, E a I definuj´ı myˇslenou rovinu funkce T nad“ troj´ uheln´ıkem ABC. ” Pro myˇslenou rovinu funkce T nad“ troj´ uheln´ıkem ABC plat´ı ” t−u , (6) h kde h je v´ yˇska v troj´ uheln´ıku BCD. Hled´ame tedy t = |EC|, kter´e splˇ nuje |∇T | =
eikonalovou rovnici 1 t−u = . (7) h F Oznaˇcme a = |BC| a b = |AC|. Z podobnosti troj´ uheln´ık˚ u AEC a AHD plyne 5
t |DH| = , b |AD|
(8)
takˇze |CD| = b − |AD| = b −
bu b(t − u) = . t t
(9)
Z kosinov´e vˇety plyne |BD|2 = a2 + |CD|2 − 2a|CD| cos θ
(10)
a ze sinov´e vˇety sin φ =
|CD| sin θ. |BD|
(11)
Potom z pravo´ uhl´eho troj´ uheln´ıka CBG dost´av´ame h = a sin φ = a
|CD| a|CD| sin θ . sin θ = p |BD| a2 + |CD|2 − 2a|CD| cos θ
(12)
Po dosazen´ı za h z rovnice (7) a za |CD| z rovnice (9) a jednoduch´ ych u ´prav´ach m´ame kvadratickou rovnici pro t:
2
2
2
2
F (a + b − 2ab cos θ) t + +2buF 2 (a cos θ − b) t+
= 0.
(13)
+b2 (u2 F 2 − a2 sin θ) ˇ sen´ı t mus´ı splˇ Reˇ novat nerovnost t > u a d´ale poˇzadujeme, aby z´apornˇe vzat´ y vektor gradientu smˇeˇroval dovnitˇr troj´ uheln´ıku, coˇz zajist´ıme pomoc´ı t´eto nerovnice: b(t − u) a < . t cos θ Dost´av´ame tedy n´asleduj´ıc´ı zp˚ usob v´ ypoˇctu: a cos θ <
Pokud u < t a z´aroveˇ n a cos θ <
b(t − u) a < , t cos θ
6
(14)
pak T (C) = min {T (C), T (A) + t}; ½ ¾ b a jinak T (C) = min T (C), T (A) + , T (B) + . F F Poˇrad´ı, v jak´em budeme v jednotliv´ ych bodech troj´ uheln´ıkov´e s´ıtˇe poˇc´ıtat hodnotu funkce T je urˇceno principem metody Fast Marching, detailnˇe rozebran´e v [3]. 3.1.4
Rozˇ s´ıˇ ren´ı pro obecnou TIN
V [3] je velmi struˇcnˇe naznaˇceno, jak rozˇs´ıˇrit metodu tak, aby bylo moˇzn´e ji pouˇz´ıt i pro obecnˇe tupo´ uhlou TIN. Nejjednoduˇsˇs´ı zp˚ usob je pˇretvoˇrit tupo´ uhlou TIN na ostro´ uhlou a t´ımto pˇrev´est probl´em na jiˇz vyˇreˇsen´ y pˇr´ıpad ostro´ uhl´e TIN. Jinou moˇznost´ı je pomoc´ı rozvinov´an´ı sousedn´ıch troj´ uheln´ık˚ u do jedn´e roviny pˇrid´avat jak´esi virtu´ aln´ı hrany, kter´e tup´e u ´hly v troj´ uheln´ıc´ıch rozdˇel´ı na dva ostr´e. Problematikou tupo´ uhl´e TIN jsem se ale nezab´ yvala.
3.2
Vlastn´ı v´ ypoˇ cet nejkratˇ s´ı cesty
Vu ´vodu t´eto kapitoly bylo uvedeno, ˇze v´ ypoˇcet nejkratˇs´ı cesty vlastnˇe znamen´a n´avrat“ z c´ılov´eho do v´ ychoz´ıho bodu pod´el z´apornˇe vzat´eho gra” dientu ˇcasov´e funkce T – gradient ud´av´a smˇer nejvˇetˇs´ı zmˇeny funkce T a tedy i lok´aln´ı smˇer nejkratˇs´ı cesty. Matematicky ˇreˇceno – ˇreˇs´ıme soustavu obyˇcejn´ ych diferenci´aln´ıch rovnic dX(s) = −∇T, ds kde X(s) popisuje nejkratˇs´ı cestu z c´ılov´eho do v´ ychoz´ıho bodu.
3.3
(15)
Aproximace gradientu funkce T
K ˇreˇsen´ı diferenci´aln´ı rovnice pouˇzijeme sch´ema druh´eho ˇra´du s pˇr´ıpadn´ ym pˇrep´ın´an´ım na sch´ema prvn´ıho ˇr´adu.
7
3.3.1
Sch´ ema prvn´ıho ˇ r´ adu
Funkci T pro jednotliv´e troj´ uheln´ıky nahrazujeme rovinou o rovnici Ax + By + C = T,
(16)
kde koeficienty A, B a C urˇc´ıme ze souˇradnic vrchol˚ u dan´eho troj´ uheln´ıka (viz obr´azek 5) a z hodnot funkce T v tˇechto vrcholech jako ˇreˇsen´ı soustavy rovnic Ax1 + By1 + C = T1 Ax2 + By2 + C = T2
(17)
Ax3 + By3 + C = T3 Pro gradient pak plat´ı ∇T ≈ (A, B)
(18)
V3
V2 V1
Obr´azek 5: Troj´ uheln´ık pro v´ ypoˇcet ∇T .
3.3.2
Sch´ ema druh´ eho ˇ r´ adu
Nyn´ı funkci T pro jednotliv´e troj´ uheln´ıky nahrazujeme plochou druh´eho stupnˇe o rovnici Ax2 + By 2 + Cxy + Dx + Ey + F = T,
(19)
kde koeficienty A, B, C, D, E a F urˇc´ıme ze souˇradnic vrchol˚ u dan´eho troj´ uheln´ıka a tˇr´ı okoln´ıch troj´ uheln´ık˚ u (viz obr´azek 6) a z hodnot funkce T v tˇechto vrcholech jako ˇreˇsen´ı soustavy rovnic 8
Ax2i + Byi2 + Cxi yi + Dxi + Eyi + F = Ti
i = 1, . . . , 6
(20)
Pro gradient pak plat´ı ∇T ≈ (2Ax + Cy + D, 2By + Cx + E)
(21)
V5
V3 V6
V2 V1 V4
ˇ rice troj´ Obr´azek 6: Ctveˇ uheln´ık˚ u pro v´ ypoˇcet ∇T . Nesm´ı ovˇsem doj´ıt k situaci jako na obr´azku 7. Plocha by byla urˇcena jen pˇeti body a soustava rovnic by mˇela nekoneˇcnˇe mnoho ˇreˇsen´ı. V t´eto situaci je nutn´e vyvolat v´ ypoˇcet prostˇrednictv´ım sch´ematu prvn´ıho ˇra´du. V3 V5
V2
V1
V4
Obr´azek 7: Situace, kdy nen´ı moˇzn´e pouˇz´ıt sch´ema druh´eho ˇra´du.
3.4
V´ ypoˇ cet jednotliv´ ych bod˚ u nejkratˇ s´ı cesty
Nejkratˇs´ı cestu do v´ ychoz´ıho bodu pak z´ısk´ame n´asleduj´ıc´ım zp˚ usobem: 1. Zvol´ıme troj´ uheln´ık v TIN. Jeho tˇeˇziˇstˇe bude bodem G1 – prvn´ım bodem nejkratˇs´ı cesty. Pro tento troj´ uheln´ık vypoˇcteme aproximaci 9
gradientu funkce T . Bod G1 a z´apornˇe vzat´ y vektor gradientu urˇcuj´ı pˇr´ımku, urˇc´ıme tedy pr˚ useˇc´ık t´eto pˇr´ımky s nˇekterou ze stran v´ ychoz´ıho troj´ uheln´ıka. Nalezen´ y pr˚ useˇc´ık je bodem G2 – druh´ ym bodem nejkratˇs´ı cesty.
G2 G1
–∇T
Obr´azek 8: Poˇc´atek v´ ypoˇctu jednotliv´ ych bod˚ u nejkratˇs´ı cesty. 2. M´ame urˇcen´ y bod Gi – i-t´ y bod nejkratˇs´ı cesty a hled´ame bod Gi+1 . Bod Gi leˇz´ı na hranˇe, kter´a je spoleˇcn´a dvˇema troj´ uheln´ık˚ um – pˇres jeden troj´ uheln´ık jsme jiˇz nejkratˇs´ı cestou pˇreˇsli a nyn´ı chceme pˇrej´ıt pˇres druh´ y. Podobnˇe jako v pˇredchoz´ım pˇr´ıpadˇe urˇc´ıme aproximaci gradientu funkce T pro troj´ uheln´ık, pˇres kter´ y chceme nyn´ı pˇrej´ıt, a pomoc´ı bodu Gi a z´apornˇe vzat´eho vektoru gradientu vyj´adˇr´ıme pˇr´ımku a vypoˇcteme jej´ı pr˚ useˇc´ık s nˇekterou ze zbyl´ ych dvou hran troj´ uheln´ıka. Nalezen´ y pr˚ useˇc´ık je bodem Gi+1 – dalˇs´ım bodem nejkratˇs´ı cesty.
Gi–2
Gi Gi–1
Gi+1
–∇T
Obr´azek 9: Pr˚ ubˇeh v´ ypoˇctu jednotliv´ ych bod˚ u nejkratˇs´ı cesty.
´kol se dostat, 3. Jsme-li jiˇz dostateˇcnˇe bl´ızko bodu, do kter´eho m´ame za u pak tento bod pˇrid´ame jako posledn´ı bod do hledan´e nejkratˇs´ı cesty a ukonˇc´ıme v´ ypoˇcet. 10
4
Implementace a v´ ysledky
Pro testovac´ı u ´ˇcely byla pouˇzita jednoduch´a rovinn´a TIN sloˇzen´a z rovnostrann´ ych troj´ uheln´ık˚ u – viz obr´azek 10.
0.5
0
−0.5 2.5 2
2.5 1.5
2 1.5
1 1
0.5
0.5 0
0
Obr´azek 10: Jednoduch´a rovinn´a TIN.
4.1
V´ ypoˇ cet bez v´ ahov´ e funkce F
Budeme-li jako v´ ychoz´ı bod uvaˇzovat vrchol uprostˇred t´eto TIN a budeme-li pˇredpokl´adat, ˇze v´ahov´a funkce F = 1, pak by hodnota ˇcasov´e funkce T v kaˇzd´em vrcholu TIN mˇela b´ yt rovna vzd´alenosti tohoto vrcholu od v´ ychoz´ıho bodu. Vizualizace pˇresn´eho ˇreˇsen´ı je na obr´azku 11. Vizualizace ˇreˇsen´ı eikonalov´e rovnice metodou Fast Marching bez uvaˇzov´an´ı v´ahov´e funkce F je na obr´azku 12. Odchylky tˇechto dvou ˇreˇsen´ı jsou zn´azornˇeny na obr´azku 13. Je vidˇet, ˇze odchylky jsou z´avisl´e na poloze bod˚ u v TIN.
11
1.6 1.4 0.5
1.2 1
0
0.8 −0.5 2.5
0.6 2
2.5 1.5
2
0.4
1.5
1
0.2
1
0.5
0.5 0
0
Obr´azek 11: Pˇresn´e ˇreˇsen´ı rovnice |∇T | = 1 na jednoduch´e TIN.
1.6 1.4 0.5
1.2 1
0
0.8 −0.5 2.5
0.6 2
2.5 1.5
2
0.4
1.5
1
1
0.5
0.2
0.5 0
0
Obr´azek 12: V´ ysledek numerick´eho v´ ypoˇctu funkce T na TIN. 12
0.03 0.025
0.5
0.02
0
0.015
−0.5 2.5
0.01 2.5
2 1.5
2 1.5
1
1
0.5
0.005
0.5 0
0
Obr´azek 13: Odchylky mezi pˇresn´ ym a pˇribliˇzn´ ym ˇreˇsen´ım.
4.2
V´ ypoˇ cet s v´ ahovou funkc´ı F
Nyn´ı budeme uvaˇzovat netrivi´aln´ı v´ahovou funkce F . Funkce F je zn´azornˇen´a na obr´azku 14. V´ ysledn´a funkce T je na obr´azku 15.
4.3
Prostorov´ a TIN
Nemus´ıme se samozˇrejmˇe omezovat jen na rovinnou TIN, algoritmus pro v´ ypoˇcet ˇcasov´e funkce T je urˇcen pro prostorovou TIN. Uk´azka v´ ypoˇctu funkce T na prostorov´e TIN je na obr´azc´ıch 16 aˇz 19.
13
1.5 1.4 1.3
0.5
1.2 0
1.1 1
−0.5 2.5
0.9 2 1.5
2
2.5 0.8
1.5
1
0.7
1
0.5
0.6
0.5 0
0
Obr´azek 14: V´ahov´a funkce F na TIN.
1.6 1.4 0.5
1.2 1
0
0.8 −0.5 2.5
0.6 2
2.5 1.5
2
0.4
1.5
1
1
0.5
0.2
0.5 0
0
Obr´azek 15: V´ ypoˇcet ˇcasov´e funkce T na TIN s u ´vahou v´ahov´e funkce F . 14
1.8 1.6 1.4 0.5 1.2 0
1 0.8
−0.5 2.5
0.6 2
2.5 1.5
2
0.4
1.5
1
1
0.5
0.2
0.5 0
0
Obr´azek 16: V´ ypoˇcet ˇcasov´e funkce T na prostorov´e TIN.
140 120 40 100
20 0
80
−20
60
−40
40
40 20
40 20
0
20
0
−20 −40
−20 −40
Obr´azek 17: V´ ypoˇcet ˇcasov´e funkce T na triangulovan´e kulov´e ploˇse. 15
6
5
40 20
4
0 3 −20 −40
2
40 20
40 20
0
1
0
−20 −40
−20 −40
Obr´azek 18: V´ahov´a funkce F na triangulovan´e kulov´e ploˇse.
Obr´azek 19: V´ ypoˇcet ˇcasov´e funkce T na TIN s u ´vahou v´ahov´e funkce F . 16
4.4
V´ ypoˇ cet nejkratˇ s´ı cesty na TIN
Chyb´ı uˇz jen posledn´ı krok – pomoc´ı vypoˇcten´e funkce T zaˇc´ıt konstruovat nejkratˇs´ı cesty na TIN podle algoritmu popsan´eho v ˇca´sti 3.2. V´ ysledky jsou vizualizov´any na n´asleduj´ıc´ıch obr´azc´ıch.
Obr´azek 20: Nejkratˇs´ı cesty na rovinn´e TIN.
17
Obr´azek 21: Nejkratˇs´ı v´aˇzen´e cesty na rovinn´e TIN.
Obr´azek 22: Nejkratˇs´ı cesty na prostorov´e TIN. 18
Obr´azek 23: Nejkratˇs´ı cesty na triangulovan´e kulov´e ploˇse.
Obr´azek 24: Nejkratˇs´ı v´aˇzen´e cesty na triangulovan´e kulov´e ploˇse. 19
5
Z´ avˇ er — vyuˇ zitelnost z´ıskan´ ych v´ ysledk˚ u
V t´eto pr´aci byl navrˇzen a implementov´an postup, jak naj´ıt nejkratˇs´ı spojnici mezi dan´ ymi dvˇema body na troj´ uheln´ıkov´e s´ıti. Vyuˇzit´ı tohoto postupu je moˇzn´e nal´ezt napˇr´ıklad v oblasti turistick´ ych GPS pˇr´ıstroj˚ u. Klasick´ y GPS pˇr´ıstroj hled´a nejkratˇs´ı cestu mezi dvˇema body v pr˚ umˇetu na referenˇcn´ı elipsoid, takˇze pˇri v´ ypoˇctu cesty nebere ohled na ter´enn´ı reli´ef ani na rozm´ıstˇen´ı vodstva, vegetace a podobnˇe. Pokud bychom GPS pˇr´ıstroji dodali informaci o reli´efu ve formˇe troj´ uheln´ıkov´e s´ıtˇe a informaci o pr˚ uchodnosti ter´enu ve formˇe v´ahov´e funkce, bylo by moˇzn´e vyuˇzit´ım zde popsan´eho postupu hledat nejkratˇs´ı cestu mezi dan´ ymi dvˇema body pˇresnˇeji neˇz dosud.
Literatura [1] KIMMEL, Ron – SETHIAN, James. Computing Geodesic Paths on Manifolds. Proceedings of National Academy of Sciences, USA, 95(15): 84318435, 1998. [2] SETHIAN, James. Fast Marching Methods. SIAM Review. Vol. 41, No. 2, pp. 199–235. Society for Industrial and Applied Mathematics. Philadelphia, 1999. [3] SETHIAN, James. Level Set Methods and Fast Marching Methods. Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision and Materials Science. 2nd edition. Cambridge University Press. Cambridge, 1999. ISBN 0-521-64204-3.
20
