![]() |
nanoflann
C++ header-only ANN library
|
#include <nanoflann.hpp>
Public Types | |
using | Base |
using | Offset = typename Base::Offset |
using | Size = typename Base::Size |
using | Dimension = typename Base::Dimension |
using | ElementType = typename Base::ElementType |
using | DistanceType = typename Base::DistanceType |
using | IndexType = typename Base::IndexType |
using | Node = typename Base::Node |
using | NodePtr = Node* |
using | Interval = typename Base::Interval |
using | BoundingBox = typename Base::BoundingBox |
using | distance_vector_t = typename Base::distance_vector_t |
![]() | |
using | ElementType |
using | DistanceType |
using | IndexType |
using | Offset |
using | Size |
using | Dimension |
using | NodePtr |
using | NodeConstPtr |
using | BoundingBox |
using | distance_vector_t |
Public Member Functions | |
KDTreeSingleIndexAdaptor (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t > &)=delete | |
template<class... Args> | |
KDTreeSingleIndexAdaptor (const Dimension dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams ¶ms, Args &&... args) | |
KDTreeSingleIndexAdaptor (const Dimension dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams ¶ms={}) | |
void | buildIndex () |
void | init_vind () |
void | computeBoundingBox (BoundingBox &bbox) |
template<class RESULTSET > | |
bool | searchLevel (RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindist, distance_vector_t &dists, const float epsError) const |
void | saveIndex (std::ostream &stream) const |
void | loadIndex (std::istream &stream) |
Query methods | |
template<typename RESULTSET > | |
bool | findNeighbors (RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const |
Size | knnSearch (const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances) const |
Size | radiusSearch (const ElementType *query_point, const DistanceType &radius, std::vector< ResultItem< IndexType, DistanceType > > &IndicesDists, const SearchParameters &searchParams={}) const |
template<class SEARCH_CALLBACK > | |
Size | radiusSearchCustomCallback (const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParameters &searchParams={}) const |
Size | rknnSearch (const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances, const DistanceType &radius) const |
![]() | |
void | freeIndex (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj) |
Size | size (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj) const |
Size | veclen (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj) |
ElementType | dataset_get (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, IndexType element, Dimension component) const |
Helper accessor to the dataset points: | |
Size | usedMemory (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj) |
void | computeMinMax (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, Offset ind, Size count, Dimension element, ElementType &min_elem, ElementType &max_elem) |
NodePtr | divideTree (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, const Offset left, const Offset right, BoundingBox &bbox) |
NodePtr | divideTreeConcurrent (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, const Offset left, const Offset right, BoundingBox &bbox, std::atomic< unsigned int > &thread_count, std::mutex &mutex) |
void | middleSplit_ (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, const Offset ind, const Size count, Offset &index, Dimension &cutfeat, DistanceType &cutval, const BoundingBox &bbox) |
void | planeSplit (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, const Offset ind, const Size count, const Dimension cutfeat, const DistanceType &cutval, Offset &lim1, Offset &lim2) |
DistanceType | computeInitialDistances (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, const ElementType *vec, distance_vector_t &dists) const |
void | saveIndex (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, std::ostream &stream) const |
void | loadIndex (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, std::istream &stream) |
Public Attributes | |
const DatasetAdaptor & | dataset_ |
const KDTreeSingleIndexAdaptorParams | indexParams |
Distance | distance_ |
![]() | |
std::vector< IndexType > | vAcc_ |
NodePtr | root_node_ |
Size | leaf_max_size_ |
Size | n_thread_build_ |
Number of thread for concurrent tree build. | |
Size | size_ |
Number of current points in the dataset. | |
Size | size_at_index_build_ |
Number of points in the dataset when the index was built. | |
Dimension | dim_ |
Dimensionality of each data point. | |
BoundingBox | root_bbox_ |
PooledAllocator | pool_ |
Additional Inherited Members | |
![]() | |
static void | save_tree (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, std::ostream &stream, const NodeConstPtr tree) |
static void | load_tree (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, std::istream &stream, NodePtr &tree) |
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, which must be ensured to have a lifetime equal or longer than the instance of this class. |
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 |
using nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::Base |
using nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::BoundingBox = typename Base::BoundingBox |
Define "BoundingBox" as a fixed-size or variable-size container depending on "DIM"
using nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::distance_vector_t = typename Base::distance_vector_t |
Define "distance_vector_t" as a fixed-size or variable-size container depending on "DIM"
|
explicitdelete |
Deleted copy constructor
|
inlineexplicit |
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. Its lifetime must be equal or longer than that of the instance of this class. |
params | Basically, the maximum leaf node size |
Note that there is a variable number of optional additional parameters which will be forwarded to the metric class constructor. Refer to example examples/pointcloud_custom_metric.cpp
for a use case.
|
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 and distances are stored in the provided pointers to array/vector.
N
of valid points in the result set.N
entries in out_indices
and out_distances
will be valid. Return is 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 |
Find the first N 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.
N
of valid points in the result set.N
entries in out_indices
and out_distances
will be valid. Return is less than num_closest
only if the number of elements in the tree is less than num_closest
.
|
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, index_t >::dataset_ |
The data source used by this index