Civil Engineering Reference
In-Depth Information
11
12
4
9
10
15
16
8
27
28
14
13
19
20
26
6
25
23
24
18
21
22
Figure 2.48
Quadtree division for 40 randomly generated points.
Table 2.7
Pointer array P for quadtree division of 40 points
i
1
2
3
4
5
6
7
8
9
10
P
i
5
25
9
3
17
2
13
3
4
0
P
10+i
3
1
3
1
1
2
21
2
3
0
P
20+i
2
3
1
1
1
2
0
2
cells. Hence, P
1
= 5 means that cell 1 has been divided into four cells 5, 6, 7 and 8; P
5
= 17
shows that cell 5 has been divided into cells 17, 18, 19 and 20; P
17
= 21 indicates that cell 17
has been divided into cells 21, 22, 23 and 24; and P
21
= 2 indicates that there are two points
in cell 21. There are three empty cells, namely, cells 10, 20 and 27, and there is only one cell
containing 4 points, which is cell 9. For a zone with P
z
smaller or equal to NP, the points
allocated in zone z are recorded in array
Q
(length NZ × NP), given by
{Q
k+j
: j = 1, P
z
; k = NP(z − 1)}, z = 1, NZ.
Given a point
p
(x,y), the containing cell can be found following a similar procedure of
point insertion, as shown by the algorithm
QTSearch
.
Algorithm QTsearch (P, x, y, z, x1, x2, y1, y2)
// Input: (x,y) = co-ordinates of the specified point
// Output: z = zone containing the given point, (x1, x2, y1, y2) =
// bounding rectangle of zone z
{
z = 0
If (x < x
min
or x > x
max
) return
If (y < y
min
or y > y
max
) return
xm =(x
min
+ x
max
)/2; ym =(y
min
+ y
max
)/2
z = 1; x1 = x
min
; x2 = xm; y1 = y
min
; y2 = ym
If (x > xm) then
