IZBIRA PRIMERNE METODE RAČUNANJA VIDNOSTI NA DIGITALNEM MODELU RELIEFA
mag. Branko Kaučič *, izr. prof. dr. Borut Zalik ^
Izvleček
KLJUČNE BESEDE: GIS, analiza terena, vidnost na terenu, vidno polje, digitalni model terena, enakomerna kvadratna mreža
Uporaba informacije o vidnosti v geografskih informacijskih sistemih narašča. Ker je večini primerov uporabe osnova vidno polje, smo v prispevku podali pregled obstoječih metod in razkrili njihove lastnosti. Na podlagi pregleda lahko sedaj vsak (uporabnik ali načrtovalec) izbere metodo, ki glede na zahteve aplikacije (čas, kakovost) najbolj ustreza.
I smijp EVHOPI
334
1. UVOD
Pomen uporabe prostorskih podatkov narašča iz dneva v dan. Občuten razmah tega zasledimo tudi pri geografskih informacijskih sistemih z analizo terena na podlagi informacije o vidnosti. Pri tem gre bodisi za teren sam ali pa objekte na terenu. Področij, kjer izkoriščamo informacijo o vidnosti je veliko, dva najbolj tipična primera bi recimo bila:
1.	Podjetja mobilne telefonije in podjetja, ki oddajajo radijske ter TV signale želijo optimizirati lokacije svojih anten. Pri tem lahko gre na primer za začetno postavitev anten, za širjenje ali povečanje zmogljivosti.
2.	Določene organizacije (državne, turistične, vojaške ipd.) želijo zakriti "vizualne" motnje kot so na primer poseki gozdov, kamnolomi, skladišča ipd., da le-teh ne vidimo iz običajnega področja gibanja.
Področij uporabe informacije o vidnosti je seveda še več. Ne glede na vrsto naloge, pa pri tovrstnih sistemih naletimo na dve, na videz nasprotujoči si, težavi. Teren želimo predstaviti čim verodostojneje, kar dandanes ob poplavi digitalnih podatkov ne predstavlja več nobene težave. Vendar s tem znatno povečamo zahteve po shranjevanju podatkov, zaradi česar "odpovedo" tradicionalne metode analiz terena - že za malo bolj zahtevnega uporabnika problemi realne velikosti namreč niso več rešljivi v doglednem času.
V nadaljevanju bomo pokazali, da pa pogled na to vendarle ni tako črnogled. Preleteli bomo osnovne definicije digitalnih modelov terena in vidnosti, zatem pa podali pregled različnih metod računanja strukture vidnosti, imenovane vidno polje. Le-ta predstavlja osnovo vsem področjem uporabe informacije o vidnosti. Testiranje metod smo opravili tako na realnih podatkih (Slovenije), kakor umetno generiranih terenih. Z dobljenimi rezultati smo razkrili dobre in slabe lastnosti metod. Prispevek smo zaključili z nekaj sklepnimi mislimi in idejami za prihodnost.
Geodetski vestnik
* Pedagoška fakulteta - Oddelek za matematiko, Maribor ' FERI - Laboratorij za geometrijsko modeliranje in algoritme multimedije, Maribor
2. OSNOVNE DEFINICIJE
Naravni teren lahko matematično modeliramo kot sliko grafa zvezne funkcije dveh spremen-ljivk, ki pa ga v splošnem zaradi kompleksnosti matematične funkcije ne uporabljamo. Teren raje predstavimo na kompakten način s končnim številom podatkov z digitanim modelom terena. V geografskih informacijskih sistemih najdemo običajno tri razrede digitalnih modelov terena: konturno mrežo, poliederski model terena in mrežni višinski model. Konturne mreže so neprimerne za računalniške analize terena, poliederski model terena najpogosteje predsta-vimo kot triangulirano neenakomerno mrežo, mrežni višinski model pa kot enakomerno kvadratno mrežo. Triangulirane mreže (Slika 1 (a)) so zelo dobro prilagodljive razgibanosti terena in v splošnem lahko isti teren predstavimo z manj točkami kot v enakomerni mreži. Njihova slabost je žal v kompleksnejših postopkih analize. Enakomerne mreže (Slika 2 (a)) so enostavne za analizo, natančne, primerne za paralelno obdelavo podatkov in s primerno prostorsko zahtevnostjo. Na podlagi trenutnega trenda v geografskih informacijskih sistemih smo poudarek v prispevku namenili enakomernim mrežam.
Slika 1: Digitalna modela terenov; a) triangulirana mreža, b) enakomerna kvadratna
335
mreža
(b)
Za dve točki terena p1 = (x1,y1,z1) in p2 = (x2,y2,z2) pravimo, da sta vidni, ko vsaka točka q = (x,y,z) = p1 + t (p2 - p1), ko 0 < t < 1 leži nad pripadajočo točko terena pq, tj. z > zq. Z drugimi besedami, dve točki sta medsebojno vidni, ko daljica pip2, ki ju povezuje, leži nad terenom in se ga dotakne le v svojih krajiščih. Kadar je ena izmed točk gledišče O, poltrak skozi drugo točko p imenujemo žarek pogleda in če žarek pogleda Op nikjer ne oviramo (s terenom ali objektom na terenu), je točka p vidna, sicer pa nevidna.
Definicijo vidnosti lahko razširimo tudi na točke (imenovane tarče), ki niso del terena, ampak ležijo nad njim. Primer vidnosti točk in tarč vidimo na sliki 2. Podan imamo teren, gledišče O ter tri tarče: P^, PB in PC. Iz gledišča vidimo točke terena, označene z odebeljeno črto. Do točke p2 so nevidne vse točke terena in tarče, ki ležijo pod žarkom pogleda Op,. Točka p, namreč v tem primeru predstavlja najvišjo oviro pri ugotavljanju vidnosti točk desno od nje.
Geodetski vestnik
Slika 2: Vidnost in žarki pogledov
--» žarek pogleda do vidne tofikeAarfie
žarek pogleda do nevidne točke/tarče žarek pogleda Oft
lokacija gledišča
žarek pogleda Opj žarek pogleda
I smijp EVHOPI
336
Pri ugotavljanju vidnosti računamo vidnost površja ali objektov, lociranih na površju (na primer zgradb, oddajnikov ipd.). V splošnem rešujemo problem, ki mora biti rešen sproti. Nasprotno imamo lahko informacijo o vidnosti izračunano vnaprej in shranjeno v primerni strukturi vidnosti. Osnovna struktura vidnosti je vidno polje. Predstavlja nam lokacijo in doseg področja, vidnega iz podanega gledišča. Na trianguliranih mrežah ga uporabljamo redko (De Floriani, 1994). Običajneje vidno polje računamo za enakomerno mrežo, kjer vidno polje zapišemo z matriko logičnih vrednosti. Praktičen primer vidnega polja, kjer je velikost vidnega polja omejena s samo aplikacijo (gre za človeški pogled brez kakršnihkoli pripomočkov, kot je na primer daljnogled) vidimo na sliki 3.
Slika 3: Primer vidnega polja; severozahodni del Slovenije, 40 km vzhodno in 40 km južno od najbolj
severozahodne točke Slovenije, radij znaša 10 km
3. RAČUNANJE VIDNOSTI
Zamislimo si primer, prikazan na sliki 4. Podano imamo ravnino E, ki gre skozi gledišče O in je pravokotna na ravnino xy. S pomočjo te ravnine definiramo 2D koordinatni sistem s horizontalno osjo U in vertikalno osjo H. S presečiščem med E in površjem terena tako definiramo krivuljo L, katere vidnost nas zanima. Če si zamislimo takšne krivulje do vseh točk na robu terena (oz. na robu pogleda), z unijo vseh takšnih krivulj dobimo površje terena.
Geodetski vestnik
Slika 4: Problem vidnosti v 3D
Problem vidnosti v 3D smo torej prenesli na množico problemov v 2D. Vsako krivuljo predsta-vimo z diskretnim prerezom D, kot vidimo na sliki 4. Če imamo na robu terena (oz. pogleda) n točk, za vidnost celotnega površja zatorej rešimo n problemov vidnosti v 2D. Na podlagi tega kako izvedemo diskretizacijo prereza Dt in računanja vidnosti posamezne točke v Dt, ločimo dve vrsti algoritmov: eksaktne in aproksimativne.
3.1. Metode računanja vidnega polja
V nadaljevanju podajamo kratek opis vseh objavljenih metod računanja vidnega polja. Podrobnejši opis najdemo v (Kaučič, 2001).
• eksaktna metoda R3: vidno polje računamo na klasičen način (Franklin, 1994). Do vsake točke znotraj radija (v področju interesa) izračunamo žarek pogleda (Slika 5) in preveri-mo, če ga zaradi kakšne višine preostalih točk terena prekinemo. Višine teh preostalih točk ocenimo po potrebi, običajno uporabimo kar linearno interpolacijo (lahko bi tudi minimum, maksimum in povprečje, vendar tisto več ni eksaktna metoda).
337
Slika 5: Delovanje metode R3 v oktantu I
aproksimativna metoda R2: na sliki 5 vidimo, da v metodi R3 vrstni red, po katerem računamo žarke pogledov, ni pomembem. Predpostavimo, da smo žarke pogledov do točk od a do d določili pred katerimikoli drugimi
Geodetski vestnik
točkami v prvem oktantu. Če med računanjem teh žarkov pogledov na križanjih z vertikalnimi mrežnimi premicami shranjujemo višine žarkov pogledov, dobimo informacijo za izračun vidnosti točk e, f, g itn. Takšno početje implicira na splošen pristop računanja žarkov pogledov le do zunanjih točk področja interesa.
aproksimativna metoda XDraw: vidnost in višine žarkov pogledov računamo za kvadratne obroče okoli gledišča, kot je prikazano na sliki 6. Ko računamo vidnost neke točke, gledamo le na točko v prejšnjem obroču in če je točka nevidna, določimo žarek pogleda ki gre nad njo od prejšnje točke. Razen v osmih nebesnih smereh žarke pogledov v vmesnih točkah računamo z aproksimacijo med dvema vmesnima točkama.
Slika 6: Obroči žarkov pogledov
I smijp EVHOPI
338
aproksimativna metoda z rasterizacijo žarkov pogledov: za diskretizacijo prereza Dt se lahko poslužimo znanega problema v računalniški grafiki -rasterizacije daljic. Namesto da se ukvarjamo z računanjem vidnosti v vmesnih točkah, uporabimo obstoječe celice. Najbolj znan pristop tega je z uporabo Bresenhamovega postopka, zasledimo pa tudi uporabo 4WS in 8WS postopka (Cohen-Or, 1995).
Slabost metode R3 je v računanju vidnosti vsake točke posebej, kar odpravimo pri aproksimativnih pristopih. Težava metod R2 in XDraw je ta, da je računanje vidnosti neke točke odvisna od točk, ki so več kot za razdaljo 1 oddaljene od žarka pogleda do te točke. Vpliv teh oddaljenih točk zmanjšamo z uporabo linearne interpolacije, razen če točke ne vsebujejo kakšne zelo dominantne lastnosti. Slabost metod z rasterizacijo žarkov pogledov je ta, da smo morda že pravilno spoznali vidnost točke, vendar pri računanju naslednje rasterizacije žarka pogleda (in vidnosti) vidnost točke spoznamo napačno. S hitrejšim računanjem torej vidnost ne računamo več pravilno.
4. TESTIRANJE METOD
Vse omenjene metode smo implementirali v programskem jeziku C++ in jih eksperimentalno preverili na treh tipih terenov. V prvem primeru smo za teren uporabili naključno generiran teren z enakomerno razporejenimi višinami
Geodetski vestnik
med 0 in 1000 metrov, v drugem primeru fraktalno generiran (z Brownovim fraktalnim gibanjem) teren in v tretjem primeru smo uporabili višinske podatke digitalnega modela reliefa Slovenije pri ločljivosti 25 m, dobljenih od Geodetske uprave Republike Slovenije. Gledišče smo v vseh primerih postavili na štiri različne višine. V prvem primeru smo ga postavili na približno višino človeškega pogleda (1,6 metra nad prvo točko), v drugem in tretjem primeru smo simulirali pogled iz opazovalnega stolpa (25 in 40 metrov nad prvo točko) in v četrtem primeru smo gledišče postavili na višino 1500 metrov (na primer pogled iz balona). Uporabili smo prenosni računalnik s procesorjem Intel Celeron 500 MHz in 64 MB pomnilnika.
Omenjene metode smo implementirali v 11 metodah. Metoda R3Int predstavlja eksakten postopek z linearno interpolacijo, metode R3Avg, R3Min in R3Max pa inačice, kjer smo interpolacijo zamenjali s povprečjem, minimumom in maksimumom. Metoda R2 predstavlja aproksimativno metodo R2, metode XDrawInt, XDrawMin, XDrawMax in XDrawAvg pa inačice metode XDraw. Med metodami na podlagi rasterizacije žarkov pogledov smo izbrali tri postopke: Bresenham, 4WS in 8WS, ker pa smo v testih pri Bresenham in 8wS dobili enake rezultate, smo v rezultatih postopek z Bresenhamovo rasterizacijo daljic opustili.
V vseh primerih smo metode testirali na kvadratu z radijem r za 20 različnih vrednosti, vsak test pa smo ponovili za 10 različnih pozicij gledišča. Za pripadajoč postopek računanja vidnosti v 2D smo uporabili postopek NajvecjiNaklon2D (Kaučič, 2001). Iz praktičnih razlogov v nadaljevanju podajamo le majhen izsek rezultatov, podrobnosti posameznih testov najdemo v (Kaučič, 2001). Časi izvajanj se med posameznimi tipi med seboj niso bistveno razlikovali (52 sekund za R3Int in 0,33 sekunde za 8WS pri r = 300), realne podatke o kakovosti metod pa smo dobili pri fraktalnem in realnem tipu terena. V tabeli 2 vidimo število prepoznanih točk pri realnih podatkih in višini gledišča +25 metrov.
339
Metoda\r	50	100	150	200	250	300
R3lnt	5129,7	618,3	15373,6	32417,0	26,5	361201,0
R3Min	5906,3	1269,7	16383,3	34355,6	43,0	361201,3
R3Max	3783,6	245,6	12968,6	26146,6	21,0	90794,3
RSAvg	5034,0	574,4	14792,3	31047,0	28,0	237286,6
R2	5158,9	571,3	15359,0	32374,0	18,0	361193,5
XDrawInt	4350,4	591,0	17023,0	31576,5	28,8	222741,4
XDrawMin	6388,3	5883,6	30641,6	50289,2	57,2	358801,7
XDrawMax	2618,6	131,1	8696,0	1888,0	19,6	121307,3
XDrawAvg	4672,5	530,3	16665,2	32754,0	26,2	278910,0
4WS	3722,3	299,0	13233,9	21857,8	10,0	229764,0
8WS	4600,0	489,0	14867,1	29484,0	23,3	269959,3
Tabela 1: Število vidnih točk (digitalni model reliefa Slovenije), gledišče: +25 metrov
Primerjavo metod v 3D lahko v grobem strnemo v tabeli 2, kjer vidimo odstotkovno primerjavo vseh metod z metodo R3Int. Naša analiza se razlikuje od analize v (Franklin, 1994), kjer poročajo o nad 90 odstotni kakovosti metode R2. Vidimo, da najmanj časa zahteva metoda 8WS, vendar je njena kvaliteta daleč od pravilne. Če odmislimo metode na podlagi metode
Geodetski vestnik
R3 (zaradi potrebnega časa), se pravilni rešitvi najbolj približamo z metodo R2, zatem pa z metodo 8WS: Katera metoda je najboljša oz. najprimernejša je težko napovedati, z gotovostjo lahko le rečemo, da metode XDrawMin, XDrawMax in 4WS s svojimi rezultati izstopajo in jih zato ne priporočamo. Pri izbiri metode igra vlogo tudi kakšne napake dovolimo. V odvisnosti od aplikacije smo lahko namreč zadovoljni, če smo kot vidne prepoznali preveč točk (in obratno), medtem ko vsaka napačna ugotovitev da je točka nevidna (in obratno), lahko predstavlja veliko napako.
Tabela 2: Primerjava metod računanja
Metoda	Cas (%)	Kakovost (%)
R3lnt	100	100
R3Min	99,469	244,216
R3Max	99,716	296,703
RSAvg	97,185	119,193
R2	1,759	70,620
XDrawInt	0,728	61,723
XDrawMin	0,696	431,997
XDrawMax	0,748	24,341
XDrawAvg	0,718	63,166
4WS	0,846	40,580
8WS	0,638	64,119
I smijp EVHOPI
340
5. ZAKLJUČEK
Ker je v geografskih informacijskih sistemih vedno več področij, ki temeljijo na podlagi informacije o vidnosti, smo v prispevku preučili metode za računanje vidnega polja. Iz rezulta-tov testiranja je možno razbrati obnašanje (čas in kakovost) posameznih metod. Menimo, da je tak pregled nujno potreben, na podlagi tega pregleda bo lahko vsak načrtovalec in uporab-nik tovrstnih geografskih informacijskih sistemov izbral kompromisno rešitev med časom izvajanja in natančnostjo rešitve.
Izziv, da bi izboljšali omenjene metode ostaja. Na nekaterih področjih računalniške grafike se je že izkazalo, da je kombinacja dobrih delov posameznih metod doprinesla novo, boljšo metodo. Verjamemo, da je kaj podobnega možno tudi tukaj.
Literatura
Cohen-Or D., Shaked A., Visibility and Dead-Zones in Digital Terrain Maps, Computer Graphics Forum, 14(3), 1995
De Floriani L., Magillo P., Visibility Algorithms on Triangulated Digital Terrain Models, Int. J. of Geographic Information Systems, 8(1), Taylor and Francis, London, 1994 De Floriani L., Magillo P., Intervisibility on Terrains, poglavje 38 v Geographic Information Systems: Principles, Techniques, Management and Applications, John Wiley & sons, 1999 Franklin Wm R., Ray C.K., Mehta S., Geometric Algorithms for Siting of Air Defense Missile Batteries, Research Proj. for Battelle, Contract Number DAAL-86-D-0001, 1994 Kaučič B., Algoritmi vidnosti nad diskretnim modelom terena, magistrsko delo, mentor Žalik B., Fakulteta za elektrotehniko, računalništvo in informatiko, Univerza v Mariboru, 2001
Geodetski vestnik