org.ddogleg.nn

Interface NearestNeighbor<D>

All Known Implementing Classes:

KdForestBbfSearch, KdTreeNearestNeighbor, VpTree, WrapExhaustiveNeighbor

public interface NearestNeighbor<D>

Abstract interface for finding the nearest neighbor to a user specified point inside of a set of points in K-dimensional space. Solution can be exact or approximate, depending on the implementation. The distance metric is intentionally left undefined and is implementation dependent.

WARNING: Do not modify the input lists until after the NN search is no longer needed. If the input lists do need to be modified, then pass in a copy instead. This restriction reduced memory overhead significantly.

Method Summary

Modifier and Type	Method and Description
void	findNearest(double[] point, double maxDistance, int numNeighbors, FastQueue<NnData<D>> result) Searches for the N nearest neighbor to the specified point.
boolean	findNearest(double[] point, double maxDistance, NnData<D> result) Searches for the nearest neighbor to the specified point.
void	init(int pointDimension) Initializes data structures.
void	setPoints(java.util.List<double[]> points, java.util.List<D> data) Specifies the set of points which are to be searched.

Method Detail

init

void init(int pointDimension)

Initializes data structures.

Parameters:

pointDimension - Dimension of input data

setPoints

void setPoints(java.util.List<double[]> points,
               java.util.List<D> data)

Specifies the set of points which are to be searched.

Parameters:

points - Set of points.

data - (Optional) Associated data. Can be null.

findNearest

boolean findNearest(double[] point,
                    double maxDistance,
                    NnData<D> result)

Searches for the nearest neighbor to the specified point. The neighbor must be within maxDistance.

NOTE: How distance is measured is not specified here. See the implementation's documentation. Euclidean distance squared is common.

Parameters:

point - A point being searched for.

maxDistance - Maximum distance (inclusive, e.g. d ≤ maxDistance) a neighbor can be from point. Values < 0 will be set to the maximum distance.

result - Storage for the result.

Returns:

true if a match within the max distance was found.

findNearest

void findNearest(double[] point,
                 double maxDistance,
                 int numNeighbors,
                 FastQueue<NnData<D>> result)

Searches for the N nearest neighbor to the specified point. The neighbors must be within maxDistance.

NOTE: How distance is measured is not specified here. See the implementation's documentation. Euclidean distance squared is common.

Parameters:

point - A point being searched for.

maxDistance - Maximum distance (inclusive, e.g. d ≤ maxDistance) the neighbor can be from point. Values < 0 will be set to the maximum distance.

numNeighbors - The number of neighbors it will search for.

result - Storage for the result. Must be empty before calling. Must support grow() function.