Civil Engineering Reference
In-Depth Information
Figure 2.54
Squarish 3-d tree of 1000 points.
noted that the construction of a 2-d tree and a 3-d tree takes a roughly equal amount of CPU
time, as the procedure is similar and the number of operations involved is exactly the same.
A
squarish
3-d tree of 1000 points distributed along a straight line is shown in Figure 2.54,
in which small cells are found near the diagonal.
The following is the
pseudo-code
for the construction of a
squarish
3-d tree by a proper
sequencing of a given set of N points, {(X
i
, Y
i
, Z
i
), i = 1,N}, for which additional arrays X1,
X2, Y1, Y2, Z1 and Z2 are needed to store the corner points of the cells of spatial partition.
Algorithm 3d_tree (N, X, Y, Q, n, P, L, R)
// Construction of a squarish 3d-tree
// N = Number of points; X, Y, Z = x, y, z co-ordinates of the points; Q =
// Sequence of 3d-tree
// n = Number of cells; Points in cell k = {Pi,
i
, i = L
k
, R
k
}
{
Loop i = 1,N // Set initial values to P
P
i
= i
End loop i
X1
1
= X
min
; X2
1
= X
max
; Y1
1
= Y
min
; Y2
1
= Y
max
; Z1
1
= Z
min
; Z2
1
= Z
max
;
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
;
m = (left + right)/2 // m is the median
U1 = X1
j
; U2 = X2
j
; V1 = Y1
j
; V2 = Y2
j
; W1 = Z1
j
; W2 = Z2
j
;
