Delauney-háromszögelés

A Wikipédiából, a szabad enciklopédiából
Delaunay-háromszögelés a síkban az üreskörök jelzésével

A geometriában és a számítástudományban egy adott P ponthalmaz Delaunay-háromszögelése egy olyan egyenes szakaszokból álló vonalhálózat, aminek sokszögtartományai köré írt gömbjei csak határukon tartalmazzák a P ponthalmaz pontjait. A korlátos sokszögtartományok tehát húrsokszögek. Ha ezek a tartományok nem mind háromszögek, akkor a Delaunay-háromszögelés elfajuló, egyébként valódi. A Delaunay-háromszögelés akkor és csak akkor valódi, ha a P halmaz pontjai között semelyik három nincs egy egyenesen, és semelyik négy nincs egy körön. Az élek száma lineárisan függ a pontok számától. A P ponthalmaz valódi Delaunay-háromszögelésének fontos tulajdonsága, hogy a P halmaz összes háromszögelés között maximalizálja a háromszögek legkisebb szögét. A Voronoj-diagramm duálisa. Ezt a háromszögelést Borisz Nyikolajevics Döloné, franciásan Boris Delaunay vezette be 1934-ben.[1] Tartalmazza a legközelebbi szomszédok gráfját, és a P ponthalmaz euklideszi minimális feszítő fáit.

Algoritmus[szerkesztés | forrásszöveg szerkesztése]

A háromszögelés elkészítésének egy módja, hogy kilépünk az eggyel magasabb dimenzióba.

Jelölje P1, P, …, Pn a megadott ponthalmaz pontjait. Felvetítjük ezeket a pontokat arra a paraboloidra, aminek egyenlete x2 + y2 = z, és meghatározzuk az alsó rész konvex burkát. Ez megadja a P1, P, …, Pn pontok Delaunay-háromszögelését.

Ez az algoritmus magasabb dimenzióra is általánosítható, ahol legfeljebb O(n^{\lceil d/2 \rceil}) tartományra kell számítani. Itt a felbontás üresgömb-felbontást ad. A valódiság szükséges és elégséges feltétele, hogy a pontok általános helyzetűek legyenek: ne legyen d + 1 pont egy hipersíkban, és d + 2 pont egy hipergömbön.

Az itt leírt algoritmus ideje n \log n konstansszorosa.

A háromszögelés a síkban maradva is megkapható.

Adva legyenek a sík P1, … , Pn pontjai. Keresünk ehhez Delaunay-háromszögelést.

Elsőként felveszünk még három pontot úgy, hogy a P1, … , Pn pontok az ezek által alkotott háromszög belsejében legyenek. Ez a háromszög lesz a kiindulási háromszögelés, ezt finomítjuk a későbbiekben. A végén ezek a pontok a belőlük induló élekkel együtt törölhetők.

A finomításhoz választunk egy új Pr pontot, és keresünk egy PiPjPk háromszöget, ami tartalmazza. Beszúrjuk a Pr pontot a PrPi, PrPj, PrPk élekkel, de figyelni kell, hogy nem lett-e a PiPjPk háromszög valamelyik éle szabálytalan. A háromszögelés egy éle szabálytalan, ha elrontja az üres kör tulajdonságot. Az ilyen élt törölni kell, és az így keletkező négyszög másik átlóját kell behúzni. Ezt mindaddig ismételni kell, amíg van az üres kör tulajdonságot elrontó él a háromszögelésben. Ha Pr két már létező háromszög határára, a PiPj élre esik, akkor mind a két háromszöget figyelembe kell venni. Be kell kötni az új éleket, és a régi éleket meg kell vizsgálni, és szükség esetén cserélni mindaddig, amíg van szabálytalan él.

Alkalmazások[szerkesztés | forrásszöveg szerkesztése]

A Delauney-háromszögelést sok helyen használják, mert kerüli a nagyon keskeny, vékony háromszögeket. A térinformatikában négyszögháló helyett a mérési pontokra illesztett Delauney-háromszögelést alkalmazzák az adatok jobb megőrzésének érdekében. Ennek segítségével a felszín könnyen háromszögelhető, ami megkönnyíti az elemző függvények alkalmazását, így az esésviszonyok, benapolás, kitettség valósághű elemzését. A háromszögvonalakkal közelíthetők a szintvonalak, számítható a felszíndarabok területe és a kiemelkedések térfogata.

A végeselem-módszerben is használják a Delauney-háromszögelést, mert kerüli a keskeny háromszögeket, és azért, mert könnyen konstruálható. A numerikus stabilitás érdekében további finomításra van szükség.

Ezen kívül még számos más alkalmazással bír, így a kristálynövekedésben, a szívritmuszavarok osztályozásában, és a fehérjék szerkezetének elemzésében.

Forrás[szerkesztés | forrásszöveg szerkesztése]

  1. Delaunay, Boris N.: Sur la sphère vide. In: Bulletin of Academy of Sciences of the USSR 7 (1934), Nr. 6, S. 793-800