Civil Engineering Reference
In-Depth Information
p
T4
T3
T2
q
T1
Figure 3.26
Searching along the line of intersection.
again. However, from the same figure, if point
q
starts the journey from position (3), it will
go to triangles (4), (5), (6), (7) and (2), and then since (3) is already visited, it is forced to
go to (1). Thereafter, point
q
will be separated from point
p
by the visited triangles, which
effectively formed a closed ring.
Instead of recording the elements visited, recording the direction (edge) visited may help
but still cannot solve the problem, as it is not sure which way to go if the choice is given.
Suppose one starts from position (1) and completes a circuit and goes back to triangle (2); all
edges have been tried, and again, one does not know what to do and where to go. A solution
to overcome the difficulty of looping is by direct crossing from point
q
to point
p
following
the line of intersection, as shown in Figure 3.26. The triangle T
1
containing
q
is known. The
edge of T
1
that is hit by ray
qp
is determined. Go across the edge along ray
qp
to triangle T
2
.
Repeat the process until T
4
and point
p
are reached. As it is not often to have a closed circuit,
a simple solution both in terms of practical implementation and CPU time is the approach
by random walk. Instead of following a systematic rule in approaching
p
, whenever more
than one choice is given, invoke the random number generator to decide which way to go.
Owing to the random nature of the approach, point
q
will not loop forever in a closed cir-
cuit. Implementation experience with work examples of triangulation random samples of
more than 1 million points demonstrates that it is efficient and reliable.
Apart from the random walk, another possibility is to change the starting triangle after
a certain number of trials. Let n be the average number of visits to locate the BASE in the
previous point insertions. If the BASE still cannot be found after, say, 2n visits, change the
starting triangle from the last triangle to the second last triangle, and repeat the search from
there. As the number of triangles is finite, this procedure of changing the starting triangle
will always converge.
3.5.4.5 Steps in locating the BASE
1. Start the search from the last triangle constructed, T.
2. Compute the area co-ordinates of point
p
relative to triangle T.
The area co-ordinates of
p
with respect to triangle T are
Δ
(
pp p
)
,
Δ
(
p pp
)
,
Δ
(
ppp
)
L
=
23
L
=
13
L
=
12
1
2
3
Δ
Δ
Δ
where Δ = Δ(
p
1
p
2
p
3
) is the area of triangle T with vertices
p
1
,
p
2
and
p
3
, as shown in
Figure 3.27.
