Ruppert's algorithm: Difference between revisions

Revision as of 20:19, 5 January 2015

Revision as of 02:06, 17 January 2015

Line 63:

| pages = 165–181

| year = 2005 }}</ref>

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 | doi=10.1016/s0925-7721(01)00047-5}}</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>{{cite arxivarXiv|last=Rand|first=Alexander|title=Improved Examples of Non-Termination for Ruppert's Algorithm|year=2011|eprint=1103.3903|class=cs.CG }}.</ref>

== See also ==

Line 101:

[[Category:Mesh generation]]

[[Category:Triangulation (geometry)]]

[[Category:Articles containing video clips]]