Dr. Sárközy Ferenc: Térinformatika
Delaunay háromszögelés (tetraéderekre bontás) - Voronoi
sokszögek (poliéderek)
Ebben a részben megismerkedünk
- a Delaunay háromszögelés és a Voronoi sokszögek
meghatározásával, az n-dimenziós algoritmussal a tesszelláció
létrehozására,
- a Delaunay háromszögelés és Voronoi cellák
felhasználásával.
A Voronoi sokszögek, más elnevezéssel
Dirichlet cellák eredetüket a matematikai krisztallográfiának
köszönhetik, s ebből következik, hogy a 3 dimenziós tér 2 dimenziós
redukálásával jöttek létre az évszázad elején. Napjainkban ellenkező tendencia
figyelhető meg, egyre gyakrabban találkozunk az elméleti és gyakorlati
irodalomban a módszer n dimenziós általánosításával.
Legyenek a síkon (térben) szabálytalan elrendezésű pontjaink.
Minden pont köré szerkeszthető egy olyan sokszög (poliéder), melynek belső
pontjai (összes pontja a határát alkotó pontok kivételével) közelebb vannak a
kérdéses ponthoz, mint az összes többi ponthoz. Az ilyen tulajdonsággal
rendelkező sokszögek (poliéderek) konvexek és folytonosan töltik ki a síkot
(teret). A meghatározásból következik, hogy a sokszög oldalai (a
poliéder oldallapjai) merőlegesek a körülvett pontot a többi ponttal összekötő
egyenesekre és felezik azokat. Természetesen nem minden sugár felező
merőleges egyenes (síklap) lesz a sokszög (poliéder) része hanem csak azok,
melyek metsződéseiből a zárt konvex sokszög (poliéder) létrejön. A sokszög
(poliéder) oldalak egyben meghatározzák az egy-egy pontból figyelembe veendő
szomszédos pontokat is, hiszen csak azok a pontok befolyásolják a sokszög
kialakulását, amelyekre menő sugarak felező merőlegesei részei a sokszögnek. Ha
minden pontot összekötünk a róla a fentiek szerint figyelembe veendő szomszédos
pontokkal, úgy síkbeli esetben, egyértelmű és bizonyos szempontból optimális
háromszögfelbontást kapunk. Ezt a felbontást nevezik Delaunay
háromszögelésnek. Térbeli esetben a szomszédosként meghatározott pontok
összekötése egyértelmű, optimális tetraéder felbontást eredményez.
A Voronoi sokszögek sarokpontjai, 2D-s esetben, a Delaunay
háromszög csúcspontjaihoz tartozó három terület találkozási helyein
találhatóak, meghatározás szerint egyenlő távolságra e három ponttól, azaz
a sarokpontok a háromszögekre szerkeszthető körök középpontjai, a
térben ez a tulajdonság úgy módosul, hogy a poliéderek sarokpontjai a
megfelelő tetraéderekre szerkeszthető gömbök középpontjai.
|
2.55 ábra -
ponthalmazra szerkesztett Voronoi sokszögek és Delaunay háromszögek
|
|
Az
elmondottak illusztrálására a 2.55 ábrán megszerkesztettük 12 szórt pont
Delaunay háromszögelését és Voronoi sokszögeit.
Az ábrán a vastag vonalak a Voronoi sokszögeket, a vékony vonalak pedig az
eredményként létrejött Delaunai háromszögelést jelölik.
|
Az optimális háromszögelés végrehajtására két dimenzióban igen
sok algoritmus ismert. Az ismertetendő n dimenziós algoritmust A. Bowyer
publikálta 1981-ben [18].
Mielőtt a számitási
lépések egymásutánját meghatároznánk célszerű eldönteni a tárolás kérdését.
Mivel a Voronoi cellák csúcspontjai mindíg három adatponttra rajzolható kör
középpontját jelölik, célszerű e csúcspontokat e háromszög pontokhoz
hozzákapcsolni. E mellett minden csúcspontnak három szomszédos csúcspontja is
van, kézenfekvő, hogy ezeket a pontokat is hozzákapcsoljuk a csúcspontokhoz.
Ezek
szerint minden csúcsponthoz két három elemű lista tartozik: az egyik
tartalmazza a kérdéses Delaunay háromszög adatpontjait, a másik a szomszédos
csúcspontokat. n - dimenzió esetén minden csúcspontnak n+1
alkotó adatpontja és n+1 szomszédos csúcspontja van.
|
|
2.56 ábra -
csúcspontok és háromszögek kapcsolatrendszere
|
Az elmondottakat 2 dimenziós esetre a 2.56 ábra segítségével
illusztráljuk.
|
A vázolt listákat az alábbi táblázatban foglaltuk össze:
A
Delaunay háromszögelést leíró listák
|
csúcspontok
|
háromszög alkotó pontok
|
szomszédos csúcspontok
|
|
első
második harmadik
|
első
második harmadik
|
V1
|
P6 P4 P5
|
V4 0 V6
|
V2
|
P1 P4 P3
|
V3 0 V7
|
V3
|
P2 P3 P4
|
V2 V4 V5
|
V4
|
P2 P3 P4
|
V1 V3 0
|
V5
|
P7 P3 P2
|
V3 0 0
|
V6
|
P6 P8 P4
|
V7 V1 0
|
V7
|
P1 P8 P4
|
V6 V2 0
|
|
2.1 táblázat
|
|
Az
ismertetendő algoritmusban nem játszik szerepet az adatpontoknak a
csomópontok körüli ciklikus rendje ezért a táblázatban az egy csúcsponthoz
tartozó adatpontok sorrendje tetszőleges.
Az
algoritmus abból indul ki, hogy felveszi az adott dimenziószámhoz tartozó
legegyszerűbb n+1 adatpont alakzatot, az úgy nevezett szimplexet,
(kétdimenziós esetben egy háromszöget, 3 dimenziós esetben egy tetraédert) és
a hozzátartozó Voronoi cella csúcspontot, melynek valamennyi szomszédja a
végtelenben van (a végtelenben lévő csúcspontokat a 2.56 ábrán és a 2.1
táblázatban 0-al jelöltük).
|
Az első
n+1 adatponttal szemben csak az a megkötés, hogy az n dimenziós
térben nem helyezkedhet el egy hipersíkon (2 dimenziós esetben a pontok nem
lehetnek egy egyenesen, háromdimenziós esetben pedig egy síkon).
Mivel
kezdetben csak a legegyszerűbb alakzathoz tartozó adatpontokat vettük fel, az
algoritmus feladata az lesz, hogy sorra illessze be a meglévő pontokat a
felvett pontok által meghatározott konvex idomba.
A 2.56 ábrán Q-al jelöltük a
beillesztendő pontot, a hozzátartozó meghatározandó területet pedig pontozott
vonallal határoltuk.
Első lépésként megkeresünk
egy olyan csúcspontot, mely az új adatpont megjelenésével törlődik. Ez a
csúcspont bármelyik lehet azok közül, melyek közelebb vannak az új adatponthoz,
mint az őket létrehozó adatpontokhoz. Egy ilyen pont mindenképpen lesz,
mégpedig az ahhoz az adatpont szimplexhez tartozó csúcspont, melyen belül az új
adatpont található. Példánk esetében legyen ez a csúcspont V4.
Ezután, ebből a csúcspontból kiindulva végigmegyünk a listáinkon és megkeressük
a többi törlendő csúcspontot is. Először megkeressük V4
végesben lévő szomszédját V6-t és megnézzük, hogy alkotó
adatpontjainál (P6, P8, P4) Q közelebb van-e hozzája
vagy sem, ezután megnézzük V6 végesben lévő szomszédját V2-t és a keresést analóg módon folytatjuk.
Az eljárás végén megkapjuk
a törlendő csúcspontok listáját, esetünkben V4, V3, V5. A törölt csúcspontok alkotó adatpontjai (P2, P5, P4, P3, P7) közvetlenül kapcsolódnak az új ponthoz Q-hoz (azaz
kétdimenziós esetben a Delaunay háromszögek, háromdimenziós esetben a
tetraéderek oldalai lesznek). Azok a korábbi összeköttetések, megszűnnek,
melyekhez tartozó valamennyi csúcspont törlésre került. Példánk esetében ilyen
a P2-P4 mivel mindkét csúcspontja, melynek alkotója volt (V4 és V3 is) törlésre került.
Az új pont Q
beillesztése öt új csúcspontot eredményezett: W1, W2, W3, W4, W5, melyek szomszédos csúcspontjait és alkotó adatpontjait kell
a továbbiakban kiszámítanunk. Minden csúcspontnál alkotó adatpontként Q-n
kívül még n olyan adatpontot kell figyelembe venni, melyek Q-val
össze vannak kötve. A tesszelláció minden vonalát n adatpont veszi körül
pld. a V3-V2 vonalat P3-P4 alkotja.
Az új csúcspontok alkotó adatpontjait és szomszédos csúcspontjait a törölt
csúcspontlista nem törölt elemei segítségével határozhatjuk meg, megkeresve a
körülöttük lévő adatpontok gyűrűjét. Pld. W5 kifelé mutat Q-tól V2 felé és P3, P4 és Q alkotják.
A vázolt algoritmus előnye, hogy mindig csak helyi
változtatásokat végez s így egy-egy pont beillesztésének időszükséglete
független a már beillesztett pontok számától. Mivel az algoritmus csak konvex
idomokba való beillesztésre készült, célszerű kezdő alakzatként a ponthalmaz
befoglaló alakzatát felvenni.
A digitális magasságmodellek
kialakulásakor, az egyszerűbb kezelhetőség kedvéért elsősorban szabályos
négyzet raszterben tárolták a magassági információt. Az esetek túlnyomó
többségében azonban a mérések által meghatározott magasságok nem estek egybe a
rácspontokkal, ezért a rácspontok magasságát interpolációval kellett
meghatározni. Közismert, hogy a közvetlen méréshez képest a legjobb
interpoláció is információ veszteséggel jár, ezért már viszonylag hamar
felmerült a kérdés, nem lehetne- e a modellben magukat a mért magasságú
pontokat tárolni?
A válasz az volt, hogy ez lehetséges, ha megoldható, hogy az
adatpontokra egyértelmű háromszöghálózatot lehessen szerkeszteni. A Delauanay
háromszögelés a 80-as évek elején bevonult a magasságmodellezésbe és azóta a
gyakorlatban használt programok javarésze (az un TIN programok) ezen az elven
alapulnak. A háromszögfelbontás nem csak a mérési eredmények konzerválása
szempontjából előnyös, hanem a különböző elemző funkciók végrehajtását
is segíti. A háromszögfelbontás ugyanis a terepfelmérést végző topográfushoz
hasonlóan síkháromszög lapokból álló poliéderekkel modellezi a bonyolultabb
terepidomokat, s ez lehetővé teszi az esésviszonyok, benapolás, kitettség
valósághű elemzését.
Az automatizált térképkészítésnél a
háromszögoldalakat, a hagyományos módszerhez hasonlóan, szintvonal
interpolálásra lehet felhasználni. A háromszögekre bontás nem gátolja a
köbtartalom és terület számításokat sem, bár a különböző metszési feladatok
végrehajtása háromszögmodellben sokkal bonyolultabb mint a négyzet raszterben.
Azt sem szabad elfelejtenünk, hogy a TIN modell tárolása lényegesen nagyobb
tároló hely igényű, mint a négyzet raszteré.
Míg a Delaunay háromszögelés a magasságmodellezés
alapeszközévé vált, a duális Voronoi cellák e téren való alkalmazásáról csak
ritkán olvashatunk. E ritka források közül Gold [19]
kutatásai alapján a Voronoi cellák egy érdekes alkalmazását szeretnénk
felvázolni.
|
2.57 ábra - a
"lopott területek" módszere
|
Ezeket
a területrészeket lopott területeknek, magát az interpoláló módszert pedig a
lopott területek módszerének nevezzük.
|
A 2.57 ábrán megismételtük a 2.56 ábra egy
kis részletét.
Tételezzük fel, hogy a Pi pontok magasságát megmértük és ezek
felhasználásával szeretnénk a Q pont magasságát meghatározni. Az egyik
legegyszerűbb interpolálási eljárás a súlyozott számtani közép.
A szokásos modszerek súlyként az
|
|
vagy
|
|
reciprok távolságokat
|
illetve távolság négyzeteket használják.
Sokkal kézenfekvőbb azonban ha azokkal a területrészekkel súlyozunk, melyeket
a Q Voronoi cellája kimetsz a Pi pontokhoz tartozó
Voronoi cellákból.
|
Hogy a súlyozás nem közömbös az eredmény szempontjából, azt
jól mutatja a 2.57 ábra egyszerű példája. Ha a h-val jelölt
pontmagasságokat a megfelelő pontnak Q-tól mért távolsága négyzetének
reciprokával súlyozzuk, úgy hQ=129.5; ha azonban
súlyokként a "lopott területeket" használjuk úgy a keresett magasság hQ=134.9. Nem
szorul magyarázatra, hogy a különböző súlyozás következtében az eredmények
jelentősen különböznek. Ha a terepmérés során ott választottuk a magassági
pontokat, ahol jól reprezentálják a környező terepet, akkor a lopott
területekkel való súlyozás nyújtja a megbízhatóbb eredményeket.
A Voronoi cellákat gyakran alkalmazzák a 2 D-s térinformatikai
rendszerekben pontbeli adatforrások attribútum értékeinek síkbeli
kiterjesztésére. A meteorológiai állomások hálózatára szerkesztett Voronoi
cellákkal gyakran modellezik pld. a csapadék eloszlást. Az, hogy mennyivel
indokoltabb ez a módszer egyéb interpoláló eljárásoknál, mindig csak a konkrét
jelenség és kapcsolatrendszere együttes vizsgálata alapján dönthető el.
Napjaink geoinformációs
modellezésében, kutatási szinten, egyre több figyelmet fordítanak az n
dimenziós Voronoi hyperpoliéderekre. Ezek a hipertestek ugyanis
alkalmasak n-3 tulajdonságérték (pld. tengeri modellek esetén sűrűség,
hőmérséklet, sókoncentráció stb.) kvázi-geometriai modellezésére, s ezzel az
attributiv adatok tárolásának és manipulálásának ismert geometriai alapokra
való visszavezetésére. Az, hogy milyen körülmények között gazdaságos a
geometriai attribútum kezelés még további elmélyült vizsgálatokat igényel.
A téma kapcsán nem árt
utalni egy olyan teljesen új koncepcióra, mely a jövőben még forradalmasíthatja
a 3 dimenziós térinformatikát. Ha fizikai hasonlattal élünk, a Voronoi cellákat
úgy tekinthetjük, mint olyan szappanbuborékokat, melyeket a tér szórt
pontjaiban egyenlő túlnyomással generálunk. A túlnyomás hatására a buborékok
mindaddig növekednek, míg el nem érik egymást, és egymáshoz feszülve,
folyamatosan kitöltik a pontok konvex héjával körülhatárolt térrészt. Az új
koncepció buborék analógiájában a szórt pontokon különböző túlnyomással
generáljuk a buborékokat s ily módon lehetővé tesszük a pontok esetlegesen
különböző megbízhatósági mérőszámainak, illetve érvényességi tartományainak
figyelembe vételét. Az így generált buborékok is hézag nélkül töltik ki a
konvex héjat, de az eredeti Voronoi celláktól eltérő geometriával. Ennek az új
geometriának a kutatását elkövetkező feladataink között tartjuk számon.
Megjegyzéseit
E-mail-en várja a szerző: Dr Sárközy Ferenc