org.openimaj.util.tree

Class IncrementalLongKDTree

java.lang.Object

org.openimaj.util.tree.IncrementalLongKDTree

public class IncrementalLongKDTree
extends Object

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

Method Summary

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

IncrementalLongKDTree

public IncrementalLongKDTree()

Create an empty KDTree object

IncrementalLongKDTree

public IncrementalLongKDTree(Collection<long[]> coords)

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

Parameters:

coords - the data to populate the index with.

IncrementalLongKDTree

public IncrementalLongKDTree(long[][] 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<long[]> coords)

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

Parameters:

coords - The points to add.

insertAll

public void insertAll(long[][] coords)

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

Parameters:

coords - The points to add.

insert

public void insert(long[] point)

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

Parameters:

point - Point to insert.

rangeSearch

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

findNearestNeighbour

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