[[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 manifold|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 (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> 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 ==
The algorithm begins with a constrained Delaunay triangulation of the input vertices. At each step, the [[circumcenter]] of a poor-quality triangle is inserted into the triangulation with one exception: If the circumcenter lies on the opposite side of an input segment as the poor quality triangle, the midpoint of the segment is inserted. Moreover, any previously inserted circumcenters inside the diametral ball of the original segment (before it is split) are removed from the triangulation.
Circumcenter insertion is repeated until no poor-quality triangles exist.
