Content deleted Content added
m WP:CHECKWIKI error fixes - Replaced endash with hyphen in sortkey per WP:MCSTJR using AWB (9100) |
Gallery of the algorithm steps |
||
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 used to obtain a [[Voronoi diagram]] of the points, which is the [[dual graph]] of the Delaunay triangulation.
Line 4 ⟶ 5:
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>
File:Bowyer-Watson 0.png|First step: insert a node in an enclosing "super"-triangle
File:Bowyer-Watson 1.png|Insert second node
File:Bowyer-Watson 2.png|Insert third node
File:Bowyer-Watson 3.png|Insert fourth node
File:Bowyer-Watson 4.png|Insert fifth (and last) node
File:Bowyer-Watson 6.png|Remove super-triangle edges
</gallery>
== See also ==
Line 13 ⟶ 23:
*{{cite doi|10.1093/comjnl/24.2.162}}
*{{cite doi|10.1093/comjnl/24.2.167}}
* [http://paulbourke.net/papers/triangulate/ Efficient Triangulation Algorithm Suitable for Terrain Modelling] generic explanations with source code examples in several languages.
{{DEFAULTSORT:Bowyer-Watson algorithm}}
| |||