Triangulación de Delaunay

En al segunda unidad del curso de geometría computacional se implemento los algoritmos de triangulación de polinomios (Ear Clipping, triangulación monótona) así como triangulación de una nube de puntos en este caso la triangulación de Delaunay de la que hablare a continuación

1. INTRODUCTION
   Se le denomina así por el matemático ruso Boris Nikolaevich Delone (Борис Николаевич Делоне, 1890 - 1980) quien lo inventó en 1934.
   Es una red de triángulos 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.
   
   
2. CONDICIÓN DE DELAUNAY
   La condición de Delaunay dice que una red de triángulos es una triangulación de Delaunay si todas las circunferencias circunscritas de todos los triángulos de la red son vacías. Esa es la definición original para espacios bidimensionales. Es posible ampliarla para espacios tridimensionales usando la esfera circunscrita en vez de la circunferencia circunscrita. También es posible ampliarla para espacios con más dimensiones pero no se usa en la práctica.
   La arista p1p2 es legal mientras que p3p4 es una arista ilegal porque p2 cae dentro del círculo que pasa por p3p1p4.
   Cuando se detecte una arista ilegal hay que hacer un intercambio de la arista para convertirla en una legal.
   
   
3. PROPIEDADES
   · La triangulación forma la envolvente convexa del conjunto de puntos.
   · El ángulo mínimo dentro de todos los triángulos está maximizado.
   · La triangulación es unívoca si en ningún borde de circunferencia circunscrita hay más que tres vértices.
   
   
4. ALGORITMOS
   ·Incremental construction
   ·Divide and conquer
   ·Sweepline
   Algoritmo Aleatorio Incremental
   1. Introducir la nube de puntos P de tamaño n en un gran triángulo conteniendo a dicha nube de puntos Algoritmo Aleatorio Incremental
   2. Para cada uno de la n puntos de P, elegir pr de forma aleatoria y triangular:
   2.1. Encontrar el triángulo pipjpk conteniendo a pr
   2.2. SI pr cae en el interior del triángulo pipjpk ENTONCES añadir aristas desde pr hasta los vértices pi,pj,pk
   ● Legalizar_Aristas (pr, pipj)
   ● Legalizar_Aristas (pr, pjpk)
   ● Legalizar_Aristas (pr, pkpi)
   2.3. SINO pr cae en la arista pipj , que es incidente a los triángulos pipjpk y pipjpl
   ● Legalizar_Aristas (pr, pipl)
   ● Legalizar_Aristas (pr, plpj)
   ●Legalizar_Aristas (pr, pjpk)
   ● Legalizar_Aristas (pr, pkpi)
   3. Finalmente eliminar los tres puntos del gran triángulo inicial.
   
   
5. EJECUTABLE
   Se desarrollo en java, se ingresan los puntos con el Mouse ya demás tener en cuenta que una ves ejecutado Delaunay ya no se pueden seguir ingresando mas puntos se debe abrir de nuevo la aplicación.
   

Descargar Delaunay