i
i
“Gora” — 2012/3/15 — 10:42 — page 1 — #1 i
i
i
i
i
i
Z NAJMANJ TRUDA NA ŠMARNO GORO!
GAŠPER JAKLIČ1,2,3, TADEJ KANDUČ4,
SELENA PRAPROTNIK2 IN EMIL ŽAGAR1,2
1Fakulteta za matematiko in fiziko, Univerza v Ljubljani
2Inštitut za matematiko, fiziko in mehaniko
3Primorski inštitut za naravoslovne in tehnične vede, Univerza na Primorskem
4Turboinštitut
Math. Subj. Class. (2010): 41A05, 41A15, 65D05, 65D07, 65D17
Iskanje krivulje na ploskvi z danimi omejitvami je v splošnem težak problem. Nanj
naletimo npr. v gradbenǐstvu pri gradnji cest in železnic po razgibanem terenu. V tem
članku se bomo omejili na problem iskanja vzpona na goro, pri katerem porabimo najmanj
energije.
Dane so diskretne meritve terena, na podlagi katerih s pomočjo makroelementov kon-
struiramo gladek opis reliefa. Energijski funkcional definiramo v odvisnosti od naklona
in dolžine poti. Z izračunom energije na robovih polinomskih ploskev zastavljeni problem
prevedemo na diskretni problem iskanja najceneǰse poti na mreži polinomskih krivulj. Nu-
merični rezultati kažejo, da se dobljene poti dobro ujemajo z naravnimi, kar predstavimo
na primeru realnih podatkov.
OPTIMAL MOUNTAIN ASCENT
Finding a curve on the surface with constraints is a difficult problem frequently enco-
untered in civil engineering at road and railway construction. In this article, an optimal
mountain ascent (in the sense of energy consumption) will be considered.
Discrete terrain data are given. A smooth terrain description is constructed using
macroelements. An energy functional which depends on terrain inclination and on path
length, is defined. By computing energy on the boundaries of polynomial patches, the
problem transforms into a discrete problem of finding the cheapest path on a mesh of
polynomial curves. Numerical results indicate that the resulting paths are good approxi-
mations of the natural routes. Some examples on real data are presented.
Uvod
Iskanje optimalne poti med danima točkama na ploskvi je težak problem.
Prva težava je predstavitev ploskve in s tem povezan zapis iskane krivulje,
vložene na ploskev. Druga težava je kriterij optimalnosti. Tu običajno
krivulji pripǐsemo energijski funkcional, s katerim utežimo dele krivulje glede
na izbrani kriterij. Bralec lahko več o energijskih funkcionalih krivulj in
ploskev izve v [2] ali [7].
Problem je zelo zanimiv v praksi, na primer pri načrtovanju ceste ali
železnice po razgibanem terenu. Tu je treba upoštevati več faktorjev, kot
Obzornik mat. fiz. 59 (2012) 1 1
i
i
“Gora” — 2012/3/15 — 10:42 — page 2 — #2 i
i
i
i
i
i
Gašper Jaklič, Tadej Kanduč, Selena Praprotnik in Emil Žagar
so omejitve naklona, radija ovinkov, geomorfološke lastnosti terena, cena
gradnje, ki je vǐsja tam, kjer je treba graditi mostove in tunele, optimiza-
cijo pri gradnji (izkop materiala, transport na drugo lokacijo in uporaba za
zasipanje).
V članku bomo obravnavali bolj enostaven problem, načrtovanje opti-
malne planinske poti na vrh gore. Kriterij za optimalnost bo poraba ener-
gije. Dobre planinske poti potekajo po naravnih prehodih, strme dele prema-
gajo z vzpenjanjem v ključih [4]. Predpostavili bomo, da strmina optimalne
poti ni večja od 45◦ in s tem ostali v mejah pohodnǐstva. Med klasične
kriterije optimizacije sicer spadajo zahteve, da je dolžina poti najkraǰsa, da
je čas vzpona minimalen, da je poraba energije (kalorij) čim manǰsa. Bralec
lahko nekaj o tem prebere v [5].
Zvezni variacijski problem iskanja optimalne poti bomo aproksimirali z
reševanjem diskretnih problemov. Površja hriba ne moremo opisati eksak-
tno, saj imamo običajno dano samo mrežo geodetskih podatkov, ponavadi
točk (xi, yi, zi). Zato je prvi korak interpolacija danih podatkov s primerno
ploskvijo, za kar bomo uporabili posebno vrsto nedavno razvitih dvorazse-
žnih zlepkov, makroelemente [6, 3]. Optimalno pot bomo iskali na krivočrtni
mreži njihovih robov.
S pomočjo energijskega funkcionala bomo izračunali porabo energije po
robovih. Optimizacijski problem bomo tako prevedli na diskretni problem
iskanja najceneǰse poti v omrežju, ki ga bomo ugnali z znanim Dijkstrovim
algoritmom.
Interpolacijski problem in makroelementi
V praksi terena nimamo danega v zaključeni obliki s predpisom. Običajno
v naravi izmerimo diskretne podatke, iz katerih nato aproksimiramo teren.
Relief območja določimo iz točk v prostoru (xi, yi, zi) ∈ R3, i = 1, 2, . . . , V .
Eden od načinov je iskanje interpolacijske ploskve, torej take, ki poteka skozi
dane točke. Običajno jo zapǐsemo v obliki odsekoma linearne ploskve, saj je
taka konstrukcija najbolj enostavna za uporabo. Vendar pa v tem primeru
dobimo le zvezno ploskev in za dobro aproksimacijo potrebujemo veliko me-
ritev. Ker bomo študirali krivulje, vložene na ploskev, potrebujemo večjo
fleksibilnost. Namesto linearnih bomo uporabili odsekoma polinomske plo-
skve (zlepke) vǐsjih stopenj. Tako lahko dobimo ploskev, ki je vsaj zvezno
odvedljiva, zato bodo tudi iskane krivulje bolj naravnih oblik.
2 Obzornik mat. fiz. 59 (2012) 1
i
i
“Gora” — 2012/3/15 — 10:42 — page 3 — #3 i
i
i
i
i
i
Z najmanj truda na Šmarno goro!
Zapǐsimo problem natančneje. Konveksno ovojnico danih točk vi :=
(xi, yi) v ravnini označimo z Ω.
Definicija 1. Funkciji
f : Ω ⊂ R2 → R,
ki zadošča pogojem
f(vi) = zi, i = 1, 2, . . . , V,
pravimo interpolacijska funkcija.
Razdelitvi območja Ω na trikotnike z oglǐsči v točkah vi pravimo trian-
gulacija območja Ω.
Definicija 2. Triangulacija je regularna, če je neprazen presek poljubnih
dveh različnih trikotnikov bodisi skupno oglǐsče bodisi skupna stranica.
Slika 1. Leva množica ni regularna triangulacija, desna je.
Na sliki 1 sta prikazana primera neregularne in regularne triangulacije.
Triangulacijo na točkah vi lahko izberemo na več načinov. Na sliki 2 sta
prikazani dve različni regularni triangulaciji na istih točkah. Desna trian-
gulacija je bolj simetrična. Izkaže se, da je zaradi numerične stabilnosti
bolje izbirati triangulacije s trikotniki, ki povezujejo bližnje točke in nimajo
premajhnih notranjih kotov. Izbira triangulacije močno vpliva na obliko
interpolacijske ploskve.
Nad dano triangulacijo želimo konstruirati gladko interpolacijsko funk-
cijo, katere zožitev na poljuben trikotnik triangulacije je dvorazsežni poli-
nom predpisane stopnje. Razredu takih funkcij pravimo zlepki.
1–10 3
i
i
“Gora” — 2012/3/15 — 10:42 — page 4 — #4 i
i
i
i
i
i
Gašper Jaklič, Tadej Kanduč, Selena Praprotnik in Emil Žagar
Slika 2. Dve različni triangulaciji istega območja glede na dane točke v ravnini. Desna
triangulacija je za interpolacijo primerneǰsa.
Glavne težave, ki nastanejo pri konstrukciji zlepka, so obstoj in enolič-
nost interpolanta, praviloma je treba reševati velik sistem linearnih enačb,
oblika zlepka pa ni odvisna samo od bližnjih podatkov (sprememba enega
interpolacijskega podatka lahko vpliva na obliko celotnega zlepka). Ome-
njenim težavam se izognemo tako, da za reševanje problema uporabimo
poseben razred gladkih zlepkov, makroelemente (slika 3). Makroelementi so
odsekoma polinomske funkcije, pri katerih se polinomi, definirani na sose-
dnjih trikotnikih triangulacije,
”
zlepijo“ gladko (po navadi vsaj enkrat zve-
zno odvedljivo), obenem pa je konstrukcija posameznih polinomskih delov
lokalna. To pomeni, da polinomsko funkcijo, ki definira del makroelementa
nad izbranim trikotnikom, določimo samo na podlagi podatkov nad tem tri-
kotnikom. Nad stranico, ki je skupna sosednjima trikotnikoma, uporabimo
Slika 3. Zvezen linearen interpolant (levo) in C1 gladek makroelement (desno).
4 Obzornik mat. fiz. 59 (2012) 1
i
i
“Gora” — 2012/3/15 — 10:42 — page 5 — #5 i
i
i
i
i
i
Z najmanj truda na Šmarno goro!
enake podatke za konstrukcijo obeh sosednjih polinomov. Zlepek je tako
odvisen le od lokalnih podatkov, pri reševanju interpolacijskega problema
pa je treba reševati le majhne sisteme linearnih enačb.
Dodatna prednost makroelementov je tudi enostaven in učinkovit po-
stopek subdivizije, tj. razbitja obstoječe ploskve na več manǰsih delov. Eno
izmed možnih subdivizij zlepka dobimo tako, da vsak trikotnik triangulacije
razbijemo na tri trikotnike (slika 4), kar razdeli tudi pripadajočo polinom-
sko ploskev. Ker z vsakim korakom subdivizije povečujemo število robnih
krivulj, lahko omenjeni postopek uporabimo za povečevanje natančnosti op-
timalne poti.
Slika 4. Osnovna triangulacija (levo) in en korak subdivizije (desno).
Energijski funkcional
Robne krivulje makroelementa so polinomske krivulje. Zanima nas energija,
ki jo porabimo za premik vzdolž ene od njih. Označimo porabo energije na
enotsko dolžino poti z M . Očitno je funkcija M odvisna od naklona te-
rena v smeri gibanja in ni simetrična glede na gibanje po klancu navzgor
ali navzdol. Intuitivno je najlažje gibanje po rahlem klancu navzdol, pri
velikih naklonih pa je gibanje navzgor lažje od gibanja navzdol. Z apro-
ksimacijo empiričnih meritev po metodi najmanǰsih kvadratov [4] dobimo
porabo energije za povprečnega pohodnika v obliki
M(s) = 0.2635 + 1.737 s + 4.237 s2 − 2.143 s3 + 1.493 s4.
V zgornji izražavi je s tangens naklonskega kota terena v smeri gibanja, M
pa merimo v kJ/m. S slike 5 vidimo, da se M obnaša po predvidevanjih. Iz
1–10 5
i
i
“Gora” — 2012/3/15 — 10:42 — page 6 — #6 i
i
i
i
i
i
Gašper Jaklič, Tadej Kanduč, Selena Praprotnik in Emil Žagar
-1.0 -0.5 0.5 1.0
1
2
3
4
5
6
Slika 5. Graf porabe energije na meter prehojene poti (kJ/m) v odvisnosti od naklona
poti. Pozitivni naklon pomeni gibanje po klancu navzgor.
izkušenj pričakujemo, da bomo pri nekem kritičnem naklonu začeli hoditi
v ključih, da bi se izognili prestrmi poti, in bomo kljub nekoliko dalǰsi poti
prihranili pri celotni porabi energije. Analiza poti s konstantnim naklonom
to potrdi [4]. Pri hoji navzgor je kritični naklonski kot enak 15.6◦, pri hoji
navzdol pa 12.5◦.
Naj bo r : [0, 1] → R3, kjer je r = (rx, ry, rz)T vektorska funkcija pa-
rametra t ∈ [0, 1], robna krivulja makroelementa. Naklon ϕ pri gibanju po
krivulji seveda ni konstanten, zato moramo uporabiti infinitezimalne pre-
mike. Prispevek energije E na delu loka krivulje d` je enak
dE(r) = M(s(t)) d`,
kjer je
s(t) = tanϕ(t) =
ṙz(t)√
ṙ2x(t) + ṙ
2
y(t)
.
Iz diferencialne geometrije vemo, da je
d` = ‖ṙ(t)‖ dt,
zato je poraba energije po celotni krivulji enaka integralu
E(r) =
∫ 1
0
M(s(t)) ‖ṙ(t)‖ dt.
6 Obzornik mat. fiz. 59 (2012) 1
i
i
“Gora” — 2012/3/15 — 10:42 — page 7 — #7 i
i
i
i
i
i
Z najmanj truda na Šmarno goro!
Tako izpeljani funkcional je posplošitev funkcionala, uporabljenega v [4] za
primer konstantnega naklona.
Reševanje optimizacijskega problema
Z definiranjem energijskega funkcionala v preǰsnjem razdelku lahko zastav-
ljeni problem iskanja optimalne poti vzpona prevedemo na iskanje najce-
neǰse poti v grafu. Ta problem je dobro poznan in ga zlahka uženemo z
Dijkstrovim algoritmom, ki je opisan v naslednjem razdelku.
Graf, ki ga kot vhodni podatek zahteva Dijkstrov algoritem, je kar tri-
angulacija na točkah vi. Točke grafa so oglǐsča trikotnikov, povezave grafa
pa so njihove stranice. Vsaki povezavi e določimo ceno we s pomočjo ener-
gijskega funkcionala, tako da je we = E(r), kjer je r krivulja na ploskvi nad
stranico, ki ustreza povezavi e.
Omenimo še, da smo izbrali triangulacijo, ki je čim bolj simetrična, da
ne bi prǐslo do favoriziranja smeri. Triangulacije so podobne triangulaciji s
slike 2, desno. Tako zagotovimo tudi morebitno hojo v ključih.
Dijkstrov algoritem
Dana sta usmerjen graf G = (V,E), kjer sta V množica točk in E mno-
žica povezav, ter začetna točka s. Vsaka povezava e ima ceno we ≥ 0. (Cena
v praksi lahko pomeni dolžino poti med krajǐsčema povezave, ceno prevoza
po poti med krajǐsčema, . . . ) Cena poti P je vsota cen vseh povezav v P.
Algoritem določi najceneǰso pot od s do vsake druge točke grafa G.
Definiramo množico S točk u, za katere smo že določili dolžino najceneǰse
poti c(u) od točke s. To je
”
raziskani“ del grafa. Na začetku je S = {s} in
c(s) = 0. Za vsako točko v ∈ V − S določimo najceneǰso pot, ki jo lahko
dobimo tako, da potujemo po raziskanem delu S do neke točke u in po
povezavi od u do v. Torej opazujemo količino
c′(v) = min
e=uv:
u∈S
(
c(u) + we
)
.
Izberemo točko v ∈ V − S, za katero je ta količina najmanǰsa, dodamo v
v množico S in definiramo c(v) = c′(v). Zapomnimo si tudi povezavo uv,
na kateri je bil dosežen minimum. Iz teh povezav potem rekonstruiramo
najceneǰso pot.
1–10 7
i
i
“Gora” — 2012/3/15 — 10:42 — page 8 — #8 i
i
i
i
i
i
Gašper Jaklič, Tadej Kanduč, Selena Praprotnik in Emil Žagar
Najceneǰso pot Pv od s do v dobimo tako, da začnemo v v, se prema-
knemo po povezavi, ki smo jo shranili za v, proti u. Zdaj se premaknemo po
povezavi, ki smo jo shranili za u. Postopek ponavljamo, dokler ne pridemo
do točke s.
Več o Dijkstrovem algoritmu je zapisano v [1].
Numerični primeri
Za konec si oglejmo primer optimalnih poti na Šmarno goro (slika 6). Iz
približno 40.000 podatkov s terena, pridobljenih iz javne baze, smo nad
triangulacijo, ki jo dobimo tako, da vsakemu elementu pravokotne mreže
dodamo diagonali (slika 2, desno), konstruirali kubični C1 interpolacijski
zlepek. Za tri priljubljena izhodǐsča poti na Šmarno goro smo izračunali
optimalne poti in jih primerjali z dejanskimi. Tabela 1 prikazuje porabo
energije pri vzponu po posamezni poti. Izkaže se, da se izračunane poti
dobro ujemajo s potmi v naravi. Na bolj strmih predelih poti se pričakovano
pojavijo ključi.
Pot iz Tacna čez Spodnjo kuhinjo zavije levo od optimalne poti, pred-
videvamo, da zaradi njenega naklona. Za nedeljske sprehajalce je pot pri
Spodnji kuhinji prestrma in prezahtevna zaradi korenin, zato naredi ovinek.
Pot, ki jo vrne naš algoritem, je bolj direktna in podobna poti, ki velja za
tekmovanje
”
Rekord Šmarne gore“.
Romarska pot z optimalne poti zavije desno, kjer se pridruži Šmarski
poti. Del optimalne poti, ki ga izpusti, je precej strm in ni preveč primeren
za stareǰse ljudi ali ljudi z manj kondicije. Romarska pot je tako v celoti
bolj naporna (ker je dalǰsa), vendar bolj položna od optimalne.
Partizanska pot se začne v Šmartnem in nadaljuje ves čas naravnost
proti vrhu, medtem ko optimalna pot poteka zelo podobno Šmarski poti (ki
se na sedlu pridruži preostalim potem). Tak rezultat ne preseneča, saj so
Partizansko pot uporabljali kurirji med drugo svetovno vojno, ki so želeli
biti na vrhu v čim kraǰsem času, ne pa z najmanj porabljene energije.
Dober oris optimalnih poti dobimo že iz bistveno manj podatkov. Če
vzamemo približno 900 podatkov s terena, se optimalne poti (slika 7, levo)
dobro ujemajo s potmi s slike 6. S subdivizijo površine lahko pridemo do še
bolǰsih rezultatov (slika 7, desno). Na sliki 7, spodaj, vidimo, da odsekoma
linearna ploskev preslabo aproksimira pravi relief, zato dobljene optimalne
poti niso dobre.
8 Obzornik mat. fiz. 59 (2012) 1
i
i
“Gora” — 2012/3/15 — 10:42 — page 9 — #9 i
i
i
i
i
i
Z najmanj truda na Šmarno goro!
Slika 6. Slika Šmarne gore, nekaj najbolj priljubljenih (tanke črne črte) in izračunanih
optimalnih poti (debele sive črte).
Izhodǐsče Pot Poraba (kJ) Prihranek (kJ) Razlika (%)
Tacen prava 1589
186 11,7
(čez Sp. kuhinjo) optimalna 1403
c. sv. Jurija prava 1484
232 15,6
(Romarska pot) optimalna 1252
Šmartno prava 1403
153 10,9
(Šmarska pot) optimalna 1250
Šmartno prava 1456
206 14,1
(Partizanska pot) optimalna 1250
Tabela 1. Poraba energije pri vzponu na Šmarno goro.
1–10 9
i
i
“Gora” — 2012/3/15 — 10:42 — page 10 — #10 i
i
i
i
i
i
Gašper Jaklič, Tadej Kanduč, Selena Praprotnik in Emil Žagar
Slika 7. Optimalne poti na grobi mreži (levo), na mreži po enem koraku subdivizije
(desno) in na odsekoma linearni ploskvi (spodaj).
LITERATURA
[1] T. H. Cormen, C. E. Leiserson, R. L. Rivest in C. Stein, Introduction to Algorithms,
Third Edition, The MIT Press, 2009.
[2] G. Jaklič in E. Žagar, Shape preserving interpolation by spatial cubic G1 splines, Annali
dell’Universita di Ferrara, 54(2), 259–267, 2008.
[3] T. Kanduč, Makro elementi, Univerza v Ljubljani, FMF, diplomsko delo, 2009.
[4] M. Llobera in T. Sluckin, Zigzagging: Theoretical insights on climbing stategies,
J. Theo. Bio, 249, 206–217, 2007.
[5] T. Schröter in M.-N. Glöckner, How to Climb a Mountain? Simulating efficient ways
to the mountain top, ECMI Newsletter, 46, 2009.
[6] L. L. Schumaker in M.-J. Lai, Spline functions on triangulations, Encyclopedia of
mathematics and its applications, Cambridge University Press, 2007.
[7] J. Wallner, Note on curve and surface energies, Comput. Aided Geom. Design, 24(8–
9), 494–498, 2007.
10 Obzornik mat. fiz. 59 (2012) 1