Geometría Computacional - Problemas - Triangulaciones de Nubes de Puntos

Geometría Computacional – Problemas – Triangulaciones de Nubes de Puntos

Triangulación de Delaunay

Definición

[Pi,Pj, Pk] es un triangulo en la triangulación de Delaunay si el circulo determinado por Pi, Pj y Pk está vacío (no contiene a ningún punto Pn), y vice versa.

Complejidad (Fuerza bruta): O(n4)

Propiedades

S = {P1,…, Pn} si Pi, Pj son los dos puntos más cercanos a un punto q cualquiera del plano.
PiPj es una arista de Delaunay.
Esto se demuestra trazando una circunferencia contenida en la circunferencia con centro q y radio qPi. el centro de la nueva circunferencia estaría en el punto de corte de qPi con la tangente de PjPi
Si tengo 4 o mas puntos en el perímetro de un círculo, con este algoritmo no habría triangulación de Delaunay.
Por lo tanto, tenemos que ver los casos degenerados.
Alternativas a los algoritmos dados para evitar el problema comentado, sería:
Al realizar la triangulación de Delaunay tomo diferentes figuras, con lo que se producirá un nº de flips (cantidad cuadrática) finito.

Problemas de Proximidad

Grafos de Proximidad

Averiguar si 2 puntos están dentro de la triangulación de Delaunay:

Generar un círculo que pase por los dos puntos
Toma el centro de la mediatriz del segmento que une los dos puntos y genera un círculo.

Cuando toque con el perímetro de ese círculo otro punto, ese es triangulo de Delaunay.

Con esta arista de mínima distancia, sabemos que no hay otro punto dentro del círculo generado: Es una arista de Delaunay.

Dos puntos son vecinos si no hay otro punto entre ellos, por tanto, si el círculo es vacío.

Grafo de Gábriel

Conjunto de puntos como vértices con cada punto unido con su vecino.

Gottfried Toussaint: Dos puntos están próximos si la luna que determinan está vacia. Vecinos mas próximos siginifica vecinidad relativa.

Gábriel: Para un triangulo de Gábriel, los tres ángulos deben ser menores de 90° cada uno.