Content deleted Content added
Added description of poor quality triangles. |
historical context |
||
Line 1:
In [[mesh generation]], '''Ruppert's algorithm''', also known as '''Delaunay refinement''', is an [[algorithm]] for creating quality [[Delaunay triangulation]]s. The algorithm takes a [[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.
When doing computer simulations such as [[computational fluid dynamics]], one starts with a model such as a 2D outline of a wing section.
The input to a 2D [[finite element method]] needs to be in the form of triangles that fill all space, and each triangle to be filled with one kind of material -- in this example, either "air" or "wing".
Long, skinny triangles cannot be simulated accurately.
The simulation time is generally proportional to the number of triangles, and so one wants to minimize the number of triangles, while still using enough triangles to give a reasonably accurate results -- typically by using an [[unstructured grid]].
The computer uses Ruppert's algorithm (or some similar meshing algorithm) to convert the polygonal model into triangles suitable for the finite element method.
The algorithm consists of two main operations.
Line 7 ⟶ 14:
These operations are repeated until no poor-quality triangles exist and all segments are not encroached.
According to Shewchuk,
"Ruppert's algorithm for two-dimensional quality mesh generation is perhaps the first theoretically guaranteed meshing algorithm to be truly satisfactory in practice."<ref>
[http://www.cs.cmu.edu/~quake/tripaper/triangle3.html "Ruppert's Delaunay Refinement Algorithm"] by Jonathan Richard Shewchuk
</ref>
Jim Ruppert discovered this algorithm in the early 1990's.
Since then, various small improvements have been made.<ref>
[http://ccom.ucsd.edu/~spav/work/index.html Steven Elliot Pav: Research]
</ref>
An extension of Ruppert's algorithm in two dimensions is implemented in the freely available (yet non-[[Free software|free]]) [http://www.cs.cmu.edu/~quake/triangle.html Triangle] package.
| |||