org.openimaj.knn

Class CoordinateKDTree<T extends Coordinate>

java.lang.Object

org.openimaj.knn.CoordinateKDTree<T>

Type Parameters:

T - the type of Coordinate.

All Implemented Interfaces:

CoordinateIndex<T>

public class CoordinateKDTree<T extends Coordinate>
extends Object
implements CoordinateIndex<T>

Implementation of a simple KDTree with range search. 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
CoordinateKDTree() Create an empty KDTree object
CoordinateKDTree(Collection<T> coords) Create a KDTree object and populate it with the given data.

Method Summary

Modifier and Type	Method and Description
protected static float	distance(Coordinate a, Coordinate b)
void	fastKNN(Collection<T> result, Coordinate query, int k) Faster implementation of K-nearest-neighbours.
void	insert(T point) Inserts a point into the tree, preserving the spatial ordering.
void	insertAll(Collection<T> coords) Insert all the points from the given collection into the index.
void	kNearestNeighbour(Collection<T> result, Coordinate query, int k) Find the k nearest neighbour points in the index to the query coordinate.
T	nearestNeighbour(Coordinate query) Find the nearest neighbour.
void	rangeSearch(Collection<T> results, Coordinate lowerExtreme, Coordinate upperExtreme) Searches the tree for all points contained within a given k-dimensional bounding box and stores them in a Collection.

Methods inherited from class java.lang.Object

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

Constructor Detail

CoordinateKDTree

public CoordinateKDTree()

Create an empty KDTree object

CoordinateKDTree

public CoordinateKDTree(Collection<T> 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<T> coords)

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

Parameters:

coords - The points to add.

insert

public void insert(T point)

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

Specified by:

insert in interface CoordinateIndex<T extends Coordinate>

Parameters:

point - Point to insert.

rangeSearch

public void rangeSearch(Collection<T> results,
                        Coordinate lowerExtreme,
                        Coordinate upperExtreme)

Searches the tree for all points contained within a given k-dimensional bounding box and stores them in a Collection.

Specified by:

rangeSearch in interface CoordinateIndex<T extends Coordinate>

Parameters:

results -

lowerExtreme -

upperExtreme -

distance

protected static final float distance(Coordinate a,
                                      Coordinate b)

nearestNeighbour

public T nearestNeighbour(Coordinate 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.

Specified by:

nearestNeighbour in interface CoordinateIndex<T extends Coordinate>

Parameters:

query - query coordinate

Returns:

nearest neighbour

kNearestNeighbour

public void kNearestNeighbour(Collection<T> result,
                              Coordinate query,
                              int k)

Description copied from interface: CoordinateIndex

Find the k nearest neighbour points in the index to the query coordinate. Store found coordinates in the results collection.

Specified by:

kNearestNeighbour in interface CoordinateIndex<T extends Coordinate>

Parameters:

result - Collection to hold the found coordinates.

query - The query coordinate.

k - The number of neighbours to find.

fastKNN

public void fastKNN(Collection<T> result,
                    Coordinate query,
                    int k)

Faster implementation of K-nearest-neighbours.

Parameters:

result - Collection to hold the found coordinates.

query - The query coordinate.

k - The number of neighbours to find.