The most up-to-date version of this page will be always available at: http://code.google.com/p/nanoflann/

1. About

nanoflann is a C++ header-only library for building KD-Trees, mostly optimized for 2D or 3D point clouds. Queries for neighbors around any arbitrary location in space can then be solved quickly and efficiently using Approximate Nearest Neighbor (ANN) algorithms.

nanoflann does not require compiling or installing, just an #include <nanoflann.hpp> in your code.

This library is a fork (and a subset) of the `flann` library, by Marius Muja and David G. Lowe, born as a child project of MRPT. Following the original license terms, nanoflann is distributed under the BSD license. If you want to contact me for reporting any issue or patch, write to joseluisblancoc@gmail.com

1.1. Obtaining the code

Latest stable release: (Feb 1st, 2012)

PPA Ubuntu repositories (web):

sudo add-apt-repository ppa:joseluisblancoc/nanoflann
sudo apt-get update
sudo apt-get install libnanoflann-dev

Unstable SVN version (browse online):

   # Check out a read-only working copy anonymously over HTTP:
   svn checkout http://nanoflann.googlecode.com/svn/trunk/ nanoflann-svn

1.2. C++ API reference

http://nanoflann-reference.mrpt.org/svn/

1.3. 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 to pay 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 anymore to make a first call to determine the number of points within the radius, then call it again to get the data. By using STL containers for the output data, containers are automatically resized.
Users can (optionally) fix the problem dimensionality at compile-time via a template argument, thus allowing the compiler to fully unroll loops.
Also, nanoflann allows users to provide a precomputed bounding box of the data, if available, to avoid recomputing it again.
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 you to directly working on your class 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.4. What can `nanoflann` do?

Building KD-trees with a single index (no randomized KD-trees).
Fast querying for neighbors on KD-trees. The two main entry points are:

nanoflann::KDTreeSingleIndexAdaptor<>::knnSearch()
nanoflann::KDTreeSingleIndexAdaptor<>::radiusSearch()

Define the dimensionality of the data at compile time, easing the generation of optimized code by the compiler.
Work with 2D and 3D point clouds or N-dimensional data sets.
Directly work with Eigen::Matrix<> classes.
Work with the distance metrics: L1 (Manhattan), L2 (Euclidean, favoring SSE2 optimization) and L2_Simple (Euclidean, for low-dimensionality data sets like point clouds).

1.5. What can't `nanoflann` do?

Using other distance metrics apart from L1 and L2.
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).
The data in the source (data set) object is assumed not to vary during the execution of kd-tree queries. If this cannot be assured, the data set should be duplicated by the user and nanoflann applied to the copy. However, this is not the case in many practical applications.

1.6. Code examples

KD-tree look-up with kdd_search() and radius_search(): pointcloud_kdd_radius.cpp
KD-tree look-up on a point cloud dataset: pointcloud_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

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/

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.

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 orientative. If you want to repeat them, read the instructions in http://nanoflann.googlecode.com/svn/trunk/perf-tests/

4. 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