Mesh generation on planar domain - Finite Element Mesh Generation - page 118

(George et al. 1991), and (ii) modification or reconnection of the triangles of the pipe to
retrieve the line segment.
3.5.7.1 Determination of the pipe
Given two points A and B in the triangulation, find the pipe , which is the polygon of trian-
gular elements intersected by line AB, as shown in Figure 3.38.
i. Find out triangle T 1 , which is connected to point A intersected by line AB.
ii. From ii. k , find triangle ii. k+1 , which is the neighbour of ii. k intersected by line AB.
iii. The pipe as a collection of triangles is determined if point B is the opposite node of
T k+1 ; else go to step (ii).
Remarks: For randomly generated points, there is a possibility that a point may lie exactly
on the line segment by some numerical interpretation. In this case, the line segment has to
be broken up into small sub-segments, each of which is to be recovered in turn. However,
in realistic practical situations, no point is allowed to fall within a very small distance from
a boundary line segment, and hence, there is always a solution for the boundary recovery
problems.
Once the pipe or the associated polygon is determined, line segment AB can be recovered
by re-triangulating the pipe. To this end, there are at least two methods that are proved to
be pretty effective.
3.5.7.2 Divide-and-conquer
As shown in Figure 3.39, a pipe is divided by the line segment AB into two regions: polygon
P1 and polygon P2. The two polygons can be dealt with in exactly the same manner by the
same procedure. Take for instance the polygon P1 on the left-hand side of line AB. Among
all the nodes above line AB, find the node, say C, which is closest to the line AB, as shown
in Figure 3.39; in case there are more than one node, any such node can be taken. Form
triangle ABC, and polygon P1 is divided effectively into three parts, namely, triangle ABC
and two smaller polygons on the left-hand side and the right-hand side of triangle ABC, as
shown in Figure 3.39. If C is next to point A or point B, only one polygon will be formed.
The same process can be applied repeatedly to the polygons so created until each polygon
is reduced to a triangle, and by then, polygon P1 will be triangulated with line AB on its
P1
A
C
B
P2
Figure 3.39 Triangulation of the pipe by divide-and-conquer.