Civil Engineering Reference
In-Depth Information
the Delaunay-ADF method will be described in detail in Section 3.7 after the introduction
of DT in this section and AFT in Section 3.6.
3.5.7 Boundary recovery in two dimensions
For MG over a bounded planar domain with a well-defined boundary made up of a series
of line segments by means of DT, the procedure can be divided into three distinct steps if
boundary integrity is to be respected, namely, (i) insertion of boundary points, (ii) insertion
of interior points and (iii) boundary recovery. The problem is known as constrained DT,
which is also considered, in general, as a typical MG problem for various engineering appli-
cations. Full compliance of the boundary in all aspects is expected for a constrained DT.
However, a solution is only proved to exist in 2D where the boundary consists of only edges.
Over a 3D space, the boundary of a general polyhedron is made up of edges as well as faces,
and it is not difficult to perceive that there is simply no solution for the partition of a twisted
pentahedron without adding an interior node. Even if interior nodes are allowed, there is
no guarantee with a formal proof that a solution exists for the most general case (Chazelle
1984; Ruppert and Seidel 1992). Hence, solutions in the form of a semi-constrained DT
have been proposed (Weatherill 1988; Si 2010) in which the geometry is recovered and the
topology is still missing, such that the edges are recovered as a list of line segments and the
boundary faces are represented as a concatenation of triangular sub-faces. Nevertheless,
theoretically sound heuristic approaches do exist for fully constrained 3D DT for most of
the practical cases, which will be discussed in Section 5.3.
Strictly speaking, constrained DT is not a DT in which the Delaunay properties of some tri-
angles are violated, at least locally, in order to satisfy the boundary constraints. Constrained
DT is a triangulation derived from the DT of the boundary points and possibly some interior
points by properly recovering all the boundary constraints with as little modification as
possible. In 2D, such constrained triangulations exist based on the following facts: (1) any
bounded region simply or multi-connected can be triangulated (George and Borouchaki
1998), and (2) any triangulation can be converted from one to another by merely swapping
the diagonals (Fournier and Montuno 1984). Knowing the existence of solutions for the
boundary recovery problems, many methods have been proposed in which boundary edges
are recovered one at a time.
Algorithm for recovering an edge.
An edge in the DT of the boundary nodes (possibly
with some interior nodes) is a line segment connecting any two points in the triangulation,
as shown in Figure 3.38. The line segment can be restored in two distinct phases: (i) determina-
tion of the polygon associated with the line segment, which is called a
pipe
in the literature
A
T
1
T
k
T
k+1
B
T
n
Figure 3.38
The pipe - polygon associated with line AB.
