nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType > Class Template Reference

#include <nanoflann.hpp>

Inheritance diagram for nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >:

Classes
struct	INode

Public Types
using	Base
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 Types inherited from nanoflann::KDTreeBaseClass< KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, -1, uint32_t >, Distance, DatasetAdaptor, -1, uint32_t >
using	ElementType
using	DistanceType
using	IndexType
using	Offset
using	Size
using	Dimension
using	NodePtr
using	NodeConstPtr
using	BoundingBox
using	distance_vector_t

Public Member Functions
	KDTreeSingleIndexIncrementalAdaptor (const Dimension dimensionality, const DatasetAdaptor &inputData, const KDTreeIncrementalIndexParams &params={})
	KDTreeSingleIndexIncrementalAdaptor (const KDTreeSingleIndexIncrementalAdaptor &)=delete
KDTreeSingleIndexIncrementalAdaptor &	operator= (const KDTreeSingleIndexIncrementalAdaptor &)=delete
Modifiers
void	addPoint (IndexType idx)
void	addPoints (IndexType start, IndexType end)
void	removePoint (IndexType idx)
void	removeBox (const BoundingBox &box)
void	removeOutsideBox (const BoundingBox &keep)
void	setCollectRemovedPoints (bool enable)
std::vector< IndexType >	acquireRemovedPoints ()
void	setInlineRebuild (bool enable)
void	snapshotLiveIndices (std::vector< IndexType > &out) const
void	collectPhysicalIndices (std::vector< IndexType > &out) const
NANOFLANN_NODISCARD bool	referencesIndex (IndexType idx) const
void	buildFromIndices (const std::vector< IndexType > &idxs)
Capacity / observers
NANOFLANN_NODISCARD Size	size () const noexcept
NANOFLANN_NODISCARD bool	empty () const noexcept
NANOFLANN_NODISCARD Size	physicalSize () const noexcept
NANOFLANN_NODISCARD Size	usedMemory () const
NANOFLANN_NODISCARD BoundingBox	boundingBox () const
void	reserve (Size n)
Query methods
template<typename RESULTSET>
bool	findNeighbors (RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
NANOFLANN_NODISCARD Size	knnSearch (const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances, const SearchParameters &searchParams={}) const
NANOFLANN_NODISCARD Size	radiusSearch (const ElementType *query_point, const DistanceType &radius, std::vector< ResultItem< IndexType, DistanceType > > &IndicesDists, const SearchParameters &searchParams={}) const
template<class SEARCH_CALLBACK>
NANOFLANN_NODISCARD Size	radiusSearchCustomCallback (const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParameters &searchParams={}) const
NANOFLANN_NODISCARD Size	rknnSearch (const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances, const DistanceType &radius) const
template<typename RESULTSET>
NANOFLANN_NODISCARD Size	findWithinBox (RESULTSET &result, const BoundingBox &bbox) const
Public Member Functions inherited from nanoflann::KDTreeBaseClass< KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, -1, uint32_t >, Distance, DatasetAdaptor, -1, uint32_t >
void	freeIndex (KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj)
NANOFLANN_NODISCARD Size	size (const KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj) const noexcept
NANOFLANN_NODISCARD Size	veclen (const KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj) const noexcept
ElementType	dataset_get (const KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, IndexType element, Dimension component) const
	Helper accessor to the dataset points:
NANOFLANN_NODISCARD Size	usedMemory (const KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj) const
void	computeMinMax (const KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, Offset ind, Size count, Dimension element, ElementType &min_elem, ElementType &max_elem) const
NANOFLANN_NODISCARD bool	isActive (IndexType) const
void	computeBoundingBox (BoundingBox &bbox)
bool	searchLevel (RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindist, distance_vector_t &dists, const DistanceType epsError) const
bool	makeNode (KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, NodePtr node, const Offset left, const Offset right, BoundingBox &bbox, Offset &idx, Dimension &cutfeat, DistanceType &cutval)
void	finalizeSplitNode (KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, NodePtr node, const Dimension cutfeat, const BoundingBox &left_bbox, const BoundingBox &right_bbox, BoundingBox &bbox)
NodePtr	divideTree (KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, const Offset left, const Offset right, BoundingBox &bbox)
NodePtr	divideTreeConcurrent (KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, const Offset left, const Offset right, BoundingBox &bbox, std::atomic< unsigned int > &thread_count, std::mutex &mutex)
void	middleSplit_ (const KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, const Offset ind, const Size count, Offset &index, Dimension &cutfeat, DistanceType &cutval, const BoundingBox &bbox)
void	planeSplit (const KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, const Offset ind, const Size count, const Dimension cutfeat, const DistanceType &cutval, Offset &lim1, Offset &lim2)
DistanceType	computeInitialDistances (const KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, const ElementType *vec, distance_vector_t &dists) const
void	saveIndex (const KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, std::ostream &stream) const
void	loadIndex (KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, std::istream &stream)

Public Attributes
const DatasetAdaptor &	dataset_
Distance	distance_
Public Attributes inherited from nanoflann::KDTreeBaseClass< KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, -1, uint32_t >, Distance, DatasetAdaptor, -1, uint32_t >
std::vector< IndexType >	vAcc_
NodePtr	root_node_
Size	leaf_max_size_
Size	n_thread_build_
	Number of thread for concurrent tree build.
Size	size_
	Number of current points in the dataset.
Size	size_at_index_build_
	Number of points in the dataset when the index was built.
Dimension	dim_
	Dimensionality of each data point.
BoundingBox	root_bbox_
PooledAllocator	pool_

Static Public Attributes
static constexpr bool	kCacheCoords = (DIM > 0)
Static Public Attributes inherited from nanoflann::KDTreeBaseClass< KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, -1, uint32_t >, Distance, DatasetAdaptor, -1, uint32_t >
static constexpr uint32_t	SAVE_MAGIC

Additional Inherited Members
Static Public Member Functions inherited from nanoflann::KDTreeBaseClass< KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, -1, uint32_t >, Distance, DatasetAdaptor, -1, uint32_t >
static void	save_tree (const KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, std::ostream &stream, const NodeConstPtr tree)
static void	load_tree (KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, std::istream &stream, NodePtr &tree)

Detailed Description

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

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.

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

Member Typedef Documentation

Base

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

using nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Base

Initial value:

 typename nanoflann::KDTreeBaseClass<
        KDTreeSingleIndexIncrementalAdaptor<Distance, DatasetAdaptor, DIM, IndexType>, Distance,
        DatasetAdaptor, DIM, IndexType>

Constructor & Destructor Documentation

KDTreeSingleIndexIncrementalAdaptor() [1/2]

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::KDTreeSingleIndexIncrementalAdaptor ( const Dimension dimensionality, const DatasetAdaptor & inputData, const KDTreeIncrementalIndexParams & params = {} )

inlineexplicit

Constructor.

Parameters

dimensionality	Runtime dimensionality (ignored if DIM>0).
inputData	Dataset adaptor; its lifetime must outlive this index.
params	Balancing thresholds (see KDTreeIncrementalIndexParams).

The tree starts empty regardless of the dataset size; call addPoints() to insert points (their indices must be valid in inputData).

KDTreeSingleIndexIncrementalAdaptor() [2/2]

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::KDTreeSingleIndexIncrementalAdaptor ( const KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType > & )

delete

Deleted copy constructor (owns raw node memory).

Member Function Documentation

acquireRemovedPoints()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

std::vector< IndexType > nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::acquireRemovedPoints ( )

inline

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

addPoint()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

void nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::addPoint ( IndexType idx )

inline

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

addPoints()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

void nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::addPoints ( IndexType start, IndexType end )

inline

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.

boundingBox()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

NANOFLANN_NODISCARD BoundingBox nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::boundingBox ( ) const

inline

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

buildFromIndices()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

void nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::buildFromIndices ( const std::vector< IndexType > & idxs )

inline

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.

collectPhysicalIndices()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

void nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::collectPhysicalIndices ( std::vector< IndexType > & out ) const

inline

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.

findNeighbors()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

template<typename RESULTSET>

bool nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::findNeighbors ( RESULTSET & result, const ElementType * vec, const SearchParameters & searchParams = {} ) const

inline

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

findWithinBox()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

template<typename RESULTSET>

NANOFLANN_NODISCARD Size nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::findWithinBox ( RESULTSET & result, const BoundingBox & bbox ) const

inline

Find all live points contained within the box bbox.

knnSearch()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

NANOFLANN_NODISCARD Size nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::knnSearch ( const ElementType * query_point, const Size num_closest, IndexType * out_indices, DistanceType * out_distances, const SearchParameters & searchParams = {} ) const

inline

Find the num_closest nearest neighbors to query_point.

physicalSize()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

NANOFLANN_NODISCARD Size nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::physicalSize ( ) const

inlinenoexcept

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

radiusSearch()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

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

inline

Radius search around query_point.

radiusSearchCustomCallback()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

template<class SEARCH_CALLBACK>

NANOFLANN_NODISCARD Size nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::radiusSearchCustomCallback ( const ElementType * query_point, SEARCH_CALLBACK & resultSet, const SearchParameters & searchParams = {} ) const

inline

Custom-callback radius search.

referencesIndex()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

NANOFLANN_NODISCARD bool nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::referencesIndex ( IndexType idx ) const

inline

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

removeBox()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

void nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::removeBox ( const BoundingBox & box )

inline

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

removeOutsideBox()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

void nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::removeOutsideBox ( const BoundingBox & keep )

inline

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

removePoint()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

void nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::removePoint ( IndexType idx )

inline

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

reserve()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

void nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::reserve ( Size n )

inline

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

rknnSearch()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

NANOFLANN_NODISCARD Size nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::rknnSearch ( const ElementType * query_point, const Size num_closest, IndexType * out_indices, DistanceType * out_distances, const DistanceType & radius ) const

inline

Radius-limited KNN around query_point.

setCollectRemovedPoints()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

void nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::setCollectRemovedPoints ( bool enable )

inline

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

setInlineRebuild()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

void nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::setInlineRebuild ( bool enable )

inline

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.

size()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

NANOFLANN_NODISCARD Size nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::size ( ) const

inlinenoexcept

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

snapshotLiveIndices()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

void nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::snapshotLiveIndices ( std::vector< IndexType > & out ) const

inline

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

usedMemory()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

NANOFLANN_NODISCARD Size nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::usedMemory ( ) const

inline

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

Member Data Documentation

dataset_

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

const DatasetAdaptor& nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::dataset_

The data source used by this index.

kCacheCoords

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>

bool nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::kCacheCoords = (DIM > 0)

staticconstexpr

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.

---

The documentation for this class was generated from the following file:

• include/nanoflann.hpp