Contact Us

Design Background

Curriculum Vitae






Two-Dimensional Delaunay triangulation for quality meshes
Added: 27Mar2007
Author: Nils Haeck M.Sc.


Creating a high-quality mesh from a polygon or set of polygons in 2D is not a trivial task, and is often a sub-task of another task, like doing calculations with Finite Element Methods. SimDesign has created a mesh generator that produces constrained Delaunay triangulations, and so-called "quality" meshes, from a set of polygon boundaries. The algorithm also detects intersections, and regions.

The start point is a Delaunay mesh, generated from all the vertices ("points") of the polygons to be meshed. Each triangle in the mesh has 3 points, and a circle can be fitted through these 3 points. In a Delaunay mesh, no other vertex falls within this circle. Theoretically, there is one, and only one, possible mesh that abides the Delaunay criterion.

Example of a Delaunay triangulation for a plate with holes

The second step in mesh generation is to add the boundary segments (e.g. the polylines making up the boundaries). Some of these segments will not coincide with the initial Delaunay mesh, therefore some triangles need to change in order to accomodate this. The result of this is what is called a constrained Delaunay triangulation. In this stage, the mesher also finds the intersections of the boundary segments, and adds these points.

The mesh is constrained, the blue segments have been added, and some triangles changed

The final step in order to generate meshes which have a set of triangles with internal angles as large as possible, a quality mesh. In order to do so, vertices must be added to the mesh to split up the triangles that are "skinny", into more triangles that do have desireable properties. These additional vertices are called Steiner points. SimDesign's mesh generator uses the "off-center" insertion location, and also ensures that segments along the boundary are split.

A quality mesh is generated, and triangles outside of the boundary are removed. The minimum angle of any triangle in the mesh is 30 degrees

The meshing algorithm also identifies regions and is able to remove interior boundaries as well, as can be seen in the example below. The resulting irregular, quality mesh is very suitable for e.g. planar strain/stress analysis in Finite Element Packages.

A quality mesh with interior boundaries removed

Online demo

You can download a small executable file here and test the above.


Contact us in order to purchase a license. Per-developer licenses as well as site licenses are available. The use of the triangulator in software is otherwise royalty-free.


   Page last changed: 10Feb2011 © Copyright 2007-2011 SimDesign