org.openimaj.util.tree

Class IncrementalIntKDTree

java.lang.Object

org.openimaj.util.tree.IncrementalIntKDTree

public class IncrementalIntKDTree
extends Object

Implementation of a simple incremental KDTree for int[]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
IncrementalIntKDTree() Create an empty KDTree object
IncrementalIntKDTree(Collection<int[]> coords) Create a KDTree object and populate it with the given data.
IncrementalIntKDTree(int[][] coords) Create a KDTree object and populate it with the given data.

Method Summary

Modifier and Type	Method and Description
protected static double	distance(int[] a, int[] b)
ObjectDoublePair<int[]>	findNearestNeighbour(int[] query) Find the nearest neighbour.
List<ObjectDoublePair<int[]>>	findNearestNeighbours(int[] query, int k) Find the K nearest neighbours.
void	insert(int[] point) Inserts a point into the tree, preserving the spatial ordering.
void	insertAll(Collection<int[]> coords) Insert all the points from the given collection into the index.
void	insertAll(int[][] coords) Insert all the points from the given collection into the index.
List<ObjectDoublePair<int[]>>	radiusDistanceSearch(int[] centre, int radius) Find all the points within the given radius of the given point.
List<int[]>	radiusSearch(int[] centre, int radius) Find all the points within the given radius of the given point
List<int[]>	rangeSearch(int[] lowerExtreme, int[] 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

IncrementalIntKDTree

public IncrementalIntKDTree()

Create an empty KDTree object

IncrementalIntKDTree

public IncrementalIntKDTree(Collection<int[]> coords)

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

Parameters:

coords - the data to populate the index with.

IncrementalIntKDTree

public IncrementalIntKDTree(int[][] 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<int[]> coords)

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

Parameters:

coords - The points to add.

insertAll

public void insertAll(int[][] coords)

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

Parameters:

coords - The points to add.

insert

public void insert(int[] point)

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

Parameters:

point - Point to insert.

rangeSearch

public List<int[]> rangeSearch(int[] lowerExtreme,
                               int[] 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(int[] a,
                                       int[] b)

findNearestNeighbour

public ObjectDoublePair<int[]> findNearestNeighbour(int[] 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<int[]>> findNearestNeighbours(int[] 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<int[]> radiusSearch(int[] centre,
                                int 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<int[]>> radiusDistanceSearch(int[] centre,
                                                          int 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