#include <kdtree_single_index.h>
Classes | |
struct | Interval |
struct | Node |
Public Types | |
typedef NNIndex< Distance > | BaseClass |
typedef Distance::ResultType | DistanceType |
typedef Distance::ElementType | ElementType |
typedef bool | needs_kdtree_distance |
![]() | |
typedef Distance::ResultType | DistanceType |
typedef Distance::ElementType | ElementType |
Public Member Functions | |
void | addPoints (const Matrix< ElementType > &points, float rebuild_threshold=2) |
Incrementally add points to the index. More... | |
virtual void | buildIndex () |
virtual void | buildIndex (const Matrix< ElementType > &dataset) |
BaseClass * | clone () const |
void | findNeighbors (ResultSet< DistanceType > &result, const ElementType *vec, const SearchParams &searchParams) const |
flann_algorithm_t | getType () const |
KDTreeSingleIndex (const IndexParams ¶ms=KDTreeSingleIndexParams(), Distance d=Distance()) | |
KDTreeSingleIndex (const KDTreeSingleIndex &other) | |
KDTreeSingleIndex (const Matrix< ElementType > &inputData, const IndexParams ¶ms=KDTreeSingleIndexParams(), Distance d=Distance()) | |
void | loadIndex (FILE *stream) |
KDTreeSingleIndex & | operator= (KDTreeSingleIndex other) |
void | saveIndex (FILE *stream) |
template<typename Archive > | |
void | serialize (Archive &ar) |
int | usedMemory () const |
virtual | ~KDTreeSingleIndex () |
![]() | |
virtual void | buildIndex () |
virtual void | buildIndex (const Matrix< ElementType > &dataset) |
IndexParams | getParameters () const |
virtual ElementType * | getPoint (size_t id) |
virtual int | knnSearch (const Matrix< ElementType > &queries, Matrix< size_t > &indices, Matrix< DistanceType > &dists, size_t knn, const SearchParams ¶ms) const |
Perform k-nearest neighbor search. More... | |
int | knnSearch (const Matrix< ElementType > &queries, std::vector< std::vector< int > > &indices, std::vector< std::vector< DistanceType > > &dists, size_t knn, const SearchParams ¶ms) const |
virtual int | knnSearch (const Matrix< ElementType > &queries, std::vector< std::vector< size_t > > &indices, std::vector< std::vector< DistanceType > > &dists, size_t knn, const SearchParams ¶ms) const |
Perform k-nearest neighbor search. More... | |
NNIndex (const IndexParams ¶ms, Distance d) | |
NNIndex (const NNIndex &other) | |
NNIndex (Distance d) | |
int | radiusSearch (const Matrix< ElementType > &queries, Matrix< int > &indices, Matrix< DistanceType > &dists, float radius, const SearchParams ¶ms) const |
virtual int | radiusSearch (const Matrix< ElementType > &queries, Matrix< size_t > &indices, Matrix< DistanceType > &dists, float radius, const SearchParams ¶ms) const |
Perform radius search. More... | |
int | radiusSearch (const Matrix< ElementType > &queries, std::vector< std::vector< int > > &indices, std::vector< std::vector< DistanceType > > &dists, float radius, const SearchParams ¶ms) const |
virtual int | radiusSearch (const Matrix< ElementType > &queries, std::vector< std::vector< size_t > > &indices, std::vector< std::vector< DistanceType > > &dists, float radius, const SearchParams ¶ms) const |
Perform radius search. More... | |
size_t | removedCount () const |
virtual void | removePoint (size_t id) |
template<typename Archive > | |
void | serialize (Archive &ar) |
size_t | size () const |
size_t | sizeAtBuild () const |
size_t | veclen () const |
virtual | ~NNIndex () |
![]() | |
virtual | ~IndexBase () |
Protected Member Functions | |
void | buildIndexImpl () |
![]() | |
void | cleanRemovedPoints () |
void | extendDataset (const Matrix< ElementType > &new_points) |
size_t | id_to_index (size_t id) |
void | indices_to_ids (const size_t *in, size_t *out, size_t size) const |
void | setDataset (const Matrix< ElementType > &dataset) |
void | swap (NNIndex &other) |
Private Types | |
typedef std::vector< Interval > | BoundingBox |
typedef BranchSt * | Branch |
typedef BranchStruct< NodePtr, DistanceType > | BranchSt |
typedef Node * | NodePtr |
Private Member Functions | |
void | computeBoundingBox (BoundingBox &bbox) |
DistanceType | computeInitialDistances (const ElementType *vec, std::vector< DistanceType > &dists) const |
void | computeMinMax (int *ind, int count, int dim, ElementType &min_elem, ElementType &max_elem) |
void | copyTree (NodePtr &dst, const NodePtr &src) |
NodePtr | divideTree (int left, int right, BoundingBox &bbox) |
void | freeIndex () |
void | middleSplit (int *ind, int count, int &index, int &cutfeat, DistanceType &cutval, const BoundingBox &bbox) |
void | middleSplit_ (int *ind, int count, int &index, int &cutfeat, DistanceType &cutval, const BoundingBox &bbox) |
void | planeSplit (int *ind, int count, int cutfeat, DistanceType cutval, int &lim1, int &lim2) |
template<bool with_removed> | |
void | searchLevel (ResultSet< DistanceType > &result_set, const ElementType *vec, const NodePtr node, DistanceType mindistsq, std::vector< DistanceType > &dists, const float epsError) const |
void | swap (KDTreeSingleIndex &other) |
Private Attributes | |
Matrix< ElementType > | data_ |
int | leaf_max_size_ |
PooledAllocator | pool_ |
bool | reorder_ |
BoundingBox | root_bbox_ |
NodePtr | root_node_ |
std::vector< int > | vind_ |
Additional Inherited Members | |
![]() | |
ElementType * | data_ptr_ |
Distance | distance_ |
std::vector< size_t > | ids_ |
IndexParams | index_params_ |
size_t | last_id_ |
std::vector< ElementType * > | points_ |
bool | removed_ |
size_t | removed_count_ |
DynamicBitset | removed_points_ |
size_t | size_ |
size_t | size_at_build_ |
size_t | veclen_ |
Single kd-tree index
Contains the k-d trees and other information for indexing a set of points for nearest-neighbor matching.
Definition at line 97 of file kdtree_single_index.h.
typedef NNIndex<Distance> rtflann::KDTreeSingleIndex< Distance >::BaseClass |
Definition at line 103 of file kdtree_single_index.h.
|
private |
Definition at line 362 of file kdtree_single_index.h.
|
private |
Definition at line 365 of file kdtree_single_index.h.
|
private |
Definition at line 364 of file kdtree_single_index.h.
typedef Distance::ResultType rtflann::KDTreeSingleIndex< Distance >::DistanceType |
Definition at line 101 of file kdtree_single_index.h.
typedef Distance::ElementType rtflann::KDTreeSingleIndex< Distance >::ElementType |
Definition at line 100 of file kdtree_single_index.h.
typedef bool rtflann::KDTreeSingleIndex< Distance >::needs_kdtree_distance |
Definition at line 105 of file kdtree_single_index.h.
|
private |
Definition at line 345 of file kdtree_single_index.h.
|
inline |
KDTree constructor
Params: params = parameters passed to the kdtree algorithm
Definition at line 113 of file kdtree_single_index.h.
|
inline |
KDTree constructor
Params: inputData = dataset with the input features params = parameters passed to the kdtree algorithm
Definition at line 127 of file kdtree_single_index.h.
|
inline |
Definition at line 137 of file kdtree_single_index.h.
|
inlinevirtual |
Standard destructor
Definition at line 159 of file kdtree_single_index.h.
|
inlinevirtual |
Incrementally add points to the index.
points | Matrix with points to be added |
rebuild_threshold |
Reimplemented from rtflann::NNIndex< Distance >.
Definition at line 171 of file kdtree_single_index.h.
|
inline |
Builds the index
Definition at line 153 of file nn_index.h.
|
inline |
Builds the index using the specified dataset
dataset | the dataset to use |
Definition at line 169 of file nn_index.h.
|
inlineprotectedvirtual |
Builds the index
Implements rtflann::NNIndex< Distance >.
Definition at line 267 of file kdtree_single_index.h.
|
inlinevirtual |
Implements rtflann::NNIndex< Distance >.
Definition at line 164 of file kdtree_single_index.h.
|
inlineprivate |
Definition at line 391 of file kdtree_single_index.h.
|
inlineprivate |
Definition at line 599 of file kdtree_single_index.h.
|
inlineprivate |
Definition at line 466 of file kdtree_single_index.h.
|
inlineprivate |
Definition at line 379 of file kdtree_single_index.h.
|
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 416 of file kdtree_single_index.h.
|
inlinevirtual |
Find set of nearest neighbors to vec. 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 maxCheck = the maximum number of restarts (in a best-bin-first manner)
Implements rtflann::NNIndex< Distance >.
Definition at line 248 of file kdtree_single_index.h.
|
inlineprivatevirtual |
Implements rtflann::NNIndex< Distance >.
Definition at line 369 of file kdtree_single_index.h.
|
inlinevirtual |
Implements rtflann::IndexBase.
Definition at line 178 of file kdtree_single_index.h.
|
inlinevirtual |
Implements rtflann::IndexBase.
Definition at line 223 of file kdtree_single_index.h.
|
inlineprivate |
Definition at line 477 of file kdtree_single_index.h.
|
inlineprivate |
Definition at line 524 of file kdtree_single_index.h.
|
inline |
Definition at line 150 of file kdtree_single_index.h.
|
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 577 of file kdtree_single_index.h.
|
inlinevirtual |
Implements rtflann::IndexBase.
Definition at line 216 of file kdtree_single_index.h.
|
inlineprivate |
Performs an exact search in the tree starting from a node.
Definition at line 621 of file kdtree_single_index.h.
|
inline |
Definition at line 185 of file kdtree_single_index.h.
|
inlineprivate |
Definition at line 673 of file kdtree_single_index.h.
|
inlinevirtual |
Computes the inde memory usage Returns: memory used by the index
Implements rtflann::IndexBase.
Definition at line 234 of file kdtree_single_index.h.
|
private |
Definition at line 699 of file kdtree_single_index.h.
|
private |
Definition at line 689 of file kdtree_single_index.h.
|
private |
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 718 of file kdtree_single_index.h.
|
private |
Definition at line 692 of file kdtree_single_index.h.
|
private |
Root bounding box
Definition at line 709 of file kdtree_single_index.h.
|
private |
Array of k-d trees used to find neighbours.
Definition at line 704 of file kdtree_single_index.h.
|
private |
Array of indices to vectors in the dataset.
Definition at line 697 of file kdtree_single_index.h.