Ruppert's algorithm

From Wikipedia, the free encyclopedia

In mesh generation, Ruppert's algorithm, also known as Delaunay refinement, is an algorithm for creating quality Delaunay triangulations. 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) 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.

[edit] See also

• Delaunay triangulation
• Voronoi diagram
• Polygon mesh

[edit] 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.