Bowyer–Watson algorithm: Difference between revisions

Revision as of 14:13, 8 June 2016

Revision as of 22:02, 13 December 2016

Line 1:

In [[computational geometry]], the '''Bowyer–Watson algorithm''' is a method for computing the [[Delaunay triangulation]] of a finite set of points in any number of [[dimension]]s. The algorithm can be also used to obtain a [[Voronoi diagram]] of the points, which is the [[dual graph]] of the Delaunay triangulation.

The Bowyer–Watson algorithm is an [[incremental algorithm]]. It works by adding points, one at a time, to a valid Delaunay triangulation of a subset of the desired points. After every insertion, any triangles whose circumcircles contain the new point are deleted, leaving a [[star-shaped polygon]]al hole which is then re-triangulated using the new point. By using the connectivity of the triangulation to efficiently locate triangles to remove, the algorithm can take ''O(N log N)'' operations to triangulate N points, although special degenerate cases exist where this goes up to ''O(N²)''.<ref>Rebay, S. ''Efficient Unstructured Mesh Generation by Means of Delaunay Triangulation and Bowyer-Watson Algorithm''. Journal of Computational Physics Volume 106 Issue 1, May 1993, p. 127.</ref>

Line 12:

File:Bowyer-Watson 3.png|Insert fourth node

File:Bowyer-Watson 4.png|Insert fifth (and last) node

File:Bowyer-Watson 6.png|Remove edges with extremes in the super-triangle edges

</gallery>

Line 44:

</syntaxhighlight>

== SeeExternal alsolinks ==

* [https://github.com/jmespadero/pyDelaunay2D pyDelaunay2D] : A python implementation of Bowyer–Watson algorithm.

* [[Fortune's algorithm]]

* [[Delaunay triangulation]]

* [[Computational geometry]]

==References==