Java Reference
In-Depth Information
C
A
D
B
E
F
Figure13.14 Searching in the k-d treeof Figure 13.11. (a) The k-d tree decom-
position for a 128128-unit region containing seven data points. (b) The k-d tree
for the region of (a).
privatevoidrshelp(KDNode<E>rt,int[]point,
intradius,intlev){
if(rt==null)return;
int[]rtkey=rt.key();
if(InCircle(point,radius,rtkey))
System.out.println(rt.element());
if(rtkey[lev]>(point[lev]-radius))
rshelp(rt.left(),point,radius,(lev+1)%D);
if(rtkey[lev]<(point[lev]+radius))
rshelp(rt.right(),point,radius,(lev+1)%D);
}
Figure13.15 The k-d tree region search method.
Figure 13.15 shows an implementation for the region search method. When
a node is visited, function InCircle is used to check the Euclidean distance
between the node's record and the query point. It is not enough to simply check
that the differences between the x- and y-coordinates are each less than the query
distances because the the record could still be outside the search circle, as illustrated
by Figure 13.13.
13.3.2
The PR quadtree
In the Point-Region Quadtree (hereafter referred to as the PR quadtree) each node
either has exactly four children or is a leaf. That is, the PR quadtree is a full four-
way branching (4-ary) tree in shape. The PR quadtree represents a collection of
data points in two dimensions by decomposing the region containing the data points
into four equal quadrants, subquadrants, and so on, until no leaf node contains more
than a single point. In other words, if a region contains zero or one data points, then
Search WWH ::




Custom Search