nanoflann

Distro	Build dev	Build releases	Stable version
ROS 2 Humble (u22.04)
ROS 2 Jazzy (u24.04)
ROS 2 Kilted (u24.04)
ROS 2 Lyrical (u26.04)
ROS 2 Rolling (u26.04)

(Binary build badges are for amd64 and arm64, respectively)

1. About

nanoflann is a header-only C++ library for building KD-Trees of datasets with different topologies. The Euclidean core (R², R³, R^N point clouds) is C++11; the optional compile-time product-manifold metrics — SO(2), SO(3), SE(2), SE(3), the unit sphere S²/S^N, tori, and arbitrary products — require C++17 (see §1.5). It also provides incremental / dynamic KD-tree indices for point clouds that change over time (e.g. sliding-window LiDAR maps). nanoflann returns exact nearest neighbors by default (an optional eps-approximate mode is available via SearchParameters::eps). It does not require compiling or installing: you just need to #include <nanoflann.hpp> in your code.

This library is a fork of the flann library by Marius Muja and David G. Lowe, and born as a child project of MRPT. Following the original license terms, nanoflann is distributed under the BSD license. Please, for bugs use the issues button or fork and open a pull request.

Citing nanoflann

If you use nanoflann in your research, please cite the following paper (published in IEEE RA-L, 2026):

J.L. Blanco-Claraco, “nanoflann: A Header-Only KD-Tree Library for Exact Nearest-Neighbor Search on Compile-Time Product Manifolds,” IEEE Robotics and Automation Letters, 2026, doi: 10.1109/LRA.2026.3747624. IEEE Xplore. Preprint (fallback): arXiv:2610.15215.

@article{blancoclaraco2026nanoflann,
  title   = {nanoflann: A Header-Only {KD}-Tree Library for Exact Nearest-Neighbor Search on Compile-Time Product Manifolds},
  author  = {Blanco-Claraco, Jose Luis},
  journal = {IEEE Robotics and Automation Letters},
  year    = {2026},
  doi     = {10.1109/LRA.2026.3747624},
  url     = {https://ieeexplore.ieee.org/document/11753906},
  note    = {Preprint: arXiv:2610.15215}
}

See the release CHANGELOG for a list of project changes.

1.1. Obtaining the code

• Easiest way: clone this GIT repository and take the include/nanoflann.hpp file for use where you need it.
• Debian or Ubuntu (21.04 or newer) users can install it simply with:

  $ sudo apt install libnanoflann-dev
  

• macOS users can install nanoflann with Homebrew with:

  $ brew install brewsci/science/nanoflann
  

or

  $ brew tap brewsci/science
  $ brew install nanoflann
  

MacPorts users can use:

  $ sudo port install nanoflann
  

• Linux users can also install it with Linuxbrew with: brew install homebrew/science/nanoflann
• conda-forge users (Linux, macOS, Windows): conda install -c conda-forge nanoflann
• List of stable releases. Check out the CHANGELOG

Although nanoflann itself doesn’t have to be compiled, you can build some examples and tests with:

$ sudo apt-get install build-essential cmake libgtest-dev libeigen3-dev
$ mkdir build && cd build && cmake ..
$ make && make test

1.2. C++ API reference

• Browse the Doxygen documentation.

• Important note: If L2 norms are used, notice that search radius and all passed and returned distances are actually squared distances.

1.3. Code examples

File truncated at 100 lines see the full file

Changelog for package nanoflann

2.0.1 (2026-10-12)

• Merge pull request #322 from jlblancoc/fix/planesplit-build-regression Fix single-thread build regression: restore two-pass partition in planeSplit()
• Restore two-pass Hoare partition in planeSplit() The one-pass three-way partition introduced in 1.9.0 swaps almost every element it visits, while the previous two-pass scheme only swaps misplaced pairs (about 7x fewer swaps on LiDAR data). This made the single-thread KD-tree build 9-12% slower than in 1.8.0. The two-pass version is restored over half-open ranges, so it stays safe for unsigned Offset types, and keeps comparing coordinates in DistanceType. Results are unchanged. A new test exercises heavy ties on the split planes, where all three partition regions are populated.
• fix test warnings for ignored return values
• Contributors: Jose Luis Blanco Claraco, Jose Luis Blanco-Claraco

2.0.0 (2026-10-11)

• Add compile-time product-manifold metrics (SO2, SO3, SE2, SE3, S\^N, tori and products) for exact non-Euclidean nearest-neighbor search (C++17, opt out with NANOFLANN_NO_MANIFOLDS). Supported by the static and the incremental KD-trees.
• Tighter block-level pruning bound for SO(3), up to ~28x faster queries on rotation-heavy data.
• Add NANOFLANN_INCREMENTAL_NO_FREELIST (ablation-only) switch.
• Breaking: remove the legacy SO2_Adaptor / SO3_Adaptor metrics, superseded by Manifold_Adaptor. SO(2) and SO(3) now require C++17; C++11 users needing the old metrics should stay on nanoflann 1.x.
• Honor NANOFLANN_NODE_ALIGNMENT > 16 in the node array before C++17 and in PooledAllocator (#321).
• Robustness and performance: reject corrupt vector sizes in load_value(), cheaper post-deletion rebalancing in the incremental index, radius results sorted once in the dynamic adaptor.
• KDTreeEigenMatrixAdaptor now owns its index via std::unique_ptr.
• New examples (SE3, S2, incremental Euclidean and manifold) and tests (Eigen adaptor, radius boundary, incremental manifolds); CI matrix for the compile-time macros.
• Docs: README and Doxygen refresh, clarify that chord_sq_to_angle returns an arc angle.
• Remove dead Travis CI files; add a release helper script.
• Contributors: Jose Luis Blanco-Claraco

1.14.0 (2026-09-25)

• Store kd-tree nodes in one contiguous std::vector instead of pointer-linked allocations, shrinking Node and speeding up kNN queries and builds (#319).
• Gather split coordinates once into a scratch array reused across builds, avoiding a second pass over the dataset in middleSplit().
• Release node memory in freeIndex() and cap the node reservation at 2N.
• loadIndex() now validates the loaded node array and rejects corrupt files.
• Concurrent build: splice only the subtrees actually built by a task, avoiding unnecessary memmoves.
• Prefetch the right child while descending the tree, improving kNN query speed.
• CI Linux: do not upgrade runner packages before installing build tools (#320).
• Contributors: Jose Luis Blanco-Claraco, Luca Bartoli

1.13.0 (2026-09-17)

• Merge pull request #318 from spyridon97/improve-build-multithreading Rewrite nanoflann's concurrent index build At 16 threads, index build time drops ~3.5x on uniform data (79ms -> 23ms) and ~3.8x on clustered data (108ms -> 29ms).
• Merge pull request #317 from jschueller/mtune CMake: Check for mtune=native flag For some archs like ppc64 this is not always available
• Merge pull request #315 from jlblancoc/fix/unsigned-elementtype-crash Fix crash and wrong results with unsigned ElementType (alternative to #314)
• fix: compute all coordinate differences in DistanceType
• Contributors: Jose Luis Blanco-Claraco, Julien Schueller, Spiros Tsalikis

1.12.1 (2026-08-08)

• docs: badges updates to use nanoflann_vendor
• Merge pull request #313 from jlblancoc/chore/rename-ros-package-to-nanoflann-vendor chore(ros): rename the ROS package to nanoflann_vendor Only the ROS package name changes. The CMake package name comes from the CMake project, so find_package(nanoflann) keeps working unchanged.

File truncated at 100 lines see the full file