Civil Engineering Reference
In-Depth Information
3
4
7
8
1
6
5
Figure 2.47
Cells containing more than four points are split.
(Holroyd and Mason 1990; Yiu et al. 1996). A maximum capacity of a cell can be set, such
that the cells containing more points than the allowable limit will be split into four quadrants
or child cells symmetrically along the x- and y-directions, as shown in Figure 2.47. In this
example, not more than 4 points are allowed in each cell, and as a result, cell 2 is further sub-
divided into four cells, which are labelled as cells 5, 6, 7 and 8. The process can be repeated
on all the subdivided cells until no cell contains more points than it is allowed to hold.
The subdivision can be done conveniently by means of a recursive procedure; however, a
more efficient looping algorithm is presented in Section 2.7.7 in which points are input one
by one until all the points are processed.
Algorithm Quadtree (N, X, Y, P, Q)
// N = Number of points, x
min
, x
max
, y
min
, y
max
= x, y limits of the points
// NP = Number of points allowed in a cell, NZ = Number of zones (cells)
// created
// P
k
= Number of points in cell k, or the first child of cell k if P
k
> NP
// Q = Array recording points allocated to the zones, (Xi,
i
, Y
i
) =
// Co-ordinates of point i, i = 1,N
{
Set pointer array P to zero, P
i
= 0, i = 1,N
NZ = 4; xm =(x
min
+ x
max
)/2; ym =(y
min
+ y
max
)/2
Loop: i = 1,N
z = 1; u = X
i
; v = Y
i
x1 = x
min
; x2 = x
max
; y1 = y
min
; y2 = y
max
If (u > xm) then
z = z + 1; x1 = xm; x2 = x
max
Endif
If (v > ym) then
z = z + 2; y1 = ym; y2 = y
max
Endif
Zone (z, i, u, v, X, Y, x1, x2, y1, y2, NZ, P, Q)
End loop i }
Procedure Zone (z, i, u, v, X, Y, x1, x2, y1, y2, NZ, P, Q)
// Insert point i (u,v) to zone z (x1,x2,y1,y2)
{ 1: n = P
z
If (n < NP) then
k = NP(z-1)+ n + 1; Q
k
= i; P
z
= n+1; return
End if
if (n = NP) Split_Zone (z, i, u, v, X, Y, x1, x2, y1, y2, NZ, P,
Q); Return
