Ruppert's algorithm: Difference between revisions

Revision as of 20:26, 31 May 2012

Revision as of 23:22, 29 March 2014

Line 13:

In [[mesh generation]], '''Ruppert's algorithm''', also known as '''Delaunay refinement''', is an [[algorithm]] for creating quality [[Delaunay triangulation]]s. The algorithm takes a [[planar straight-line graph]] (or in dimension higher than two a [[Piecewise linear manifold|piecewise linear]] system) 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.

Discovered by Jim Ruppert in the early 1990s,<ref>{{cite journal | doi=10.1006/jagm.1995.1021 | first=Jim | last=Ruppert | title=A Delaunay refinement algorithm for quality 2-dimensional mesh generation | journal=Journal of Algorithms | year=1995 | issue=3 | pages= 548–585 | volume=18}}</ref>

"Ruppert's algorithm for two-dimensional quality mesh generation is perhaps the first theoretically guaranteed meshing [[algorithm]] to be truly satisfactory in practice."<ref>{{cite web | last = Shewchuk | first = Jonathan | title = Ruppert's Delaunay Refinement Algorithm | url = http://www.cs.cmu.edu/~quake/tripaper/triangle3.html | accessdate = April 2010}}</ref>

== Motivation ==