nanoflann

After building and installing nanoflann (setting CMAKE_INSTALL_PREFIX as needed), you can integrate it into your CMake project using find_package and linking against the nanoflann::nanoflann target.

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

The examples/examples_gui directory contains example programs that provide a live GUI visualization of matches found by nanoflann.

To use these examples, you must have mrpt-gui installed as a dependency.

Each subdirectory within this directory can be compiled as an independent project by setting the CMake SOURCE_DIR to that specific subdirectory.

Although nanoflann is a header-only library and does not require compilation to use, you can build the included examples and tests using CMake if you have the necessary dependencies installed (build-essential, cmake, libgtest-dev, and libeigen3-dev).

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

You can install nanoflann using various package managers depending on your operating system:

• Debian/Ubuntu: sudo apt install libnanoflann-dev
• macOS (Homebrew):

  brew tap brewsci/science
  brew install nanoflann

• macOS (MacPorts): sudo port install nanoflann
• Linux (Linuxbrew): brew install homebrew/science/nanoflann
• Conan: conan install --requires="nanoflann/[*]" --build=missing
• vcpkg:

  ./vcpkg install nanoflann

The leaf_max_size parameter controls the threshold for dividing nodes during KD-tree construction. Points are stored in leaf nodes, and queries perform a linear search within these leaves.

This parameter is a tradeoff:

• Large values: Faster tree construction (smaller tree) but slower queries (more points to search linearly in each leaf).
• Small values: Slower tree construction (more nodes) but faster queries (up to a point where tree traversal overhead dominates).

Rule of thumb: For applications where query cost dominates (e.g., ICP), a value between 10 and 50 is often optimal. The default value is 10.

You can control library behavior using the following preprocessor definitions:

• NANOFLANN_FIRST_MATCH: If two points have the same distance, the one with the lowest index is returned first.
• NANOFLANN_NO_THREADS: Disables multithreading capabilities. This allows using the library without linking against pthreads. Attempting to use multiple threads will throw an exception.
• NANOFLANN_NODE_ALIGNMENT: Sets the memory alignment in bytes for KD-tree nodes (defaults to 16).

The n_thread_build parameter determines the maximum number of threads used concurrently during the construction of the KD tree.

• Default: 1
• Automatic threading: Set the value to 0 to let nanoflann automatically determine the optimal number of threads.

Note: Using the maximum number of threads is not always the most efficient approach; benchmarking is recommended for your specific data.

For datasets that change over time, nanoflann provides two main adaptors:

• nanoflann::KDTreeSingleIndexDynamicAdaptor<>: Uses a Bentley–Saxe "logarithmic forest" of static sub-trees.
• nanoflann::KDTreeSingleIndexIncrementalAdaptor<>: A single self-balancing tree recommended for sliding-window LiDAR-style maps. Supports addPoints, lazy removePoint, and axis-aligned box trimming (removeBox / removeOutsideBox).
• nanoflann::KDTreeSingleIndexIncrementalAdaptorMT<>: The incremental adaptor with large rebalancing rebuilds offloaded to a background thread to bound update latency. This is disabled if NANOFLANN_NO_THREADS is defined.

The nanoflann::KDTreeSingleIndexAdaptor<> class provides several methods for querying nearest neighbors:

• knnSearch(): Finds the num_closest nearest neighbors to a query point. Indices are stored in the result object.
• radiusSearch(): Finds all neighbors within a maximum radius. Returns a vector of pairs (point index, distance).
• radiusSearchCustomCallback(): Uses a callback for each point found in range, which can be more efficient than building a large result vector.
• findWithinBox(): Optimized search within an axis-aligned bounding box.

Important: When using L2 norms, the search radius and all returned distances are squared distances.

Understanding thread safety for nanoflann operations:

• Index Build: Parallelize the build by passing n_thread_build > 1 in KDTreeSingleIndexAdaptorParams (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, provided no thread is concurrently building or modifying the index.
• Warning: The internal PooledAllocator is not thread-safe. Do not build an index from multiple threads or mix queries with an in-progress build.