Google
 

sábado, 27 de septiembre de 2008

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

3 comentarios:

Jorge Carlos dijo...

maaaaaaasteeerrrr, estas rayando con los algoritmos de geometria computacional, bien ahi :D

XYOX dijo...

Excelente se nota que dominas el tema, estaba buscando informacion al respecto agradecido saludo :D

DiegoGG dijo...

¿Tienes alguna información sobre la triangulación de Delaunay en 3D?