nanoflann

nanoflann

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

1. About

nanoflann is a C++11 header-only library for building KD-Trees of datasets with different topologies: R2, R3 (point clouds), SO(2) and SO(3) (2D and 3D rotation groups). No support for approximate NN is provided. nanoflann 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.

Cite as:

@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
• 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: dynamic_pointcloud_example.cpp
• KD-tree look-up on a rotation group (SO2): SO2_example.cpp
• KD-tree look-up on a rotation group (SO3): SO3_example.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, no approximate searches).
• 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