Civil Engineering Reference
In-Depth Information
ym =(x1 + x2)/2; ym =(y1 + y2)/2
if (u > xm) n = n + 1; x1 = xm else x2 = xm
if (v > ym) n = n + 2; y1 = ym else y2 = ym
z = n
Go to 1 }
// Convention: if applies to the entire line
Procedure Split_Zone (z, i, u, v, X, Y, x1, x2, y1, y2, NZ, P, Q)
// Zone z is split into zones NZ + j, j = 1,4 and points in zone z are
// put in zones NZ + j
{
k = NP(z - 1)
1:
xm =(x1 + x2)/2; ym =(y1 + y2)/2; P
z
= NZ + 1
Assign (i, u, v, xm, ym, NZ, P, Q)
Loop j = 1,NP
L = Q
k+j
;
Assign (L, X
L
, Y
L
, xm, ym, NZ, P, Q)
End Loop j
NZ = NZ + 4
Loop j = 1,4
z = NZ + j - 4
If (P
z
> NP) then
If (j > 2) y1 = ym
else y2 = ym
If (j = 2 or j = 4) x1 = xm
else x2 = xm
Go to 1
End if
End Loop j }
Procedure Assign (i, u, v, xm, ym, NZ, P, Q)
// Assign point i (u,v) to zone NZ + j, j = 1,2 3 or 4 according to its
// position relative to (xm,ym)
{
z = NZ + 1
If (u > xm) z = z + 1
If (v > ym) z = z + 2
P
z
= P
z
+ 1; k = NP(z-1)+ P
z
; Q
k
= if
}
The algorithm runs as follows. The insertion point is first assigned to one of the four pri-
mary zones 1, 2, 3 or 4 according to its position relative to the central division lines. In the
Procedure Zone
, if the number of points in the current zone is less than NP, the insertion
point is assigned to this zone; if the capacity of the zone (NP) is exceeded by the addition of
the insertion point, then the current zone is split symmetrically into four cells, and further
splitting of cells might be necessary if all the points are found in one of the subdivided cells.
In case the cell is already split, the co-ordinates of the insertion point are checked against
the central division lines to determine which child cell contains the insertion point. The
Procedure Zone
can be repeated until the point settles in a non-saturated cell.
The Quadtree division of the same set of 40 randomly generated points is shown in Figure
2.48, in which the rectangle containing all the points is partitioned into 28 zones. In this
example, the maximum number of points allowed in each zone is set equal to 4, i.e. a zone
will be split into four quadrants once the number of points in it exceeds 4. The pointer array
for the Quadtree division of the points is given in Table 2.7.
A P
z
value less than or equal to NP = 4 gives the number of points in the zone z, whereas if
the P
z
value is greater than NP, it represents the first child in the subdivision into four child
