Delaunay háromszögelés
A Delaunay - háromszögelés egy sík S pontjainak adott halmazára vonatkozó háromszögelés, amelyben bármely háromszögben az S -ből származó összes pont , kivéve azokat a pontokat, amelyek annak csúcsai, kívül esnek a háromszög körül leírt körön. Jelölve: DT( S ) . Boris Delaunay szovjet matematikus írta le először 1934 -ben .
Tulajdonságok
- A Delaunay-háromszögelés egy az egyhez felel meg a Voronoi-diagramnak ugyanarra a ponthalmazra.
- Következmény: ha nincs négy pont ugyanazon a körön, a Delaunay-háromszögelés egyedi.
- A Delaunay-háromszögelés maximalizálja a minimális szöget az összes megszerkesztett háromszög összes szöge között, elkerülve ezzel a "vékony" háromszögeket.
- A Delaunay-háromszögelés maximalizálja a beírt körök sugarának összegét.
- A Delaunay-háromszögelés minimalizálja a diszkrét Dirichlet funkciót .
- A Delaunay-háromszögelés minimalizálja a minimális befoglaló gömb maximális sugarát.
- A Delaunay-háromszögelés síkon rendelkezik a háromszögekre körülírt körök sugarainak minimális összegével az összes lehetséges háromszögelés között [1] .
Oszd meg és uralkodj algoritmus
Ez az algoritmus a sok algoritmusra vonatkozó szabványos módszeren alapul, amely egy összetett problémát egyszerűbbre redukál, amelyben a megoldás nyilvánvaló. Maga az algoritmus 2 lépésből áll:
- Az eredeti készlet felosztása kisebb készletekre. Ehhez függőleges vagy vízszintes vonalakat húzunk a halmaz közepére, és már ezekhez a vonalakhoz képest két részre osztjuk a pontokat körülbelül a mentén . Ezt követően minden pontcsoportnál rekurzívan elindítjuk az osztási folyamatot.
- Optimális háromszögelések uniója. Először két pontpárt találunk, amelyek szakaszai a megszerkesztett háromszögletekkel együtt konvex alakot alkotnak. Szegmensekkel vannak összekötve, és a kapott szegmensek egyikét a következő kiiktatás kezdeteként választjuk. A kitérő a következő: ezen a szakaszon úgy tűnik, hogy „fújjuk fel a buborékot” befelé az első pontig, amelyet a „buborék” felfújó köre elér. A talált pont a szegmens azon pontjához kapcsolódik, amely nem csatlakozott hozzá. Az eredményül kapott szegmensben ellenőrzik a már meglévő háromszögelési szakaszokkal való metszéspontot, és metszés esetén eltávolítják a háromszögelésből. Ezt követően az új szegmens egy új "buborék" kezdete. A ciklust addig ismételjük, amíg a kezdet egybe nem esik a konvex hajótest második szegmensével.
A halmaz felosztásának bonyolultsága , összekapcsolás - minden egyes összekapcsolásnál az algoritmus végső összetettsége - [2] .
Változatok és általánosítások
- A háromdimenziós térben hasonló konstrukció lehetséges a körök helyett gömbökkel.
- Az általánosításokat az euklideszitől eltérő metrikák bevezetésekor is alkalmazzák .
- A Delaunay-háromszögelés egyik tulajdonsága - a körülírt körök sugarainak minimális összege - alkalmazható az úgynevezett korlátozott Delaunay-háromszögelésre . n pont van , a háromszögelési élek egy részét már megrajzoltuk; rajzoljuk meg a maradékot úgy, hogy a körülírt körök sugarainak összege a legkisebb legyen.
Alkalmazás
A minimális euklideszi feszítőfa garantáltan Delaunay-háromszögelésen van, így egyes algoritmusok háromszögelést használnak. Ezenkívül a Delaunay-háromszögelés révén megközelítőleg megoldódik az euklideszi utazó eladó probléma .
A 2D interpolációban a Delaunay-háromszögelés a lehető legvastagabb háromszögekre osztja fel a síkot, elkerülve a túl éles és túl tompa szögeket. Ezekből a háromszögekből fel lehet építeni például bilineáris interpolációt .
A végeselemes módszer, a parciális differenciálegyenletek numerikus megoldására szolgáló módszer rendkívül sokoldalú, és a számítógépek teljesítményének növekedésével és a szabványos könyvtárak fejlődésével egyre népszerűbb. A végeselemes háló építése azonban egészen a közelmúltig kézi munka maradt. A végeselemes módszer legtöbb változatában a hiba fordítottan arányos a minimális vagy maximális hálószög szinuszával, ezért az automatikus hálózási algoritmusok közül sok Delaunay-háromszögelést használ.
Lásd még
Jegyzetek
- ↑ Skvorcov, 2002 , 3. tétel, p. tizenegy.
- ↑ Skvortsov, 2002 , 3. fejezet, 3.1 algoritmus.
Irodalom
- Skvortsov A. V. Delaunay háromszögelés és alkalmazása . - Tomszk: Tomszki Egyetem Kiadója, 2002. - 128 p. — ISBN 5-7511-1501-5 .
- Skvortsov A. V., Mirza N. S. Algoritmusok a háromszögelés felépítéséhez és elemzéséhez . - Tomszk: Tomszki Egyetem Kiadója, 2006. - 168 p. — ISBN 5-7511-2028-0 .