Chew's second algorithm

Chew's second algorithm
Mesh generated with Chew's second algorithm text
Mesh of Lake Michigan using Chew's second algorithm implemented in the Triangle package.

In mesh generation, Chew's second algorithm is a Delaunay refinement algorithm for creating quality constrained Delaunay triangulations. 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,[1] 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 Triangle package.[2] 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.[3]

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.

See also

References

  1. ^ Chew, L. Paul (1993). "Guaranteed-quality mesh generation for curved surfaces". Proceedings of the Ninth Annual Symposium on Computational Geometry. pp. 274–280. 
  2. ^ Shewchuk, Jonathan (2002). "Delaunay refinement algorithms for triangular mesh generation". Computational Geometry: Theory and Applications 22 (1-3): 21–74. 
  3. ^ Rand, Alexander (2011). "Where and How Chew's Second Delaunay Refinement Algorithm Works". Proceedings of the 23rd Canadian Conference on Computational Geometry. pp. 157–162. http://2011.cccg.ca/PDFschedule/papers/paper91.pdf. 

Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Ruppert's algorithm — Input planar straight line graph Output conforming Delaunay triangulation …   Wikipedia

  • Constrained Delaunay triangulation — In computational geometry, a constrained Delaunay triangulation is a generalization of the Delaunay triangulation that forces certain required segments into the triangulation[1][2]. Because a Delaunay triangulation is almost always unique, often… …   Wikipedia

  • Swiss system tournament — A Swiss system tournament is a commonly used type of tournament in chess, bridge, Scrabble, squash, and other games where players or teams need to be paired to face each other. This type of tournament was first used in a Zurich chess tournament… …   Wikipedia

  • Electromagnetic field solver — Electromagnetic field solvers (or sometimes just field solvers) are specialized programs that solve (a subset of) Maxwell s equations directly. They form a part of the field of electronic design automation, or EDA, and are commonly used in the… …   Wikipedia

  • Benzodiazepine misuse — Benzodiazepines …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”