nanoflann

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}
}

@misc{blanco2014nanoflann,
  title        = {nanoflann: a {C}++ header-only fork of {FLANN}, a library for Nearest Neighbor ({NN}) with KD-trees},
  author       = {Blanco, Jose Luis and Rai, Pranjal Kumar},
  howpublished = {\url{https://github.com/jlblancoc/nanoflann}},
  year         = {2014}
}

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
• KD-tree look-up on a dynamic point cloud dataset (Bentley–Saxe forest): dynamic_pointcloud_example.cpp
• Incremental / sliding-window point cloud index (addPoints + box trimming): pointcloud_incremental_example.cpp
• Exact KD-tree look-up on a rotation group (SO2), C++17: manifold_so2_example.cpp
• Exact KD-tree look-up on a rotation group (SO3), C++17: manifold_so3_example.cpp
• Exact KD-tree look-up on SE(3) poses, C++17: manifold_se3_example.cpp
• Exact KD-tree look-up on the unit sphere S² (3D directions), C++17: manifold_s2_example.cpp
• Incremental KD-tree on SE(3) poses (manifold + churn), C++17: manifold_se3_incremental_example.cpp
• Custom user-defined distance metric: pointcloud_custom_metric.cpp
• Custom user-defined result set (callback-style collection): pointcloud_custom_resultset.cpp
• KD-tree look-up on a point cloud dataset with an external adaptor class: pointcloud_adaptor_example.cpp
• KD-tree look-up directly on an Eigen::Matrix<>: matrix_example.cpp
• KD-tree look-up directly on std::vector<std::vector<T> > or std::vector<Eigen::VectorXd>: vector_of_vectors_example.cpp
• Example with a Makefile for usage through pkg-config (for example, after doing a “make install” or after installing from Ubuntu repositories): example_with_pkgconfig/
• Example of how to build an index and save it to disk for later usage: saveload_example.cpp
• GUI examples (requires mrpt-gui, e.g. sudo apt install libmrpt-gui-dev):
  • nanoflann_gui_example_R3

1.4. Why a fork?

• Execution time efficiency:

  • The power of the original flann library comes from the possibility of choosing between different ANN algorithms. The cost of this flexibility is the declaration of pure virtual methods which (in some circumstances) impose run-time penalties. In nanoflann all those virtual methods have been replaced by a combination of the Curiously Recurring Template Pattern (CRTP) and inlined methods, which are much faster.
  • For radiusSearch(), there is no need to make a call to determine the number of points within the radius and then call it again to get the data. By using STL containers for the output data, containers are automatically resized.
  • Users can (optionally) set the problem dimensionality at compile-time via a template argument, thus allowing the compiler to fully unroll loops.
  • nanoflann allows users to provide a precomputed bounding box of the data, if available, to avoid recomputation.
  • Indices of data points have been converted from int to size_t, which removes a limit when handling very large data sets.

• Memory efficiency: Instead of making a copy of the entire dataset into a custom flann-like matrix before building a KD-tree index, nanoflann allows direct access to your data via an adaptor interface which must be implemented in your class.

Refer to the examples below or to the C++ API of nanoflann::KDTreeSingleIndexAdaptor<> for more info.

1.5. What can nanoflann do?

• Building KD-trees with a single index (no randomized KD-trees). Searches return exact nearest neighbors by default; an optional eps-approximate pruning mode is available via SearchParameters::eps.
• Fast, thread-safe querying for closest neighbors on KD-trees. The entry points are:
  • nanoflann::KDTreeSingleIndexAdaptor<>::knnSearch()
    • Finds the num_closest nearest neighbors to query_point[0:dim-1]. Their indices are stored inside the result object. See an example usage code.
  • nanoflann::KDTreeSingleIndexAdaptor<>::radiusSearch()
    • Finds all the neighbors to query_point[0:dim-1] within a maximum radius. The output is given as a vector of pairs, of which the first element is a point index and the second the corresponding distance. See an example usage code.
  • nanoflann::KDTreeSingleIndexAdaptor<>::radiusSearchCustomCallback()
  • Can be used to receive a callback for each point found in range. This may be more efficient in some situations instead of building a huge vector of pairs with the results.
  • nanoflann::KDTreeSingleIndexAdaptor<>::findWithinBox() [New in 1.8.0]: Optimized search within a given axis-aligned bound box.
• Working with 2D and 3D point clouds or N-dimensional data sets.
• Working with integral element types, including unsigned ones. Since _DistanceType defaults to the element type and must be signed, an unsigned element type requires passing it explicitly, wide enough for the distances of the actual coordinate range, e.g. nanoflann::L2_Simple_Adaptor<uint8_t, MyCloud, int32_t>. To use it through the nanoflann::metric_* tags, define your own tag:

  struct my_metric_L2 : public nanoflann::Metric
  {
      template <class T, class DataSource, typename IndexType = size_t>
      struct traits
      {
          using distance_t = nanoflann::L2_Simple_Adaptor<T, DataSource, int32_t, IndexType>;
      };
  };
  

• Working directly with Eigen::Matrix<> classes (matrices and vectors-of-vectors).
• Working with dynamic point clouds without a need to rebuild entire kd-tree index. Two options:
  • nanoflann::KDTreeSingleIndexDynamicAdaptor<>: the Bentley–Saxe “logarithmic forest” of static sub-trees.
  • nanoflann::KDTreeSingleIndexIncrementalAdaptor<> [New]: a single self-balancing tree, recommended for sliding-window LiDAR-style maps. Supports incremental addPoints, lazy removePoint, and axis-aligned box trimming (removeBox / removeOutsideBox) with bounded memory under churn. See the design & benchmark report in nanoflann-benchmark/incrementalTests.
  • nanoflann::KDTreeSingleIndexIncrementalAdaptorMT<> [New]: the same index with the large rebalancing rebuilds offloaded to a background thread, to bound the foreground update-latency tail (see the threading analysis). Disabled under NANOFLANN_NO_THREADS.
• Working with the distance metrics:
  • R^N: Euclidean spaces:
    • L1 (Manhattan)
    • L2 (squared Euclidean norm, favoring SSE2 optimization).
    • L2_Simple (squared Euclidean norm, for low-dimensionality data sets like point clouds).
  • SO(2) / SO(3) rotational groups and other non-Euclidean spaces are now handled exactly by the compile-time product-manifold metrics below. (The legacy metric_SO2 / metric_SO3 adaptors were removed in 2.0: they kept Euclidean pruning (wrong across the +/-pi seam) and ignored the quaternion double cover. Use metric_Manifold<SO2> / metric_Manifold<SO3> instead.)
  • Compile-time product manifolds [New, C++17]: declare the search space as a product of base manifolds and get exact nearest neighbors honoring the correct geodesic metric and pruning. Base spaces: nanoflann::Rn<N>, SO2, SO3, SE2, SE3, Torus<N>, the unit sphere Sn<N> / S2 (3D directions / bearings), and arbitrary Product<...> (e.g. Product<Rn<3>, S2> for oriented points). Use the synthesized nanoflann::Manifold_Adaptor<Space, T, Dataset> (or metric_Manifold<Space>) as the distance type. Supported by both the static KDTreeSingleIndexAdaptor and the incremental KDTreeSingleIndexIncrementalAdaptor (and its MT wrapper). See examples/manifold_se3_example.cpp, examples/manifold_s2_example.cpp, and examples/manifold_se3_incremental_example.cpp. Opt out with NANOFLANN_NO_MANIFOLDS.
• Saves and load the built indices to disk.
• GUI based support for benchmarking multiple kd-tree libraries namely nanoflann, flann, fastann and libkdtree.

1.6. What can’t nanoflann do?

• Use other distance metrics apart from L1, L2, and the compile-time product manifolds (R^n, SO(2), SO(3), SE(2), SE(3), S^N, tori, and products).
• Only the C++ interface exists: there is no support for C, MATLAB or Python.
• There is no automatic algorithm configuration (as described in the original Muja & Lowe’s paper).

1.7. Use in your project via CMake

You can directly drop the nanoflann.hpp file in your project. Alternatively, the CMake standard method is also available:

• Build and “install” nanoflann. Set CMAKE_INSTALL_PREFIX to a proper path and then execute make install (Linux, OSX) or build the INSTALL target (Visual Studio).
• Then, add something like this to the CMake script of your project:

# Find nanoflannConfig.cmake:
find_package(nanoflann)

add_executable(my_project test.cpp)

# Make sure the include path is used:
target_link_libraries(my_project nanoflann::nanoflann)

1.8. Package Managers

Using conan

You can install pre-built binaries for nanoflann or build it from source using Conan. Use the following command to install latest version:

$ conan install --requires="nanoflann/[*]" --build=missing

For detailed instructions on how to use Conan, please refer to the Conan documentation.

The nanoflann Conan recipe is kept up to date by Conan maintainers and community contributors. If the version is out of date, please create an issue or pull request on the ConanCenterIndex repository.

Using vcpkg

You can download and install nanoflann using the vcpkg dependency manager:

$ git clone https://github.com/Microsoft/vcpkg.git
$ cd vcpkg
$ ./bootstrap-vcpkg.sh
$ ./vcpkg integrate install
$ ./vcpkg install nanoflann

The nanoflann port in vcpkg is kept up to date by Microsoft team members and community contributors. If the version is out of date, please create an issue or pull request on the vcpkg repository.

1.9. Compile time definitions

• NANOFLANN_FIRST_MATCH: If defined and two points have the same distance, the one with the lowest-index will be returned first. Otherwise there is no particular order.
• NANOFLANN_NO_THREADS: If defined, multithreading capabilities will be disabled, so that the library can be used without linking with pthreads. If one tries to use multiple threads, an exception will be thrown.
• NANOFLANN_NODE_ALIGNMENT: The memory alignment, in bytes, used for KD-tree nodes. Must be a power of two and >= 8. Defaults to 16 (also a good value for AVX; use 32/64 for AVX/AVX-512 aligned loads). Every node honors this alignment, with any C++ standard.
• NANOFLANN_NO_MANIFOLDS: If defined, disables the C++17 product-manifold topology support (Manifold_Adaptor, Product<>, SO2/SO3/SE2/SE3/Sn/Torus, metric_Manifold<>). It is auto-enabled under C++17; define this to force it off (the C++11 Euclidean core is unaffected).
• NANOFLANN_INCREMENTAL_NO_COORD_CACHE: If defined, the incremental index does not keep a per-node contiguous copy of point coordinates (trades query speed for memory).
• NANOFLANN_INCREMENTAL_INNODE_DISTANCE: If defined, the (Euclidean) incremental index reuses the per-axis coordinate cache for the in-node distance. Has no effect for manifold metrics, which always use the full evalMetric.

1.10. Thread safety

• Index build: pass n_thread_build > 1 in KDTreeSingleIndexAdaptorParams to parallelize the build via std::async (unless NANOFLANN_NO_THREADS is defined).
• Queries: findNeighbors(), knnSearch(), radiusSearch() and rknnSearch() are const and safe to call concurrently from multiple threads on the same index, as long as no thread is concurrently building or modifying it.
• Building an index from multiple threads (or mixing queries with an in-progress build) is not supported.

2. Any help choosing the KD-tree parameters?

2.1. KDTreeSingleIndexAdaptorParams::leaf_max_size

A KD-tree is… well, a tree :-). And as such it has a root node, a set of intermediary nodes and finally, “leaf” nodes which are those without children.

Points (or, properly, point indices) are only stored in leaf nodes. Each leaf contains a list of which points fall within its range.

While building the tree, nodes are recursively divided until the number of points inside is equal or below some threshold. That is leaf_max_size. While doing queries, the “tree algorithm” ends by selecting leaf nodes, then performing linear search (one-by-one) for the closest point to the query within all those in the leaf.

So, leaf_max_size must be set as a tradeoff:

• Large values mean that the tree will be built faster (since the tree will be smaller), but each query will be slower (since the linear search in the leaf is to be done over more points).
• Small values will build the tree much slower (there will be many tree nodes), but queries will be faster… up to some point, since the “tree-part” of the search (logarithmic complexity) still has a significant cost.

What number to select really depends on the application and even on the size of the processor cache memory, so ideally you should do some benchmarking for maximizing efficiency.

But to help choosing a good value as a rule of thumb, I provide the following two benchmarks. Each graph represents the tree build (horizontal) and query (vertical) times for different leaf_max_size values between 1 and 10K (as 95% uncertainty ellipses, deformed due to the logarithmic scale).

• A 100K point cloud, uniformly distributed (each point has (x,y,z) float coordinates):

• A ~150K point cloud from a real dataset (scan_071_points.dat from the Freiburg Campus 360 dataset, each point has (x,y,z) float coordinates):

So, it seems that a leaf_max_size between 10 and 50 would be optimum in applications where the cost of queries dominates (e.g. ICP). At present, its default value is 10.

2.2. KDTreeSingleIndexAdaptorParams::checks

This parameter is really ignored in nanoflann, but was kept for backward compatibility with the original FLANN interface. Just ignore it.

2.3. KDTreeSingleIndexAdaptorParams::n_thread_build

This parameter determines the maximum number of threads that can be called concurrently during the construction of the KD tree. The default value is 1. When the parameter is set to 0, nanoflann automatically determines the number of threads to use.

See this pull request for some benchmarking showing that using the maximum number of threads is not always the most efficient approach. Do benchmarking on your data!

3. Performance

3.1. nanoflann: faster and less memory usage

Refer to the “Why a fork?” section above for the main optimization ideas behind nanoflann.

Notice that there are no explicit SSE2/SSE3 optimizations in nanoflann, but the intensive usage of inline and templates in practice turns into automatically SSE-optimized code generated by the compiler.

3.2. Benchmark: original flann vs nanoflann

The most time-consuming part of many point cloud algorithms (like ICP) is querying a KD-Tree for nearest neighbors. This operation is therefore the most time critical.

nanoflann provides a ~50% time saving with respect to the original flann implementation (times in this chart are in microseconds for each query):

Although most of the gain comes from the queries (due to the large number of them in any typical operation with point clouds), there is also some time saved while building the KD-tree index, due to the templatized-code but also for the avoidance of duplicating the data in an auxiliary matrix (times in the next chart are in milliseconds):

These performance tests are only representative of our testing. If you want to repeat them, read the instructions in perf-tests

4. Releasing a new version (maintainers only)

The version number is duplicated in include/nanoflann.hpp (two macros), package.xml, the CHANGELOG.rst header and the git tag. scripts/release.py keeps all of them in sync:

scripts/release.py check                   # verify all sources agree (also run in CI)
scripts/release.py prepare --bump minor    # or: --version 1.12.0, and --dry-run

prepare runs catkin_generate_changelog, pauses for you to edit the Forthcoming section, then calls catkin_prepare_release and folds the header macro bump into the same release commit and tag. Nothing is pushed: the script prints the remaining git push and bloom-release commands.

Pushing the tag triggers the Create GitHub release workflow, which publishes a GitHub release with the notes taken from that version’s CHANGELOG.rst entry (scripts/release.py notes renders it as Markdown).

5. Other KD-tree projects

• FLANN - Marius Muja and David G. Lowe (University of British Columbia).
• FASTANN - James Philbin (VGG, University of Oxford).
• ANN - David M. Mount and Sunil Arya (University of Maryland).
• libkdtree++ - Martin F. Krafft & others.

Note: The project logo is due to CedarSeed

Contributors