|
39. Fejezet - A TIN MODELL
Szerkesztette: Thomas K. Poiker, Simon Fraser University
Magyar változat: Závoti József, Geodéziai és Geofizikai Kutató Intézet, Sopron
A. BEVEZETÉS
A TIN modell
TIN-ek létrehozása
B. HOGYAN VEGYÜNK FEL PONTOKAT?
1. Fowler és Little algoritmusa
2. VIP (Nagyon fontos pontok) algoritmusa
3. Heurisztikus elhagyás
C. HOGYAN HÁROMSZÖGESÍTSÜNK EGY TIN-T?
1. Távolságrendezés
2. Delaunay háromszöglefedés
D. TIN-EK ALKOTÁSÁNAK ALTERNATÍV MÓDSZEREI
Törésvonalak
TIN-ek szintvonalakból
E. TIN-EK TÁROLÁSA
1. Háromszög háromszöggel
2. Pontok és szomszédaik
A két struktúra összehasonlítása
F. ALGORITMUSOK TIN-EKEN
Dőlés és irány
Szintvonalazás
Vízgyűjtőhálózatok meghatározása
IRODALOM
ELLENŐRZŐ KÉRDÉSEK
MEGJEGYZÉSEK
39. Fejezet - A TIN MODELL
Szerkesztette: Thomas K. Poiker, Simon Fraser University
Magyar változat: Závoti József, Geodéziai és Geofizikai Kutató Intézet, Sopron
A. BEVEZETÉS
- a háromszögesített szabálytalan hálózat (TIN) modell egy lényeges alternatívája a szabályos raszter DTM-nek és adaptálták számos GIS-be és automatikus térképszerkesztés szintvonalszerkesztő programcsomagba
- a TIN modellt a korai 1970-es években fejlesztették ki abból a célból, hogy egyszerű módon felépítsenek egy felületet szabálytalan eloszlású pontok halmazából
- számos prototípus rendszert fejlesztettek az 1970-es években
- TIN-t használó kereskedelmi rendszerek az 1980-as években kezdtek megjelenni szintvonalszerkesztő programok formájában, vagy GIS-ek részeként
A TIN modell
- a szabálytalan eloszlású mintapontok a terephez illeszthetők, több ponttal az egyenetlen terep területein és kevesebbel a sima terepen
- egy szabálytalan eloszlású minta ezért hatékonyabb egy felület előállításakor
- egy TIN modellben a mintapontok egyenesekkel vannak összekötve úgy, hogy háromszögek keletkezzenek
- minden háromszög belsejében a felületet általában egy síkkal állítjuk elő
- azáltal, hogy háromszögeket használunk, biztosítjuk, hogy a mozaikszerű felület minden darabja illeszkedni fog a szomszédos darabokhoz - a felület folytonos lesz - miután mindegyik háromszög felületét meghatározzák a három sarokpont magasságai
- néhány esetben lehetne értelme összetettebb poligonokat használni mozaikelemekként, de azok mindig felbonthatók háromszögekre
- például, ha egy fennsík vízmosás által kimosódik , a megmaradó fennsík egy sima (sík) terület lenne egy szabálytalan, többoldalú poligonnal határolva. A TIN modellben ezt az alakzatot több, azonos magasságú háromszög állítaná elő
- vektoralapú GIS-eknél a TIN-ek úgy tekinthetők, mint dőlés, irány és terület tulajdonságokkal rendelkező poligonok, amelyekből három csúcs magasság tulajdonságokkal és három szél dőlés és irány tulajdonságokkal rendelkezik
- a TIN modell egyszerűsége és gadaságossága miatt vonzó
- ráadásul terepek bizonyos típusai nagyon célszerűen sík oldalakkal háromszögekre oszthatók
- ez különösen igaz folyamok által kimosott tájakra
- ugyanakkor más tájak, mint például a jéggel borítottak, nem állíthatók elő jól sík háromszögekből
- háromszögek legjobban olyan területeken működnek, amelyek dőlése élesen törik, ahol a megtört TIN élek sorbarendezhetők. Pl. gerincek vagy mélyedések mentén
TIN-ek létrehozása
- egyszerűsége ellenére egy TIN modell készítése sok döntést igényel:
- hogyan vegyünk fel mintapontokat?
- sok esetben ezeket néhány meglevő, sűrű DTM-ből vagy digitalizált szintvonalakból kell kiválasztani
- normális körülmények között egy 100 pontból álló TIN ugyanolyan jól fog működni, akárcsak egy több száz pontból álló DTM egy felület előállításakor
- hogyan kapcsoljunk pontokat háromszögekbe?
- hogyan modellezzük a felületet az egyes háromszögekben?
- ez majdnem mindig megoldott egy sík felület használatával
- azonban, ha a felület szintvonalakat tartalmaz, a vonalak egyenesek és párhuzamosak lesznek minden háromszögben, de erős töréseket szenvednek a háromszög széleinél
- következésképpen a TIN néhány megvalósítása a felületet minden háromszögben egy matematikai függvény segítségével adja meg, amelyet arra a célra választottak ki, hogy biztosítsa a dőlés folytonos, nem szakadásos változását a háromszög éleinél
B. HOGYAN VEGYÜNK FEL PONTOKAT?
- adott egy sűrű DTM vagy a digitalizált szintvonalak halmaza, hogyan kellene kiválasztani úgy pontokat, hogy a felület pontosan legyen előállítva?
- egy DTM-ből való választásra tekintsük a következő három módszert!
- valamennyi a felület jellemző töréseinél próbál kiválasztani pontokat
- ilyen törések gyakoriak a terepen és hiányoznak sima matematikai felületeken
1. Fowler és Little algoritmusa
- ez a megközelítés olyan felület-specifikus pontok fogalmán alapszik, amelyek különleges szerepet játszanak a felületen
- pl. olyan jellegzetességeket képviselnek, mint csúcsok és gödrök
Eljárás
- először vizsgáljuk meg a felületet egy 3x3-as ablak segítségével úgy, hogy minden lépésben egy kis, 9 pontból álló tömböt tekintünk
- jelölje a középpont 8 szomszédját + , ha az magasabb, -, ha az alacsonyabb
- egy pont csúcsnak tekinthető, ha mind a 8 szomszédja alacsonyabban van (8 db +)
- egy pont gödörnek tekinthető, ha mind a 8 szomszédja magasabban van (8 db -)
- egy pont nyeregpontként viselkedik, ha a + és - jelek váltakoznak a pont körül, legalább két teljes ciklusban, pl.
+ + -
- -
- + + (2 ciklus)
vagy
+ - +
- -
+ - + (4 ciklus)
- a következőben a felületet egy 2x2-es ablak segítségével vizsgáljuk meg
- a szélek kivételével minden pont az ablak négy helyén jelenik meg
- egy pont potenciális gerincpont, ha az ablak tetszőleges helyzetében soha nem a legalacsonyabb
- egy pont potenciális mélyedéspont, ha az ablak tetszőleges helyzetében soha nem a legmagasabb
- ekkor egy nyeregpontból kiindulva haladjunk a szomszédos gerincpontokon keresztül, amíg egy csúcsot elérünk
- ehhez hasonlóan, haladjunk a nyeregpontból a szomszédos mélyedéspontokon keresztül, amíg egy gödröt elérünk
- a TIN készre alakítása
- ennek a folyamatnak az eredménye csúcsok, gödrök, nyeregpontok, gerincvonalak és mélyvonulatok egy összefüggő halmaza
- Fowler és Little ajánlották, hogy a pontok számát minden gerincvonalon és mélyvonulaton csökkentsük elvékonyítással egy szabványos elvékonyító algoritmus segítségével
- kívánatos lehet olyan pótlólagos pontokat a DTM-ből hozzáadni, amelyek nincsenek gerinceken vagy mélyedéseken, ha ezzel valamilyen lényeges eltérést a valóságos felülettől jelentősen csökkenteni tudunk
- minden kiválasztott pont között háromszögeket építünk
- az eredményül kapott felület különbözni fog az eredeti DTM-től, néhány területen talán lényegesen
Megjegyzések:
- Fowler és Little algoritmusa komplex
- bizonyos terepviszonyok esetén más módszereknél jobb eredményeket ad, különösen ahol gerincek mentén a dőlésnek éles törései vannak és ahol a csatornák élesen bemetszettek
- a jó működéshez szükség lehet egy alapos "finom hangolásra"
2. VIP (Nagyon fontos pontok) algoritmusa
- az előző algoritmussal szemben, amelyik megprobálja azonosítani a terep fontos tulajdonságait, a VIP egy ablak használatával a felületet lokálisan vizsgálja
- ez egyszerűsítése annak a technikának, amely az ARC/INFO ESRI-ében használatos
Eljárás
- minden pontnak 8 szomszédja van, 4 átlósan ellenkező párt alkotva, pl. fent és lent, jobbra és balra, balra fent és jobbra lent, továbbá jobbra fent ás balra lent
- minden pont esetén sorra vizsgáljunk meg minden szomszédos párt
- két szomszédos pontot kössünk össze egy egyenessel és számoljuk ki a középpont merőleges távolságát ettől az egyenestől
- átlagoljuk a négy távolságot azért, hogy a pont "fontosságára" nyerjünk egy mértéket
- növekvő fontossági sorrendben töröljünk pontokat a DTM-ből, először a legkevésbé fontosat törölve!
- mindezt addig folytatjuk, amíg a következő két feltétel valamelyike nem teljesül:
- a pontok száma elér egy előre megadott határt
- a fontosság elér egy előre megadott határt
Megjegyzések:
- lokális természete folytán ez a módszer akkor a legjobb, ha a törölt pontok aránya kicsi
- mivel fontos szerepe van az egyenes vonalaknak és a TIN által alkalmazott síkoknak, görbült felületekre kevésbé kielégítő
3. Heurisztikus elhagyás
- ez a módszer a problémát optimalizálási feladatként kezeli
- adott egy sűrű DTM, keressük meg egy előre megadott számú pont legjobb részhalmazát úgy, hogy a TIN a lehető legjobb előállítását adja a felületnek, ha a pontok össze vannak kötve a háromszögeken átfektetett síkokkal
Eljárás
- induljunk a teljes DTM-mel
- sorra vizsgáljunk meg minden pontot
- ideiglenesen hagyjuk el a pontot és ennek megfelelően módosítsuk a környező háromszögeket
- keressük meg azt a háromszöget, amelyik tartalmazza az elhagyott pontot
- határozzuk meg a pont magassága és az új felület pontbeli magassága közötti különbséget
- állítsuk vissza az elhagyott pontot és tároljuk a kiszámolt magasságkülönbséget
- folytassuk az eljárást, sorra elhagyva valamennyi pontot
- ha minden pontot elhagytunk, töröljük azt a pontot, amelyik a legkisebb különbséget okozta és az eljárást kezdjük elölről
Megjegyzések
- a TIN valószínűleg pontosabb lenne, ha a különbségeket nem csak az elhagyott pontokra határoznánk meg, hanem minden korábban, a módosított háromszögekben fekvő elhagyott pontra is, de ez időigényes lenne
- ahelyett, hogy a DTM-ből választanánk pontokat, a legjobb megoldás (abban az értelemben, hogy a lehető legjobb TIN-t készítsük adott számú pont esetén) az lehet, hogy TIN pontokat nem az eredeti raszterhelyeknél és magasságoknál helyezünk el
- ezeket a pontokat légifelvételekből vagy földi felmérésekből választhatjuk
C. HOGYAN HÁROMSZÖGESÍTSÜNK EGY TIN-T?
- ha kiválasztottuk a TIN pontok egy halmazát, ezek lesznek a háromszöghálózat csúcsai
- többféleképpen köthetők össze a csúcsok háromszögekbe
- előnyben részesítjük a 60 fokhoz közeli szögekkel rendelkező, "telt" háromszögeket, mivel ezek biztosítják, hogy tetszőleges felületi pont olyan közel van egy csúcshoz, amennyire csak lehet
- ez lényeges, mert a felület előállítása valószínűleg a csúcsoknál a legpontosabb
- tekintsük a következő két módszert a háromszögek felépítésére
- a gyakorlatban majdnem valamennyi rendszer a másodikat használja
1. Távolságrendezés
Eljárás
- számoljuk ki valamennyi pontpár közötti távolságot és rendezzük a legkisebbtől a legnagyobbig
- kössük össze a legközelebbi pontpárt
- kössük össze a következő legközelebbi párt, ha az összekötő szakasz nem metsz korábbi szakaszokat
- addig ismételjük, amíg további vonalat nem lehet választani
- a pontok ezzel össze lesznek kötve háromszögekkel
- ez a módszer hajlamos sok keskeny háromszöget produkálni az előnyös "telt" háromszögek helyett
2. Delaunay háromszöglefedés
- definíció szerint 3 pont egy Delaunay háromszöget alkot akkor és csak akkor, ha a rajtuk keresztülmenő kör nem tartalmaz más pontot
- másik lehetőség a Delaunay háromszöglefedés definiálására a következő:
- osszuk fel a térképet úgy, hogy hozzárendelünk minden helyet a legközelebbi csúcshoz
- ezzel az eljárással előállított határok a poligonok egy halmazát alkotják, amelyeket Thiessen poligonoknak vagy Voronoi vagy Dirichlet tartományoknak nevezünk
39.1. ábra - Delaunay háromszögek Thiessen poligonokból
- két csúcs össze van kötve a Delaunay háromszöglefedésben, ha a Thiessen poligonjaiknak van közös éle
- ez a módszer az előnyös telt háromszögeket szolgáltatja
- a Delaunay hálózat határélei alkotják azt a konvex burkot, amelyik a legkisebb, minden csúcsot tartalmazó poligon
Eljárás
- több technika létezik háromszögek felépítésére :
1. mivel a konvex burok mindig része lesz a Delaunay hálózatnak
- kezdjük ezzel a széllel és haladjunk befelé, amíg a hálózat kész lesz
2. kössük össze a legközelebbi párt, amelynek definició szerint egy Delaunay élnek kell lenni
- keressünk egy harmadik pontot úgy, hogy ne essen más pont a rajtuk keresztülmenő körbe
- folytassuk ezekből az élekből kifelé haladva a legközelebbi pontra
- problémák
- a Delaunay háromszögek nem hierarchikusak
- azokat nem lehet egyesíteni úgy, hogy nagyobb háromszögeket alkossanak
- ha azokat kisebb háromszögekre osztjuk, azok már rossz alakúak lehetnek ( nem "teltek")
D. A TIN-EK ALKOTÁSÁNAK ALTERNATÍV MÓDSZEREI
Törésvonalak
- a fent bemutatott módszerek lényege, hogy először TIN csúcsokat találnak, majd azokat háromszögekkel kötik össze
- a TIN-ek fő előnye az a képességük, hogy megfogják a dőlés töréseit, ha az élek csatlakoztathatók ismert gerincekhez vagy mélyedésekhez
- ez másfajta megközelítést követel, ahol a pontok háromszögesítése után a "törésvonalak" élek formájában bekerülnek a háromszög-hálózatba
- az eredmény általában nem-Delaunay, azaz egy él nem feltétlenül él a csúcsok Delaunay hálózatában
- ez a megközelítés be van építve néhány TIN szoftverbe, pl. az ARC/INFO TIN modulba
TIN-ek szintvonalakból
- szintvonalak a digitális magassági adatok megszokott forrását képezik
- ahelyett,hogy a szintvonalakból egy rácsra (DTM) és aztán egy TIN-re térnénk át, célszerűbb a szintvonalakból közvetlenül TIN-t nyerni
- egy TIN-t megalkothatunk a digitalizált szintvonalak kiválogatott pontjaival
- a kiválogatás szolgáltathat olyan háromszöget, melynek három csúcsa ugyanazon a szinten van (ugyanazon magasságon)
- egy ilyen "lapos háromszög"-nek nincs határozott iránya, ami problémákat okoz a túlfolyás modellezésében
- ezen problémák elkerülésére kigondoltak néhány lehetőséget
E. TIN-EK TÁROLÁSA
- alapjában véve két lehetőség létezik háromszöghálózatok tárolására
1. Háromszög háromszöggel
2. Pontok és szomszédaik
39.2. ábra - TIN-ek tárolása
1. Háromszög háromszöggel
- ebben az esetben általában egy rekord tartalma:
- egy hivatkozási szám a háromszögre
- a három csúcs (x, y, z) koordinátái
- a három szomszédos háromszög hivatkozási száma
- mivel egy csúcs átlagosan hat háromszögben vesz részt, a koordináták ismétlését el lehet kerülni egy különálló csúcs-file létrehozásával és hivatkozva azokra a háromszög file-ban
2. Pontok és szomszédaik
- ezen alternatíva keretében minden csúcsra vonatkozólag tároljuk az alábbiakat:
- egy azonosító szám
- az xyz koordináták
- hivatkozások (pointerek) a szomszédos csúcsokra az óramutató forgásával megegyezően vagy ellentétesen
- ez a struktúra volt az eredeti TIN struktúra ( Peucker et al, 1978 )
A két struktúra összehasonlítása
- mindkét struktúra szükséges - a céltól függően
- a dőlés analízise igényli az elsőt
- szintvonalazás és más metszési eljárások a legjobban a másodikkal működnek
- mindaddig, amíg egyiket elő lehet állítani a másikból közel lineáris időn belül (azaz egy kimerítő pontonkénti keresés nélkül), mindegyik alkalmas lehet
- a második általában kevesebb tárolási helyet igényel
- azonban a különböző TIN struktúrákon belüli megtakarítások eltörpülnek ahhoz képest, amikor a szabályos rácsból pontredukcióval jutunk el a háromszöghálózathoz
F. ALGORITMUSOK TIN-EKEN
Dőlés és irány
- DTM-hez viszonyítva, TIN-t használva, bizonyos helyeken egyszerű a dőlés és az irány meghatározása - egyszerűen meghatározzuk a tartalmazó háromszög dőlés és irány tulajdonságait
Szintvonalazás
39.3. ábra - TIN-ek szintvonalazása
Példa: adjuk meg a 100 m-es szintet!
- kezdjük annak meghatározásával, egy másik algoritmust használva, hogy egy él metszi a 100 m-es szint síkját
- a szint síkja feletti csúcs az (r), "referencia pont" és az egyik alatta levő csúcs az (s), "alpont"
- hozzunk létre a memóriában egy helyet azon pontpárnak, amelyet jelenlegi élnek fogunk hívni
- az első szintvonalpont, a P1 kiszámítása, triviálisan lineáris számolás
- most váltsunk a metszési eljárásra
- tekintsük a harmadik csúcsot a háromszögben és kérdezzük:
vajon ez egy referencia vagy egy alpont?
ehhez megnézzük, vajon a szint síkja felett vagy alatt van-e?
- az eredmény felváltja a megfelelő értéket a jelenlegi élben és rátérünk a következő szintpont számítására
- a jelenlegi él csúcsai egy második háromszöget jelölnek ki, amelynek harmadik csúcsa a következő jelölt
Vízgyűjtőhálózatok meghatározása
- két megközelítést lehet használni vízgyűjtő és vízválasztó hálózatok megtalálására:
1. Kezeljünk minden háromszöget diszkrét elemként!
- mint a DTM-nél, a víz egyik háromszögből a másikba áramlik, minden esetben a legmeredekebb dőlés irányába lévő szomszédot választva
2. Kezeljük a felületet síkok mozaikjaként!
- az áramlás két formája fordul elő - csatorna és felszíni lefolyás
- a víz valamennyi háromszög felett folytonos rétegként folyik és összegyűlik az élek mentén
- ebben a modellben a víz összegyűlhet két háromszög közötti csatornában, folyhat egy csúcshoz és folyhat egy vagy több háromszög felületére
- ez utóbbi esetben meg kell adnunk egy csatornát ezen háromszögek tetőpontjáról a legmeredekebb dőlés egyenese mentén
- ha egynél több ilyen háromszög van, akkor egy elágazást tartalmaz és a víz a tetőpontról egynél több irányban és egynél több vízgyűjtő medencébe folyik
- ez kényelmetlen, mivel így nincs többé pontos definíciónk a vízválasztóra
IRODALOM
Chen, Z., and J.A. Guevara, 1987. "Systematic selection of very important points (VIP) from digital terrain
models for construction triangular irregular networks," Proceedings, AutoCarto 8, ASPRS/ACSM. Falls Church, VA, pp. 50-56. A description of ESRI's VIP approach to constructing a TIN
Fowler, R.J., and J.J. Little, 1979. "Automatic extraction of irregular network digital terrain models"Computer Graphics 13:199-207
Heller, M., 1986. "Triangulation and Interpolation of Surfaces," in: R. Sieber and K. Brassel (eds), "A Selected Bibliography on Spatial Data"
Handling: "Data Structures, Generalization and Three-Dimensional Mapping", Geo-Processing Series, vol 6,
Department of Geography, University of Zurich, pp. 36 - 45. A good overview with literature, mainly on triangulation
Mark, D.M., 1975. "Computer Analysis of Topography: A Comparison of Terrain Storage Methods",
Geografisker Annaler 57A:179-188. A quantitative comparison of regular grids and triangulated networks
Mark, D.M., 1979. "Phenomenon-Based Data-Structuring and Digital Terrain Modelling," Geo-Processing
1:27-36. A very interesting conceptual article proposing a phenomenon-based approarch to data structuring. Such an approach has to involve expert knowledge of the phenomenon
Peucker, T.K., R.J. Fowler, J.J. Little and D.M. Mark, 1978. "The Triangulated Irregular Network",
Proceedings, American Society of Photogrammetry: Digital Terrain Models (DTM) Symposium, St. Louis, Missouri, May 9-11,
ELLENŐRZŐ KÉRDÉSEK
1. Ismertesse a szabályos rács és a háromszöghálós megközelítés közötti különbségeket! Alkalmazza az ismereteket a dőlés, a szintvonalazás és a láthatóság kiszámítására!
2. Mark 1979-es tanulmánya ismertette, hogy a TIN modell bizonyos földrajzi jelenségek sajátosságainak leírására jobban alkalmas. Elfogadja? Milyen fajta földformákhoz alkalmas a TIN jobban és melyekhez kevésbé?
3. Vitassuk meg a különböző módszereket, amelyek ajánlottak a TIN csúcsok DTM-ből való kiválasztására, továbbá a relatív erősségüket és gyengeségüket!
4. Írja le, hogyan nyerhető információ a TIN-ből az áramlás irányáról, továbbá a tárgyalt folyamhálózat sajátosságait! Hogyan hasonlítanak ezek azokhoz a hálózatokhoz, amelyeket a DTM-ekből vezetnek le?
|
