Content deleted Content added
Jitse Niesen (talk | contribs) remove {{sources}} now that references are provided, remove "see also" of dubious relevance, and more |
No edit summary |
||
Line 1:
The algorithm of Bowyer/Watson falls into the category of incremental insertion algorithms. Most
often the algorithm is know as just the Watson algorithm. If we are not given an initial triangulation
it starts by forming the super triangle enclosing the vertex set V that we want to triangulate.
The algorithm then proceeds by incrementally inserting the vertices p belongs to V in the triangulation
. After every insertion step a search is made, to find the triangles whose circumcircles
enclose p. These triangles are deleted, forming a polygon containing p called the insertion
polygon. Edges between the vertices of the insertion polygon and p are inserted forming the new
triangulation, which is Delaunay . We have now, after inserting all the vertices p belongs to V this
way, obtained the Delaunay triangulation Del(V ). In the last step all we need to do is remove the super triangle and its edges going into the triangulation.
==Reference==
Voronoi and Delaunay Techniques
Henrik Zimmer
{{context|date=May 2007}}
The '''Bowyer–Watson algorithm''' computes the [[Voronoi diagram]] of a finite set of points in any number of [[dimension]]s. It is named after its inventors, [[Adrian Bowyer]] and [[David F. Watson]].
| |||