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 735 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. | |
~KDTreeSingleIndexAdaptor () | |
Standard destructor. | |
void | freeIndex () |
Frees the previously-built index. | |
void | buildIndex () |
Builds the index. | |
size_t | size () const |
Returns size of index. | |
size_t | veclen () const |
Returns the length of an index feature. | |
size_t | usedMemory () const |
Computes the inde memory usage Returns: memory used by the index. | |
void | saveIndex (FILE *stream) |
Stores the index in a binary file. | |
void | loadIndex (FILE *stream) |
Loads a previous index from a binary file. | |
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]. | |
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]. | |
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. | |
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". | |
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". | |
typedef BranchStruct< NodePtr, DistanceType > | BranchSt |
typedef BranchSt * | Branch |
Protected Attributes | |
std::vector< IndexType > | vind |
Array of indices to vectors in the dataset. | |
size_t | m_leaf_max_size |
const DatasetAdaptor & | dataset |
The dataset used by this index. | |
const KDTreeSingleIndexAdaptorParams | index_params |
size_t | m_size |
int | dim |
Dimensionality of each data point. | |
NodePtr | root_node |
Array of k-d trees used to find neighbours. | |
BoundingBox | root_bbox |
PooledAllocator | pool |
Pooled memory allocator. | |
Private Member Functions | |
KDTreeSingleIndexAdaptor (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType > &) | |
Hidden copy constructor, to disallow copying indices (Not implemented) | |
void | init_vind () |
Make sure the auxiliary list vind has the same size than the current dataset, and re-generate if size has changed. | |
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) |
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]. | |
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. | |
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. | |
|
protected |
Define "BoundingBox" as a fixed-size or variable-size container depending on "DIM".
Definition at line 801 of file nanoflann.hpp.
|
protected |
Definition at line 830 of file nanoflann.hpp.
|
protected |
Definition at line 829 of file nanoflann.hpp.
|
protected |
Define "distance_vector_t" as a fixed-size or variable-size container depending on "DIM".
Definition at line 804 of file nanoflann.hpp.
typedef Distance::DistanceType nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::DistanceType |
Definition at line 742 of file nanoflann.hpp.
typedef Distance::ElementType nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::ElementType |
Definition at line 741 of file nanoflann.hpp.
|
protected |
Definition at line 792 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 854 of file nanoflann.hpp.
|
inline |
Standard destructor.
Definition at line 872 of file nanoflann.hpp.
|
inline |
Builds the index.
Definition at line 886 of file nanoflann.hpp.
Referenced by nanoflann::KDTreeEigenMatrixAdaptor< MatrixType, DIM, Distance, IndexType >::KDTreeEigenMatrixAdaptor(), mrpt::math::KDTreeCapable< Derived, num_t, metric_t >::rebuild_kdTree_2D(), mrpt::math::KDTreeCapable< Derived, num_t, metric_t >::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 1026 of file nanoflann.hpp.
References nanoflann::CArray< T, N >::resize().
|
inlineprivate |
Definition at line 1201 of file nanoflann.hpp.
|
inlineprivate |
Definition at line 1110 of file nanoflann.hpp.
|
inlineprivate |
Helper accessor to the dataset points:
Definition at line 996 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 1060 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::divfeat, nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Node::divhigh, nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Node::divlow, nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Node::left, nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Node::lr, nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Node::right, 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 935 of file nanoflann.hpp.
References nanoflann::CArray< T, N >::assign(), and nanoflann::SearchParams::eps.
Referenced by mrpt::math::KDTreeCapable< Derived, num_t, metric_t >::kdTreeClosestPoint2D(), mrpt::math::KDTreeCapable< Derived, num_t, metric_t >::kdTreeClosestPoint2D(), mrpt::math::KDTreeCapable< Derived, num_t, metric_t >::kdTreeClosestPoint3D(), mrpt::math::KDTreeCapable< Derived, num_t, metric_t >::kdTreeClosestPoint3D(), mrpt::math::KDTreeCapable< Derived, num_t, metric_t >::kdTreeNClosestPoint2D(), mrpt::math::KDTreeCapable< Derived, num_t, metric_t >::kdTreeNClosestPoint2DIdx(), mrpt::math::KDTreeCapable< Derived, num_t, metric_t >::kdTreeNClosestPoint3D(), mrpt::math::KDTreeCapable< Derived, num_t, metric_t >::kdTreeNClosestPoint3DIdx(), mrpt::math::KDTreeCapable< Derived, num_t, metric_t >::kdTreeNClosestPoint3DWithIdx(), mrpt::math::KDTreeCapable< Derived, num_t, metric_t >::kdTreeTwoClosestPoint2D(), and nanoflann::KDTreeEigenMatrixAdaptor< MatrixType, DIM, Distance, IndexType >::query().
|
inline |
Frees the previously-built index.
Automatically called within buildIndex().
Definition at line 877 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 987 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 953 of file nanoflann.hpp.
References nanoflann::KNNResultSet< DistanceType, IndexType, CountType >::init().
|
inlineprivate |
Definition at line 1013 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 1293 of file nanoflann.hpp.
References nanoflann::load_value().
|
inlineprivate |
Definition at line 1121 of file nanoflann.hpp.
|
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 1172 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 972 of file nanoflann.hpp.
References nanoflann::RadiusResultSet< DistanceType, IndexType >::size(), and nanoflann::SearchParams::sorted.
Referenced by mrpt::math::KDTreeCapable< Derived, num_t, metric_t >::kdTreeRadiusSearch2D(), and mrpt::math::KDTreeCapable< Derived, num_t, metric_t >::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 1279 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 1225 of file nanoflann.hpp.
References nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Node::child1, nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Node::child2, nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Node::divfeat, nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Node::divhigh, nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Node::divlow, nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Node::left, nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Node::lr, nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Node::right, and nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Node::sub.
|
inline |
Returns size of index.
Definition at line 898 of file nanoflann.hpp.
|
inline |
Computes the inde memory usage Returns: memory used by the index.
Definition at line 915 of file nanoflann.hpp.
References nanoflann::PooledAllocator::usedMemory, and nanoflann::PooledAllocator::wastedMemory.
|
inline |
Returns the length of an index feature.
Definition at line 906 of file nanoflann.hpp.
|
protected |
The dataset used by this index.
The source of our data
Definition at line 756 of file nanoflann.hpp.
|
protected |
Dimensionality of each data point.
Definition at line 761 of file nanoflann.hpp.
Distance nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::distance |
Definition at line 845 of file nanoflann.hpp.
|
protected |
Definition at line 758 of file nanoflann.hpp.
|
protected |
Definition at line 750 of file nanoflann.hpp.
|
protected |
Definition at line 760 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 841 of file nanoflann.hpp.
|
protected |
Definition at line 832 of file nanoflann.hpp.
|
protected |
Array of k-d trees used to find neighbours.
Definition at line 828 of file nanoflann.hpp.
|
protected |
Array of indices to vectors in the dataset.
Definition at line 748 of file nanoflann.hpp.
Page generated by Doxygen 1.9.7 for MRPT 1.4.0 SVN: at Tue Jun 27 17:12:06 UTC 2023 |