Ruppert's algorithm: Difference between revisions

Revision as of 22:14, 17 July 2011

Revision as of 05:27, 13 September 2011

Line 1:

{{multiple image

| direction = vertical

| width = 350

| footer = Example of Ruppert's algorithm

| image1 = RuppertsAlgorithm-input.png

| alt1 = Ruppert's Algorithm input

| caption1 = Input planar straight-line graph

| image2 = RuppertsAlgorithm-output.png

| alt2 = Output conforming Delaunay triangulation

| caption2 = Output conforming 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) 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.

Line 33:

These operations are repeated until no poor-quality triangles exist and all segments are not encroached.

== Pseudocode ==

Line 54 ⟶ 53:

16 '''return''' ''T'';

17 '''end''' Ruppert.

== Practical Usage ==

Line 67 ⟶ 65:

Ruppert's algorithm can be naturally extended to three dimensions, however its output guarantees are somewhat weaker due to the sliver type tetrahedron.

An extension of Ruppert's algorithm in two dimensions is implemented in the freely available Triangle package. Two variants of Ruppert's algorithm in this package are guaranteed to terminate for a poor-quality threshold of about 26.5 degrees.<ref>{{cite journal | first1=Jonathan | last1=Shewchuk | title=Delaunay refinement algorithms for triangular mesh generation | journal=Computational Geometry: Theory and Applications | year=2002 | volume=22 | issue=1–3 | pages=21–74}}</ref> In practice these algorithms are successful for poor-quality thresholds over 30 degrees. However, examples are known which cause the algorithm to fail with a threshold greater than 29.06 degrees.<ref>{{citationcite arxiv|last=Rand|first=Alexander|title=Improved Examples of Non-Termination for Ruppert's Algorithm|year=2011|ideprint={{arxiv|1103.3903}} }}.</ref>

== See also ==