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.

A Delaunay háromszögelés és a Voronoi sokszögek meghatározása, n-dimenziós algoritmus a tesszelláció létrehozására

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

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.

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 V₄. 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 V₄ végesben lévő szomszédját V₆-t és megnézzük, hogy alkotó adatpontjainál (P₆, P₈, P₄) Q közelebb van-e hozzája vagy sem, ezután megnézzük V₆ végesben lévő szomszédját V₂-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 V₄, V₃, V₅. A törölt csúcspontok alkotó adatpontjai (P₂, P₅, P₄, P₃, P₇) 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 P₂-P₄ mivel mindkét csúcspontja, melynek alkotója volt (V₄ és V₃ is) törlésre került.

Az új pont Q beillesztése öt új csúcspontot eredményezett: W₁, W₂, W₃, W₄, W₅, 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 V₃-V₂ vonalat P₃-P₄ 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. W₅ kifelé mutat Q-tól V₂ felé és P₃, P₄ é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 Delaunay háromszögelés és Voronoi cellák felhasználása

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.

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.