template class mrpt::math::KDTreeCapable

Overview

Adaptor class providing Nearest Neighbor (NN) searcg via nanoflann, making use of the CRTP design pattern.

Derived classes must call kdtree_mark_as_outdated() when data points change to mark the cached KD-tree (an “index”) as invalid, and they must 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.

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 std::optional<float>& maximumSearchDistanceSqr = std::nullopt
        ) 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 std::optional<float>& maximumSearchDistanceSqr = std::nullopt
        ) const;

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

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

// direct descendants

class CFeatureList;

template <typename FEAT>
class CFeatureListKDTree;

class CPointsMap;

Construction

KDTreeCapable()

Constructor.