Algoritmo de Bowyer-Watson
# Algoritmo de Bowyer-Watson

En geometría computacional, el Algoritmo de Bowyer–Watson es un método para calcular la triangulación de Delaunay de un conjunto finito de puntos en cualquier número de dimensiones. El algoritmo se puede emplear también para construir el Diagrama de Voronoi de los puntos, el cual es el grafo dual de dicha triangulación. El algoritmo es a veces denominado como Algoritmo de Bowyer o Algoritmo de Watson ya que ambos autores, Adrian Bowyer y David Watson, lo desarrollaron de forma independiente al mismo tiempo. Cada uno publicó un artículo sobre el mismo asunto en la revista The Computer Journal.

## Descripción del algoritmo

El algoritmo de Bowyer-Watson emplea un método incremental, donde se parte de una triangulación de Delaunay trivial (generalmente un triángulo o un par de triángulos que forman una caja contenedora) a la que se añaden uno a uno los puntos. Después de cada inserción, se eliminan aquellos triángulos cuyo circuncírculo contengan al punto recién introducido. El agujero resultante tiene forma de polígono estrellado simple, el cual puede ser retriangulado alrededor del punto recién insertado.

Si nuestra estructura de datos dispone de información de conectividad entre triángulos, el algoritmo tiene orden O(N log N) operaciones para triangular N puntos, a pesar de que existen casos degenerados especiales donde puede tomar O(N2). El orden en que se insertan los vértices tiene una gran influencia en el tiempo de ejecución del algoritmo, por lo que a veces se realiza una ordenación previa de los mismos acorde a una curva de Hilbert.

Este algoritmo puede ser sensible a datos de entrada degenerados, como puntos situados en patrones regulares que hacen que la resolución de si un punto está dentro o fuera del circuncírculo de un triángulo dependa de decimales por debajo del umbral de precisión de la representación en coma flotante. Por ello, es recomendable emplear algún test robusto en lugar de comparar distancias euclídeas entre puntos.

## Explicación gráfica del proceso

* Generación de la triangulación inicial trivial (en este caso un super-triángulo) e inserción del primer nodo.
* Inserta segundo nodo
* Inserta tercer nodo
* Inserta cuarto nodo
* Inserta quinto (y último) nodo
* Elimina las aristas con algún extremo en el super-triángulo inicial.
