#include <nanoflann.hpp>
Public Types | |
typedef Distance::ElementType | ElementType |
typedef Distance::DistanceType | DistanceType |
typedef nanoflann::KDTreeBaseClass < nanoflann::KDTreeSingleIndexAdaptor < Distance, DatasetAdaptor, DIM, IndexType >, Distance, DatasetAdaptor, DIM, IndexType > ::Node | Node |
typedef Node * | NodePtr |
typedef nanoflann::KDTreeBaseClass < nanoflann::KDTreeSingleIndexAdaptor < Distance, DatasetAdaptor, DIM, IndexType >, Distance, DatasetAdaptor, DIM, IndexType > ::Interval | Interval |
typedef nanoflann::KDTreeBaseClass < nanoflann::KDTreeSingleIndexAdaptor < Distance, DatasetAdaptor, DIM, IndexType >, Distance, DatasetAdaptor, DIM, IndexType > ::BoundingBox | BoundingBox |
typedef nanoflann::KDTreeBaseClass < nanoflann::KDTreeSingleIndexAdaptor < Distance, DatasetAdaptor, DIM, IndexType >, Distance, DatasetAdaptor, DIM, IndexType > ::distance_vector_t | distance_vector_t |
Public Member Functions | |
KDTreeSingleIndexAdaptor (const int dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams ¶ms=KDTreeSingleIndexAdaptorParams()) | |
~KDTreeSingleIndexAdaptor () | |
void | buildIndex () |
void | init_vind () |
ElementType | dataset_get (size_t idx, int component) const |
Helper accessor to the dataset points: | |
void | save_tree (FILE *stream, NodePtr tree) |
void | load_tree (FILE *stream, NodePtr &tree) |
void | computeBoundingBox (BoundingBox &bbox) |
template<class RESULTSET > | |
bool | searchLevel (RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindistsq, distance_vector_t &dists, const float epsError) const |
void | saveIndex (FILE *stream) |
void | loadIndex (FILE *stream) |
Query methods | |
template<typename RESULTSET > | |
bool | findNeighbors (RESULTSET &result, const ElementType *vec, const SearchParams &searchParams) const |
size_t | knnSearch (const ElementType *query_point, const size_t num_closest, IndexType *out_indices, DistanceType *out_distances_sq, const int=10) const |
size_t | radiusSearch (const ElementType *query_point, const DistanceType &radius, std::vector< std::pair< IndexType, DistanceType > > &IndicesDists, const SearchParams &searchParams) const |
template<class SEARCH_CALLBACK > | |
size_t | radiusSearchCustomCallback (const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParams &searchParams=SearchParams()) const |
Public Member Functions inherited from nanoflann::KDTreeBaseClass< KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >, Distance, DatasetAdaptor, DIM, IndexType > | |
void | freeIndex (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType > &obj) |
Public Attributes | |
std::vector< IndexType > | vind |
size_t | m_leaf_max_size |
const DatasetAdaptor & | dataset |
The source of our data. More... | |
const KDTreeSingleIndexAdaptorParams | index_params |
size_t | m_size |
Number of current points in the dataset. | |
size_t | m_size_at_index_build |
Number of points in the dataset when the index was built. | |
int | dim |
Dimensionality of each data point. | |
NodePtr | root_node |
BoundingBox | root_bbox |
PooledAllocator | pool |
Distance | distance |
Additional Inherited Members | |
Protected Types inherited from nanoflann::KDTreeBaseClass< KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >, Distance, DatasetAdaptor, DIM, IndexType > | |
typedef Distance::ElementType | ElementType |
typedef Distance::DistanceType | DistanceType |
typedef Node * | NodePtr |
typedef array_or_vector_selector< DIM, Interval >::container_t | BoundingBox |
typedef array_or_vector_selector< DIM, DistanceType >::container_t | distance_vector_t |
Protected Member Functions inherited from nanoflann::KDTreeBaseClass< KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >, Distance, DatasetAdaptor, DIM, IndexType > | |
size_t | size (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType > &obj) const |
size_t | veclen (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType > &obj) |
size_t | usedMemory (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType > &obj) |
void | computeMinMax (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType > &obj, IndexType *ind, IndexType count, int element, ElementType &min_elem, ElementType &max_elem) |
NodePtr | divideTree (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType > &obj, const IndexType left, const IndexType right, BoundingBox &bbox) |
void | middleSplit_ (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType > &obj, IndexType *ind, IndexType count, IndexType &index, int &cutfeat, DistanceType &cutval, const BoundingBox &bbox) |
void | planeSplit (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType > &obj, IndexType *ind, const IndexType count, int cutfeat, DistanceType &cutval, IndexType &lim1, IndexType &lim2) |
DistanceType | computeInitialDistances (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType > &obj, const ElementType *vec, distance_vector_t &dists) const |
kd-tree static 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):
DatasetAdaptor | The user-provided adaptor (see comments above). |
Distance | The distance metric to use: nanoflann::metric_L1, nanoflann::metric_L2, nanoflann::metric_L2_Simple, etc. |
DIM | Dimensionality of data points (e.g. 3 for 3D points) |
IndexType | Will be typically size_t or int |
typedef nanoflann::KDTreeBaseClass<nanoflann::KDTreeSingleIndexAdaptor<Distance, DatasetAdaptor, DIM, IndexType>, Distance, DatasetAdaptor, DIM, IndexType>::BoundingBox nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::BoundingBox |
Define "BoundingBox" as a fixed-size or variable-size container depending on "DIM"
typedef nanoflann::KDTreeBaseClass<nanoflann::KDTreeSingleIndexAdaptor<Distance, DatasetAdaptor, DIM, IndexType>, Distance, DatasetAdaptor, DIM, IndexType>::distance_vector_t nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::distance_vector_t |
Define "distance_vector_t" as a fixed-size or variable-size container depending on "DIM"
|
inline |
KDTree constructor
Refer to docs in README.md or online in https://github.com/jlblancoc/nanoflann
The KD-Tree point dimension (the length of each point in the datase, e.g. 3 for 3D points) is determined by means of:
inputData | Dataset with the input features |
params | Basically, the maximum leaf node size |
|
inline |
Standard destructor
|
inline |
Builds the index
|
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
RESULTSET | Should be any ResultSet<DistanceType> |
|
inline |
Make sure the auxiliary list vind has the same size than the current dataset, and re-generate if size has changed.
|
inline |
Find the "num_closest" nearest neighbors to the query_point[0:dim-1]. Their indices are stored inside the result object.
N
of valid points in the result set. Only the first N
entries in out_indices
and out_distances_sq
will be valid. Return may be less than num_closest
only if the number of elements in the tree is less than num_closest
.
|
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
|
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.
|
inline |
Just like radiusSearch() but with a custom callback class for each point found in the radius of the query. See the source of RadiusResultSet<> as a start point for your own classes.
|
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
|
inline |
Performs an exact search in the tree starting from a node.
RESULTSET | Should be any ResultSet<DistanceType> |
const DatasetAdaptor& nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::dataset |
The source of our data.
The dataset used by this index
PooledAllocator nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::pool |
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.
NodePtr nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::root_node |
The KD-tree used to find neighbours
std::vector<IndexType> nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::vind |
Array of indices to vectors in the dataset.