Content deleted Content added
Mentioning recent improvement to analysis. |
m adding link to reference |
||
Line 1:
[[File:LakeMichiganMesh.png|thumb|alt=Mesh generated with Chew's second algorithm text|Mesh of [[Lake Michigan]] using Chew's second algorithm implemented in the [http://www.cs.cmu.edu/~quake/triangle.html Triangle] package.]]
In [[mesh generation]], '''Chew's second algorithm''' is a [[Delaunay refinement]] [[algorithm]] for creating quality [[constrained Delaunay triangulation]]s. The algorithm takes a [[piecewise linear]] system (PLS) and returns a constrained Delaunay triangulation of only quality triangles where quality is defined by the minimum angle in a triangle. Developed by L. Paul Chew for meshing surfaces embedded in three-dimensional space <ref>{{cite conference | first1=L. Paul| last1=Chew| title=Guaranteed-quality mesh generation for curved surfaces | booktitle=Proceedings of the Ninth Annual Symposium on Computational Geometry | year=1993 | pages=274–280}}</ref>, Chew's second algorithm has been adopted as a two-dimensional mesh generator due to practical advantages over [[Ruppert's algorithm]] in certain cases and is the default quality mesh generator implemented in the freely available [http://www.cs.cmu.edu/~quake/triangle.html Triangle] package<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>. Chew's second algorithm is guaranteed to terminate and produce a [[local feature size]]-graded meshes with minimum angle up to about 28.6 degrees<ref>{{cite conference | first1=Alexander | last1=Rand | title=Where and How Chew's Second Delaunay Refinement Algorithm Works | booktitle=Proceedings of the 23rd Canadian Conference on Computational Geometry | year=2011 | pages=157–162 | url=http://2011.cccg.ca/PDFschedule/papers/paper91.pdf}}</ref>.
== Algorithm Description ==
| |||