org.tinfour.utils

Class NearestNeighborPointCollector

java.lang.Object

org.tinfour.utils.NearestNeighborPointCollector

public class NearestNeighborPointCollector
extends Object

Provides a utility for the efficient identification of the K-nearest points to a specified set of query coordinates. This utility works by creating a grid of bins into which the vertices are initially separated. The bins are then searched to find the nearest vertices.

This class is intended to support testing and verification. It has no direct relationship with any of the graph-based structures produced by the Tinfour library.

The design of this class is optimized for repeated searches of very large vertex sets. While the up front processing is not trivial, the time cost is compensated for by more efficient processing across multiple searches.

Constructor Summary

Constructors

Constructor and Description
NearestNeighborPointCollector(List<Vertex> vList, boolean mergeDuplicates) Construct a collector based on the specified list of vertices and bounds.

Method Summary

Modifier and Type	Method and Description
int	getNearestNeighbors(double x, double y, int k, double[] d, Vertex[] v) Get the K nearest neighbors from the collection.
List<Vertex>	getVertices() Gets a list of the vertices currently stored in the collection.
void	setResolutionRule(VertexMergerGroup.ResolutionRule rule) Sets the rule for resolving coincident vertices; recalculates value for vertices in the collection, if necessary

Methods inherited from class java.lang.Object

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

Constructor Detail

NearestNeighborPointCollector

public NearestNeighborPointCollector(List<Vertex> vList,
                                     boolean mergeDuplicates)

Construct a collector based on the specified list of vertices and bounds. It is assumed that the coordinates and values of all specifications are valid floating-point values (no NaN's included).

Parameters:

vList - a list of valid vertices

mergeDuplicates - indicates whether duplicates should be merged.

Method Detail

setResolutionRule

public void setResolutionRule(VertexMergerGroup.ResolutionRule rule)

Sets the rule for resolving coincident vertices; recalculates value for vertices in the collection, if necessary

Parameters:

rule - a valid member of the enumeration

getNearestNeighbors

public int getNearestNeighbors(double x,
                               double y,
                               int k,
                               double[] d,
                               Vertex[] v)

Get the K nearest neighbors from the collection. The

Parameters:

x - the x coordinate of the search position

y - the y coordinate of the search position

k - the target number of vertices to be collected

d - storage for the distances to the vertices to be collected (must be dimensioned at least to size k, but can be larger)

v - storage for the vertices to be collected (must be dimensioned at least to size k, but can be larger)

Returns:

the number of neighboring vertices identified.

getVertices

public List<Vertex> getVertices()

Gets a list of the vertices currently stored in the collection. The result may be slightly smaller than the original input if merge rules were in effect and causes some co-located vertices to be merged.

Returns:

a valid list.