Civil Engineering Reference
In-Depth Information
C
k
I2
I3
k
p
I1
Frontal segment
to be deleted
Figure 3.30
Finding the CORE.
or not. If the triangle associated with this edge is zero (no neighbour) or the triangle con-
nected to this edge is Delaunay with respect to the inserted point
p
, then this is a boundary
edge of the CORE. Otherwise, the associate non-Delaunay triangle has to be deleted, and
the number of frontal segments will be increased by one, replacing the edge under consid-
eration with two edges, which are the other two sides of the associated triangle deleted, as
shown in Figure 3.30. This procedure is repeated on each segment of the construction front
until there is no more segment left in the set. The following are the detailed steps of this
algorithm.
Input: the point inserted, the BASE triangle, the current triangulation
Output: list of boundary segments and the triangles deleted
1. Set up the initial front of the CORE.
The frontal segments initially are those from the BASE triangle, each of which
is yet to be determined whether it is a boundary edge of the CORE. As shown in
Figure 3.29, for instance, if triangle T3 is to be retained, P1-P2 will be a boundary
segment of the CORE.
Initial number of boundary segment, m = 0
Number of frontal segment, n = 3
1
2
3
1
2
3
PV;P
1
=
2
=
V; P3
=
V; TT;T
1
=
2
= TT; T3
=
T
BASE
BASE
BASE
BASE
BASE
BASE
1
2
3
1
2
3
1
2
3
FPFPFT;F
=
2
;
=
3
;
=
1
=
P
3
;F
=
P;FTFPFPF 3
1
=
2
;
=
1
;
=
2
;
=
1
1
1
2
2
2
3
3
3
where P1, P2, P3 and T1, T2, T3 are, respectively, the vertices and the neighbours
of the BASE.
Delete the BASE triangle from the triangulation.
2. Check whether the last frontal segment is a boundary segment or not.
Triangle associated with the n
th
frontal segment,
k =
3
Vertices of the n
th
frontal segment are
I
1
=
and
I
n
2
=
n
2
If (k = 0 or
p
∉ C
k
) then
m = m + 1;
BI
1
2
3
;
n = n - 1;
=
1
;
BI
=
2
;
Bk
=
m
m
m
If (n > 0) go to (2) else return;
End if
I3 = vertex of triangle k opposite to edge I1 - I2
If (Δ(
p
, I1, I3) < 0 or Δ(
p
, I3, I1) < 0) then
m = m + 1;
BI
1
=
1
;
BI
2
=
2
;
Bk
3
=
;
n = n - 1;
m
m
m
