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):
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. |
IndexType | Will be typically size_t or int |
Definition at line 734 of file nanoflann.hpp.
#include <mrpt/otherlibs/nanoflann/nanoflann.hpp>
Classes | |
struct | BranchStruct |
This record represents a branch point when finding neighbors in the tree. More... | |
struct | Interval |
struct | Node |
Public Types | |
typedef Distance::ElementType | ElementType |
typedef Distance::DistanceType | DistanceType |
Public Member Functions | |
KDTreeSingleIndexAdaptor (const int dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams ¶ms=KDTreeSingleIndexAdaptorParams()) | |
KDTree constructor. More... | |
~KDTreeSingleIndexAdaptor () | |
Standard destructor. More... | |
void | freeIndex () |
Frees the previously-built index. More... | |
void | buildIndex () |
Builds the index. More... | |
size_t | size () const |
Returns size of index. More... | |
size_t | veclen () const |
Returns the length of an index feature. More... | |
size_t | usedMemory () const |
Computes the inde memory usage Returns: memory used by the index. More... | |
void | saveIndex (FILE *stream) |
Stores the index in a binary file. More... | |
void | loadIndex (FILE *stream) |
Loads a previous index from a binary file. More... | |
Query methods | |
template<typename RESULTSET > | |
void | findNeighbors (RESULTSET &result, const ElementType *vec, const SearchParams &searchParams) const |
Find set of nearest neighbors to vec[0:dim-1]. More... | |
void | knnSearch (const ElementType *query_point, const size_t num_closest, IndexType *out_indices, DistanceType *out_distances_sq, const int=10) const |
Find the "num_closest" nearest neighbors to the query_point[0:dim-1]. More... | |
size_t | radiusSearch (const ElementType *query_point, const DistanceType radius, std::vector< std::pair< IndexType, DistanceType > > &IndicesDists, const SearchParams &searchParams) const |
Find all the neighbors to query_point[0:dim-1] within a maximum radius. More... | |
Public Attributes | |
Distance | distance |
Protected Types | |
typedef Node * | NodePtr |
typedef array_or_vector_selector< DIM, Interval >::container_t | BoundingBox |
Define "BoundingBox" as a fixed-size or variable-size container depending on "DIM". More... | |
typedef array_or_vector_selector< DIM, DistanceType >::container_t | distance_vector_t |
Define "distance_vector_t" as a fixed-size or variable-size container depending on "DIM". More... | |
typedef BranchStruct< NodePtr, DistanceType > | BranchSt |
typedef BranchSt * | Branch |
Protected Attributes | |
std::vector< IndexType > | vind |
Array of indices to vectors in the dataset. More... | |
size_t | m_leaf_max_size |
const DatasetAdaptor & | dataset |
The dataset used by this index. More... | |
const KDTreeSingleIndexAdaptorParams | index_params |
size_t | m_size |
int | dim |
Dimensionality of each data point. More... | |
NodePtr | root_node |
Array of k-d trees used to find neighbours. More... | |
BoundingBox | root_bbox |
PooledAllocator | pool |
Pooled memory allocator. More... | |
Private Member Functions | |
KDTreeSingleIndexAdaptor (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType > &) | |
Hidden copy constructor, to disallow copying indices (Not implemented) More... | |
void | init_vind () |
Make sure the auxiliary list vind has the same size than the current dataset, and re-generate if size has changed. More... | |
ElementType | dataset_get (size_t idx, int component) const |
Helper accessor to the dataset points: More... | |
void | save_tree (FILE *stream, NodePtr tree) |
void | load_tree (FILE *stream, NodePtr &tree) |
void | computeBoundingBox (BoundingBox &bbox) |
NodePtr | divideTree (const IndexType left, const IndexType right, BoundingBox &bbox) |
Create a tree node that subdivides the list of vecs from vind[first] to vind[last]. More... | |
void | computeMinMax (IndexType *ind, IndexType count, int element, ElementType &min_elem, ElementType &max_elem) |
void | middleSplit_ (IndexType *ind, IndexType count, IndexType &index, int &cutfeat, DistanceType &cutval, const BoundingBox &bbox) |
void | planeSplit (IndexType *ind, const IndexType count, int cutfeat, DistanceType cutval, IndexType &lim1, IndexType &lim2) |
Subdivide the list of points by a plane perpendicular on axe corresponding to the 'cutfeat' dimension at 'cutval' position. More... | |
DistanceType | computeInitialDistances (const ElementType *vec, distance_vector_t &dists) const |
template<class RESULTSET > | |
void | searchLevel (RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindistsq, distance_vector_t &dists, const float epsError) const |
Performs an exact search in the tree starting from a node. More... | |
|
protected |
Define "BoundingBox" as a fixed-size or variable-size container depending on "DIM".
Definition at line 800 of file nanoflann.hpp.
|
protected |
Definition at line 829 of file nanoflann.hpp.
|
protected |
Definition at line 828 of file nanoflann.hpp.
|
protected |
Define "distance_vector_t" as a fixed-size or variable-size container depending on "DIM".
Definition at line 803 of file nanoflann.hpp.
typedef Distance::DistanceType nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::DistanceType |
Definition at line 741 of file nanoflann.hpp.
typedef Distance::ElementType nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::ElementType |
Definition at line 740 of file nanoflann.hpp.
|
protected |
Definition at line 791 of file nanoflann.hpp.
|
private |
Hidden copy constructor, to disallow copying indices (Not implemented)
|
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)
Definition at line 853 of file nanoflann.hpp.
|
inline |
Standard destructor.
Definition at line 871 of file nanoflann.hpp.
|
inline |
Builds the index.
Definition at line 885 of file nanoflann.hpp.
Referenced by nanoflann::KDTreeEigenMatrixAdaptor< MatrixType, DIM, Distance, IndexType >::KDTreeEigenMatrixAdaptor(), mrpt::math::KDTreeCapable< CFeatureList >::rebuild_kdTree_2D(), mrpt::math::KDTreeCapable< CFeatureList >::rebuild_kdTree_3D(), mrpt::vision::TSIFTDescriptorsKDTreeIndex< distance_t, metric_t >::regenerate_kdtreee(), and mrpt::vision::TSURFDescriptorsKDTreeIndex< distance_t, metric_t >::regenerate_kdtreee().
|
inlineprivate |
Definition at line 1025 of file nanoflann.hpp.
|
inlineprivate |
Definition at line 1200 of file nanoflann.hpp.
References mrpt::math::distance(), and nanoflann::KNNResultSet< DistanceType, IndexType, CountType >::dists.
|
inlineprivate |
Definition at line 1109 of file nanoflann.hpp.
References nanoflann::KNNResultSet< DistanceType, IndexType, CountType >::count.
|
inlineprivate |
Helper accessor to the dataset points:
Definition at line 995 of file nanoflann.hpp.
|
inlineprivate |
Create a tree node that subdivides the list of vecs from vind[first] to vind[last].
The routine is called recursively on each sublist. Place a pointer to this new tree node in the location pTree.
Params: pTree = the new node to create first = index of the first vector last = index of the last vector
Definition at line 1059 of file nanoflann.hpp.
References nanoflann::PooledAllocator::allocate(), nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Node::child1, nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Node::child2, nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Node::lr, and nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Node::sub.
|
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 934 of file nanoflann.hpp.
References nanoflann::KNNResultSet< DistanceType, IndexType, CountType >::dists, and nanoflann::SearchParams::eps.
Referenced by mrpt::math::KDTreeCapable< CFeatureList >::kdTreeClosestPoint2D(), mrpt::math::KDTreeCapable< CFeatureList >::kdTreeClosestPoint3D(), mrpt::math::KDTreeCapable< CFeatureList >::kdTreeNClosestPoint2D(), mrpt::math::KDTreeCapable< CFeatureList >::kdTreeNClosestPoint2DIdx(), mrpt::math::KDTreeCapable< CFeatureList >::kdTreeNClosestPoint3D(), mrpt::math::KDTreeCapable< CFeatureList >::kdTreeNClosestPoint3DIdx(), mrpt::math::KDTreeCapable< CFeatureList >::kdTreeNClosestPoint3DWithIdx(), mrpt::math::KDTreeCapable< CFeatureList >::kdTreeTwoClosestPoint2D(), and nanoflann::KDTreeEigenMatrixAdaptor< MatrixType, DIM, Distance, IndexType >::query().
|
inline |
Frees the previously-built index.
Automatically called within buildIndex().
Definition at line 876 of file nanoflann.hpp.
References nanoflann::PooledAllocator::free_all().
|
inlineprivate |
Make sure the auxiliary list vind has the same size than the current dataset, and re-generate if size has changed.
Definition at line 986 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.
Definition at line 952 of file nanoflann.hpp.
References nanoflann::KNNResultSet< DistanceType, IndexType, CountType >::init().
|
inlineprivate |
Definition at line 1012 of file nanoflann.hpp.
References nanoflann::PooledAllocator::allocate(), nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Node::child1, nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Node::child2, and nanoflann::load_value().
|
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 1292 of file nanoflann.hpp.
References nanoflann::load_value().
|
inlineprivate |
Definition at line 1120 of file nanoflann.hpp.
References nanoflann::KNNResultSet< DistanceType, IndexType, CountType >::count.
|
inlineprivate |
Subdivide the list of points by a plane perpendicular on axe corresponding to the 'cutfeat' dimension at 'cutval' position.
On return: dataset[ind[0..lim1-1]][cutfeat]<cutval dataset[ind[lim1..lim2-1]][cutfeat]==cutval dataset[ind[lim2..count]][cutfeat]>cutval
Definition at line 1171 of file nanoflann.hpp.
References nanoflann::KNNResultSet< DistanceType, IndexType, CountType >::count.
|
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 971 of file nanoflann.hpp.
References nanoflann::RadiusResultSet< DistanceType, IndexType >::size(), and nanoflann::SearchParams::sorted.
Referenced by mrpt::math::KDTreeCapable< CFeatureList >::kdTreeRadiusSearch2D(), and mrpt::math::KDTreeCapable< CFeatureList >::kdTreeRadiusSearch3D().
|
inlineprivate |
|
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 1278 of file nanoflann.hpp.
References nanoflann::save_value().
|
inlineprivate |
Performs an exact search in the tree starting from a node.
RESULTSET | Should be any ResultSet<DistanceType> |
Definition at line 1224 of file nanoflann.hpp.
References nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Node::child1, nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Node::child2, mrpt::math::distance(), nanoflann::KNNResultSet< DistanceType, IndexType, CountType >::dists, nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Node::lr, and nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Node::sub.
|
inline |
Returns size of index.
Definition at line 897 of file nanoflann.hpp.
|
inline |
Computes the inde memory usage Returns: memory used by the index.
Definition at line 914 of file nanoflann.hpp.
References nanoflann::PooledAllocator::usedMemory, and nanoflann::PooledAllocator::wastedMemory.
|
inline |
Returns the length of an index feature.
Definition at line 905 of file nanoflann.hpp.
|
protected |
The dataset used by this index.
The source of our data
Definition at line 755 of file nanoflann.hpp.
|
protected |
Dimensionality of each data point.
Definition at line 760 of file nanoflann.hpp.
Distance nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::distance |
Definition at line 844 of file nanoflann.hpp.
|
protected |
Definition at line 757 of file nanoflann.hpp.
|
protected |
Definition at line 749 of file nanoflann.hpp.
|
protected |
Definition at line 759 of file nanoflann.hpp.
|
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.
Definition at line 840 of file nanoflann.hpp.
|
protected |
Definition at line 831 of file nanoflann.hpp.
|
protected |
Array of k-d trees used to find neighbours.
Definition at line 827 of file nanoflann.hpp.
|
protected |
Array of indices to vectors in the dataset.
Definition at line 747 of file nanoflann.hpp.
Page generated by Doxygen 1.8.16 for MRPT 1.4.0 SVN: at Mon Oct 14 23:08:25 UTC 2019 |