Algorithms in a Nutshell

(^286) | Chapter 9: Computational Geometry
Figure 9-21. kd-tree core concepts
Example 9-5. Nearest Neighbor Queries implemented with kd-tree
// method in KDTree
public IMultiPoint nearest (IMultiPoint target) {
if (root == null) return null;
// find parent node to which target would have been inserted. This is our
// best shot at locating closest point; compute best distance guess so far
DimensionalNode parent = parent(target);
IMultiPoint result = parent.point;
double smallest = target.distance(result);
// now start back at the root, and check all rectangles that potentially
// overlap this smallest distance. If better one is found, return it.
double best[] = new double[] { smallest };
double raw[] = target.raw( );
IMultiPoint betterOne = root.nearest (raw, best);
if (betterOne != null) { return betterOne; }
return result;
}
// method in DimensionalNode. min[0] contains best computed shortest distance.
IMultiPoint nearest (double[] rawTarget, double min[]) {
// Update minimum if we are closer.
IMultiPoint result = null;
// If shorter, update minimum
double d = shorter(rawTarget, min[0]);
if (d >= 0 && d < min[0]) {
min[0] = d;
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use