Ruppert's algorithm: Difference between revisions

Revision as of 05:28, 6 October 2018

Revision as of 01:52, 29 December 2018

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 | accessdatedate=12 August 1996| access-date=28 AprilDecember 20102018}}</ref>

== Motivation ==

Line 82:

| title = 2D Conforming Triangulations and Meshes

| url = http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Mesh_2/Chapter_main.html

| access-date=28 December 2018

| accessdate = April 2010

}}

Line 89:

| title = Triangle: A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator.

| url = http://www.cs.cmu.edu/~quake/triangle.html

| access-date = 28 December 2018

| accessdate = April 2010

}}

Line 95:

| last = Si | first = Hang

| title = TetGen: A Quality Tetrahedral Mesh Generator and a 3D Delaunay Triangulator

| url = http://wias-berlin.de/software/tetgen/index.jsp?id=TetGen&lang=1

| date=2015

| accessdate = September 2014

| access-date = 28 December 2018

| archive-url = http://wias-berlin.de/software/tetgen/

| archive-date = c. 2014

| dead-url=no

}}