Content deleted Content added
historical context |
|||
Line 1:
In [[mesh generation]], '''Ruppert's algorithm''', also known as '''Delaunay refinement''', is an [[algorithm]] for creating quality [[Delaunay triangulation]]s. The algorithm takes a [[piecewise linear]] system (PLS) and returns a conforming Delaunay triangulation of only quality triangles. A triangle is considered poor-quality if it has a circumradius to shortest edge ratio larger than some prescribed threshold.
When doing computer simulations such as [[computational fluid dynamics]], one starts with a model such as a 2D outline of a wing section.
Line 11:
* 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.
According to Shewchuk,
Line 20:
</ref>
Jim Ruppert discovered this algorithm in the early
Since then, various small improvements have been made.<ref>
[http://ccom.ucsd.edu/~spav/work/index.html Steven Elliot Pav: Research]
Line 27:
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.
In two dimensions, the poor-quality threshold must be at least
== See also ==
Line 39:
== References ==
{{Reflist}}<!--added under references heading by script-assisted edit-->
* 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.
| |||