Page 206 - Basic Structured Grid Generation

Unstructured grid generation 195

x
x 5 4

x 1 x 3
x 2
x 6

Fig. 8.8 New point x 6 lying outside triangulation and inside one circumcircle.

x 7

x 2 x 3 x 4 x 5
x 1 x 6

x 8

Fig. 8.9 New point lying outside triangulation and inside two circumcircles.

An example of a new point lying outside T i but within two circumcircles is shown
in Fig. 8.9. Here we start with a Delaunay triangulation of seven points x 1 , x 2 ,..., x 7 ;
the new point x 8 lies within the circumcircles of triangles x 1 x 2 x 3 and x 4 x 5 x 6 ,which
together make up the set S. We therefore remove edges x 1 x 3 and x 4 x 6 , and connect
x 8 to the points x 1 , x 2 , x 3 , x 4 , x 5 , x 6 . The remaining vertex x 7 is not ‘visible’ from x 8 .
In the final case 3, the new point x i+1 lies outside the existing triangulation T i and
the union of circumcircles. No deletion of edges in T i is now necessary. All that is
required is to locate the external edges of T i which are visible to x i+1 . The triangulation
is completed by connecting x i+1 to each of the vertices on these external edges. An
example is shown in Fig. 8.10, which starts with a Delaunay triangulation of five
points x 1 , x 2 ,... , x 5 . Here the outer edges of T i visible to x 6 (which is not contained
in any of the three circumcircles) are x 1 x 2 and x 2 x 3 .So x 6 must be connected to each
vertex x 1 , x 2 ,and x 3 for the new Delaunay triangulation to be complete. Clearly the
circumcircles of each of the new triangles x 1 x 2 x 6 and x 2 x 3 x 6 do not contain any of
the three remaining points, and the Circumcircle Property is satisfied.
As might be expected, the final Delaunay triangulation of a set of data points is
unaffected by the order in which individual points are inserted into a pre-existing
triangulation (using the Bowyer-Watson algorithm).