shark::IterativeNNQuery< DataContainer > Class Template Reference

Iterative nearest neighbors query. More...

#include <shark/Algorithms/NearestNeighbors/TreeNearestNeighbors.h>

Public Member Functions

 IterativeNNQuery (tree_type const *tree, DataContainer const &data, value_type const &point)
 ~IterativeNNQuery ()
 destroy the query object and its internal data structures More...
std::size_t neighbors () const
 return the number of neighbors already found More...
result_type next ()
 find and return the next nearest neighbor More...
std::size_t queuesize () const

Detailed Description

template<class DataContainer>
class shark::IterativeNNQuery< DataContainer >

Iterative nearest neighbors query.

The IterativeNNQuery class (Iterative Nearest Neighbor Query) allows the nearest neighbors of a reference point to be queried iteratively. Given the reference point, a query is set up that returns the nearest neighbor first, then the second nearest neighbor, and so on. Thus, nearest neighbor queries are treated in an "online" fashion. The algorithm follows the paper (generalized to arbitrary space-partitioning trees):
Strategies for efficient incremental nearest neighbor search. A. J. Broder. Pattern Recognition 23(1/2), pp 171-178, 1990.
The algorithm is based on traversing a BinaryTree that partitions the space into nested cells. The triangle inequality is applied to exclude cells from the search. Furthermore, candidate points are cached in a queue, such that subsequent queries profit from points that could not be excluded this way, but that did not turn out the be the (current) nearest neighbor.
The tree must have a bucket size of one, but leaf nodes with multiple copies of the same point are allowed. This means that the space partitioning must be carried out to the finest possible scale.

The Data must be sotred in a random access container. This means that elements have O(1) access time. This is crucial for the performance of the tree lookup. When data is stored in a Data<T>, a View should be chosen as template parameter.

Definition at line 82 of file TreeNearestNeighbors.h.

Constructor & Destructor Documentation

◆ IterativeNNQuery()

template<class DataContainer>
shark::IterativeNNQuery< DataContainer >::IterativeNNQuery ( tree_type const *  tree,
DataContainer const &  data,
value_type const &  point 

create a new query

treeUnderlying space-partitioning tree (this is assumed to persist for the lifetime of the query object).
dataContainer holding the stored data which is referenced by the tree
pointPoint whose nearest neighbors are to be found.

Definition at line 94 of file TreeNearestNeighbors.h.

References shark::BinaryTree< InputT >::hasChildren(), shark::BinaryTree< InputT >::isLeft(), shark::BinaryTree< InputT >::left(), and shark::BinaryTree< InputT >::right().

◆ ~IterativeNNQuery()

template<class DataContainer>
shark::IterativeNNQuery< DataContainer >::~IterativeNNQuery ( )

destroy the query object and its internal data structures

Definition at line 122 of file TreeNearestNeighbors.h.

Member Function Documentation

◆ neighbors()

template<class DataContainer>
std::size_t shark::IterativeNNQuery< DataContainer >::neighbors ( ) const

return the number of neighbors already found

Definition at line 129 of file TreeNearestNeighbors.h.

◆ next()

template<class DataContainer>
result_type shark::IterativeNNQuery< DataContainer >::next ( )

find and return the next nearest neighbor

Definition at line 134 of file TreeNearestNeighbors.h.


◆ queuesize()

template<class DataContainer>
std::size_t shark::IterativeNNQuery< DataContainer >::queuesize ( ) const

The documentation for this class was generated from the following file: