Delaunay-triangulatie

Een delaunay-triangulatie, waarbij de omgeschreven cirkels getoond zijn

De delaunay-triangulatie is in de computationele meetkunde een triangulatie op een discrete verzameling punten, bestaande uit een netwerk van driehoeken met als hoekpunten de punten van de verzameling. Daarbij geldt voor elke driehoek dat er in de omgeschreven cirkel van de driehoek geen enkel ander punt van de verzameling mag liggen.

Delaunay-triangulatie is genoemd naar de Russische wiskundige Boris Delaunay of Delone (Delaunay is de Franse schrijfwijze van zijn naam).

Als alle punten in de verzameling op eenzelfde rechte lijn liggen, is er geen delaunay-triangulatie mogelijk. Als er vier of meer punten op eenzelfde cirkel liggen (bijvoorbeeld de hoekpunten van een rechthoek of een gelijkzijdige zeshoek), zijn er meerdere delaunay-triangulaties mogelijk: men kan dan kiezen welke drie punten men tot een driehoek verbindt.

De delaunay-triangulatie heeft als eigenschap, dat het de kleinste hoek van alle driehoeken in de triangulatie maximaliseert, en zo weinig mogelijk "smalle" driehoeken genereert. Dit is in de computergrafiek gewenst omdat het de kans op afrondingsfouten verkleint. De delaunay-triangulatie wordt onder meer toegepast voor het construeren van een niet-uniform rooster voor eindige-elementenmethoden.

De delaunay-triangulatie kan naar meer dimensies uitgebreid worden. In het driedimensionale geval moet men tetraëders tussen vier punten van de verzameling vinden waarvoor geldt dat in de omgeschreven bol geen andere punten liggen.

Verband met voronoi-diagrammen

In grafentheoretische zin is de delaunay-triangulatie van een discrete verzameling punten in het vlak een planaire graaf, en wel de duale graaf van het voronoi-diagram van die verzameling. De hoekpunten van de voronoi-cellen zijn de middelpunten van de omgeschreven cirkels van de driehoeken van de delaunay-triangulatie. Het zijn, met andere woorden, de snijpunten van de middelloodlijnen van de drie zijden van elke driehoek.

• 
  Een delaunay-triangulatie met de omgeschreven cirkels en hun middelpunten in het rood.
• 
  Door de middelpunten te verbinden verkrijgt men het voronoi-diagram (in het rood getekend).

Als twee punten in de delaunay-triangulatie verbonden zijn, hebben de voronoi-cellen van die punten een gemeenschappelijke zijde, en omgekeerd.

Algoritme

Er bestaan verschillende algoritmen voor het maken van een delaunay-triangulatie. Een eenvoudig algoritme in twee dimensies is het "flip"-algoritme. Dat gaat uit van een willekeurige triangulatie van de verzameling van discrete punten. Van elke driehoek wordt dan onderzocht of zijn omgeschreven cirkel het derde hoekpunt van een aangrenzende driehoek omvat. Zo ja, dan is niet voldaan aan de delaunay-voorwaarde. Door de gemeenschappelijke zijde van de twee driehoeken te "flippen", wordt er wel aan voldaan, althans lokaal. Door de flip kan echter de delaunay-voorwaarde in de aangrenzende driehoeken weer ongedaan gemaakt zijn. In het slechtste geval moeten na een flip alle andere driehoeken opnieuw onderzocht worden. Het algoritme heeft daarom een looptijd van ${\mathcal {O}}(n^{2})$.

• 
  Deze triangulatie voldoet niet aan de delaunay-voorwaarde: de omgeschreven cirkels bevatten meer dan drie punten.
• 
  Door de gemeenschappelijke zijde te "flippen" verkrijgt men een plaatselijke delaunay-triangulatie voor deze vier punten.

Er bestaan efficiëntere algoritmen; de beste hebben een looptijd van ${\mathcal {O}}(n\log n)$. Tot die algoritmen behoren:

• de incrementele constructie van een triangulatie, waarbij de punten een voor een aan de triangulatie worden toegevoegd;
• het "sweepline"-algoritme, waarbij ook telkens nieuwe driehoeken aan de triangulatie worden toegevoegd die men verkrijgt door een horizontale lijn van onder naar boven over het vlak te laten "sweepen";
• "verdeel-en-heers"-algoritmen, die de triangulatie opbouwen door kleinere delaunay-triangulaties te verbinden met behoud van de delaunay-voorwaarde.

Zie ook

• Gabrielgraaf, een deelgraaf van de delaunay-triangulatie
• Urquhartgraaf, eveneens een deelgraaf
• Relative neighborhood graph, eveneens een deelgraaf

Externe link

• Triangle: software voor het maken van delaunay-triangulaties en voronoi-diagrammen