Civil Engineering Reference
In-Depth Information
Level
Q
1
P
1
1
Q
2
Q
3
2
P
3
P
2
Q
4
Q
5
Q
6
Q
7
P
5
P
7
P
6
3
P
4
Q
13
Q
12
P
13
Q
k
P
12
P
k
L
k = 2
L-1
. . . 2
L-1
Q
2k
Q
2k+1
P
2k
P
2k+1
Figure 2.52
Sequence of sub-regions and pivots.
Algorithm 2d_tree (N, X, Y, Q)
// Construction of a balanced 2d-tree
// N = Number of points, X, Y = x, y co-ordinates of the points, Q =
// Sequence of 2d-tree
// Working arrays: P, L, R
{ Loop i = 1,N // Set initial values to P
P
i
= i
End loop i
n = 1; L
1
= 1; R
1
= N; J2 = 0; k = 0; l = 0; level = INT(log(N +
0.5)/log(2.0))
While (l < level) { l = l + 1; J1 = J2 + 1; J2 = n;
Loop j = J1, J2
left = L
j
; right = R
j
if (mod(l,2)= 1) Sort (left, right, P, X)
//Sort P according
//to X from left to
//right
if (mod(l,2)= 0) Sort (left, right, P, Y)
//Sort P according
//to Y from left to
//right
m =(left + right)/2
// m is the median
k = k + 1; Q
k
= P
m
// median node assign to Q
k
n = n + 1; L
n
= left; R
n
= m - 1
n = n + 1; L
n
= m + 1; R
n
= right
End loop j }
J1 = J2 + 1; J2 = n;
Loop j = J1, J2
left = L
j
; right = R
j
k = k + 1; Q
k
= 0
if (left = right) Q
k
= P
left
End loop j }
2.7.8.1.2 2-d tree diagram
Let's consider the relationship of the points in the sequence {Q
k
, k = 1, N
+
} associated with
region subdivisions,
P
1
,
P
2
, …,
P
N
, where N
+
= 2
L
1 ≥− N. Q
1
is the root node, which has the
child nodes Q
2
and Q
3
, and in general, Q
k
generates Q
2k
and Q
2k+1
. Hence, Q
2k
and Q
2k+1
are
the children of Q
k
, and Q
k
is the father of Q
2k
and Q
2k+1
, as shown in Figure 2.52. On the other
