| Revision as of 14:46, 26 March 2014 editNojhan (talk | contribs)74 edits Gallery of the algorithm steps← Previous edit | Revision as of 18:52, 5 August 2014 edit undoSupernovaPhoenix (talk | contribs)301 edits added information about the complexity analysisNext edit → | ||
| Line 2: | Line 2: | ||
| In ], the '''Bowyer–Watson algorithm''' is a method for computing the ] of a finite set of points in any number of ]s. The algorithm can be used to obtain a ] of the points, which is the ] of the Delaunay triangulation. | In ], the '''Bowyer–Watson algorithm''' is a method for computing the ] of a finite set of points in any number of ]s. The algorithm can be used to obtain a ] of the points, which is the ] 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 ]al hole which is then re-triangulated using the new point. | 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 ]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'''. ] 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 '']'' (see below). | The algorithm is sometimes known just as the '''Bowyer Algorithm''' or the '''Watson Algorithm'''. ] 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 '']'' (see below). | ||
Revision as of 18:52, 5 August 2014
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 dimensions. The algorithm can be 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 polygonal 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).
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).
-
First step: insert a node in an enclosing "super"-triangle
-
Insert second node
-
Insert third node
-
Insert fourth node
-
Insert fifth (and last) node
-
Remove super-triangle edges
See also
References
- Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1093/comjnl/24.2.162, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with
|doi=10.1093/comjnl/24.2.162instead. - Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1093/comjnl/24.2.167, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with
|doi=10.1093/comjnl/24.2.167instead. - Efficient Triangulation Algorithm Suitable for Terrain Modelling generic explanations with source code examples in several languages.
 | This applied mathematics–related article is a stub. You can help Misplaced Pages by expanding it. |
- 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.