#include <nn_index.h>

Inheritance diagram for rtflann::NNIndex< Distance >:

Public Types
typedef Distance::ResultType	DistanceType
typedef Distance::ElementType	ElementType
Public Member Functions
virtual void	addPoints (const Matrix< ElementType > &points, float rebuild_threshold=2)
	Incrementally add points to the index.
virtual void	buildIndex ()
virtual void	buildIndex (const Matrix< ElementType > &dataset)
virtual NNIndex *	clone () const =0
virtual void	findNeighbors (ResultSet< DistanceType > &result, const ElementType *vec, const SearchParams &searchParams) const =0
IndexParams	getParameters () const
virtual ElementType *	getPoint (size_t id)
virtual int	knnSearch (const Matrix< ElementType > &queries, Matrix< size_t > &indices, Matrix< DistanceType > &dists, size_t knn, const SearchParams &params) const
	Perform k-nearest neighbor search.
int	knnSearch (const Matrix< ElementType > &queries, Matrix< int > &indices, Matrix< DistanceType > &dists, size_t knn, const SearchParams &params) const
int	knnSearch (const Matrix< ElementType > &queries, std::vector< std::vector< size_t > > &indices, std::vector< std::vector< DistanceType > > &dists, size_t knn, const SearchParams &params) const
	Perform k-nearest neighbor search.
int	knnSearch (const Matrix< ElementType > &queries, std::vector< std::vector< int > > &indices, std::vector< std::vector< DistanceType > > &dists, size_t knn, const SearchParams &params) const
	NNIndex (Distance d)
	NNIndex (const IndexParams &params, Distance d)
	NNIndex (const NNIndex &other)
int	radiusSearch (const Matrix< ElementType > &queries, Matrix< size_t > &indices, Matrix< DistanceType > &dists, float radius, const SearchParams &params) const
	Perform radius search.
int	radiusSearch (const Matrix< ElementType > &queries, Matrix< int > &indices, Matrix< DistanceType > &dists, float radius, const SearchParams &params) const
int	radiusSearch (const Matrix< ElementType > &queries, std::vector< std::vector< size_t > > &indices, std::vector< std::vector< DistanceType > > &dists, float radius, const SearchParams &params) const
	Perform radius search.
int	radiusSearch (const Matrix< ElementType > &queries, std::vector< std::vector< int > > &indices, std::vector< std::vector< DistanceType > > &dists, float radius, const SearchParams &params) const
size_t	removedCount () const
virtual void	removePoint (size_t id)
template<typename Archive >
void	serialize (Archive &ar)
size_t	size () const
size_t	sizeAtBuild () const
size_t	veclen () const
virtual	~NNIndex ()
Protected Member Functions
virtual void	buildIndexImpl ()=0
void	cleanRemovedPoints ()
void	extendDataset (const Matrix< ElementType > &new_points)
virtual void	freeIndex ()=0
size_t	id_to_index (size_t id)
void	indices_to_ids (const size_t in, size_t out, size_t size) const
void	setDataset (const Matrix< ElementType > &dataset)
void	swap (NNIndex &other)
Protected Attributes
ElementType *	data_ptr_
Distance	distance_
std::vector< size_t >	ids_
IndexParams	index_params_
size_t	last_id_
std::vector< ElementType * >	points_
bool	removed_
size_t	removed_count_
DynamicBitset	removed_points_
size_t	size_
size_t	size_at_build_
size_t	veclen_

Detailed Description

template<typename Distance>
class rtflann::NNIndex< Distance >

Nearest-neighbour index base class

Definition at line 73 of file nn_index.h.

Member Typedef Documentation

template<typename Distance>

typedef Distance::ResultType rtflann::NNIndex< Distance >::DistanceType

Reimplemented in rtflann::HierarchicalClusteringIndex< Distance >, rtflann::KMeansIndex< Distance >, rtflann::LshIndex< Distance >, rtflann::AutotunedIndex< Distance >, rtflann::KDTreeIndex< Distance >, rtflann::CompositeIndex< Distance >, rtflann::KDTreeSingleIndex< Distance >, and rtflann::LinearIndex< Distance >.

Definition at line 77 of file nn_index.h.

template<typename Distance>

typedef Distance::ElementType rtflann::NNIndex< Distance >::ElementType

Reimplemented in rtflann::HierarchicalClusteringIndex< Distance >, rtflann::KMeansIndex< Distance >, rtflann::LshIndex< Distance >, rtflann::AutotunedIndex< Distance >, rtflann::KDTreeIndex< Distance >, rtflann::CompositeIndex< Distance >, rtflann::KDTreeSingleIndex< Distance >, and rtflann::LinearIndex< Distance >.

Definition at line 76 of file nn_index.h.

Constructor & Destructor Documentation

template<typename Distance>

rtflann::NNIndex< Distance >::NNIndex ( Distance d ) [inline]

Definition at line 79 of file nn_index.h.

template<typename Distance>

rtflann::NNIndex< Distance >::NNIndex	(	const IndexParams &	params,
		Distance	d
	)		`[inline]`

Definition at line 84 of file nn_index.h.

template<typename Distance>

rtflann::NNIndex< Distance >::NNIndex ( const NNIndex< Distance > & other ) [inline]

Definition at line 89 of file nn_index.h.

template<typename Distance>

virtual rtflann::NNIndex< Distance >::~NNIndex ( ) [inline, virtual]

Definition at line 112 of file nn_index.h.

Member Function Documentation

template<typename Distance>

virtual void rtflann::NNIndex< Distance >::addPoints	(	const Matrix< ElementType > &	points,
		float	rebuild_threshold = `2`
	)		`[inline, virtual]`

Incrementally add points to the index.

Parameters:

points	Matrix with points to be added
rebuild_threshold

Reimplemented in rtflann::KMeansIndex< Distance >, rtflann::HierarchicalClusteringIndex< Distance >, rtflann::CompositeIndex< Distance >, rtflann::AutotunedIndex< Distance >, rtflann::LshIndex< Distance >, rtflann::KDTreeSingleIndex< Distance >, rtflann::KDTreeIndex< Distance >, and rtflann::LinearIndex< Distance >.

Definition at line 152 of file nn_index.h.

template<typename Distance>

virtual void rtflann::NNIndex< Distance >::buildIndex ( ) [inline, virtual]

Builds the index

Reimplemented in rtflann::CompositeIndex< Distance >, and rtflann::AutotunedIndex< Distance >.

Definition at line 125 of file nn_index.h.

template<typename Distance>

virtual void rtflann::NNIndex< Distance >::buildIndex ( const Matrix< ElementType > & dataset ) [inline, virtual]

Builds the index using the specified dataset

Parameters:

dataset the dataset to use

Reimplemented in rtflann::AutotunedIndex< Distance >.

Definition at line 141 of file nn_index.h.

template<typename Distance>

virtual void rtflann::NNIndex< Distance >::buildIndexImpl ( ) [protected, pure virtual]

Implemented in rtflann::LshIndex< Distance >, rtflann::AutotunedIndex< Distance >, rtflann::KMeansIndex< Distance >, rtflann::HierarchicalClusteringIndex< Distance >, rtflann::KDTreeIndex< Distance >, rtflann::KDTreeSingleIndex< Distance >, rtflann::CompositeIndex< Distance >, and rtflann::LinearIndex< Distance >.

template<typename Distance>

void rtflann::NNIndex< Distance >::cleanRemovedPoints ( ) [inline, protected]

Definition at line 792 of file nn_index.h.

template<typename Distance>

virtual NNIndex* rtflann::NNIndex< Distance >::clone ( ) const [pure virtual]

Implemented in rtflann::HierarchicalClusteringIndex< Distance >, rtflann::KMeansIndex< Distance >, rtflann::LshIndex< Distance >, rtflann::KDTreeSingleIndex< Distance >, rtflann::KDTreeIndex< Distance >, rtflann::AutotunedIndex< Distance >, rtflann::CompositeIndex< Distance >, and rtflann::LinearIndex< Distance >.

template<typename Distance>

void rtflann::NNIndex< Distance >::extendDataset ( const Matrix< ElementType > & new_points ) [inline, protected]

Definition at line 773 of file nn_index.h.

template<typename Distance>

virtual void rtflann::NNIndex< Distance >::findNeighbors	(	ResultSet< DistanceType > &	result,
		const ElementType *	vec,
		const SearchParams &	searchParams
	)		const `[pure virtual]`

Implemented in rtflann::LshIndex< Distance >, rtflann::AutotunedIndex< Distance >, rtflann::HierarchicalClusteringIndex< Distance >, rtflann::KMeansIndex< Distance >, rtflann::KDTreeIndex< Distance >, rtflann::KDTreeSingleIndex< Distance >, rtflann::CompositeIndex< Distance >, and rtflann::LinearIndex< Distance >.

template<typename Distance>

virtual void rtflann::NNIndex< Distance >::freeIndex ( ) [protected, pure virtual]

Implemented in rtflann::KMeansIndex< Distance >, rtflann::HierarchicalClusteringIndex< Distance >, rtflann::LshIndex< Distance >, rtflann::AutotunedIndex< Distance >, rtflann::KDTreeSingleIndex< Distance >, rtflann::KDTreeIndex< Distance >, rtflann::CompositeIndex< Distance >, and rtflann::LinearIndex< Distance >.

template<typename Distance>

IndexParams rtflann::NNIndex< Distance >::getParameters ( ) const [inline, virtual]

Returns the parameters used by the index.

Returns:: The index parameters

Implements rtflann::IndexBase.

Reimplemented in rtflann::AutotunedIndex< Distance >.

Definition at line 229 of file nn_index.h.

template<typename Distance>

virtual ElementType* rtflann::NNIndex< Distance >::getPoint ( size_t id ) [inline, virtual]

Get point with specific id

Parameters:

id

Returns:

Definition at line 187 of file nn_index.h.

template<typename Distance>

size_t rtflann::NNIndex< Distance >::id_to_index ( size_t id ) [inline, protected]

Definition at line 715 of file nn_index.h.

template<typename Distance>

void rtflann::NNIndex< Distance >::indices_to_ids	(	const size_t *	in,
		size_t *	out,
		size_t	size
	)		const `[inline, protected]`

Definition at line 747 of file nn_index.h.

template<typename Distance>

virtual int rtflann::NNIndex< Distance >::knnSearch	(	const Matrix< ElementType > &	queries,
		Matrix< size_t > &	indices,
		Matrix< DistanceType > &	dists,
		size_t	knn,
		const SearchParams &	params
	)		const `[inline, virtual]`

Perform k-nearest neighbor search.

Parameters:

[in]	queries	The query points for which to find the nearest neighbors
[out]	indices	The indices of the nearest neighbors found
[out]	dists	Distances to the nearest neighbors found
[in]	knn	Number of nearest neighbors to return
[in]	params	Search parameters

Reimplemented in rtflann::AutotunedIndex< Distance >, and rtflann::LshIndex< Distance >.

Definition at line 315 of file nn_index.h.

template<typename Distance>

int rtflann::NNIndex< Distance >::knnSearch	(	const Matrix< ElementType > &	queries,
		Matrix< int > &	indices,
		Matrix< DistanceType > &	dists,
		size_t	knn,
		const SearchParams &	params
	)		const `[inline]`

Parameters:

queries
indices
dists
knn
params

Returns:

Definition at line 378 of file nn_index.h.

template<typename Distance>

int rtflann::NNIndex< Distance >::knnSearch	(	const Matrix< ElementType > &	queries,
		std::vector< std::vector< size_t > > &	indices,
		std::vector< std::vector< DistanceType > > &	dists,
		size_t	knn,
		const SearchParams &	params
	)		const `[inline]`

Perform k-nearest neighbor search.

Parameters:

[in]	queries	The query points for which to find the nearest neighbors
[out]	indices	The indices of the nearest neighbors found
[out]	dists	Distances to the nearest neighbors found
[in]	knn	Number of nearest neighbors to return
[in]	params	Search parameters

Reimplemented in rtflann::LshIndex< Distance >, and rtflann::AutotunedIndex< Distance >.

Definition at line 405 of file nn_index.h.

template<typename Distance>

int rtflann::NNIndex< Distance >::knnSearch	(	const Matrix< ElementType > &	queries,
		std::vector< std::vector< int > > &	indices,
		std::vector< std::vector< DistanceType > > &	dists,
		size_t	knn,
		const SearchParams &	params
	)		const `[inline]`

Parameters:

queries
indices
dists
knn
params

Returns:

Definition at line 476 of file nn_index.h.

template<typename Distance>

int rtflann::NNIndex< Distance >::radiusSearch	(	const Matrix< ElementType > &	queries,
		Matrix< size_t > &	indices,
		Matrix< DistanceType > &	dists,
		float	radius,
		const SearchParams &	params
	)		const `[inline]`

Perform radius search.

Parameters:

[in]	query	The query point
[out]	indices	The indices of the neighbors found within the given radius
[out]	dists	The distances to the nearest neighbors found
[in]	radius	The radius used for search
[in]	params	Search parameters

Returns:: Number of neighbors found

Definition at line 501 of file nn_index.h.

template<typename Distance>

int rtflann::NNIndex< Distance >::radiusSearch	(	const Matrix< ElementType > &	queries,
		Matrix< int > &	indices,
		Matrix< DistanceType > &	dists,
		float	radius,
		const SearchParams &	params
	)		const `[inline]`

Parameters:

queries
indices
dists
radius
params

Returns:

Definition at line 584 of file nn_index.h.

template<typename Distance>

int rtflann::NNIndex< Distance >::radiusSearch	(	const Matrix< ElementType > &	queries,
		std::vector< std::vector< size_t > > &	indices,
		std::vector< std::vector< DistanceType > > &	dists,
		float	radius,
		const SearchParams &	params
	)		const `[inline]`

Perform radius search.

Parameters:

[in]	query	The query point
[out]	indices	The indices of the neighbors found within the given radius
[out]	dists	The distances to the nearest neighbors found
[in]	radius	The radius used for search
[in]	params	Search parameters

Returns:: Number of neighbors found

Definition at line 611 of file nn_index.h.

template<typename Distance>

int rtflann::NNIndex< Distance >::radiusSearch	(	const Matrix< ElementType > &	queries,
		std::vector< std::vector< int > > &	indices,
		std::vector< std::vector< DistanceType > > &	dists,
		float	radius,
		const SearchParams &	params
	)		const `[inline]`

Parameters:

queries
indices
dists
radius
params

Returns:

Definition at line 690 of file nn_index.h.

template<typename Distance>

size_t rtflann::NNIndex< Distance >::removedCount ( ) const [inline]

Definition at line 206 of file nn_index.h.

template<typename Distance>

virtual void rtflann::NNIndex< Distance >::removePoint ( size_t id ) [inline, virtual]

Remove point from the index

Parameters:

index Index of point to be removed

Reimplemented in rtflann::CompositeIndex< Distance >, and rtflann::AutotunedIndex< Distance >.

Definition at line 161 of file nn_index.h.

template<typename Distance>

template<typename Archive >

void rtflann::NNIndex< Distance >::serialize ( Archive & ar ) [inline]

Reimplemented in rtflann::HierarchicalClusteringIndex< Distance >, rtflann::KMeansIndex< Distance >, rtflann::AutotunedIndex< Distance >, rtflann::LshIndex< Distance >, rtflann::KDTreeIndex< Distance >, rtflann::KDTreeSingleIndex< Distance >, and rtflann::LinearIndex< Distance >.

Definition at line 236 of file nn_index.h.

template<typename Distance>

void rtflann::NNIndex< Distance >::setDataset ( const Matrix< ElementType > & dataset ) [inline, protected]

Definition at line 756 of file nn_index.h.

template<typename Distance>

size_t rtflann::NNIndex< Distance >::size ( ) const [inline, virtual]

Returns:: number of features in this index.

Implements rtflann::IndexBase.

Reimplemented in rtflann::AutotunedIndex< Distance >, and rtflann::CompositeIndex< Distance >.

Definition at line 201 of file nn_index.h.

template<typename Distance>

size_t rtflann::NNIndex< Distance >::sizeAtBuild ( ) const [inline]

Definition at line 211 of file nn_index.h.

template<typename Distance>

void rtflann::NNIndex< Distance >::swap ( NNIndex< Distance > & other ) [inline, protected]

Definition at line 812 of file nn_index.h.

template<typename Distance>

size_t rtflann::NNIndex< Distance >::veclen ( ) const [inline, virtual]

Returns:: The dimensionality of the features in this index.

Implements rtflann::IndexBase.

Reimplemented in rtflann::AutotunedIndex< Distance >, and rtflann::CompositeIndex< Distance >.

Definition at line 219 of file nn_index.h.

Member Data Documentation

template<typename Distance>

ElementType* rtflann::NNIndex< Distance >::data_ptr_ [protected]

Pointer to dataset memory if allocated by this index, otherwise NULL

Definition at line 891 of file nn_index.h.

template<typename Distance>

Distance rtflann::NNIndex< Distance >::distance_ [protected]

The distance functor

Definition at line 833 of file nn_index.h.

template<typename Distance>

std::vector<size_t> rtflann::NNIndex< Distance >::ids_ [protected]

Array of point IDs, returned by nearest-neighbour operations

Definition at line 881 of file nn_index.h.

template<typename Distance>

IndexParams rtflann::NNIndex< Distance >::index_params_ [protected]

Parameters of the index.

Definition at line 861 of file nn_index.h.

template<typename Distance>

size_t rtflann::NNIndex< Distance >::last_id_ [protected]

Each index point has an associated ID. IDs are assigned sequentially in increasing order. This indicates the ID assigned to the last point added to the index.

Definition at line 841 of file nn_index.h.

template<typename Distance>

std::vector<ElementType*> rtflann::NNIndex< Distance >::points_ [protected]

Point data

Definition at line 886 of file nn_index.h.

template<typename Distance>

bool rtflann::NNIndex< Distance >::removed_ [protected]

Flag indicating if at least a point was removed from the index

Definition at line 866 of file nn_index.h.

template<typename Distance>

size_t rtflann::NNIndex< Distance >::removed_count_ [protected]

Number of points removed from the index

Definition at line 876 of file nn_index.h.

template<typename Distance>

DynamicBitset rtflann::NNIndex< Distance >::removed_points_ [protected]

Array used to mark points removed from the index

Definition at line 871 of file nn_index.h.

template<typename Distance>

size_t rtflann::NNIndex< Distance >::size_ [protected]

Number of points in the index (and database)

Definition at line 846 of file nn_index.h.

template<typename Distance>

size_t rtflann::NNIndex< Distance >::size_at_build_ [protected]

Number of features in the dataset when the index was last built.

Definition at line 851 of file nn_index.h.

template<typename Distance>

size_t rtflann::NNIndex< Distance >::veclen_ [protected]

Size of one point in the index (and database)

Definition at line 856 of file nn_index.h.

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

nn_index.h

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

template<typename Distance> class rtflann::NNIndex< Distance >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename Distance>
class rtflann::NNIndex< Distance >