Delaunay Triangulation Algorithm in Contour Generation

Delaunay Triangulation

Triangulation is the process of connecting points to form a very large triangular network. Delaunay triangulation is used as a tool, using which surfaces can be divided into regions with certain common characteristics. An example of triangular network is shown below

There are numerous applications of triangulation. Triangulation decides the shape of road network for a particular area, decides the pattern of telephone network etc.

The rule guarding the Delaunay triangulation is the circumcircle property, which states that three points are connected to form a triangle if the circumcircle drawn for three points does not enclose any other point within it. To understand this better, look at the points and the circles shown below

 

From the above logic, it can be learnt that the red circles indicate false triangulation while the black circles show the correct triangulation for the given set of points.

This type of triangulation ensures minimum error as well as reliable data plotting and makes image regeneration possible. Also this method ensures that skinny triangles generating huge circles are also eliminated, thus reducing the amount of error. To understand skinny triangle consider the figure shown below

As seen in the above figure, the arc shown in green generates a really huge circle with respect to the other nearby circles. The cause for such a huge circle generation is that the 3 points considered for the circle have a high angle and produce an obtuse angled triangle known as a Skinny triangle. To overcome this problem a maximum radius is set for the circle arising from the points known as the scanning radius.

The concept of triangulation can also be extended to 3D to generate objects with their true surface features.