Bowyer–Watson algorithm: Difference between revisions

Revision as of 18:52, 5 August 2014

Revision as of 16:31, 7 August 2014

Line 14:

File:Bowyer-Watson 6.png|Remove super-triangle edges

</gallery>

==Pseudocode==

The following [[pseudocode]] describes a basic implementation of the Bowyer-Watson algorithm. Efficiency can be improved in a number of ways. For example, the triangle connectivity can be used to locate the triangles which contain the new point in their circumcircle, without having to check all of the triangles. Pre-computing the circumcircles can save time at the expense of additional memory usage. And if the points are uniformly distributed, sorting them along a space filling [[Hilbert curve]] prior to insertion can also speed point ___location.<ref>Liu, Yuanxin, and Jack Snoeyink. "A comparison of five implementations of 3D Delaunay tessellation." Combinatorial and Computational Geometry 52 (2005): 439-458.</ref>

<syntaxhighlight lang="javascript">

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

return triangulation

</syntaxhighlight>

== See also ==