Content deleted Content added
sectionize |
|||
Line 2:
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.
==Description==
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<sup>2</sup>)''.<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>
The algorithm is sometimes known just as the '''Bowyer Algorithm''' or the '''Watson Algorithm'''. [[Adrian Bowyer]] and David Watson devised it independently of each other at the same time, and each published a paper on it in the same issue of ''[[The Computer Journal]]'' (see below).▼
<gallery>
Line 14 ⟶ 13:
File:Bowyer-Watson 6.png|Remove edges with extremes in the super-triangle
</gallery>
==History==
▲The algorithm is sometimes known just as the '''Bowyer Algorithm''' or the '''Watson Algorithm'''. [[Adrian Bowyer]] and David Watson devised it independently of each other at the same time, and each published a paper on it in the same issue of ''[[The Computer Journal]]'' (see below).
==Pseudocode==
| |||