edu.stanford.math.plex4.kd

Class KDTree

java.lang.Object

edu.stanford.math.plex4.kd.KDTree

public class KDTree
extends java.lang.Object

This class implements the functionality of a KD-tree. It is designed for the efficient searching of Euclidean spaces.

Author:

Andrew Tausz

Constructor Summary

Constructors

Constructor and Description
KDTree(double[][] dataPoints) Constructor for initializing the KD-tree with a set of points.

Method Summary

Methods

Modifier and Type	Method and Description
gnu.trove.TIntHashSet	epsilonNeighborhoodSearch(double[] queryPoint, double epsilon, boolean openNeighborhood) This function finds all points within an open or closed neighborhood of the query point.
int	nearestNeighborSearch(double[] queryPoint) This function returns the index of the nearest neighbor to the query point.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

KDTree

public KDTree(double[][] dataPoints)

Constructor for initializing the KD-tree with a set of points.

Parameters:

dataPoints -

Method Detail

nearestNeighborSearch

public int nearestNeighborSearch(double[] queryPoint)

This function returns the index of the nearest neighbor to the query point.

Parameters:

queryPoint - the point to find the closest point to

Returns:

the index of the nearest point to the query point

epsilonNeighborhoodSearch

public gnu.trove.TIntHashSet epsilonNeighborhoodSearch(double[] queryPoint,
                                              double epsilon,
                                              boolean openNeighborhood)

This function finds all points within an open or closed neighborhood of the query point.

Parameters:

queryPoint - the center of the ball to query

epsilon - the radius of the ball

openNeighborhood - true if the neighborhood is open and false otherwise

Returns:

the indices of those points that fall within the ball centered at the query point