Bowyer–Watson algorithm: Difference between revisions

Revision as of 23:10, 28 July 2020

Latest revision as of 22:44, 25 November 2024

(5 intermediate revisions by 5 users not shown)

Line 1:

{{Short description|Computation method in geometry}}

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 computing|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>

<gallery>

Line 21 ⟶ 22:

<syntaxhighlight lang="javascript">

// this pseudocode does not work, notice:

// 'triangulation' starts with a single element, the 'super-triangle', then we add 'super-triangle' to

// 'badTriangles' (since the super-triangle, by definition, contains all points, hence, it is a bad triangle)

// now, let us analyze the following line:

// 'if edge is not shared by any other triangles in badTriangles'

// 'edge' from 'triangle' from 'badTriangles' is always going to share an 'edge' with 'badTriangles'

// hence, no new triangles are added to the triangulation, never!

function BowyerWatson (pointList)

// pointList is a set of coordinates defining the points to be triangulated

triangulation := empty triangle mesh data structure

add super-triangle to triangulation // must be large enough to completely contain all the points in pointList

for each point in pointList do // add all the points one at a time to the triangulation

badTriangles := empty set

for each triangle in triangulation do // first find all the triangles that are no longer valid due to the insertion

if point is inside circumcircle of triangle

add triangle to badTriangles

polygon := empty set

for each triangle in badTriangles do // find the boundary of the polygonal hole

for each edge in triangle do

if edge is not shared by any other triangles in badTriangles

add edge to polygon

for each triangle in badTriangles do // remove them from the data structure

remove triangle from triangulation

for each edge in polygon do // re-triangulate the polygonal hole

newTri := form a triangle from edge to point

add newTri to triangulation

for each triangle in triangulation // done inserting points, now clean up

if triangle contains a vertex from original super-triangle

remove triangle from triangulation

return triangulation

</syntaxhighlight>

Line 59 ⟶ 51:

== Further reading ==

*{{Cite journal | last1 = Bowyer | first1 = Adrian |author1-link=Adrian Bowyer| title = Computing Dirichlet tessellations | doi = 10.1093/comjnl/24.2.162 | journal = [[The Computer Journal|Comput. J.]] | volume = 24 | issue = 2 | pages = 162–166 | year = 1981 | pmid = | pmc = | doi-access = free }}

*{{Cite journal | last1 = Watson | first1 = David F. | authorlink1 = | title = Computing the ''n''-dimensional Delaunay tessellation with application to Voronoi polytopes | doi = 10.1093/comjnl/24.2.167 | journal = [[The Computer Journal|Comput. J.]] | volume = 24 | issue = 2 | pages = 167–172 | year = 1981 | pmid = | pmc = | doi-access = free }}

* [http://paulbourke.net/papers/triangulate/ Efficient Triangulation Algorithm Suitable for Terrain Modelling] generic explanations with source code examples in several languages.