Delaunaytriangulatsiooni

Delaunay-triangulatsioon on punktide kogumi planar triangulatsioon, mille korral iga kolmnurga ümbermõõdringus ei ole ühtegi teist punkti. Selline omadus aitab vältida väga teravate nurkadega kolmnurkade teket ja soodustab ühtlasemat geomeetrilist ja rakenduste kvaliteeti. Delaunay-triangulatsiooni peamiseks omaduseks on selle seos punktide ja nende ümbermõõdringide vahel.

See on Voroni diagrammi dual, mis tähendab, et kahe punkti vahel moodustuvad servad siis, kui nende Voroni piirkonnad jagavad piirjoont. Delaunay-triangulatsioon pakub seetõttu loogilist struktuuri sujuvate ruumiliste lõikuspindade ja geomeetriliste omaduste uurimiseks ning on tihti eelistatud baasstruktuuriks ruumiliste andmete meshamiseks.

Algoritmid ja keerukus: Delaunay-triangulatsiooni konstrueerimiseks on mitmeid meetodeid, sealhulgas Bowyer–Watson, inkrementaalne ja divide-and-conquer-lähenemised. Üldine ootuspärane tööaeg on O(n log n); halvima korral võib see olla O(n^2). Kui andmed on degeneratiivsed (nt neli punkti sama ümbermõõdringil), võib triangulatsioon olla mitmekordne ja unikaalse tulemuse puududa.

Rakendused ja tähendus: Delaunay-triangulatsiooni kasutatakse laialdaselt GIS-is ja geoinformaatikas, arvutigraafikas ning erinevates simulatsioonides ja inseneeringus. FEM-i võrkude genereerimine, interpolatsioon ja loomulik naaber-interpolatsioon on levinud kasutusalad. Delaunay-triangulatsiooni üldistused on saadaval kõrgemates dimensioonides, kus moodustuvad vastavalt tetraedrid või muud hüpertriangelid.

Ajalugu: nime on saanud vene matemaatik Boris Delaunay, kes tutvustas meetodit 1934. aastal. Punktide degeneratsioonide korral võib triangulatsioon olla mitmekesine, kuid üldises „neutraalsetes“ olukordades on see konstruktsioon laialdaselt kasutatav ja hästi mõistetav.