The Methods of Triangulation



3- Delaunay Triangulation Algorithms
There are a wide variety of algorithms available to build a Delaunay triangulation for a set of points. Delaunay triangulation is discussed by B.Delaunay in 1934. Delaunay triangulation maximizes the minimum angles in triangles and avoids skinny triangles.

3-1-Delaunay Triangulation
A Delaunay triangulation T of P is a triangulation of P such that the circum-circle of any triangle belonging to T does not contain points of P in its interior. The Delaunay triangulation of a set P of points is uniqe provided that no four or more points of P are co-circular.

3-2-Properties of Delaunay triangulation

1-Local empty-circle property:
The circum-circle of any triangle in Delaunay triangulation does not contain the vertex of the other triangle in its interior[1].

2- max-min angle property:
In Figure 3-1 PlPk satisfies the max-min angle property if PlPk is the diagonal of tetrahedral which miximizes the minimum of the six internal angles associated whit each of the two possible triangulations of tetrahedra[11].


Figure 3-1 : Angle criterion in Delaunay Triangulation[11]

3- Uniquness:
There is a unique Delaunay triangulation from a set of points[9].

4- Boundary property:
External edges of Delaunay triangulation make the Convex hull of the point set[2].

3-3-Delaunay triangulation algorithms

3-3-1-Incremental Algorithms
The method of point insertion is very well known. It has been used, among others, by Lawson and Sloan in order to obtain an incremental algorithm that calculates the Delaunay triangulation of a set of points. This method is based on the following proposition:

Proposition 1. Let T be a DT of a given set of points, S. Therefore, the insertion of one point p Ï S inside the triangulated region, forming the new DT S È {p}, only modifies the triangles of T whose circumcircle contains the point p [3].

The derived algorithm begins by generating a triangle that contains all the points from which the DT can be obtained in order to guarantee that all the points will lie within the triangulation. The points are inserted within the triangulation one at a time; each inserted point implies making a series of changes in edges shared by two triangles, until all the triangles that contain the inserted point have been updated. Lawson demonstrated that this iterative process converges, after a finite number of steps, towards the new Delaunay triangulation [6].

The bottleneck of incremental DT algorithm is the search for a triangle, into which the currently integrating point falls. Zalik and Kolingerova [6] have transformed the problem into finding the closest point, which takes less processing time. Three main steps of the algorithm are:
  • Initialization,
  • Triangulation,
  • Finalization.
To make the algorithm work fast, the searching structure has to be initialized[12]. The algorithm proceeds as follows :
  • Add a point to the triangulation
  • Find all existing triangles whose circumcircle contains the new point (Figure 3-2). First the triangle which contains the new point has to be found, which is a proximity search taking time O(logn) for a suitable data structure (e.g., quadtree/octree). Then the neighbours of this triangle are searched and then their neighbours, etc., until no more neighbours have the new point in their circumcircle. This takes, on average, time O(1) but in the worst case the circumcircles of all the existing triangles contain the new point, taking timeO(n) .
  • Delete these triangles, which creates (always) a convex cavity.
  • Join the new point to all the vertices on the boundary of the cavity (Figure 3-2)


Figure 3-2 : Building an Incremental Delaunay Triangulation[13]

3-3-2- Step by step algorithm
The external esdges in Delaunay triangulation form Convex hull and therefore we can start delaunization from these edges[10].
  • The smallest edge in Convex hull is selected as Base line,
  • Third point that can form a Delaunay triangle is found.
  • The traingle is checked with a circle that passes from these three points. If there are more than three points in circle, the size of circle should be changed.
  • Near points to bisector of base line are selected .
3-3-3-Filliping algorithm
This algorithm has two steps:
  1. Construction of an arbitrary triangulation,
  2. Optimization of the made triangulation to produce a Delaunay triangulation.
In the first step we build a triangulation with incremental approach and in second step we swap every edge with other diagonal of the tetrahedral that is not locally optimal. We iterate this process until not any other edge swap is needed[7].

3-3-4- Plane Sweep Algorithm
This algorithm is a gradual algorithm for Delaunay triangulation. In this method we sweep all points with a line. The points behind of the line are triangulated. As the line sweeps other points new triangles are built. This algorithm was introduced and developed for Voronoi diagram by Fortune in 1987 [13].


Figure 3-3 : plane sweep Triangulation[13]

3-3-5- Divide and Conquer Algorithm
The divide-and-conquer algorithm subdivides the area into two partial areas, computes recursively the Delaunay triangulation of the partial areas and merges finally both triangulations. The difficult section in this algorithm is to merge the parts. Technique to increase the speed of this algorithm should be used. Time complexity of this algorithm in the worst case is O(nlogn)[13].

Page 2 of 3
| Previous | Next |