Civil Engineering Reference
In-Depth Information
not intersected by the other nearest facets. For a large mesh with a lot of boundary faces, a
background grid can be used to speed up the searching process.
2.5 TOPOLOGICAL OPERATIONS AND ALGORITHMS
2.5.1 Find the neighbouring elements of a triangular mesh
Let
=
Ti
i
1
be the set of triangular elements, with vertices
V
i
j
(j = 1,2,3) for the j
th
vertex of element i. We are going to find
T
i
j
, the j
th
neighbour (opposite to the j
th
vertex) of ele-
ment i, and
T
i
j
= 0
if there is no neighbour on a boundary edge. The concept of the algorithm
is based on the fact that two elements are neighbours if they share a common edge, and an
edge is uniquely defined by the two ending nodes, as shown in Figure 2.25. The first part
of the neighbour searching algorithm is to establish pointer array P in which P
k
stores the
number of nodes greater than and connected to a particular node k. Setting P
1
= 1, a cumula-
tive count of nodal connections is obtained by adding P
k
+ P
k-1
to P
k
such that nodes greater
than k and connected to it are in the range P
k-1
to P
k
− 1 inclusive. With the aid of array Q,
the second double loops i and j are to find any match of edge nodes with k being the smaller
node of an edge. When the smaller node k is identified on an edge, searching along vector Q
starting from P
k
- 1 downwards, (i) if there is no match for the other node connected to k,
register the larger node in Q and set a neighbouring element equal to 0; else (ii) establish the
mutual neighbouring relationship between the current element and a previously registered
element with the same edge nodes. The last part {L = m - 1; While (Q
L
≠ 0) L = L − 1; Q
m
=
Q
L+1
; Q
L+1
= 0} is to delete the matched edge, which will not affect the normal function of
the algorithm but makes it run faster for large systems.
{.
=
,
}
Algorithm Neighbour_T3 (Np, Ne, V, T, P, Q)
// Np and Ne are respectively the number of nodes and elements in the mesh.
// Input: V = Vertices of the elements
// Output: T = Neighbouring triangles
// Working arrays: P, Q
Initialize linear array P: P
1
= 1, {P
k
= 0, k = 2,N
p
}
Loop: i = 1,Ne
Loop: j = 1,3
j1 V
i
mod(j,3)+1
;
j2=V
i
mod(j+1,3)+1
; k = min(j1, j2)
=
P
k
= P
k
+1
End loop j
End loop i
Loop: k=2,Np
k
2*
=
k
2?
i
*
i
k
1
Figure 2.25
Adjacent elements
i
and
i
* share common edge
k
1-
k
2.
