Template Class KDTreeSingleIndexIncrementalAdaptor

Nested Relationships

Nested Types

Inheritance Relationships

Base Type

  • public nanoflann::KDTreeBaseClass< KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, -1, uint32_t >, Distance, DatasetAdaptor, -1, uint32_t > (Template Class KDTreeBaseClass)

Class Documentation

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>
class KDTreeSingleIndexIncrementalAdaptor : public nanoflann::KDTreeBaseClass<KDTreeSingleIndexIncrementalAdaptor<Distance, DatasetAdaptor, -1, uint32_t>, Distance, DatasetAdaptor, -1, uint32_t>

kd-tree incremental dynamic index — a single, self-balancing k-d tree.

This is an additive alternative to KDTreeSingleIndexDynamicAdaptor (the “logarithmic forest”). Instead of maintaining O(log N) static sub-trees, it keeps a single weight-balanced k-d tree that supports cheap incremental point insertion, lazy point removal, and pruned axis-aligned box deletions (removeBox / removeOutsideBox), the latter being the primary map-maintenance primitive used in LiDAR odometry (keep a local cube around the sensor and discard everything outside it as the platform moves).

Compared with the forest, the single tree avoids the multiplicative O(log N) query penalty of querying every sub-tree, and keeps deletion garbage bounded (a subtree is rebuilt once its dead fraction crosses alpha_deleted), at the price of synchronous O(N) rebuild spikes near the root.

Like the other adaptors this is zero-copy: the data points live in the user-provided dataset; the tree only stores point indices. Each tree node holds a single point plus augmentation (subtree size, tombstone count and an axis-aligned bounding box) used to prune the box-region operations.

Note

Threading: like the rest of nanoflann, const queries are safe for concurrent readers, but mutating operations (addPoints / removePoint / removeBox / removeOutsideBox) must not run concurrently with any query.

Note

A compile-time fixed DIM (e.g. 3 for 3D LiDAR) is recommended: the per-node bounding box is then a stack std::array and no per-node heap allocation occurs. With DIM=-1 each node’s box is a std::vector.

Template Parameters:

  • Distance – The distance metric (nanoflann::metric_L2_Simple, etc).

  • DatasetAdaptor – The user-provided dataset adaptor.

  • DIM – Dimensionality of the data points (e.g. 3), or -1 for runtime.

  • IndexType – Type used to index data points (e.g. uint32_t).

Modifiers

inline void addPoint(IndexType idx)

Insert a single point (by its index in the dataset).

inline void addPoints(IndexType start, IndexType end)

Insert all points with indices in the inclusive range [start, end].

When the batch is large relative to the current tree (an empty tree, or a batch comparable to the live count — e.g. a full LiDAR scan rebuilding a heavily-trimmed map) it is cheaper to flatten the live points and bulk-build one balanced tree than to descend-insert each point and trigger near-root scapegoat rebuilds. Small batches relative to a large map take the incremental per-point path.

inline void removePoint(IndexType idx)

Lazily remove the point with the given index (no-op if absent/removed).

inline void removeBox(const BoundingBox &box)

Remove every live point lying inside the axis-aligned box box.

inline void removeOutsideBox(const BoundingBox &keep)

Remove every live point lying outside the axis-aligned box keep. This is the LiDAR sliding-window map-trimming primitive.

inline void setCollectRemovedPoints(bool enable)

Enable/disable recording of physically-evicted point indices, returned by acquireRemovedPoints(). Off by default (cost-free when unused).

inline std::vector<IndexType> acquireRemovedPoints()

Move out the list of point indices physically dropped (during rebuilds) since the last call. Requires setCollectRemovedPoints(true).

inline void setInlineRebuild(bool enable)

Enable/disable inline (synchronous) rebalancing. When disabled the index only appends and lazily tombstones; balance must be restored externally via buildFromIndices(). Used by the multi-threaded wrapper.

inline void snapshotLiveIndices(std::vector<IndexType> &out) const

Append the live point indices (DFS, skipping tombstones) into out. Non-destructive; used to snapshot the tree for a background rebuild.

inline void collectPhysicalIndices(std::vector<IndexType> &out) const

Append EVERY physically-stored point index (live and tombstoned) into out. Used by the multi-threaded wrapper to detect which dataset slots become free after a background rebuild swap.

inline NANOFLANN_NODISCARD bool referencesIndex (IndexType idx) const

True if some tree node currently references the given point index (i.e. the dataset slot is in use and must not be recycled).

inline void buildFromIndices(const std::vector<IndexType> &idxs)

Discard the current tree and bulk-build a fresh, balanced tree over the given point indices. O(M log M). Reuses recycled nodes via the pool.

Capacity / observers

inline NANOFLANN_NODISCARD Size size () const noexcept

Number of live (non-removed) points currently in the index.

inline NANOFLANN_NODISCARD bool empty () const noexcept
inline NANOFLANN_NODISCARD Size physicalSize () const noexcept

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

inline NANOFLANN_NODISCARD Size usedMemory () const

Approximate bytes used by the node pool and the index->node map.

inline NANOFLANN_NODISCARD BoundingBox boundingBox () const

Axis-aligned bounding box of all points currently in the index (live and not-yet-reclaimed tombstones — a conservative superset of the live set). O(1): returns the cached root box. Meaningless if empty() (all zeros).

inline void reserve(Size n)

Pre-size the internal index->node map (and the rebuild scratch buffer) to avoid reallocations while the point count grows toward n.

Query methods

template<typename RESULTSET>
inline bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams = {}) const

Core search: find neighbors of vec, storing them in result.

inline NANOFLANN_NODISCARD Size knnSearch (const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances, const SearchParameters &searchParams={}) const

Find the num_closest nearest neighbors to query_point.

inline NANOFLANN_NODISCARD Size radiusSearch (const ElementType *query_point, const DistanceType &radius, std::vector< ResultItem< IndexType, DistanceType > > &IndicesDists, const SearchParameters &searchParams={}) const

Radius search around query_point.

template<class SEARCH_CALLBACK> inline NANOFLANN_NODISCARD Size radiusSearchCustomCallback (const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParameters &searchParams={}) const

Custom-callback radius search.

inline NANOFLANN_NODISCARD Size rknnSearch (const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances, const DistanceType &radius) const

Radius-limited KNN around query_point.

template<typename RESULTSET> inline NANOFLANN_NODISCARD Size findWithinBox (RESULTSET &result, const BoundingBox &bbox) const

Find all live points contained within the box bbox.

Public Types

using Base = typename nanoflann::KDTreeBaseClass<KDTreeSingleIndexIncrementalAdaptor<Distance, DatasetAdaptor, DIM, IndexType>, Distance, DatasetAdaptor, DIM, IndexType>
using ElementType = typename Base::ElementType
using DistanceType = typename Base::DistanceType
using Offset = typename Base::Offset
using Size = typename Base::Size
using Dimension = typename Base::Dimension
using Interval = typename Base::Interval
using BoundingBox = typename Base::BoundingBox
using distance_vector_t = typename Base::distance_vector_t

Public Functions

inline explicit KDTreeSingleIndexIncrementalAdaptor(const Dimension dimensionality, const DatasetAdaptor &inputData, const KDTreeIncrementalIndexParams &params = {})

Constructor.

The tree starts empty regardless of the dataset size; call

addPoints() to insert points (their indices must be valid in inputData).

Parameters:

  • dimensionality – Runtime dimensionality (ignored if DIM>0).

  • inputData – Dataset adaptor; its lifetime must outlive this index.

  • params – Balancing thresholds (see KDTreeIncrementalIndexParams).

KDTreeSingleIndexIncrementalAdaptor(const KDTreeSingleIndexIncrementalAdaptor&) = delete

Deleted copy constructor (owns raw node memory).

KDTreeSingleIndexIncrementalAdaptor &operator=(const KDTreeSingleIndexIncrementalAdaptor&) = delete
inline ~KDTreeSingleIndexIncrementalAdaptor()

Public Members

const DatasetAdaptor &dataset_

The data source used by this index.

Distance distance_

Public Static Attributes

static bool kCacheCoords = (DIM > 0)

Whether per-node coordinate caching is active: only for a compile-time fixed DIM, so the cache is a stack array and adds no per-node heap. Define NANOFLANN_INCREMENTAL_NO_COORD_CACHE to opt out (e.g. a very large ElementType) and always read coordinates from the dataset.

struct INode

Augmented tree node: stores a single data point plus the maintenance metadata. Children pointers are nullptr at the leaves.

Public Members

IndexType ptIdx = 0

index of the stored data point

Dimension divfeat = 0

splitting axis at this node

bool deleted = false

this node’s point is tombstoned

bool treeDeleted = false

whole subtree lazily tombstoned

INode *child1 = nullptr

“< split” child (also free-list link)

INode *child2 = nullptr

“>= split” child

INode *parent = nullptr

parent (nullptr at the root)

Size subtree_size = 0

number of nodes in this subtree

Size invalid_count = 0

number of tombstoned nodes in subtree

BoundingBox box

AABB of all points (live+dead) in this subtree Cache of this node’s own point coordinates, kept in-node to avoid the dataset_get() indirection on the hot query / insert / box paths. Only populated for a compile-time fixed DIM (kCacheCoords); for DIM=-1 it stays an empty vector and the code falls back to the dataset.

array_or_vector<DIM, ElementType>::type pcoord