org.openimaj.util.tree

Class DoubleKDTree

java.lang.Object

org.openimaj.util.tree.DoubleKDTree

public class DoubleKDTree
extends Object

Immutable KD-Tree implementation for double[] data. Allows various tree-construction strategies to be applied through the DoubleKDTree.SplitChooser. Supports efficient range, radius and nearest-neighbour search for relatively low dimensional spaces.

Author:

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

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	DoubleKDTree.ApproximateBBFMedianSplit Approximate best-bin-first median splitting.
static class	DoubleKDTree.BasicMedianSplit Basic median split.
static class	DoubleKDTree.BBFMedianSplit Best-bin-first median splitting.
static class	DoubleKDTree.KDTreeNode An internal node of the KDTree
static class	DoubleKDTree.RandomisedBBFMeanSplit Randomised best-bin-first splitting strategy: Nodes with less than a set number of items become leafs.
static interface	DoubleKDTree.SplitChooser Interface for describing how a branch in the KD-Tree should be created

Field Summary

Fields

Modifier and Type	Field and Description
double[][]	data The underlying data array
DoubleKDTree.KDTreeNode	root The tree roots

Constructor Summary

Constructors

Constructor and Description
DoubleKDTree(double[][] data) Construct with the given data and default splitting strategy (DoubleKDTree.BBFMedianSplit)
DoubleKDTree(double[][] data, DoubleKDTree.SplitChooser split) Construct with the given data and splitting strategy

Method Summary

Modifier and Type	Method and Description
double[][]	coordinateRadiusSearch(double[] centre, double radius) Find all the points within the given radius of the given point.
void	coordinateRadiusSearch(double[] centre, double radius, gnu.trove.procedure.TObjectDoubleProcedure<double[]> proc) Find all the points within the given radius of the given point.
double[][]	coordinateRangeSearch(double[] lowerExtreme, double[] upperExtreme) Search the tree for all points contained within the hyperrectangle defined by the given upper and lower extremes.
int[]	indexRadiusSearch(double[] centre, double radius) Search the tree for the indexes of all points contained within the hypersphere defined by the given centre and radius.
int[]	indexRangeSearch(double[] lowerExtreme, double[] upperExtreme) Search the tree for all points contained within the hyperrectangle defined by the given upper and lower extremes.
List<int[]>	leafIndices() Find all the indices seperated by leaves
IntDoublePair	nearestNeighbour(double[] qu) Nearest-neighbour search
List<IntDoublePair>	nearestNeighbours(double[] qu, int n) Nearest-neighbour search
void	radiusSearch(double[] centre, double radius, gnu.trove.procedure.TIntObjectProcedure<double[]> proc) Find all the points within the given radius of the given point.
void	rangeSearch(double[] lowerExtreme, double[] upperExtreme, gnu.trove.procedure.TIntObjectProcedure<double[]> proc) Search the tree for all points contained within the hyperrectangle 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

Field Detail

root

public final DoubleKDTree.KDTreeNode root

The tree roots

data

public final double[][] data

The underlying data array

Constructor Detail

DoubleKDTree

public DoubleKDTree(double[][] data)

Construct with the given data and default splitting strategy (DoubleKDTree.BBFMedianSplit)

Parameters:

data - the data

DoubleKDTree

public DoubleKDTree(double[][] data,
                    DoubleKDTree.SplitChooser split)

Construct with the given data and splitting strategy

Parameters:

data - the data

split - the splitting strategy

Method Detail

coordinateRangeSearch

public double[][] coordinateRangeSearch(double[] lowerExtreme,
                                        double[] upperExtreme)

Search the tree for all points contained within the hyperrectangle defined by the given upper and lower extremes.

Parameters:

lowerExtreme - the lower extreme of the hyperrectangle

upperExtreme - the upper extreme of the hyperrectangle

Returns:

the points within the given bounds

indexRangeSearch

public int[] indexRangeSearch(double[] lowerExtreme,
                              double[] upperExtreme)

Search the tree for all points contained within the hyperrectangle defined by the given upper and lower extremes.

Parameters:

lowerExtreme - the lower extreme of the hyperrectangle

upperExtreme - the upper extreme of the hyperrectangle

Returns:

the points within the given bounds

indexRadiusSearch

public int[] indexRadiusSearch(double[] centre,
                               double radius)

Search the tree for the indexes of all points contained within the hypersphere defined by the given centre and radius.

Parameters:

centre - the centre point

radius - the radius

Returns:

the points within the given bounds

radiusSearch

public void radiusSearch(double[] centre,
                         double radius,
                         gnu.trove.procedure.TIntObjectProcedure<double[]> proc)

Find all the points within the given radius of the given point. Internally this works by finding the points in the hyper-square encompassing the hyper-circle and then filtering. Each valid point that is found is reported to the given processor together with its index.

The search can be stopped early by returning false from the TIntObjectProcedure.execute(int, Object) method.

Parameters:

centre - the centre point

radius - the radius

proc - the process

rangeSearch

public void rangeSearch(double[] lowerExtreme,
                        double[] upperExtreme,
                        gnu.trove.procedure.TIntObjectProcedure<double[]> proc)

Search the tree for all points contained within the hyperrectangle defined by the given upper and lower extremes. Each valid point that is found is reported to the given processor together with its index in the original data.

The search can be stopped early by returning false from the TIntObjectProcedure.execute(int, Object) method.

Parameters:

lowerExtreme - the lower extreme of the hyperrectangle

upperExtreme - the upper extreme of the hyperrectangle

proc - the processor

nearestNeighbours

public List<IntDoublePair> nearestNeighbours(double[] qu,
                                             int n)

Nearest-neighbour search

Parameters:

qu - the query point

n - the number of neighbours to find

Returns:

the indices and distances

nearestNeighbour

public IntDoublePair nearestNeighbour(double[] qu)

Nearest-neighbour search

Parameters:

qu - the query point

Returns:

the indices and distances

coordinateRadiusSearch

public double[][] coordinateRadiusSearch(double[] centre,
                                         double radius)

Find all the points within the given radius of the given point. Internally this works by finding the points in the hyper-square encompassing the hyper-circle and then filtering.

Parameters:

centre - the centre point

radius - the radius

Returns:

the points

coordinateRadiusSearch

public void coordinateRadiusSearch(double[] centre,
                                   double radius,
                                   gnu.trove.procedure.TObjectDoubleProcedure<double[]> proc)

Find all the points within the given radius of the given point. Internally this works by finding the points in the hyper-square encompassing the hyper-circle and then filtering. Each valid point that is found is reported to the given processor together with its distance from the centre.

The search can be stopped early by returning false from the TIntObjectProcedure.execute(int, Object) method.

Parameters:

centre - the centre point

radius - the radius

proc - the process

leafIndices

public List<int[]> leafIndices()

Find all the indices seperated by leaves

Returns:

all the leaves