#include <nanoflann.hpp>
Public Types | |
typedef nanoflann::KDTreeBaseClass< nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >, Distance, DatasetAdaptor, DIM, IndexType > | BaseClassRef |
typedef BaseClassRef::BoundingBox | BoundingBox |
typedef BaseClassRef::distance_vector_t | distance_vector_t |
typedef BaseClassRef::DistanceType | DistanceType |
typedef BaseClassRef::ElementType | ElementType |
typedef BaseClassRef::Interval | Interval |
typedef BaseClassRef::Node | Node |
typedef Node * | NodePtr |
Public Types inherited from nanoflann::KDTreeBaseClass< KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, size_t >, Distance, DatasetAdaptor, -1, size_t > | |
typedef array_or_vector_selector< DIM, Interval >::container_t | BoundingBox |
typedef array_or_vector_selector< DIM, DistanceType >::container_t | distance_vector_t |
typedef Distance::DistanceType | DistanceType |
typedef Distance::ElementType | ElementType |
typedef Node * | NodePtr |
Public Member Functions | |
void | buildIndex () |
void | computeBoundingBox (BoundingBox &bbox) |
void | init_vind () |
KDTreeSingleIndexAdaptor (const int dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams ¶ms=KDTreeSingleIndexAdaptorParams()) | |
KDTreeSingleIndexAdaptor (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType > &)=delete | |
void | loadIndex (FILE *stream) |
void | saveIndex (FILE *stream) |
template<class RESULTSET > | |
bool | searchLevel (RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindistsq, distance_vector_t &dists, const float epsError) const |
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, -1, size_t >, Distance, DatasetAdaptor, -1, size_t > | |
DistanceType | computeInitialDistances (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, size_t > &obj, const ElementType *vec, distance_vector_t &dists) const |
void | computeMinMax (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, size_t > &obj, size_t *ind, size_t count, int element, ElementType &min_elem, ElementType &max_elem) |
ElementType | dataset_get (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, size_t > &obj, size_t idx, int component) const |
Helper accessor to the dataset points: More... | |
NodePtr | divideTree (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, size_t > &obj, const size_t left, const size_t right, BoundingBox &bbox) |
void | freeIndex (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, size_t > &obj) |
void | load_tree (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, size_t > &obj, FILE *stream, NodePtr &tree) |
void | loadIndex_ (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, size_t > &obj, FILE *stream) |
void | middleSplit_ (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, size_t > &obj, size_t *ind, size_t count, size_t &index, int &cutfeat, DistanceType &cutval, const BoundingBox &bbox) |
void | planeSplit (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, size_t > &obj, size_t *ind, const size_t count, int cutfeat, DistanceType &cutval, size_t &lim1, size_t &lim2) |
void | save_tree (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, size_t > &obj, FILE *stream, NodePtr tree) |
void | saveIndex_ (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, size_t > &obj, FILE *stream) |
size_t | size (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, size_t > &obj) const |
size_t | usedMemory (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, size_t > &obj) |
size_t | veclen (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, size_t > &obj) |
Public Attributes | |
const DatasetAdaptor & | dataset |
The source of our data. More... | |
Distance | distance |
const KDTreeSingleIndexAdaptorParams | index_params |
Public Attributes inherited from nanoflann::KDTreeBaseClass< KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, size_t >, Distance, DatasetAdaptor, -1, size_t > | |
int | dim |
Dimensionality of each data point. More... | |
size_t | m_leaf_max_size |
size_t | m_size |
Number of current points in the dataset. More... | |
size_t | m_size_at_index_build |
PooledAllocator | pool |
BoundingBox | root_bbox |
NodePtr | root_node |
std::vector< size_t > | vind |
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 |
Definition at line 1116 of file nanoflann.hpp.
typedef nanoflann::KDTreeBaseClass< nanoflann::KDTreeSingleIndexAdaptor<Distance, DatasetAdaptor, DIM, IndexType>, Distance, DatasetAdaptor, DIM, IndexType> nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::BaseClassRef |
Definition at line 1139 of file nanoflann.hpp.
typedef BaseClassRef::BoundingBox nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::BoundingBox |
Define "BoundingBox" as a fixed-size or variable-size container depending on "DIM"
Definition at line 1150 of file nanoflann.hpp.
typedef BaseClassRef::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"
Definition at line 1154 of file nanoflann.hpp.
typedef BaseClassRef::DistanceType nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::DistanceType |
Definition at line 1142 of file nanoflann.hpp.
typedef BaseClassRef::ElementType nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::ElementType |
Definition at line 1141 of file nanoflann.hpp.
typedef BaseClassRef::Interval nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Interval |
Definition at line 1147 of file nanoflann.hpp.
typedef BaseClassRef::Node nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Node |
Definition at line 1144 of file nanoflann.hpp.
typedef Node* nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::NodePtr |
Definition at line 1145 of file nanoflann.hpp.
|
delete |
Deleted copy constructor
|
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 |
Definition at line 1170 of file nanoflann.hpp.
|
inline |
Builds the index
Definition at line 1190 of file nanoflann.hpp.
|
inline |
Definition at line 1316 of file nanoflann.hpp.
|
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> |
Definition at line 1221 of file nanoflann.hpp.
|
inline |
Make sure the auxiliary list vind has the same size than the current dataset, and re-generate if size has changed.
Definition at line 1307 of file nanoflann.hpp.
|
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
. Definition at line 1252 of file nanoflann.hpp.
|
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
Definition at line 1424 of file nanoflann.hpp.
|
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.
Definition at line 1278 of file nanoflann.hpp.
|
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.
Definition at line 1295 of file nanoflann.hpp.
|
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
Definition at line 1417 of file nanoflann.hpp.
|
inline |
Performs an exact search in the tree starting from a node.
RESULTSET | Should be any ResultSet<DistanceType> |
Definition at line 1346 of file nanoflann.hpp.
const DatasetAdaptor& nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::dataset |
The source of our data.
The dataset used by this index
Definition at line 1129 of file nanoflann.hpp.
Distance nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::distance |
Definition at line 1133 of file nanoflann.hpp.
const KDTreeSingleIndexAdaptorParams nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::index_params |
Definition at line 1131 of file nanoflann.hpp.