Ruppert's algorithm: Difference between revisions

Revision as of 01:52, 29 December 2018

Revision as of 20:39, 29 August 2019

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=httphttps://www.cs.cmu.edu/~quake/tripaper/triangle3.html| date=12 August 1996| access-date=28 December 2018}}</ref>

== Motivation ==

Line 88:

| last = Shewchuk | first = Jonathan

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

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

| access-date = 28 December 2018

}}