Algoritme de Bowyer-Watson
En geometria computacional, el Algoritme de Bowyer–Watson és un método per a calcular la triangulació de Delaunay d'un conjunt finito de punts en qualsevol número de dimensions. L'algoritme es pot amprar també per a construir el Diagrama de Voronoi dels punts, el qual és el grafo dual de dita triangulació. L'algoritme és a voltes denominat com a Algoritme de Bowyer o Algoritme de Watson ya que abdós autors, Adrian Bowyer i David Watson, ho varen desenrollar de forma independent al mateix temps. Cada u va publicar un artícul sobre el mateix assunt en la revista The Computer Journal. [1] [2]
Descripció de l'algoritme
[editar | editar còdic]L'algoritme de Bowyer-Watson ampra un método incremental, a on es partix d'una triangulació de Delaunay trivial (generalment un triàngul o un parell de triànguls que formen una caixa contenidor) a la que s'afigen un a un els punts. Despuix de cada inserció, s'eliminen aquells triànguls que el seu circuncírculo continguen al punt recent introduït. El forat resultant té forma de polígon estrelat simple, el qual pot ser retriangulado al voltant del punt recent insertat.
Si nostra estructura de senyes dispon d'informació de conectivitat entre triànguls, l'algoritme té orde O(N log N) operacions per a triangular N punts, a pesar de que existixen casos degenerados especials a on pot prendre O(N2). L'orde en que s'inserten els vèrtiços té una gran influència en el temps d'eixecució de l'algoritme, per lo que a voltes es realisa una ordenació prèvia dels mateixos concorde a una curva de Hilbert.[3]
Este algoritme pot ser sensible a senyes d'entrada degenerados, com a punts situats en patrons regulars que fan que la resolució de si un punt està dins o fòra del circuncírculo d'un triàngul depenga de decimals per baix del llindar de precisió de la representació en menge flotant. Per això, és recomanable amprar algun test robust en lloc de comparar distàncies euclídeas entre punts. [4]
Explicació gràfica del procés
[editar | editar còdic]-
Generació de la triangulació inicial trivial (en este cas un super-triàngul) i inserció del primer nodo. -
Inserta segon nodo -
Inserta tercer nodo -
Inserta quart nodo -
Inserta quint (i últim) nodo -
Elimina les arestes en algun extrem en el super-triàngul inicial.
Referències
[editar | editar còdic]- ↑ (1981).Comput. J..24(2)
- 162–166.doi:10.1093/comjnl/24.2.162.
- ↑ (1981).Comput. J..24(2)
- 167–172.doi:10.1093/comjnl/24.2.167.J.
- ↑ Journal of Computation Physics.(106)
- 125–138.Consultat el 14 de decembre de 2016.
- ↑ (1997).Discrete & Computational Geometry.(18)
- 305-363.J.
Referències
[editar | editar còdic]
- Este artícul conté una traducció derivada de «Algoritmo de Bowyer-Watson» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.