Delaunayova triangulace

Delaunayova triangulace je triangulace pro danou množinu bodů S na rovině, ve které pro jakýkoli trojúhelník všechny body z S , kromě bodů, které jsou jeho vrcholy, leží mimo kružnici popsanou kolem trojúhelníku. Označeno DT( S ) . Poprvé popsaný v roce 1934 sovětským matematikem Borisem Delaunayem .

Vlastnosti

Delaunayova triangulace odpovídá jedna ku jedné Voronoiově diagramu pro stejnou sadu bodů.
Jako důsledek: pokud žádné čtyři body neleží na stejné kružnici, je Delaunayova triangulace jedinečná.
Delaunayova triangulace maximalizuje minimální úhel mezi všemi úhly všech zkonstruovaných trojúhelníků, čímž se vyhne „tenkým“ trojúhelníkům.
Delaunayova triangulace maximalizuje součet poloměrů vepsaných kružnic.
Delaunayova triangulace minimalizuje diskrétní Dirichletovu funkcionalitu .
Delaunayova triangulace minimalizuje maximální poloměr minimální uzavírací koule.
Delaunayova triangulace na rovině má ze všech možných triangulace minimální součet poloměrů kružnic opsaných trojúhelníkům [1] .

Algoritmus rozděl a panuj

Tento algoritmus vychází ze standardu pro mnoho algoritmů metody redukce složitého problému na jednodušší, ve kterém je řešení zřejmé. Samotný algoritmus se skládá ze 2 kroků: $N>1$

Rozdělení původní sady na menší sady. K tomu nakreslíme svislé nebo vodorovné čáry uprostřed sady a již s ohledem na tyto čáry rozdělíme body na dvě části přibližně podél . Poté pro každou skupinu bodů rekurzivně spustíme proces dělení. $N/2$
Sjednocení optimálních triangulací. Nejprve se najdou dvě dvojice bodů, jejichž segmenty spolu se sestrojenými triangulacemi tvoří konvexní obrazec. Jsou propojeny segmenty a jeden ze získaných segmentů je vybrán jako začátek pro následný bypass. Obtok je následující: na tomto segmentu se zdá, že „nafukujeme bublinu“ směrem dovnitř k prvnímu bodu, kterého dosáhne nafukovací kruh „bubliny“. Nalezený bod je připojen k bodu segmentu, který k němu nebyl připojen. Výsledný segment je zkontrolován na průnik s již existujícími triangulačními segmenty a v případě průniku jsou z triangulace odstraněny. Poté je nový segment považován za začátek nové "bubliny". Cyklus se opakuje, dokud se začátek nekryje s druhým segmentem konvexního trupu.

Složitost rozdělení množiny , spojování - pro každé spojování konečná složitost algoritmu - [2] . $O(\log N)$ $NA)$ $O(N\log N)$

Variace a zobecnění

V trojrozměrném prostoru je podobná konstrukce možná s kruhy nahrazenými koulemi.
Zobecnění se také používají při zavádění jiných než euklidovských metrik .
Jedna z vlastností Delaunayovy triangulace - minimální součet poloměrů opsaných kružnic - může být aplikována na tzv. omezenou Delaunayovu triangulaci . Existuje n bodů, některé triangulační hrany již byly nakresleny; zbytek nakreslete tak, aby součet poloměrů kružnic opsaných byl nejmenší.

Aplikace

Minimální euklidovský kostra je zaručena na Delaunayově triangulaci, takže některé algoritmy používají triangulaci. Také pomocí Delaunayovy triangulace je euklidovský problém obchodního cestujícího přibližně vyřešen .

Při 2D interpolaci rozděluje Delaunayova triangulace rovinu na nejtlustší možné trojúhelníky, čímž se vyhne příliš ostrým a příliš tupým úhlům. Z těchto trojúhelníků lze sestavit například bilineární interpolaci .

Metoda konečných prvků , metoda numerického řešení parciálních diferenciálních rovnic, je mimořádně univerzální a s růstem výkonu počítačů a rozvojem standardních knihoven je stále populárnější. Konstrukce sítě konečných prvků však donedávna zůstávala ruční prací. Ve většině variant metody konečných prvků je chyba nepřímo úměrná sinusu minimálního nebo maximálního úhlu sítě, takže mnoho automatických algoritmů sítě používá Delaunayovu triangulaci.

Viz také

Kvazitriangulace

Poznámky

↑ Skvortsov, 2002 , věta 3, str. jedenáct.
↑ Skvortsov, 2002 , kapitola 3, algoritmus 3.1.

Literatura

Skvorcovova A. V. Delaunayova triangulace a její aplikace . - Tomsk: Nakladatelství Tomské univerzity, 2002. - 128 s. — ISBN 5-7511-1501-5 .
Skvortsov A. V., Mirza N. S. Algoritmy pro konstrukci a analýzu triangulace . - Tomsk: Nakladatelství Tomské univerzity, 2006. - 168 s. — ISBN 5-7511-2028-0 .