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(N2).[1]
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 edges with extremes in the super-triangle
Historyedit
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).
Pseudocodeedit
The following pseudocode describes a basic implementation of the Bowyer-Watson algorithm. Its time complexity is . 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 - by doing so we can decrease time complexity to . 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.[2]
functionBowyerWatson(pointList)// pointList is a set of coordinates defining the points to be triangulatedtriangulation:=emptytrianglemeshdatastructureaddsuper-triangletotriangulation// must be large enough to completely contain all the points in pointListforeachpointinpointListdo// add all the points one at a time to the triangulationbadTriangles:=emptysetforeachtriangleintriangulationdo// first find all the triangles that are no longer valid due to the insertionifpointisinsidecircumcircleoftriangleaddtriangletobadTrianglespolygon:=emptysetforeachtriangleinbadTrianglesdo// find the boundary of the polygonal holeforeachedgeintriangledoifedgeisnotsharedbyanyothertrianglesinbadTrianglesaddedgetopolygonforeachtriangleinbadTrianglesdo// remove them from the data structureremovetrianglefromtriangulationforeachedgeinpolygondo// re-triangulate the polygonal holenewTri:=formatrianglefromedgetopointaddnewTritotriangulationforeachtriangleintriangulation// done inserting points, now clean upiftrianglecontainsavertexfromoriginalsuper-triangleremovetrianglefromtriangulationreturntriangulation
Referencesedit
^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.
^Liu, Yuanxin, and Jack Snoeyink. "A comparison of five implementations of 3D Delaunay tessellation." Combinatorial and Computational Geometry 52 (2005): 439-458.
Watson, David F. (1981). "Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes". Comput. J.24 (2): 167–172. doi:10.1093/comjnl/24.2.167.
Efficient Triangulation Algorithm Suitable for Terrain Modelling generic explanations with source code examples in several languages.
External linksedit
pyDelaunay2D : A didactic Python implementation of Bowyer–Watson algorithm.
Bl4ckb0ne/delaunay-triangulation : C++ implementation of Bowyer–Watson algorithm.
April 11, 2024
bowyer, watson, algorithm, computational, geometry, method, computing, delaunay, triangulation, finite, points, number, dimensions, algorithm, also, used, obtain, voronoi, diagram, points, which, dual, graph, delaunay, triangulation, contents, description, his. 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 also used to obtain a Voronoi diagram of the points which is the dual graph of the Delaunay triangulation Contents 1 Description 2 History 3 Pseudocode 4 References 5 Further reading 6 External linksDescription editThe 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 N2 1 nbsp First step insert a node in an enclosing super triangle nbsp Insert second node nbsp Insert third node nbsp Insert fourth node nbsp Insert fifth and last node nbsp Remove edges with extremes in the super triangleHistory editThe 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 Pseudocode editThe following pseudocode describes a basic implementation of the Bowyer Watson algorithm Its time complexity is O n2 displaystyle O n 2 nbsp 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 by doing so we can decrease time complexity to O nlog n displaystyle O n log n nbsp 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 2 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 triangulationReferences edit 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 Liu Yuanxin and Jack Snoeyink A comparison of five implementations of 3D Delaunay tessellation Combinatorial and Computational Geometry 52 2005 439 458 Further reading editBowyer Adrian 1981 Computing Dirichlet tessellations Comput J 24 2 162 166 doi 10 1093 comjnl 24 2 162 Watson David F 1981 Computing the n dimensional Delaunay tessellation with application to Voronoi polytopes Comput J 24 2 167 172 doi 10 1093 comjnl 24 2 167 Efficient Triangulation Algorithm Suitable for Terrain Modelling generic explanations with source code examples in several languages External links editpyDelaunay2D A didactic Python implementation of Bowyer Watson algorithm Bl4ckb0ne delaunay triangulation C implementation of Bowyer Watson algorithm Retrieved from https en wikipedia org w index php title Bowyer Watson algorithm amp oldid 1187471014, wikipedia, wiki, book, books, library,