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 (accepted for publication 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 (accepted).

@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},
  note    = {Accepted for publication}
}

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

• KD-tree look-up with knnSearch() and radiusSearch(): pointcloud_kdd_radius.cpp
• KD-tree look-up on a point cloud dataset: pointcloud_example.cpp

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