Page 202 - Basic Structured Grid Generation

Unstructured grid generation 191

8.2 Delaunay triangulation

8.2.1 Basic geometric properties

The principal objective here is to represent the two-dimensional solution domain of a
problem by a set of triangles. The method discussed here, Delaunay triangulation, was
first presented by Dirichlet in terms of connecting an arbitrary set of points together,
thus producing a set of triangles, in such a way that the resulting triangulation was as
near uniformly equilateral as possible.
Figure 8.1 shows a typical set of initial points N 1 ,N 2 ,...,N 8 , which give rise to
a so-called Dirichlet,or Voronoi, tessellation of the plane into convex polygons T 1 ,
T 2 ,...,T 8 , called tiles(or Voronoi regions), as shown. The tiles have the property that
any point in the interior of the tile T j is closer to the point N j than to any other point
N k , j = k. Hence the boundaries of the tiles consist of segments of the perpendicular
bisectors of lines joining the points N 1 , N 2 ,...,N 8 to each other. Tiles having a
common edge are called contiguous. A Delaunay triangulation is then obtained by
connecting together those initial points belonging to contiguous tiles (see Figure 8.2).
The convex polygon (N 1 N 2 N 3 N 4 N 5 N 6 in Fig. 8.2) which is the outer boundary of the
triangulation is called the convex hull of the set of initial points.
A typical vertex of a Dirichlet tessellation (or Voronoi polygon) is clearly equidistant
from three initial points, and these points form a Delaunay triangle of which the given
vertex of the tessellation is the circumcentre (the centre of the circumcircle of the
triangle). Fig. 8.3 shows one such circumcircle. Thus to each Delaunay triangle there
corresponds a unique vertex of a Voronoi polygon lying at its circumcentre.
An important feature of a Delaunay triangulation is the Circumcircle Property:this
guarantees that in a Delaunay triangulation none of the points (vertices) of a triangle
can lie within the circumcircle of any other triangle. The triangles ABD and BCD in
Fig. 8.4, for example, cannot represent a Delaunay triangulation, since the circumcircle
of the triangle BCD contains the point A. However, changing the diagonal of the
quadrilateral ABCD to AC instead of BD produces the triangles ABC and ADC, which

N 5
T 5 N 4
T
T 7 4
T 6
N 7
N 6
T 8 N 3
T
N 8 3

N
N 1 2
T 2
T 1

Fig. 8.1 Dirichlet tessellation with Voronoi regions.