Ugrás a tartalomhoz

Térinformatika 11., Interpoláció és domborzatmodellezés

Márkus Béla (2010)

Nyugat-magyarországi Egyetem

11.3 Elemi műveletek

11.3 Elemi műveletek

Ezt az alfejezetet a domborzatmodellező algoritmusok kialakulásával és fejlődésével kezdjük. Ezután összefoglalóan tárgyaljuk a szabályos, rácshálós modelleken végzett interpolációt. A szabálytalan modellekre bemutatjuk a dinamikus felületek, a természetes szomszédok, és a lokális háromszögek módszerét, végül foglalkozunk a TIN és a spline módszerrel. Mielőtt a műveletekre rátérünk, ismerjünk meg néhány fogalmat!

A támpontok eloszlása szerint megkülönböztetünk:

  1. szabályos modelleket, ahol a támpontok szabályos rácsháló metszéspontjaiban helyezkednek el,

  2. strukturális modelleket, amelyek felépítésekor figyelembe veszik a domborzat jellegzetességeit, és

  3. véletlenszerű modelleket, ahol a nem szabályosan elhelyezkedő támpontok valamilyen ok miatt nem esnek a terepfelszín jellemző pontjaira (például tó vagy folyó medrének felmérésekor).

11.12. ábra. Szabályos, strukturális és véletlenszerű DDM

A DDM feladatok közül igen gyakori az eredeti modellből új modell levezetése. Ilyen esetekben az eredeti modell támpontjait elsődleges pontoknak az új modell támpontjait másodlagos (levezetett, interpolált) pontoknak nevezzük. A modellek általában támpontok strukturált halmazaként épülnek fel. A modellező műveletek a támpontok alkalmas készletére támaszkodva állítanak elő új információkat a modellezett terepről.

Elsődleges modellként általában strukturális modelleket vagy nagy pontsűrűségű szabályos modelleket alkalmaznak. A levezetett modellek - az egyszerű, gyors kezelhetőség miatt - rendszerint szabályosak.

11.3.1 Korai algoritmusok

A térinformatikai gyökerei a digitális domborzatmodellezésben rejlenek. A múlt század ötvenes éveinek közepén Charles Miller (Massachusetts Institute of Technology (MIT), USA) számítógéppel segített vasúttervezési fejlesztéseket folytatott. Ennek során 1957-ben elkészült az első digitális domborzatmodell. A mérési eredményeket sztereofotogrammetria szolgáltatta. A modell támpontjait keresztszelvényekben rögzítették. A tervező programok e szelvényekben lineáris interpolációval nyertek magassági adatokat.

11.13. ábra. Az első DDM támponteloszlásának és a tervezésnek elvi sémája

Ezt a modellt a fejlesztők ugyan digitális terepmodellnek nevezték el, de a mai értelemben domborzatmodellnek hívnánk. A projekt úttörő jellegének aláhúzására megemlítjük, hogy olyan informatikai környezetben kezdték a munkát, amikor az IBM főmérnöke azt vizionálta, hogy a világnak mindössze öt számítógépre lesz szüksége. Charles Miller munkájának elismeréseképpen az MIT legfiatalabb professzoraként kapott kinevezést.

Egy másik irányzat (a svéd Nordisk ADB, a japán Nakamura és mások képviselték) az interpolációt a szintvonalakon végzett szerkesztésekkel végezte el. A legegyszerűbb algoritmus első lépésben megkereste a P ponton átmenő függőleges és vízszintes egyenesek mentén a szintvonalakkal való első metszéspontot, majd a második lépésben lineáris interpolációt végzett az 1-2 és a 3-4 szakaszokon, végül a P pont magasságát az előző lépésben kapott értékek számtani közepeként nyertük.

11.14. ábra. A P pont magassága az 1-2 és a 3-4 szakaszon végzett lineáris interpoláció számtani közepe

A processzorok teljesítményének javulása megengedte a hosszabb számításokat. A következő ábrán szemléltetett algoritmus első lépésben megkereste a P ponton átmenő fő és mellékégtájakra futó egyenesek mentén a szintvonalakkal való első metszéspontot, majd a második lépésben kiválasztotta a legnagyobb lejtésű szakaszt (ez ábránkon az 1-2), majd lineáris interpolációt végzett ezen a szakaszon. Lényegében a manuális megoldás esésvonalon végzett lineáris interpolációját imitálta az algoritmus.

11.15. ábra. A P pont magasságát a legnagyobb esésű 1-2 szakaszon végzett lineáris interpoláció adja

Befejezésül a harmadfokú polinommal történő interpolációt mutatjuk be. A polinom egyenlete a következő: z=a0+a1x+a2x2+a3x3. Az egyenletben 4 ismeretlen van, a szabatos interpolációhoz 4 pontra van szükség. Ezek az előző megoldás szerint kiválasztott legnagyobb lejtésű vonal pontjai (1 és 2), valamint a kihosszabbításával kapott 9 és 10 jelű metszéspontok.

11.16. ábra. A P pont magasságát a 9-1-2-10 pontokra végzett harmadfokú görbével végzett interpoláció adja

Amint látjuk, a korai algoritmusok a manuális megoldást igyekeztek számítógépre vinni. Tanulságként mutattuk be ezeket. A gondolkodásmód átalakítása hosszú folyamat. A mai szoftverekben alkalmazott algoritmusokat a hetvenes években alapozták meg.

A következőkben néhány ilyen algoritmust mutatunk be először szabályos, majd szabálytalan modellekre.

11.3.2 Kettősen lineáris interpoláció

A szabályos modelleket széleskörűen alkalmazzák elemezési, tervezési feladatok megoldására. A szabályos modellek előnye, hogy könnyen meghatározható a levezetendő pont környezete, gyorsan kiválaszthatók a lokális interpoláció támpontjai, a számítás egyszerű. A modell hátrányai között említhető, hogy a rácspontok nem esnek a terep jellemző pontjaiba, ezért csak kellően sűrű modell ad kielégítő eredményt. A modelleket leggyakrabban fotogrammetriai úton, vagy számítógéppel történt levezetés útján nyerik. Több szabályos modell elérhető az interneten is.

Két megoldást ismertetünk a következőkben. Lényegében mindkettő szabatos megoldás, és kettősen lineáris (bi-lineáris) interpoláción alapul. Az első algoritmus elvét a következő ábra szemlélteti. A P pont környezetét azon rácselem sarokpontjai képviselik, amelybe a pont esik (00,10,11,01). Határozzuk meg az 1 jelű pont magasságát a 00-10 oldalon lineáris interpolációval, ugyanígy a 2 jelű pontot a 01-11 oldalon. Végül a P pont magasságát az 1-2 szakaszon végzett lineáris interpoláció szolgáltatja.

11.17. ábra. A kettősen lineáris interpoláció elve

A második megoldást akkor alkalmazzuk, ha a rácselemben több pont interpolációját is el kell végezni. Ilyen esetben célszerű egy felületillesztést végezni, és a magasságokat a felület egyenletéből számítjuk.

11.18. ábra. Hiperbolikus paraboloid illesztése

A szabatos interpolációra használható legegyszerűbb felület a hiperbolikus paraboloid. Ennek egyenlete z=a00+a01y+a10x+a11xy. A 4x4-es egyenletrendszer szokásos megoldása helyett gyorsul a számítás, ha az előző ábrán látható módon, a 00 jelű pontban egy relatív koordinátarendszert veszünk fel. Ekkor x=0 és y=0, ezért a00=z00. A 01 jelű pontban x=0, az 10 jelű pontban y=0, ezért az a01 és az a10 a rácsoldalak mentén vett magasságkülönbségek és az oldalhossz (l) hányadosaként számíthatók. Ezek után a negyedik ismeretlen (a11) már az egyenletbe helyettesítéssel és átrendezésével egyszerűen számítható. Az ismeretlenek meghatározásával tetszőleges pont magassága gyorsan meghatározható.

A módszer gyakorlati alkalmazásával találkozunk például az ArcMap-nek az adatszint tulajdonságok (Layer Properties) menüjében, ha a Bilinear Interpolation opciót választjuk.

Mindkét említett módszer hibája, hogy egyik rácselemről egy másikra átlépve az interpoláló felület élesen törik. Ezt a hatást a környezet kiterjesztésével 12 vagy 16 rácspont alkalmazásával lehet csökkenteni.

A szabályos modelleken történő interpolációról most áttérünk a szabálytalan modellekre kialakított magasságszámító algoritmusokra.

11.3.3 Dinamikus felületek

A dinamikus felületek módszere egy matematikailag meghatározott felületet használ a számításra. Ennek helyzete dinamikusan változik a P pont helyzetének függvényében.

A következőkben öt módszert mutatunk be. A módszereket a felület megválasztása és a környezet meghatározása szerint osztályozzuk.

A legközelebbi szomszéd

A legközelebbi szomszéd (Nearest Neighbor) módszere a legegyszerűbb eset, a környezetet a legközelebbi támpont jelenti, a terep felszínét vízszintes síkkal közelítjük.

11.19. ábra. A P pont magasságát a legközelebbi támpont adja

A módszer gyakorlati alkalmazásával találkozunk például az ArcMap-nek az adatszint tulajdonságok (Layer Properties) menüjében, ha a Nearest Neighbour opciót választjuk.

A módszer szabatos és szakadásos.

Súlyozott számtani közép

Ennél a módszernél a kiválasztott támpontokból a magasság a következő képlettel egyszerűen, a támpontok magasságának súlyozott számtani közepeként kiszámítható:

ahol

  • Zp – az új pont magassága,

  • pi – az i pont súlya (Tobler törvénye alapján, a P és az i jelű támpont közötti távolsággal fordítottan arányos, rendszerint 1/ti2),

  • zi – az i támpont ismert magassága.

Itt környezet alatt általában egy adott (r) sugarú kört értünk.

11.20. ábra. A P pont magasságát a kiválasztott támpontokra illesztett vízszintes kiegyenlítő sík adja

Problémát jelent, ha nagy a sugár, akkor túl sok pont esik a környezetbe (lásd a következő ábra bal oldalán, a sok pontnak túlzott simító hatása van), vagy kicsi a sugár, és túl kevés a környezetbe eső támpont, akkor nem tud a gép magasságot számítani. Más esetekben az így kiválasztott pontok térbeli eloszlása nem szerencsés (lásd az ábra jobb oldalán). Ha jól megnézzük, akkor ebben az utóbbi esetben a levezetendő pont nem esik a kiválasztott támpontok burkoló sokszögébe, vagyis interpolálás helyett extrapolálna az eljárás.

11.21. ábra. Az adott sugarú körrel leírt környezetbe eső támpontok száma változó

A következő ábrán egy olyan kiválasztási módszert látunk, amely ezt a problémát orvosolja. Itt a kiválasztás az első lépésben egy megfelelően nagy sugárral történik, majd a második lépcsőben a négy síknegyedből kiválasztjuk a levezetendő ponthoz legközelebb esőket. Ez a kétlépcsős módszer segít abban, hogy P pontot a támpontok valóban fogják közre.

11.22. ábra. A szabálytalan DDM pontjaiból a környező pontok kiválasztása kétlépcsős módszerrel. A P pont a támpontok burkolósokszögébe esik

Ha a terepen törésvonalak vannak (pl. rézsűvonalak. éles völgyek, gerincek, akkor előírható, hogy az ezek átellenes oldalára eső támpontok ne kerüljenek kiválasztásra.

11.23. ábra. Terepi törésvonalak megadása

Ezt a módszert alkalmazza az ArcGIS 3D Analyst kiterjesztésének IDW (Inverze Distance Weighted) algoritmusa, amelyet a következő modulban alkalmazni fogunk.

A következő ábra az IDW módszer paraméterezését mutatja az ArcGIS-ben. Látható, hogy a súly képletében szereplő kitevő (Power) változtatható. Az alapértelmezés 2. Minél nagyobb a kitevő, annál nagyobb a közeli támpontok relatív súlya. A kisebb kitevő simító hatású, nagyobb hatást enged a távolabbi pontoknak. A kereső sugár (Search radius) lehet állandó (Fix) vagy változó (Variable). Állandó sugár esetén meg kell adni a minimális pontszámot (Minimal number of points). Ennél kevesebb pont esetén az eljárás nem ad eredményt. Változó sugár esetén meg kell adni a kétlépcsős szelekció pontjainak előírt számát: 4,8,12. A maximális ponttávolság (Maximum distance) megadása opcionális. A terepi törésvonalak megadása ugyancsak opcionális.

11.24. ábra. Az IDW módszer paraméterezése az ArcGIS-ben

A módszer közelítő és folyamatos.

Interpoláció ferde síkkal

Az előző két módszer nem alkalmas a lejtés meghatározására, mert az interpoláló felület vízszintes sík. Ha a támpontokra ferde síkot illesztünk, akkor a sík egyenletéből a lejtés, és annak iránya is számítható.

A ferde síkkal (elsőfokú polinommal) való közelítés esetén a magasság a következő képlettel számítható:

ahol

  • aij – a sík együtthatói (ismeretlenek),

  • x és y – relatív koordináták (origó a P pontban).

Vegyük észre, hogy amíg az előző esetben mindössze egy ismeretlenünk volt, vagyis egy támpont is elegendő lenne a meghatározáshoz, addig a ferde síkkal való közelítés esetén már az ismeretlenek száma három (három támpontra van minimálisan szükség a környezetben).

Ha háromnál több támpontunk, tehát fölös adatunk van, akkor a ferde sík nem illeszthető egyértelműen (ellentmondás-, eltérésmentesen) a támpontokra. A megoldást a legkisebb négyzetek módszere adja. Ezzel itt nem foglalkozunk (a Kiegyenlítőszámítás című tantárgy részletesen tárgyalja), de lényege az, hogy a legjobban simuló síknak azt tekinti, amelyre a támpontokon számított eltérések súlyozott négyzetösszege a legkisebb.

Interpoláció másodfokú polinommal

Ha a terep görbültségét is keressük, akkor közelíthetünk másodfokú polinommal

A fenti képlet alkalmazásához legalább hat támpontra van szükség. Ezért a kétlépcsős kiválasztás során a két-két vagy három-három legközelebbi pontot választjuk ki. A nagyobb számításigény ellenértéke, hogy itt a pontbeli görbültséget is megkapjuk. Ezzel vizsgálható, hogy az adott környezet milyen terepidomot jellemez, ami a topográfiai mérések tervezésétől az eróziós védekezésig sok mindenre felhasználható.

Természetes szomszédok

11.25. ábra. A természetes szomszédok módszerét alkalmazva, a támpontok súlya a Thiessen poligonból kimetszett területtel arányos

A természetes szomszédok (Natural Neighbor) módszert használva a számítás hasonló, mint az IDW esetén, de a számításba bevont pontok kiválasztása az új pontra szerkesztett Thiessen poligonnal történik. Az új pontot hozzáadva a támpontokhoz, megszerkesztjük annak Thiessen poligonját, és a közvetlen szomszédokat választjuk ki. Ezek jelentik a környezetet. Átlapolva ezt a poligont a támpontok eredeti (új pont nélküli) Thiessen poligonjaival, átfedő területeket kapunk. A támpontok súlya az átfedő területtel arányos.

11.3.4 Spline

Szabályos, rácshálós modellek levezetésekor gyakran alkalmazzák a spline függvényeket, különösen, ha sima lefutású szintvonalrajzot akarnak előállítani. Az interpoláló függvény a támpontokra illeszkedő rugalmas membrán alakját követi. A függvény átmegy valamennyi támponton, és a görbültsége minimális. A felszín sima, de a támpontok környékén a lejtés erősen változhat, ezért a görbültség számítására nem javasolt.

A módszer szabatos és folyamatos, sőt folytonos (!). A spline interpoláció használatát a következő modulban bemutatjuk.

11.3.5 TIN

A domborzatmodellezés korai szakaszában számos kutatás foglalkozott szabálytalan modelleken optimális háromszöghálózat szerkesztésével. Mára a Tom Poiker által kidolgozott TIN (Triangulated Irregular Network) módszer vált általánossá. Az ArcGIS is ezt alkalmazza. A TIN megszerkesztése a korábban tárgyalt Thiessen poligonok szerkesztése után egyszerűen elvégezhető, ha összekötjük mindazon pontokat, amelyek Thiessen poligonjai érintkeznek egymással. Bizonyítható, hogy ez a hálózat a lehető legzömökebb (az egyenlő oldalú háromszögekhez legközelebb álló) alakzatot adja.

11.26. ábra. A Thiessen poligonok és a TIN kapcsolata

Miután a globális TIN hálózat rendelkezésre áll, az interpoláció háromszögenként (lokálisan) egy-egy ferde síkkal történik.

11.27. ábra. A háromszög csúcspontjai a síkot egyértelműen határozzák meg.

A módszer szabatos és folyamatos.

11.3.6 Lokális háromszögek

A lokális háromszögek módszere a TIN módszerrel ellentétben mindig csak a levezetendő pont környezetében építi fel a háromszöget. Az első lépésben kiválasztásra kerül a legközelebbi pont. A második legközelebbi pontra igaznak kell lennie annak a feltételnek, hogy az 1-P-2 szög ( ) nagyobb, mint 600. A harmadik legközelebbi pontnak az 1-P és 2-P irányok által kimetszett körcikkbe kell esnie. A módszer biztosítja azt, hogy a levezetendő pont mindenképpen a háromszög területére essen.

11.28. ábra. A lokális háromszögek módszerének elve

Miután a lokális háromszög rendelkezésre áll, az interpoláció egy ferde síkkal történik. A módszer szabatos és folyamatos.

11.3.7 Lejtés és görbültség

Az előzőekben a „Mi van itt?” kérdés a magasságra vonatkozott. Most ezt kiterjesztjük a pontbeli lejtésre és görbültségre.

Amint említettük a ferde síkkal való közelítés esetén a magasság a következő képlettel számítható:

ahol

  • aij – a sík együtthatói (ismeretlenek),

  • x és y – relatív koordináták (origó a P pontban).

Ebben az esetben már meghatározható az első differenciálhányadosokból a lejtés ( ), és a lejtés irányszöge ( )

= , és a

= arctan ( ) is.

A lejtés és lejtésirány osztályozásával a következő alfejezetben foglalkozunk.

Amennyiben a felszínillesztést a

másodfokú polinommal végeztük, akkor már a görbültség is képezhető a második differenciálhányadosokból . A felszín görbületi viszonyait jellemző Hesse-mátrixból

H = ,

a részletek mellőzésével, a maximális és minimális görbültség a

G max,min = ,

ahol

S = spur H = 2a20 + 2a02 , és

D = det H = a20 a02 – a112 .

A görbültség ismerete hasznos például a talajerózió modellezésében, de a lejtés és a görbültség együttes elemzése segít a domborzati formák felismerésében és lehatárolásában.

A következő táblázatban ez utóbbi lehetőséget foglaltuk össze.

Ha a lejtés közel nulla, és a

  • maximális és minimális görbültség is pozitív, akkor a pont magaspont;

  • ha maximális és minimális görbültség is negatív, akkor a pont mélypont;

  • ha a két görbültség ellenkező előjelű, akkor a pont nyeregpont.

Függetlenül a lejtéstől, ha a maximális görbültség pozitív, a minimális közel nulla, akkor a domborzati forma gerinc; ha a maximális görbültség negatív, a minimális közel nulla, akkor a domborzati forma völgy.

A kihajló lejtőnél a maximális görbültség pozitív, a minimális nulla, a behajló lejtőnél a maximális görbültség negatív, a minimális nulla.

Síknak minősül a pont, ha mind a lejtés, mind a minimális és maximális görbültség közel nulla.

Domborzati forma

Lejtés

Maximális görbültség

Minimális görbültség

Magaspont

0

+

+

Mélypont

0

-

-

Nyeregpont

0

+

-

Gerinc

x

+

0

Völgy

x

-

0

Kihajló lejtő

+

+

0

Behajló lejtő

+

-

0

Sík

0

0

0