Civil Engineering Reference
In-Depth Information
boundary. Line AB is retrieved, and the
pipe
is triangulated when the divide-and-conquer
process is also applied to polygon P2 on the other side of line AB.
3.5.7.3 Swapping of diagonals
As mentioned in Section 3.5.7.2, one triangulation can be transformed into any triangula-
tion by merely swapping the diagonals between two adjacent triangles. Hence, line AB in the
pipe
can be recovered by swapping the diagonals of adjacent triangles of the
pipe
. However,
even if a solution exists, one doesn't know how to arrive at it, i.e. one doesn't know the cor-
rect sequence of the diagonal swaps so that line AB can be recovered for the most general
case. George and Borouchaki (1998) proposed a swapping process by taking a pair of tri-
angles at random until line AB is recovered. However, a more systematic approach can be
formulated, which can be proved to give convergent results (Lo and Liu 2002).
Starting from the first two triangles T
1
and T
2
, swap the diagonal within the quadrilat-
eral so formed, as shown in Figure 3.40. Remove the triangle not intersected by line AB,
and the number of triangles in the
pipe
is reduced by one. Repeat the same process with
the diminished polygon, and if both triangles are intersected by line AB after the diagonal
swap or in the case of a concave quadrilateral where diagonal swap is not allowed, pass on
to the next pair of triangles. When one comes to the end of the
pipe
, start the entire process
over again with the first two triangles. This process has been proved to be convergent, and
finally, the
pipe
is reduced into a quadrilateral with line AB on the main diagonal, as shown
in Figure 3.41.
Remarks:
Comparing between the two methods, the diagonal swap for a recovering line
segment is probably simpler as no new object is introduced in the process. The basic idea to
implement the diagonal swap algorithm is to maintain a correct sequence of triangles for the
shrinking
pipe
when triangles are taken away until the
pipe
is reduced to a quadrilateral.
A sequence of contiguous triangles from point A to point B is needed as this would allow
adjacent triangles to pair up easily to form quadrilaterals for diagonal swap.
A
T
1
T
2
T
k
T
k+1
B
Triangle to
be removed
T
n
A
B
Figure 3.40
Recovering line segment by diagonal swap.
