OpenGP  1.1
Open Geometry Processing Library
Classes | Public Member Functions | Protected Types | Protected Attributes | List of all members
nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType > Class Template Reference

#include <nanoflann.hpp>

Classes

struct  BranchStruct
 

Public Member Functions

 KDTreeSingleIndexAdaptor (const int dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams &params=KDTreeSingleIndexAdaptorParams())
 
 ~KDTreeSingleIndexAdaptor ()
 
void freeIndex ()
 
void buildIndex ()
 
size_t size () const
 
size_t veclen () const
 
size_t usedMemory () const
 
void saveIndex (FILE *stream)
 
void loadIndex (FILE *stream)
 
Query methods
template<typename RESULTSET >
void findNeighbors (RESULTSET &result, const ElementType *vec, const SearchParams &searchParams) const
 
void knnSearch (const ElementType *query_point, const size_t num_closest, IndexType *out_indices, DistanceType *out_distances_sq, const int nChecks_IGNORED=10) const
 
size_t radiusSearch (const ElementType *query_point, const DistanceType radius, std::vector< std::pair< IndexType, DistanceType > > &IndicesDists, const SearchParams &searchParams) const
 

Protected Types

typedef array_or_vector_selector< DIM, Interval >::container_t BoundingBox
 
typedef array_or_vector_selector< DIM, DistanceType >::container_t distance_vector_t
 

Protected Attributes

std::vector< IndexType > vind
 
const DatasetAdaptor & dataset
 The source of our data. More...
 
int dim
 Dimensionality of each data point.
 
NodePtr root_node
 
PooledAllocator pool
 

Detailed Description

template<typename Distance, class DatasetAdaptor, int DIM = -1, typename IndexType = size_t>
class nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >

kd-tree index

Contains the k-d trees and other information for indexing a set of points for nearest-neighbor matching.

The class "DatasetAdaptor" must provide the following interface (can be non-virtual, inlined methods):

// Must return the number of data points
inline size_t kdtree_get_point_count() const { ... }
// Must return the Euclidean (L2) distance between the vector "p1[0:size-1]" and the data point with index "idx_p2" stored in the class:
inline DistanceType kdtree_distance(const T *p1, const size_t idx_p2,size_t size) const { ... }
// Must return the dim'th component of the idx'th point in the class:
inline T kdtree_get_pt(const size_t idx, int dim) const { ... }
// Optional bounding-box computation: return false to default to a standard bbox computation loop.
// Return true if the BBOX was already computed by the class and returned in "bb" so it can be avoided to redo it again.
// Look at bb.size() to find out the expected dimensionality (e.g. 2 or 3 for point clouds)
template <class BBOX>
bool kdtree_get_bbox(BBOX &bb) const
{
bb[0].low = ...; bb[0].high = ...; // 0th dimension limits
bb[1].low = ...; bb[1].high = ...; // 1st dimension limits
...
return true;
}
Template Parameters
IndexTypeWill be typically size_t or int

Member Typedef Documentation

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
typedef array_or_vector_selector<DIM,Interval>::container_t nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::BoundingBox
protected

Define "BoundingBox" as a fixed-size or variable-size container depending on "DIM"

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
typedef array_or_vector_selector<DIM,DistanceType>::container_t nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::distance_vector_t
protected

Define "distance_vector_t" as a fixed-size or variable-size container depending on "DIM"

Constructor & Destructor Documentation

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::KDTreeSingleIndexAdaptor ( const int  dimensionality,
const DatasetAdaptor &  inputData,
const KDTreeSingleIndexAdaptorParams params = KDTreeSingleIndexAdaptorParams() 
)
inline

KDTree constructor

Params: inputData = dataset with the input features params = parameters passed to the kdtree algorithm (see http://code.google.com/p/nanoflann/ for help choosing the parameters)

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::~KDTreeSingleIndexAdaptor ( )
inline

Standard destructor

Member Function Documentation

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::buildIndex ( )
inline

Builds the index

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
template<typename RESULTSET >
void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::findNeighbors ( RESULTSET &  result,
const ElementType *  vec,
const SearchParams searchParams 
) const
inline

Find set of nearest neighbors to vec[0:dim-1]. Their indices are stored inside the result object.

Params: result = the result object in which the indices of the nearest-neighbors are stored vec = the vector for which to search the nearest neighbors

Template Parameters
RESULTSETShould be any ResultSet<DistanceType>
See also
knnSearch, radiusSearch
template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::freeIndex ( )
inline

Frees the previously-built index. Automatically called within buildIndex().

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::knnSearch ( const ElementType *  query_point,
const size_t  num_closest,
IndexType *  out_indices,
DistanceType *  out_distances_sq,
const int  nChecks_IGNORED = 10 
) const
inline

Find the "num_closest" nearest neighbors to the query_point[0:dim-1]. Their indices are stored inside the result object.

See also
radiusSearch, findNeighbors
Note
nChecks_IGNORED is ignored but kept for compatibility with the original FLANN interface.
template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::loadIndex ( FILE *  stream)
inline

Loads a previous index from a binary file. IMPORTANT NOTE: The set of data points is NOT stored in the file, so the index object must be constructed associated to the same source of data points used while building the index. See the example: examples/saveload_example.cpp

See also
loadIndex
template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
size_t nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::radiusSearch ( const ElementType *  query_point,
const DistanceType  radius,
std::vector< std::pair< IndexType, DistanceType > > &  IndicesDists,
const SearchParams searchParams 
) const
inline

Find all the neighbors to query_point[0:dim-1] within a maximum radius. The output is given as a vector of pairs, of which the first element is a point index and the second the corresponding distance. Previous contents of IndicesDists are cleared.

If searchParams.sorted==true, the output list is sorted by ascending distances.

For a better performance, it is advisable to do a .reserve() on the vector if you have any wild guess about the number of expected matches.

See also
knnSearch, findNeighbors
Returns
The number of points within the given radius (i.e. indices.size() or dists.size() )
template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::saveIndex ( FILE *  stream)
inline

Stores the index in a binary file. IMPORTANT NOTE: The set of data points is NOT stored in the file, so when loading the index object it must be constructed associated to the same source of data points used while building it. See the example: examples/saveload_example.cpp

See also
loadIndex
template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
size_t nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::size ( ) const
inline

Returns size of index.

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
size_t nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::usedMemory ( ) const
inline

Computes the inde memory usage Returns: memory used by the index

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
size_t nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::veclen ( ) const
inline

Returns the length of an index feature.

Member Data Documentation

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
const DatasetAdaptor& nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::dataset
protected

The source of our data.

The dataset used by this index

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
PooledAllocator nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::pool
protected

Pooled memory allocator.

Using a pooled memory allocator is more efficient than allocating memory directly when there is a large number small of memory allocations.

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
NodePtr nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::root_node
protected

Array of k-d trees used to find neighbours.

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
std::vector<IndexType> nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::vind
protected

Array of indices to vectors in the dataset.


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