Algoritmo de Bowyer-Watson

Algoritmo de Bowyer–Watson
Tipo	Geometría computacional
Problema que resuelve	Triangulación de Delaunay / Diagrama de Voronoi
Estructura de datos	Malla de Triángulos
Creador	Adrian Bowyer y David Watson
Fecha	1981
Clase de complejidad	P
Tiempo de ejecución
Peor caso	${\displaystyle O(|N|^{2})\,}$
Caso promedio	${\displaystyle O(|N|log|N|)\,}$
[editar datos en Wikidata]

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. ^[1]​ ^[2]​

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.^[3]​

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. ^[4]​

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.

Pseudocódigo

   function BowyerWatson (pointList)
      // pointList es una lista de coordenadas de los puntos de entrada
      triangulation := super-triangle // Crea un triángulo suficientemente grande como para contener todos los puntos de entrada

      for each point in pointList do // Añade los puntos uno a uno

         badTriangles := empty set
         for each triangle in triangulation do // busca los triángulos que van a dejar de ser válidos
            if point is inside circumcircle of triangle
               add triangle to badTriangles

         for each triangle in badTriangles do // Elimina los triángulos de la estructura, creando un hueco
            remove triangle from triangulation

         polygon := empty set
         for each triangle in badTriangles do // Calcula la frontera del hueco creado por bad_triangles
            for each edge in triangle do
               if edge is not shared by any other triangles in badTriangles
                  add edge to polygon

         for each edge in polygon do // re-triangula el hueco usando el nuevo punto.
            newTri := form a triangle from edge to point
            add newTri to triangulation

      for each triangle in triangulation // Limpieza de los triángulos externos a la lista de vértices.
         if triangle contains a vertex from original super-triangle
            remove triangle from triangulation
      return triangulation

Enlaces externos

• Algoritmo de triangulación para Modelización de Terreno explicaciones genéricas del algoritmo con ejemplos de código fuente en varios lenguajes de programación.
• pyDelaunay2D : Una implementación en python del algoritmo de Bowyer-Watson.

Referencias

1. Bowyer, Adrian (1981). «Computing Dirichlet tessellations». Comput. J. 24 (2): 162-166. doi:10.1093/comjnl/24.2.162. 
2. Watson, David F. (1981). «Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes». Comput. J. 24 (2): 167-172. doi:10.1093/comjnl/24.2.167. J.
3. Rebay, S. (1993). «Efficient Unstructured Mesh Generation by Means of Delaunay Triangulation and Bowyer-Watson Algorithm». Journal of Computation Physics (106): 125-138. Consultado el 14 de diciembre de 2016. 
4. Shewchuk, Jonathan Richard (1997). «Adaptive Precision Floating-Point Arithmetic and Fast Robust Predicates for Computational Geometry». Discrete & Computational Geometry (18): 305-363. J.