template class mrpt::math::KDTreeCapable

A generic adaptor class for providing Nearest Neighbor (NN) lookup via the nanoflann library.

This makes use of the CRTP design pattern.

Derived classes must be aware of the need to call “kdtree_mark_as_outdated()” when the data points change to mark the cached KD-tree (an “index”) as invalid, and also implement the following interface (note that these are not virtual functions due to the usage of CRTP):

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

  // Returns the distance between the vector "p1[0:size-1]" and the data
point with index "idx_p2" stored in the class:
  inline float kdtree_distance(const float *p1, const size_t idx_p2,size_t
size) const { ... }

  // Returns the dim'th component of the idx'th point in the class:
  inline num_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 = ...;  // "x" limits
     return true;
  }

The KD-tree index will be built on demand only upon call of any of the query methods provided by this class.

Notice that there is only ONE internal cached KD-tree, so if a method to query a 2D point is called, then another method for 3D points, then again the 2D method, three KD-trees will be built. So, try to group all the calls for a given dimensionality together or build different class instances for queries of each dimensionality, etc.

See also:

See some of the derived classes for example implementations. See also the documentation of nanoflann

#include <mrpt/math/KDTreeCapable.h>

template <
    class Derived,
    typename num_t = float,
    typename metric_t = nanoflann::L2_Simple_Adaptor<num_t, Derived>
    >
class KDTreeCapable
{
public:
    // typedefs

    typedef KDTreeCapable<Derived, num_t, metric_t> self_t;

    // structs

    template <int _DIM = -1>
    struct TKDTreeDataHolder;

    struct TKDTreeSearchParams;

    // construction

    KDTreeCapable();
    KDTreeCapable(const KDTreeCapable&);

    //
methods

    float kdTreeClosestPoint2DsqrError(const TPoint2D& p0) const;

    void kdTreeTwoClosestPoint2D(
        const TPoint2D& p0,
        TPoint2D& pOut1,
        TPoint2D& pOut2,
        float& outDistSqr1,
        float& outDistSqr2
        ) const;

    std::vector<size_t> kdTreeNClosestPoint2D(
        const TPoint2D& p0,
        size_t N,
        std::vector<TPoint2D>& pOut,
        std::vector<float>& outDistSqr
        ) const;

    void kdTreeNClosestPoint2DIdx(
        const TPoint2D& p0,
        size_t N,
        std::vector<size_t>& outIdx,
        std::vector<float>& outDistSqr
        ) const;

    void kdTreeNClosestPoint3D(
        const TPoint3D& p0,
        size_t N,
        std::vector<TPoint3D>& pOut,
        std::vector<float>& outDistSqr
        ) const;

    void kdTreeNClosestPoint3DIdx(
        const TPoint3D& p0,
        size_t N,
        std::vector<size_t>& outIdx,
        std::vector<float>& outDistSqr
        ) const;

    void kdTreeEnsureIndexBuilt3D();
    void kdTreeEnsureIndexBuilt2D();
    KDTreeCapable& operator = (const KDTreeCapable&);
};

// direct descendants

class CFeatureList;

template <typename FEAT>
class CFeatureListKDTree;

class CPointsMap;

Construction

KDTreeCapable()

Constructor.