Delaunaytriangulointi

Delaunaytriangulointi on pistejoukon muodostama kolmioverkko, jossa kunkin muodostuvan kolmion ympärysympyrän sisäpuolella ei ole muita pisteitä. Tämä ominaisuus tunnetaan ympyrätyypin tyhjyyden (circumcircle empty) periaatteena, ja sen vuoksi triangulaatio pyrkii välttämään kapeita kolmioita.

Delaunaytriangulaation duali on Voronoi-diagrammi. Tämä tarkoittaa, että kummankin pisteen ympärille syntyvä Voronoi-solmu vastaa Delaunay-triangulaation pistettä ja naapuripisteet olevan yhteisiä akooppeja. Delaunay-päätelmät ovat usein hyvin tasapainoisia, mikä tekee triangulaatiosta suosittua verkkojen ja metritason mallinnuksessa.

Algoritmit ja ominaisuudet: 2D-Delaunay-triangulaation voi rakentaa useilla tavoilla, kuten Bowyer–Watson -algoritmilla, inkrementaalisella lisäyksellä tai jakamis-yhdistelemällä sekä kuuluisilla käännöissä (edge flips). Komplekssisuus on tyypillisesti O(n log n). Delaunay-triangulaatio voidaan yleistää korkeammille ulottuvuuksille (3D tetraedroinniksi ja yleisemmin D-pisteiden Delaunay-simppliciaalikompleksiksi). Yleensä reuna- ja sisäoletukset huomioiden voidaan puhua myös rajoitetusta Delaunay-triangulaatiosta, jossa tietyt reunat tai esteet on pakko säilyttää.

Sovellukset: sen käyttöalueisiin kuuluvat verkko- ja mesh-muotoilu (finite element -menetelmiä varten), interpolaatiot (esim. luonnollinen naapuri -menetelmät), tietotekniikka ja GIS sekä grafiikka, joissa tasainen ja luotettava triangulaatio on hyödyksi.

Lyhyt historia: nimeäminen liittyy Boris Delaunyn työn 1930-luvulta; periaate on laajasti käytössä nykyisessä tuotannollisessa ja teoreettisessa geometriassa.