Algorithm
Development Kit 1.0

algs.model.kdtree
Class KDTree

java.lang.Object
  extended by algs.model.kdtree.KDTree

public class KDTree
extends java.lang.Object

Standard unbalanced k-dimensional binary tree.

Stores a set of points against which one can execute 2-dimensional range queries against a rectangle D whose domain is defined by a rectangle D=[x1,x2] x [y1,y2]. Note that the rectangle could be infinite in none, one, or two of these dimensions by having any of its coordinates set to Double.NEGATIVE_INFINITY or Double.POSITIVE_INFINITY. A rectangle could be one-dimensional (if either x1==x2 or y1==y2) or zero-dimensional (if both x1==x2 and y1==y2).

Note that the example above is for Double values; the node values stored could be of any type that implements Comparable.

Original source derived from Bentley [1975]. http://portal.acm.org/citation.cfm?id=361007

Since:
1.0
Version:
1.0, 6/15/08
Author:
George Heineman

Field Summary
 int maxDimension
          Maximum dimension for this tree.
 
Constructor Summary
KDTree(int md)
          Default KDTree constructor.
 
Method Summary
 int count()
          Helper method for testing.
 int getNumDoubleRecursion()
           
 int getNumRecursion()
           
 DimensionalNode getRoot()
          Return the root of the KDTree.
 int height()
          Helper method for testing.
 void insert(IMultiPoint value)
          Insert the value into its proper location.
 IMultiPoint nearest(IMultiPoint target)
          Find the nearest point in the KDtree to the given point.
 int nextDimension(DimensionalNode node)
          Helper method to always determine the next dimensionality given a node.
 int nextDimension(int d)
          Helper method to always determine the next dimensionality given an integer representing the specified dimension in the KDTree.
 DimensionalNode parent(IMultiPoint value)
          Return the parent of the point IF the point were to be inserted into the kd-tree.
 void removeAll()
          Empty the KDTree of all of its internal points.
 java.util.ArrayList<IMultiPoint> search(IHypercube space)
          Locate all points within the KDTree that fall within the given IHypercube.
 void search(IHypercube space, IVisitKDNode visitor)
          Locate all points within the TwoDTree that fall within the given IHypercube and visit those nodes via the given visitor.
 void setRoot(DimensionalNode newRoot)
          Set the root of the KDTree.
 java.lang.String toString()
          Reasonable toString to aid debugging.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

maxDimension

public final int maxDimension
Maximum dimension for this tree.

Constructor Detail

KDTree

public KDTree(int md)
Default KDTree constructor.

Parameters:
md - Maximum dimension of nodes within this tree.
Method Detail

nextDimension

public int nextDimension(DimensionalNode node)
Helper method to always determine the next dimensionality given a node. Used in test cases.

Parameters:
node - returns dimension to use for children of this node.

nextDimension

public int nextDimension(int d)
Helper method to always determine the next dimensionality given an integer representing the specified dimension in the KDTree. Used in test cases.

Parameters:
d - returns dimension of children nodes for next dimension.

removeAll

public void removeAll()
Empty the KDTree of all of its internal points. Leave the maximum dimensionality the same.


parent

public DimensionalNode parent(IMultiPoint value)
Return the parent of the point IF the point were to be inserted into the kd-tree. Returns null only if the tree is empty to begin with (i.e., there are no parents). Note that you will have to inspect the dimension for the DimensionalNode to determine if this is a Below or an Above parent.


insert

public void insert(IMultiPoint value)
Insert the value into its proper location.

No balancing is performed.

isBelow checks for strict less than. This means that (by default) equal coordinates are going to appear in above Subtree

Parameters:
value - non-null value to be added into the tree.
Throws:
java.lang.IllegalArgumentException - if value is null

getRoot

public DimensionalNode getRoot()
Return the root of the KDTree.


setRoot

public void setRoot(DimensionalNode newRoot)
Set the root of the KDTree. Use with Caution! One issue that may cause problems is when the new root does not have 'boundless' space associated with it, so the initial infinite region is propagated throughout the tree whenever the root is set.

Parameters:
newRoot - The desired node to be the root of the tree.

nearest

public IMultiPoint nearest(IMultiPoint target)
Find the nearest point in the KDtree to the given point.

Only returns null if the tree was initially empty. Otherwise, must return some point that belongs to the tree.

If tree is empty or if the target is null then null is returned.

Parameters:
target - the target of the search.

search

public java.util.ArrayList<IMultiPoint> search(IHypercube space)
Locate all points within the KDTree that fall within the given IHypercube.

Parameters:
space - non-null space in which to search
Returns:
ArrayList of MultiPoints that fall within the given space.
Throws:
java.lang.NullPointerException - if space is null

search

public void search(IHypercube space,
                   IVisitKDNode visitor)
Locate all points within the TwoDTree that fall within the given IHypercube and visit those nodes via the given visitor.

Parameters:
space - non-null space within which to search.
visitor - non-null IVisitTwoDNode visitor that contains behavior to process at each discovered point within the space.
Throws:
java.lang.NullPointerException - if space or visitor is null

toString

public java.lang.String toString()
Reasonable toString to aid debugging.

Overrides:
toString in class java.lang.Object

count

public int count()
Helper method for testing.


height

public int height()
Helper method for testing.


getNumRecursion

public int getNumRecursion()

getNumDoubleRecursion

public int getNumDoubleRecursion()

Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.