This is an archive of the former personal blog at www.juergentreml.de
[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)
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.
Averiguar si 2 puntos están dentro de la triangulación de Delaunay:
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.
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.