Finite Element Method - 2D Mesh Generator - Metfem2D

Delaunay triangulation algorithm

Let's remind briefly the main points of the Delaunay triangulation method[1] together with their numerical implementation using Octave and Matlab software[2]. Let P = {pi, i = 1, 2, … ,N} be a set of points in two – dimensional Euclidean plane ℜ2. They are called forming points of mesh[1]. Let us define the triangle T as a set of three mesh points

T = {tj ∈ P, j = 1,2,3}.

Definition of Delaunay zones

Using the Delaunay criterion one can generate triangulation where no four points from the set of forming points P are co – circular:

∀ pi ∈ P ∧ pi ∉ T ||pi - u|| > ρ2

where u is the center of the T triangle and ρ is its radius. The proposed algorithm consists of the following steps:

The algorithm ends up with the new triangular mesh Ωnew.
If you wish you can have an insight into the program delaunayTakeTechEase.m that implements the above – presented algorithm using the Octave and Matlab software (it is a part of a free Octave and Matlab course). One can use also the appropriate Octave and Matlab library function.
Help. In order to find an orientation of a triangle T one can check the sign of An (see equation). If it is greater than 0 the triangle orientation is clockwise unless counterclockwise. In the latter case, to ensure the clockwise orientation one can once flip up and down matrix in equation then the triangle orientation turns into the opposite one. Obviously, this flipping results in the change of the sign of the matrix determinant D(T) → -D(T).

finite element method, fem, numerical integration, differential equations, lde, 2D mesh generator, Metfem2D, taketechease


  1. ^ B. Delaunay, Sur la sphre vide, Izvestia Akademii Nauk SSSR, Otdelenie Matematicheskikh i Estestvennykh Nauk, 7, pp. 793-800, 1934
  2. ^The source code of Octave is freely distributed GNU project, for more info please go to the following web page