org.openimaj.util.tree

Class IncrementalDoubleKDTree

java.lang.Object

org.openimaj.util.tree.IncrementalDoubleKDTree

public class IncrementalDoubleKDTree
extends Object

Implementation of a simple incremental KDTree for double[]s. Includes support for range search, neighbour search, and radius search. The tree created by this class will usually be rather unbalanced.

The KDTree allows fast search for points in relatively low-dimension spaces.

Author:

Jonathon Hare (jsh2@ecs.soton.ac.uk)

Constructor Summary

Constructors

Constructor and Description
IncrementalDoubleKDTree() Create an empty KDTree object
IncrementalDoubleKDTree(Collection<double[]> coords) Create a KDTree object and populate it with the given data.
IncrementalDoubleKDTree(double[][] coords) Create a KDTree object and populate it with the given data.

Method Summary

Modifier and Type	Method and Description
protected static double	distance(double[] a, double[] b)
ObjectDoublePair<double[]>	findNearestNeighbour(double[] query) Find the nearest neighbour.
List<ObjectDoublePair<double[]>>	findNearestNeighbours(double[] query, int k) Find the K nearest neighbours.
void	insert(double[] point) Inserts a point into the tree, preserving the spatial ordering.
void	insertAll(Collection<double[]> coords) Insert all the points from the given collection into the index.
void	insertAll(double[][] coords) Insert all the points from the given collection into the index.
List<ObjectDoublePair<double[]>>	radiusDistanceSearch(double[] centre, double radius) Find all the points within the given radius of the given point.
List<double[]>	radiusSearch(double[] centre, double radius) Find all the points within the given radius of the given point
List<double[]>	rangeSearch(double[] lowerExtreme, double[] upperExtreme) Searches the tree for all points contained within the bounding box defined by the given upper and lower extremes

Methods inherited from class java.lang.Object

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

Constructor Detail

IncrementalDoubleKDTree

public IncrementalDoubleKDTree()

Create an empty KDTree object

IncrementalDoubleKDTree

public IncrementalDoubleKDTree(Collection<double[]> coords)

Create a KDTree object and populate it with the given data.

Parameters:

coords - the data to populate the index with.

IncrementalDoubleKDTree

public IncrementalDoubleKDTree(double[][] coords)

Create a KDTree object and populate it with the given data.

Parameters:

coords - the data to populate the index with.

Method Detail

insertAll

public void insertAll(Collection<double[]> coords)

Insert all the points from the given collection into the index.

Parameters:

coords - The points to add.

insertAll

public void insertAll(double[][] coords)

Insert all the points from the given collection into the index.

Parameters:

coords - The points to add.

insert

public void insert(double[] point)

Inserts a point into the tree, preserving the spatial ordering.

Parameters:

point - Point to insert.

rangeSearch

public List<double[]> rangeSearch(double[] lowerExtreme,
                                  double[] upperExtreme)

Searches the tree for all points contained within the bounding box defined by the given upper and lower extremes

Parameters:

lowerExtreme -

upperExtreme -

Returns:

the points within the given bounds

distance

protected static final double distance(double[] a,
                                       double[] b)

findNearestNeighbour

public ObjectDoublePair<double[]> findNearestNeighbour(double[] query)

Find the nearest neighbour. Only one neighbour will be returned - if multiple neighbours share the same location, or are equidistant, then this might not be the one you expect.

Parameters:

query - query coordinate

Returns:

nearest neighbour

findNearestNeighbours

public List<ObjectDoublePair<double[]>> findNearestNeighbours(double[] query,
                                                              int k)

Find the K nearest neighbours.

Parameters:

query - query coordinate

k - the number of neighbours to find

Returns:

nearest neighbours

radiusSearch

public List<double[]> radiusSearch(double[] centre,
                                   double radius)

Find all the points within the given radius of the given point

Parameters:

centre - the centre point

radius - the radius

Returns:

the points

radiusDistanceSearch

public List<ObjectDoublePair<double[]>> radiusDistanceSearch(double[] centre,
                                                             double radius)

Find all the points within the given radius of the given point. Returns the distance to the point as well as the point itself. Distance is the squared L2 distance.

Parameters:

centre - the centre point

radius - the radius

Returns:

the points and distances