ca.pfv.spmf.datastructures.kdtree

Class KDTree

java.lang.Object

ca.pfv.spmf.datastructures.kdtree.KDTree

public class KDTree
extends java.lang.Object

This is an implementation of a "KD tree" based on the description in the book: "Algorithms in a Nutshell" by Heineman et al. (2008).

This implementation uses the Randomized-Select algorithm described in the book "Introduction to algorithms" book by Cormen et al. (2001) as suggested by Heineman.

Elements that are inserted into the tree have to be arrays of double.

The class provide methods for - building the tree by inserting points, - using the tree to find the nearest neighbor to a given point - using the tree to find the k nearest neighbors to a given point

To find the k-nearest neighboors, the closest points are stored in a red black tree.

Constructor Summary

Constructors

Constructor and Description
KDTree() Default constructor

Method Summary

Modifier and Type	Method and Description
void	buildtree(double[][] points) This method build the KDtree from a set of points.
RedBlackTree<KNNPoint>	knearest(double[] targetPoint, int k) Method to get the k nearest neighboors
double[]	nearest(double[] targetPoint) Method to get the nearest neighbor
int	size() Get the number of nodes in the KD-TREE
java.lang.String	toString() Convert this tree to a string representation

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

KDTree

public KDTree()

Default constructor

Method Detail

size

public int size()

Get the number of nodes in the KD-TREE

Returns:

the number of nodes

buildtree

public void buildtree(double[][] points)

This method build the KDtree from a set of points. This method should be called only once.

Parameters:

points - an array of points, where each point is a double[]

nearest

public double[] nearest(double[] targetPoint)

Method to get the nearest neighbor

knearest

public RedBlackTree<KNNPoint> knearest(double[] targetPoint,
                                       int k)

Method to get the k nearest neighboors

toString

public java.lang.String toString()

Convert this tree to a string representation

Overrides:

toString in class java.lang.Object