Civil Engineering Reference
In-Depth Information
Figure 3.19
Delaunay triangulation of 14 points.
In the incremental algorithm of Bowyer and Watson, the points are processed one at a
time. In a typical step of point insertion, the triangles whose circumcircle contains the inser-
tion point are identified and deleted. New triangles are constructed in the cavity left behind
by the triangles removed. Hence, the efficiency of the triangulation scheme depends on how
fast one can identify the triangles to be removed and determine correctly the cavity for inser-
tion and the speed with which the circumcentres, circumradii and adjacency relationship of
the new triangles are computed.
The Delaunay criterion itself is not an algorithm for MG. It merely provides a rule to
connect a set of existing points in space to form a triangulation. As a result, although the
boundary of the domain is well specified, it is necessary to devise a scheme to determine the
number and the locations of node points to be inserted within the domain of interest. A typi-
cal approach is to first create a triangular mesh large enough to contain the entire domain.
The boundary nodes are then inserted and connected according to the Delaunay criterion,
and this forms a triangulation of the boundary nodes. More nodes are then inserted pro-
gressively into the coarse boundary mesh, refining the triangles as each new node is intro-
duced, until a desirable number of elements are formed at appropriate positions (Borouchaki
et al. 1996).
In FE applications, there is a requirement that the triangulation contains the boundary of
the domain, so that the boundary integrity can be easily enforced by deleting all the trian-
gles outside the given domain. In most DT processes, before interior nodes are introduced,
a tessellation of the nodes on the domain boundary is produced. However, in this process,
there is no guarantee that boundary segments will all be present in the triangulation. In
many implementations, the approach is to tessellate the boundary nodes using a standard
Delaunay point insertion algorithm with no regard to the integrity of the domain boundary.
A second step is then employed to force or recover the boundary segments. Of course, by
doing so, the triangulation in general is not strictly Delaunay at least locally, hence the term
boundary-constrained DT. In 2D, the edge recovery is straightforward simply by swapping
diagonals (Weatherill 1990), and in 3D, it is less obvious how boundary integrity could be
achieved in general, which will be further elaborated in Chapter 5.
There are a number of ways to create interior points according to the node spacing
requirement, which in fact would lead to meshes of different characteristics. Hermeline
