Triangulación de Delaunay

Triangulación de Delaunay de 10 puntos. El circuncírculo de cada triángulo no contiene vértices en su interior.

Una triangulación de Delaunay (pronunciado /dəlo'ne/, a veces escrito fonéticamente «Deloné»), es una red de triángulos conexa y convexa que cumple la condición de Delaunay. Esta condición dice que la circunferencia circunscrita de cada triángulo de la red no debe contener ningún vértice de otro triángulo. Las triangulaciones de Delaunay tienen importante relevancia en el campo de la geometría computacional, especialmente en gráficos 3D por computadora.

Se le denomina así por el matemático ruso Borís Nikolaevich Delone quien lo ideó en 1934;[1] el mismo Delone usó la forma francesa de su apellido, «Delaunay», como apreciación a sus antecesores franceses.

Condición de Delaunay

Vértice completamente en el interior de la circunferencia circunscrita. No se cumple la condición de Delaunay
Vértice en el exterior de la circunferencia circunscrita. Se cumple la condición de Delaunay

La condición de Delaunay de un triángulo establece que la circunferencia circunscrita del mismo no debe contener ningún otro vértice de la triangulación en su interior, aunque sí se admiten vértices situados sobre la circunferencia.

Se dice que una red de triángulos es una triangulación de Delaunay si todos los triángulos de la misma cumplen la condición de Delaunay. Es decir, que cada circunferencia circunscrita de cada triángulo no contiene vértices de la triangulación en su interior. Esta definición original para espacios bidimensionales se puede ampliar a espacios tridimensionales o incluso dimensiones superiores, usando la esfera circunscrita en vez de la circunferencia circunscrita.

La operación de giro de aristas (Flipping)

Para un par de triángulos adyacentes con una arista en común, es posible demostrar que ambos triángulos cumplen la condición de Delaunay si (y sólo si) la suma de los ángulos opuestos a la arista común es menor o igual a 180°.

Esta propiedad nos permite definir una operación geométrica importante denominada Giro de arista (o flipping en inglés). Si los dos triángulos no cumplen la condición de Delaunay, podemos reemplazar la arista común por una nueva arista que una los vértices opuestos a la anterior. El resultado es un nuevo par de triángulos con la misma frontera que el par original, pero que sí cumplen la condición de Delaunay.

Other Languages