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. [1] [2]
| 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 | ||
| Caso promedio | ||
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
- Bowyer, Adrian (1981). «Computing Dirichlet tessellations». Comput. J. 24 (2): 162-166. doi:10.1093/comjnl/24.2.162.
- 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.
- 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.
- Shewchuk, Jonathan Richard (1997). «Adaptive Precision Floating-Point Arithmetic and Fast Robust Predicates for Computational Geometry». Discrete & Computational Geometry (18): 305-363.J.