IZ ZNANOSTI IN STROKE POMEN RAČUNA NIŠ E GEO ETRIJE ZA v UCI O TEP OG SKE v RESITVE GEOG FS "H INFO CIJSKIH SISTE H Sergej Čapelnik, Območna geodetska uprava Slovenj Gradec, Slovenj Gradec dr, Borut Žalik, Fakulteta za elektrotehniko, računalništvo in . informatiko, Maribor Prispelo za objavo: 1998-03-31 Pripravljeno za objavo: 1998-06-26 Izvleček Članek predstavlja nekaj lastnih programskih rešitev s področja računalniške geometrije, primemih za aplikacije GIS. Najprej opišemo pomen dekompozicije prostora. Omenimo štiriška drevesa, enakomemo delitev prostora in enakomerno adaptivno delitev. V nadaljevanju predstavimo algoritme za rekonstrukcijo topologije iz črtnih risb, algoritem za določanje vidnosti na rastrskih slikah in algoritem za presek poljubnih mnogokotnikov. Ključne besede: algoritmi, delitev prostora, presek, računalniška geometrija, vidnost UVOD ačunalniška geometrija ( computational geometry) se je začela razvijati pred slabimi dvajsetimi leti z doktorsko disertacijo M. I. Shamosa na Univerzi Y ale 1978. Ukvarja se s programskimi rešitvami (algoritmi), ki se spopadajo z geometrijskimi problemi. Ker je pri reševanju le-teh podanih pogosto veliko geometrijskih podatkov, je pomembno, da so algoritmi hitri, učinkoviti in predvsem zanesljivi. Na redko katerem področju uporabe računalnikov najdemo toliko mejnih primerov in imamo toliko težav s končno aritmetiko računalnika kot prav pri reševanju geometrijskih problemov. To je razlog, da mnogi komercialni paketi GIS-ov ne nudijo potrebnih funkcij za izvedbo določenih problemov ali pa so izvedbe posameznih rešitev počasne in okorne. Primera takšnih problemov sta: o iskanje presekov poljubnih mnogokotnikov z luknjami, o tvorba očrtij ( okoli mnogokotnika ali množice daljic na določeni razdalji začrtamo očrtje, sestavljeno iz daljic in krožnih odsekov). Prav zaradi tega se področje računalniške geometrije še zmeraj hitro razvija, z razširitvijo Interneta pa so nove programske rešitve hitro znane in dostopne. Na Geodetski vestnik 42 (1998) 2 Fakulteti za elektrotehniko, računalništvo in informatiko Univerze v Mariboru se na Inštitutu za računalništvo, v okviru Laboratorija za računalniško grafiko in umetno inteligenco ter še posebej Centra za geometrijsko modeliranje, že kar nekaj časa ukvarjamo tudi s področjem geometrijskega modeliranja. Do pred kratkim je bila večina naših naporov usmerjena predvsem v klasične algoritme računalniške grafike (vizualizacija) in algoritme za predstavitev krivulj in ploskev (tako aproksimacijskih kot interpolacijskih metod). V zadnjih letih pa smo se v okviru Centra za geometrijsko modeliranje bolj sistematično lotili tudi področja razvoja algoritmov računalniške geometrije, ki bi bili zanimivi za širši krog uporabnikov. V tem članku bomo na kratko predstavili nekaj izvirnih programskih rešitev s tega področja, in sicer: algoritem hitrega iskanja geometrijskih podatkov, konstrukcijo topologije mnogokotnikov iz lomljenk, določitev problema vidnosti iz rastrskih slik in algoritem za iskanje presekov nad kompleksnimi mnogokotniki. HiTRO ISKANJE GEOMETRIJSKIH PODATKOV Podatki o prostoru v geodeziji so sestavljeni iz točk, črt, mnogokotnikov, ploskev in teles. Predstavitev tovrstnih podatkov za učinkovito računalniško obdelavo postaja vse bolj pomembna na področjih, kot so: računalniška grafika, računalniško podprti modelirni sistemi, robotika, obdelava slik, prepoznavanje vzorcev, računalniška geometrija, GIS-i in še marsikatera druga področja. Pri geografskih informacijskih sistemih so na primer podatki o posameznih geometrijskih elementih v večini primerov ločeni glede na povezanost. Zemeljski prelomi, nastali zaradi potresov, so lahko predstavljeni z eno samo črto, reke s svojimi pritoki običajno ponazorimo z drevesno strukturo, cestno ali železniško omrežje je smiselno opisati z mrežnimi strukturami, za obrise parcel, jezer, hiš pa se običajno uporabijo mnogokotniki oz. lomljenke (polylines). a bi omogočili hiter dostop do podatkov, moramo le-te primerno predstaviti v pomnilniku računalnika. Osredotočiti se moramo na ozek del zanimivih podatkov in izvajati operacije le na njih. Tako je lahko odziv dobrega sistema zelo hiter kljub ogromnim količinam podatkov. V ozadju takšnih sistemov se skrivajo različne hierarhične podatkovne strukture. Podatki, shranjeni v eni od takšnih hierarhičnih struktur, omogočajo dajanje hitrih odgovorov na geometrijska vprašanja, kot so: katera točka je najbližja točki p, katera mnogokotnika delita podani rob, katere parcele so sosednje podani parceli ipd. Primer slabih, neučinkovitih programskih rešitev pa bi recimo bil primer ugotavljanja, ali se dve cesti sekata. Vsaka izmed cest je ~evcda lahko predstavljena z nekaj 1 000 robovi. Če bi preverjali sekanje vsakega roba ene ceste z robom druge, potem takšno iskanje ne bi bilo učinkovito in hitro, zato bomo v nadaljevanju predstavili nekaj predlogov boljših rešitev. Štiriška drevesa Ena najbolj osnovnih in najbolj uporabljenih podatkovnih struktur je štiriško drevo ( quadtree ). Izraz štiriško drevo uporabljamo za opisovanje podatkovnih struktur, ki temeljijo na načelu ponavljajoče (rekurzivne) razgradnje (Samet, 1989). Razgradnja lahko na vsakem koraku prostor deli na enako velike dele ( enakomerna razgradnja) ali pa je velikost delov prostora neenakomerna, vodena s programom Geodetski vestnik 42 (1998) 2 (neenakomerna razgradnja). I\fivo razgradnje pove, kolikokrat zaporedoma smo razgradnjo opravili. Slika 1 prikazuje idejo predstavitve prostorskih podatkov s štiriškim drevesom. Predpostavimo, da želimo ugotoviti, kateri del področja je zaseden z mnogokotnikom (Slika la). Na sliki lb vidimo tako imenovano metodo z razdelitvijo prostora v celice in ugotavljanja zasedenega prostora v njih (Mortenson, 1985). V tem primeru prostor razdelimo na enako velike celice in ugotavljamo, katera izmed njih je zasedena z mnogokotnikom. Osnovno vprašanje, ki se pri tem pojavi, je, kako gosta mora biti mreža, da bi lahko naš mnogokotnik dovolj dobro predstavili. V primeru goste mreže je očitna zahteva po velikem pomnilniškem prostoru, poveča pa se tudi čas ugotavljanja zasedenosti posameznih celic. Ti slabosti sta bili odločilni, da so poskušali najti učinkovitejšo metodo zasedenosti prostora s posameznimi elementi. Pomembna je bila ideja, da celic, ki so povsem zasedene z nekim elementom ali povsem prazne, ni treba nadalje deliti. Celotno področje najprej razdelimo na štiri enako velike dele ( oz. na osem delov v 3D prostoru) in ugotavljamo zasedenost teh področij z geometrijskimi elementi. V našem primeru (Slika le) hitro ugotovimo, da je levi zgornji kvadrant ( označimo ga kot severozahodni kvadrant, SZ) povsem nezaseden z našim mnogokotnikom, zato ga je nesmiselno nadalje obdelovati, ampak ga označimo kot praznega. Preostale tri kvadrante delimo dalje. Postopek delitve in dobljeno štiriško drevo prikazuje slika ld. o o o o o o o o o o o o o o o o s z s v o o o o 1 1 1 1 o o o o 1 1 1 1 o o o 1 1 1 1 1 o o i 1 1 1 1 1 J z o o 1 1 1 1 o o 11 o o 1 'I 1 o o o b C Nivo3 Nivo2 Nivo 1 . Nivo O. d Slika 1: a) primer področja (parcele) predstavljene z b) binamo mahiko c) parcela predstavljena s štiriškim drevesom d) štiriško drevo Geodetski vestnik 42 ( 1998) 2 Enakomerna delitev ljub temu, da je v prejšnjem podpoglavju enakomerna delitev prostora izgledala okorna, pa je majhna modifikacija tega pristopa zelo učinkovita. V takšnem primeru prostor najprej razdelimo na razumno mnogo enako velikih celic (nekaj 100 je večinoma dovolj). I,Tato na tako razdeljeno območje položimo prisotne geometrijske elemente. V vsaki celici vodimo seznam tistih geometrijskih elementov, ki so v tej celici prisotni. Če je kakšen geometrijski element (npr. daljša črta, mnogokotnik) v dveh ali celo več celicah, se pojavi v seznamu vseh teh celic. Ko smo vstavili vse prisotne geometrijske elemente, lahko zavržemo vse prazne celice. Ostali algoritmi, ki takšno delitev prostora uporabljajo, se osredotočijo le na tiste celice, ki so zasedene z vsaj enim izmed geometrijskih elementov. Vsak konkreten problem je sedaj rešljiv lokalno (znotraj ene same celice ali s pomočjo neposredno sosednjih celic, ki jih je največ 9). To nam omogoča, da zgradimo hitre iskalne algoritme. Primer enakomerne delitve prostora vidimo na sliki 2, kjer so nekatere celice zasedene z geometrijskimi elementi, druge pa ne. ot smo omenili, takšna predstavitev podatkov omogoča hitre odgovore na ovpraševanja o sosedstvu. Če nas na primer zanima, katera točka je najbližje točki va, preverimo celico [0,2]. Tam najdemo točko vb, ki je prvi kandidat za odgovor. Za tem preiščemo še celice: [0,1], [1,1], [1,2], [l,3] in [0,3] ter ugotovimo, da so prazne. To je zadosten pogoj, da lahko z gotovostjo proglasimo točko vb kot najbližjo točki va. Tako ni treba računati razdalj do vseh točk na sceni in med njimi izbirati najmanjšo. Izračun razdalj po Pitagorovem izreku sicer ni zelo zahteven, a si pri velikem številu točk odreže kar lep kos procesorskega časa. o 2 3 4 s 6 O 1 2 3 4 5 6 ) \, \l ~1 ~ --- \ 1\ ~ \ 1~ ~ \ >\ \ y / \ ) \ }/ \ v Slika 2: Enakomerna delitev prostora Za učinkovito uporabo enakomerne delit-ve prostora moramo skonstruirati zanesljive in predvsem hitre algoritme, ki ugotavljajo, v katerih celicah se posamezen geometrijski element nahaja. S točkami seveda ni težav, problemi pa nastopijo že pri daljicah oz. lomljenkah. V ta namen smo razvili hiter in zanesljiv algoritem, ki deluje v aritmetiki s plavajočo vejico, saj se realnim številom v GIS-u običajno ne moremo izogniti (Žalik, 1997). Ko znamo ugotoviti, katere celice zaseda daljica, lahko z nekoliko modificiranim algoritmom obdelamo tudi polnjena polja (algoritem s preiskovalno premico). Nekoliko več težav je pri krivuljah in ploskvah svobodnih oblik (npr. B-zlepki, ki pa se v klasičnih aplikacijah v geodeziji redko srečajo). Geodetski vestnik 42 (1998) 2 Enakomerna adaptivna delitev a metoda je zelo podobna pravkar opisani. Bistvena razlika je v delitvi prostora oz. ravnine. Ta delitev se sedaj opravi na dveh ravneh. Uporabimo osnovno delitev (kot pri zgornji metodi) ter podrobnejšo delitev tam, kjer je to potrebno. Za podrobnejšo delitev se odločimo na mestih, kjer gostota geometrijskih ele1nentov bistveno odstopa od povprečja. Realizacija enakomerne adaptivne delitve prostora in razvoj pripadajočih algoritmov za označevanje celic in iskanja sosednosti bo opravljena v okviru magistrske naloge znotraj Centra za geometrijsko modeliranje. A 8 C D E F A B 2 3 4 b Slika 3: Adaptivna enakomema delitev prostora C a) Prikaz poligonskih točk v okolici občine Slovenj Gradec b) izrez DKN, del K.O. Šentilj pod Turjakom KONSTRUKCIJA TOPOLOGIJE IZ ČRTNIH PODATKOV D E ačrti parcel so mnogokrat narisani ( ali pa se še rišejo) v splošno namenskih risalnih programih ( običajno AutoCAD). Le-ti niso bili strogo namenjeni za geodetske aplikacije, zato je uporabnik lahko narisal tudi povsem nekonsistentno sliko, na kar ga program ni bil sposoben opozoriti. Tako mnogokotniki, ki predstavljajo parcele, zaradi nenatančnega risanja večkrat niso sklenjeni, še večje težave pa se pojavijo, če želimo zaradi boljše preglednosti posamezne parcele zapolniti z barvo. Takrat hitro ugotovimo, da zaradi napačne topologije tega ne moremo storiti. Ročno popravljanje starih grehov zahteva seveda mnogo časa. Zato smo razvili program, ki tvori iz podatkov o parcelah, opisanih samo z lomljenkami, popolno topološko predstavitev. Primer vidimo na sliki 4. Program deluje v več korakih. ajprej združi tiste točke posameznih lomljenk, ki bi se očitno morale stikati in ki so si bliže od razdalje, ki jo poda uporabnik. Analizira podatke in označi tiste dele na sliki, ki še vedno niso zaključeni. Uporabnik nato na interaktiven način takšne dele poveže z drugimi deli ali pa jih odstrani. Preveri, če se lomljenke sekajo. Če se, tvori nova vozlišča in ustrezne nove lomljenke. V zadnjem koraku tvori zaključene mnogokotnike. Geodetski vestnik 42 (1998) 2 ' 1 ·., ' ,·. ~' '• . . ' ' , -._ '.i_/ / .. ~ ... / . . . ',,/ 1 //.---:.-, ' .. . 1.: ) . .-1 ✓ ' ,. -~ . r • 1 Slika 4: a) Nekonsistentna predstavitev parcele b) Tvorjena topologija parcele REŠITEV PROBLEMA VIDNOSTI TERENA IZ RASTRSKIH SLIK/PODOB a podlagi višin terena (digitalni model reliefa) smo razvili in implementirali algoritme za izračunavanje lastnosti geografskih modelov, kot so: vidnost med dvema točkama modela terena, izračun naklonin in osončenosti terena, prikazovanje terena in prekrivanje tematskih kart, predstavljenih z rastrskimi slikami. Končni rezultat je nabor algoritmov (diplomsko delo T. Trobca), ki omogoča analiziranje teh podatkov (Trobec, 1997). Na sliki 5 vidimo primer vidnosti z vrha Triglava. Slika 5: Razgled z vrha Triglava Nad tako dobljenimi rastrskimi slikami/podobami je možno izvajati še dodatne matematične operacije. Če vzamemo dve takšni rastrski sliki/podobi, lahko tvorimo med njima preseke ali unije in s tem združujemo ali izločamo območja z žcljenimi lastnostmi (pokrivanje tematskih kart). Odpirajo se tudi novi vidiki, ki lahko služijo kot motivacija bralcem za nadaljnja razmišljanja in iskanja na tem področju. Pri izračunavanju lastnosti terena iz rastrskih slik/podob bi se lahko razvili algoritmi, na primer za: simulacijo erozije, simulacijo poplav, izračunavanje osenčenosti terena v Geodetski vestnik 42 (1998) 2 nekem časovnem obdobju, izdelavo 3D-slik in animacij, ki bi prispevale k večji razumljivosti in preglednosti nekaterih rezultatov. PRESEKI POLJUBNIH 20-MNOGOKOTNlfKOV oločanje preseka mnogokotnikov je eden izmed klasičnih problemov računalniške geometrije. V teoriji je problem obravnavan ločeno za dve skupini mnogokotnikov: o presek opravljamo le med konveksnimi mnogokotniki, o vhodni mnogokotniki so lahko poljubni mnogokotniki, tudi z ugnezdenimi luknjami. Presek konveksnih mnogokotnikov je dobro znan in brez večjih težav lahko realiziramo programsko rešitev. Druga množica mnogokotnikov pa je večji zalogaj, ki mu ni kos marsikateri komercialni GIS. V literaturi pogosto najdemo nasvet, da mnogokotnike, ki niso konveksni, najprej razbijmo s postopkom razgradnje v _konveksne mnogokotnike ( trikotnike ali trapezoide), nato nad konveksnimi deli opravimo preseke in rezultat združimo v končen presečni mnogokotnik. Pri realnih mnogokotnikih (mnogokotnik z 28 000 oglišči vidimo na sliki 6) pa ta ideja ni najučinkovitejša. Zato smo razvili algoritem, ki se neposredno spopada s problemom presečišča med dvema poljubnima mnogokotnikoma, in pri implementaciji uporabili kar nekaj inovativnih rešitev. Algoritem je možno poklicati v poljuben programski jezik, trenutno pa ga uporabljajo: o kot dodatek programu Arc/lnfo na Fakulteti za gradbeništvo Univerze v Mariboru o Department of Soil, Water, and Climate, University of Minnesota, USA o criterion planners & engineers, Portland, Oregon, USA Slika 6: Mnogokotnik z 28 000 oglišči Geodetski vestnik 42 (1998) 2 ZAKLJUČEK članku smo na kratko predstavili le nekaj algoritmov s področja računalniške geometrije, ki so plod dejavnosti Centra za geometrijsko modeliranje na Fakulteti za elektrotehniko, računalništvo in informatiko Univerze v Mariboru. Cilj ustanovitve tega centra je bil vzpostaviti povezavo med raziskovalnim delom na Univerzi in pa praktičnimi potrebami uporabnikov z razvojem lastnih, učinkovitih in robustnih implementacij geometrijskih problemov. Upamo, da smo s tem člankom storili vsaj majhen korak k uresničitvi tega cilja. V centru budno spremljamo raziskovalne dosežke na tem področju, prav tako pa imamo temeljno literaturo s tega področja. Osebje laboratorija si želi resnih izzivov s področja računalniške geometrije, povezane z geodetsko problematiko, in pripravljeni smo na sodelovanje pri reševanju zahtevnejših problemov. Zahvala: Avtorja članka se recenzentu doc.dr. Radošu Šumradi prisrčno zahvaljujeva za koristne pripombe in napotke, ki so omogočili izboljšavo prispevka. Literatura: Mortenson, M. E., Geometric Modeling. John Wiley & Sons, New York, 1985 Samet, H., The Design and Analysis of Spatial Data Structures. Addison-Wesley, 1989 Trobec, T. et al., Calculation of Visibility from Raster Relief Models. ln L. Szinnay-Kalos (Ed.) Spring Conference on Computer Graphics SCCG 1998 -WSCG'98, Budmerice, 1998, pp. 247-256, - lSBN 80-223-0837-4 Trobec, T., Prikaz in analiza geografskega prostora s pomočjo rasterskih slik. Univerza v Mariboru, Fakulteta za elektrotehniko, računalništvo in informatiko. Diplomsko delo, 1997 Žalik, B. et al., An Efficient Code-Based Voxel-Traversing Algorithm. Computer Graphics Forum, 1997, Vol. 16 No. 2 Žalik, B. et al., A Quick Intersection Algorithm for Arbitrmy Polygons. In L. Szinnay-Kalos (Ed.) Spring Conference on Computer Graphics SCCG 98 WSCG'98, Budmerice, 1998, pp. 195-204, ISBN 80-223-0837-4 Recenziia: Uroš Mladenovič - v delu doc.dr. Radoš Šwnrada Geodetski vestnik 42 ( l 998) 2