|
#REDIRECT [[Delaunay refinement#Ruppert's algorithm]]
Ruppert's algorithm is an algorithm for creating quality [[Delaunay triangulation]]s. The algorithm takes a piecewise linear system (PLS) and returns a conforming, Delaunay triangulation.
The algorithm consists of two main operations.
* The midpoint of a segment with non-empty diametral circles is inserted into the triangulation.
* The [[circumcenter]] of a poor quality triangle is inserted into the triangulation, unless this circumcenter lies in the diametral circle of some segment. In this case, the encroached segment is split instead.
These operations are repeated until no poor quality triangles exist and all segments are not encroached.
An extension of Ruppert's algorithm in two dimensions is implemented in the freely available (yet non-[[Free software|free]]) [http://www.cs.cmu.edu/~quake/triangle.html Triangle] package.
Ruppert's algorithm has been shown to terminate for any input PLS with no small angles. The algorithm can be extended to handle any input by slightly relaxing the quality requirement on the output (Miller et al., 2003).
Ruppert's algorithm can be naturally extended to three dimensions, however its output guarantees are somewhat weaker due to the sliver type tetrahedron.
== See also ==
* [[Delaunay Triangulation]]
* [[Voronoi diagram]]
* [[Polygon_mesh]]
== References ==
* G. L. Miller, S. E. Pav, and N. J. Walkington. When and why Ruppert's algorithm works. In Proceedings of the 12th International Meshing Roundtable, pages 91-102. Sandia National Laboratory, September 2003.
* J. Ruppert. A delaunay refinement algorithm for quality 2-dimensional mesh generation, 1995.
| 