Civil Engineering Reference
In-Depth Information
z = z + 1; x1 = xm; x2 = x
max
End if
If (y > ym) then
z = z + 2; y1 = ym; y2 = y
max
End if
Search_Zone (x, y, z, x1, x2, y1, y2, P)
}
Procedure Search_Zone (x, y, z, x1, x2, y1, y2, P)
{ 1: n = P
z
if (n ≤ NP) return
xm =(x1 + x2)/2; ym =(y1+y2)/2
if (x > xm) n = n + 1; x1 = xm else x2 = xm
if (y > ym) n = n + 2; y1 = ym else y2 = ym
z = n
Go to 1
}
Quadtree partitioning into zones for a set of N points constructed by the point insertion
algorithm has an average complexity of Nlog(N), as each point is assigned to a zone follow-
ing a subdivision procedure such that the size of a cell is halved in each cell split, and it takes,
on average, log(N) times of cell splits before it settles in a non-saturated cell. Of course, a
point will go through more levels of subdivision if all the points but one are clustered in a
small area. The performance of the insertion algorithm has been tested with randomly gen-
erated points from 10
3
points to 10
7
points, as shown in Table 2.8. A quasi-straight line is
resulted in a plot of the CPU time against Nlog(N), as shown in Figure 2.49.
Table 2.8
CPU time(s) for Quadtree, Octree and kd-trees
N
Nlog
10
(N)
Quadtree
Octree
2-d tree
3-d tree
1000
3000
0.000138
0.000123
0.000931
0.000928
10,000
40,000
0.00177
0.00163
0.01622
0.0165
100,000
500,000
0.0225
0.0215
0.28
0.259
1,000,000
6,000,000
0.35
0.311
4.426
4.316
10,000,000
70,000,000
5.77
4.41
74.03
70.27
100
10
Quadtree
1
Octree
0.1
2-d tree
0.01
3-d tree
0.001
0.0001
1
10
100
1000
10,000
100,000 1,000,00010,000,000 100,000,000
Nlog10(N)
Figure 2.49
CPU time vs Nlog(N) for Quadtree, Octree and kd-trees.
