Ruppert's algorithm: Difference between revisions

Revision as of 16:00, 17 November 2010

Revision as of 14:39, 19 November 2010

Line 5:

| image1 = RuppertsAlgorithm-input.png

| alt1 = Ruppert's Algorithm input

| caption1 = PLSInput inputplanar straight-line graph

| image2 = RuppertsAlgorithm-output.png

| alt2 = Ruppert'sOutput algorithmconforming outputDelaunay triangulation

| caption2 = Output meshconforming Delaunay triangulation

}}

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 (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.

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>