template class nanoflann::KDTreeSingleIndexAdaptor

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):

// Must return the number of data poins
inline size_t kdtree_get_point_count() const { ... }

// [Only if using the metric_L2_Simple type] Must return the Euclidean (L2) distance between the vector "p1[0:size-1]" and the data point with index "idx_p2" stored in the class:
inline DistanceType kdtree_distance(const T *p1, const size_t idx_p2,size_t size) const { ... }

// Must return the dim'th component of the idx'th point in the class:
inline T kdtree_get_pt(const size_t idx, int dim) const { ... }

// Optional bounding-box computation: return false to default to a standard bbox computation loop.
//   Return true if the BBOX was already computed by the class and returned in "bb" so it can be avoided to redo it again.
//   Look at bb.size() to find out the expected dimensionality (e.g. 2 or 3 for point clouds)
template <class BBOX>
bool kdtree_get_bbox(BBOX &bb) const
{
   bb[0].low = ...; bb[0].high = ...;  // 0th dimension limits
   bb[1].low = ...; bb[1].high = ...;  // 1st dimension limits
   ...
   return true;
}

Parameters:

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

#include <nanoflann.hpp>

template <
    typename Distance,
    class DatasetAdaptor,
    int DIM = -1,
    typename IndexType = size_t
    >
class KDTreeSingleIndexAdaptor
{
public:
    // typedefs

    typedef Distance::ElementType ElementType;
    typedef Distance::DistanceType DistanceType;

    // structs

    struct Interval;
    struct Node;

    //
fields

    Distance distance;

    // construction

    KDTreeSingleIndexAdaptor(const int dimensionality, const DatasetAdaptor& inputData, const KDTreeSingleIndexAdaptorParams& params = KDTreeSingleIndexAdaptorParams());

    //
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;

    void freeIndex();
    void buildIndex();
    size_t size() const;
    size_t veclen() const;
    size_t usedMemory() const;
    void saveIndex(FILE* stream);
    void loadIndex(FILE* stream);
};

Construction

KDTreeSingleIndexAdaptor(
    const int dimensionality,
    const DatasetAdaptor& inputData,
    const KDTreeSingleIndexAdaptorParams& params = KDTreeSingleIndexAdaptorParams()
    )

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:

• The DIM template parameter if >0 (highest priority)

• Otherwise, the dimensionality parameter of this constructor.

Parameters:

inputData	Dataset with the input features
params	Basically, the maximum leaf node size

Methods

template <typename RESULTSET>
bool findNeighbors(
    RESULTSET& result,
    const ElementType* vec,
    const SearchParams& searchParams
    ) const

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

Parameters:

RESULTSET

Should be any ResultSet<DistanceType>

Returns:

True if the requested neighbors could be found.

See also:

knnSearch, radiusSearch

size_t 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].

Their indices are stored inside the result object. nChecks_IGNORED is ignored but kept for compatibility with the original FLANN interface.

Returns:

Number 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.

See also:

radiusSearch, findNeighbors

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.

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.

Returns:

The number of points within the given radius (i.e. indices.size() or dists.size())

See also:

knnSearch, findNeighbors, radiusSearchCustomCallback

template <class SEARCH_CALLBACK>
size_t radiusSearchCustomCallback(
    const ElementType* query_point,
    SEARCH_CALLBACK& resultSet,
    const SearchParams& searchParams = SearchParams()
    ) const

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.

See also:

radiusSearch

void freeIndex()

Frees the previously-built index.

Automatically called within buildIndex().

void buildIndex()

Builds the index.

size_t size() const

Returns number of points in dataset.

size_t veclen() const

Returns the length of each point in the dataset.

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.

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

See also:

loadIndex

void loadIndex(FILE* stream)

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

See also:

loadIndex