class mola::internal::IncrementalKDTree

Overview

Abstract facade over the nanoflann incremental k-d tree index (KDTreeSingleIndexIncrementalAdaptor and its multi-threaded variant), used by mola::IncrementalPointCloud.

This header intentionally exposes no nanoflann type: the whole library is included by a single implementation file that pulls in no MRPT header. MRPT bundles (and its binaries are compiled against) its own copy of nanoflann, which is typically older than the one providing the incremental index. Both copies declare the same non-template entities, so letting them be visible to the same translation unit or exporting either of them through a public header would be an ODR violation with real memory-corruption potential. See IncrementalKDTree.cpp.

Point coordinates are not owned here: the index only stores point indices (“slots”) into externally-owned x/y/z buffers, see setPointBuffers().

#include <IncrementalKDTree.h>

class IncrementalKDTree
{
public:
    // structs

    struct Neighbor;
    struct Params;

    // construction

    IncrementalKDTree(const IncrementalKDTree&);

    // methods

    virtual void setPointBuffers(const float* xs, const float* ys, const float* zs, std::size_t count) = 0;
    virtual void reserve(std::size_t n) = 0;
    virtual void clear() = 0;
    virtual void addPoint(uint32_t index) = 0;

    virtual void addPoints(
        uint32_t firstIndex,
        uint32_t lastIndex
        ) = 0;

    virtual void removePoint(uint32_t index) = 0;
    virtual void keepOnlyPointsInsideBox(const float minCorner [3], const float maxCorner [3]) = 0;
    virtual std::vector<uint32_t> acquireRemovedPoints() = 0;
    virtual void waitForPendingRebuilds() = 0;
    virtual void saveIndex(std::ostream& stream) = 0;
    virtual void loadIndex(std::istream& stream) = 0;
    virtual std::size_t size() const = 0;
    virtual std::size_t physicalSize() const = 0;
    virtual void snapshotLiveIndices(std::vector<uint32_t>& out) const = 0;
    virtual bool boundingBox(float minCorner [3], float maxCorner [3]) const = 0;

    virtual std::size_t knnSearch(
        const float query [3],
        std::size_t k,
        uint32_t* outIndices,
        float* outDistsSqr
        ) const = 0;

    virtual std::size_t knnSearchWithinRadius(
        const float query [3],
        std::size_t k,
        float maxDistSqr,
        uint32_t* outIndices,
        float* outDistsSqr
        ) const = 0;

    virtual void radiusSearch(const float query [3], float radiusSqr, std::vector<Neighbor>& out) const = 0;
    static std::unique_ptr<IncrementalKDTree> Create(const Params& p);
    IncrementalKDTree& operator = (const IncrementalKDTree&);
};

Methods

virtual void setPointBuffers(
    const float* xs,
    const float* ys,
    const float* zs,
    std::size_t count
    ) = 0

Rebinds the coordinate buffers the index reads point coordinates from. Must be called again after anything that may have reallocated them (i.e. after growing the owner point cloud).

virtual void reserve(std::size_t n) = 0

Pre-sizes internal structures for an expected point count.

virtual void clear() = 0

Drops the whole tree (and any pending background rebuild).

virtual void keepOnlyPointsInsideBox(
    const float minCorner [3],
    const float maxCorner [3]
    ) = 0

Removes every point outside the given axis-aligned box: the sliding window map-trimming primitive.

virtual std::vector<uint32_t> acquireRemovedPoints() = 0

Point slots that became physically free since the last call, so the owner can recycle them. Removal is lazy (tombstones), so slots only show up here once an actual rebuild reclaimed them.

virtual void waitForPendingRebuilds() = 0

Blocks until any in-flight background rebuild has been integrated.

virtual void saveIndex(std::ostream& stream) = 0

Serializes the tree topology to a binary stream, so it does not have to be rebuilt (an O(N log N) bulk build) the next time this same point set is indexed. Requires nanoflann >= 1.11.0 (the release that added saveIndex() /loadIndex() to the incremental index); throws std::runtime_error on older builds. Blocks on any in-flight background rebuild first (see waitForPendingRebuilds()).

virtual void loadIndex(std::istream& stream) = 0

Loads a topology previously written by saveIndex(). Must be called right after construction (or clear()), on an index already bound (via setPointBuffers()) to the same point coordinates that were indexed when saveIndex() was called. Requires nanoflann >= 1.11.0; throws std::runtime_error on older builds.

virtual std::size_t size() const = 0

Number of live (non-removed) points.

virtual std::size_t physicalSize() const = 0

Number of nodes physically stored (live + not-yet-reclaimed tombstones).

virtual void snapshotLiveIndices(std::vector<uint32_t>& out) const = 0

Appends the live point slots into out.

virtual bool boundingBox(float minCorner [3], float maxCorner [3]) const = 0

O(1) AABB of the points in the index (a conservative superset of the live set, since not-yet-reclaimed tombstones still contribute).

Returns:

false if the index is empty, in which case the outputs are unset.

virtual std::size_t knnSearch(
    const float query [3],
    std::size_t k,
    uint32_t* outIndices,
    float* outDistsSqr
    ) const = 0

Returns:

the number of neighbors actually found (<= k).

virtual std::size_t knnSearchWithinRadius(
    const float query [3],
    std::size_t k,
    float maxDistSqr,
    uint32_t* outIndices,
    float* outDistsSqr
    ) const = 0

As knnSearch(), but discarding neighbors farther than maxDistSqr.

virtual void radiusSearch(
    const float query [3],
    float radiusSqr,
    std::vector<Neighbor>& out
    ) const = 0

Appends every neighbor closer than radiusSqr (squared distance).