README.md
1
2
3# nanoflann
4[](https://travis-ci.org/jlblancoc/nanoflann)
5
6
7## 1. About
8
9*nanoflann* is a **C++11 [header-only](http://en.wikipedia.org/wiki/Header-only) library** for building KD-Trees of datasets with different topologies: R<sup>2</sup>, R<sup>3</sup> (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.
10
11This library is a *fork* of the [flann library](http://www.cs.ubc.ca/research/flann/) ([git](https://github.com/mariusmuja/flann)) by Marius Muja and David G. Lowe, and born as a child project of [MRPT](https://www.mrpt.org/). 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.
12
13Cite as:
14```
15@misc{blanco2014nanoflann,
16 title = {nanoflann: a {C}++ header-only fork of {FLANN}, a library for Nearest Neighbor ({NN}) with KD-trees},
17 author = {Blanco, Jose Luis and Rai, Pranjal Kumar},
18 howpublished = {\url{https://github.com/jlblancoc/nanoflann}},
19 year = {2014}
20}
21```
22
23### 1.1. Obtaining the code
24
25* Easiest way: clone this GIT repository and take the `include/nanoflann.hpp` file for use where you need it.
26* macOS users can install `nanoflann` with [Homebrew](https://brew.sh) with:
27 ```shell
28 $ brew install brewsci/science/nanoflann
29 ```
30 or
31 ```shell
32 $ brew tap brewsci/science
33 $ brew install nanoflann
34 ```
35* Linux users can install it with [Linuxbrew](https://linuxbrew.sh/) with: `brew install homebrew/science/nanoflann`
36* List of [**stable releases**](https://github.com/jlblancoc/nanoflann/releases). Check out the [CHANGELOG](https://raw.githubusercontent.com/jlblancoc/nanoflann/master/CHANGELOG.txt)
37
38Although nanoflann itself doesn't have to be compiled, you can build some examples and tests with:
39
40 sudo apt-get install build-essential cmake libgtest-dev libeigen3-dev
41 mkdir build && cd build && cmake ..
42 make && make test
43
44
45### 1.2. C++ API reference
46
47 * Browse the [Doxygen documentation](http://jlblancoc.github.io/nanoflann/).
48
49 * **Important note:** If L2 norms are used, notice that search radius and all passed and returned distances are actually *squared distances*.
50
51### 1.3. Code examples
52
53 * KD-tree look-up with `kdd_search()` and `radius_search()`: [pointcloud_kdd_radius.cpp](https://github.com/jlblancoc/nanoflann/blob/master/examples/pointcloud_kdd_radius.cpp)
54 * KD-tree look-up on a point cloud dataset: [pointcloud_example.cpp](https://github.com/jlblancoc/nanoflann/blob/master/examples/pointcloud_example.cpp)
55 * KD-tree look-up on a dynamic point cloud dataset: [dynamic_pointcloud_example.cpp](https://github.com/jlblancoc/nanoflann/blob/master/examples/dynamic_pointcloud_example.cpp)
56 * KD-tree look-up on a rotation group (SO2): [SO2_example.cpp](https://github.com/jlblancoc/nanoflann/blob/master/examples/SO2_adaptor_example.cpp)
57 * KD-tree look-up on a rotation group (SO3): [SO3_example.cpp](https://github.com/jlblancoc/nanoflann/blob/master/examples/SO3_adaptor_example.cpp)
58 * KD-tree look-up on a point cloud dataset with an external adaptor class: [pointcloud_adaptor_example.cpp](https://github.com/jlblancoc/nanoflann/blob/master/examples/pointcloud_adaptor_example.cpp)
59 * KD-tree look-up directly on an `Eigen::Matrix<>`: [matrix_example.cpp](https://github.com/jlblancoc/nanoflann/blob/master/examples/matrix_example.cpp)
60 * KD-tree look-up directly on `std::vector<std::vector<T> >` or `std::vector<Eigen::VectorXd>`: [vector_of_vectors_example.cpp](https://github.com/jlblancoc/nanoflann/blob/master/examples/vector_of_vectors_example.cpp)
61 * 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/](https://github.com/jlblancoc/nanoflann/blob/master/examples/example_with_pkgconfig/)
62 * Example of how to build an index and save it to disk for later usage: [saveload_example.cpp](https://github.com/jlblancoc/nanoflann/blob/master/examples/saveload_example.cpp)
63
64
65### 1.4. Why a fork?
66
67 * **Execution time efficiency**:
68 * 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](http://www.cs.cmu.edu/~gilpin/c%2B%2B/performance.html#virtualfunctions). In `nanoflann` all those virtual methods have been replaced by a combination of the [Curiously Recurring Template Pattern](http://en.wikipedia.org/wiki/Curiously_recurring_template_pattern) (CRTP) and inlined methods, which are much faster.
69 * 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.
70 * Users can (optionally) set the problem dimensionality at compile-time via a template argument, thus allowing the compiler to fully unroll loops.
71 * `nanoflann` allows users to provide a precomputed bounding box of the data, if available, to avoid recomputation.
72 * Indices of data points have been converted from `int` to `size_t`, which removes a limit when handling very large data sets.
73
74 * **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.
75
76Refer to the examples below or to the C++ API of [nanoflann::KDTreeSingleIndexAdaptor<>](http://jlblancoc.github.io/nanoflann/classnanoflann_1_1KDTreeSingleIndexAdaptor.html) for more info.
77
78
79### 1.5. What can *nanoflann* do?
80
81 * Building KD-trees with a single index (no randomized KD-trees, no approximate searches).
82 * Fast, thread-safe querying for closest neighbors on KD-trees. The entry points are:
83 * [nanoflann::KDTreeSingleIndexAdaptor<>](http://jlblancoc.github.io/nanoflann/classnanoflann_1_1KDTreeSingleIndexAdaptor.html)`::knnSearch()`
84 * 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](https://github.com/jlblancoc/nanoflann/blob/master/examples/pointcloud_kdd_radius.cpp#L119).
85 * [nanoflann::KDTreeSingleIndexAdaptor<>](http://jlblancoc.github.io/nanoflann/classnanoflann_1_1KDTreeSingleIndexAdaptor.html)`::radiusSearch()`
86 * 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](https://github.com/jlblancoc/nanoflann/blob/master/examples/pointcloud_kdd_radius.cpp#L141).
87 * [nanoflann::KDTreeSingleIndexAdaptor<>](http://jlblancoc.github.io/nanoflann/classnanoflann_1_1KDTreeSingleIndexAdaptor.html)`::radiusSearchCustomCallback()`
88 * 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.
89 * Working with 2D and 3D point clouds or N-dimensional data sets.
90 * Working directly with `Eigen::Matrix<>` classes (matrices and vectors-of-vectors).
91 * Working with dynamic point clouds without a need to rebuild entire kd-tree index.
92 * Working with the distance metrics:
93 * `R^N`: Euclidean spaces:
94 * `L1` (Manhattan)
95 * `L2` (**squared** Euclidean norm, favoring SSE2 optimization).
96 * `L2_Simple` (**squared** Euclidean norm, for low-dimensionality data sets like point clouds).
97 * `SO(2)`: 2D rotational group
98 * `metric_SO2`: Absolute angular diference.
99 * `SO(3)`: 3D rotational group (better suppport to be provided in future releases)
100 * `metric_SO3`: Inner product between quaternions.
101 * Saves and load the built indices to disk.
102 * GUI based support for benchmarking multiple kd-tree libraries namely nanoflann, flann, fastann and libkdtree.
103
104### 1.6. What can't *nanoflann* do?
105
106 * Use other distance metrics apart from L1, L2, SO2 and SO3.
107 * Support for SE(3) groups.
108 * Only the C++ interface exists: there is no support for C, MATLAB or Python.
109 * There is no automatic algorithm configuration (as described in the original Muja & Lowe's paper).
110
111### 1.7. Use in your project via CMake
112
113You can directly drop the `nanoflann.hpp` file in your project. Alternatively,
114the CMake standard method is also available:
115
116 * Build and "install" nanoflann. Set `CMAKE_INSTALL_PREFIX` to a proper path
117 and then execute `make install` (Linux, OSX) or build the `INSTALL`
118 target (Visual Studio).
119 * Then, add something like this to the CMake script of your project:
120
121```
122# Find nanoflannConfig.cmake:
123find_package(nanoflann)
124
125add_executable(my_project test.cpp)
126
127# Make sure the include path is used:
128target_link_libraries(my_project nanoflann::nanoflann)
129```
130
131------
132
133## 2. Any help choosing the KD-tree parameters?
134
135### 2.1. `KDTreeSingleIndexAdaptorParams::leaf_max_size`
136
137A 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.
138
139Points (or, properly, point indices) are only stored in leaf nodes. Each leaf contains a list of which points fall within its range.
140
141While 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.
142
143So, `leaf_max_size` must be set as a **tradeoff**:
144 * 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).
145 * 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.
146
147What 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.
148
149But 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).
150
151 * A 100K point cloud, uniformly distributed (each point has (x,y,z) `float` coordinates):
152
153
154
155 * A ~150K point cloud from a real dataset (`scan_071_points.dat` from the [Freiburg Campus 360 dataset](http://ais.informatik.uni-freiburg.de/projects/datasets/fr360/), each point has (x,y,z) `float` coordinates):
156
157
158
159So, 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](http://en.wikipedia.org/wiki/Iterative_closest_point])). At present, its default value is 10.
160
161
162### 2.2. `KDTreeSingleIndexAdaptorParams::checks`
163
164This parameter is really ignored in `nanoflann`, but was kept for backward compatibility with the original FLANN interface. Just ignore it.
165
166-----
167
168## 3. Performance
169
170### 3.1. `nanoflann`: faster and less memory usage
171
172Refer to the "Why a fork?" section above for the main optimization ideas behind `nanoflann`.
173
174Notice 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.
175
176
177### 3.2. Benchmark: original `flann` vs `nanoflann`
178
179The 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.
180
181`nanoflann` provides a ~50% time saving with respect to the original `flann` implementation (times in this chart are in microseconds for each query):
182
183
184
185Although 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):
186
187
188
189These performance tests are only representative of our testing. If you want to repeat them, read the instructions in [perf-tests](https://github.com/jlblancoc/nanoflann/tree/master/perf-tests)
190
191
192----
193
194## 4. Other KD-tree projects
195
196 * [FLANN](http://www.cs.ubc.ca/research/flann/) - Marius Muja and David G. Lowe (University of British Columbia).
197 * [FASTANN](http://www.robots.ox.ac.uk/~vgg/software/fastann/) - James Philbin (VGG, University of Oxford).
198 * [ANN](http://www.cs.umd.edu/~mount/ANN/) - David M. Mount and Sunil Arya (University of Maryland).
199 * [libkdtree++](https://packages.debian.org/source/sid/libkdtree++) - Martin F. Krafft & others.
200
201<br>
202
203*Note: The project logo is due to [CedarSeed](http://www.iconarchive.com/show/patisserie-icons-by-cedarseed/Flan-icon.html)*
204
){kind=link}
){kind=link}
){kind=link}
){kind=link}
){kind=link}
){kind=link}