PicoTree

PicoTree is a C++ header only library with Python bindings for nearest neighbor searches and range searches using a KdTree.

See the table below to get an impression of the performance provided by the KdTree of this library versus several other implementations:

	Build C++	Build Python	Knn C++	Knn Python
nanoflann v1.3.2	1.5s	...	3.2s	...
SciPy KDTree v1.6.3	...	5.0s	...	547.2s
Scikit-learn KDTree 0.22.2	...	12.2s	...	44.5s
OpenCV FLANN 4.5.2	1.9s	...	4.7s	...
PicoTree KdTree v0.7.4	0.9s	1.0s	2.8s	3.1s

It compares the performance of the build and query algorithms using two LiDAR based point clouds of sizes 7733372 and 7200863. The first is used to compare build times and both are used to compare query times. All benchmarks were generated with the following parameters: max_leaf_size=10, knn=1 and OMP_NUM_THREADS=1. Note that a different C++ back-end was used for each of the Knn C++ and Knn Python benchmarks. This means that they shouldn't be compared directly. See the Python comparison for more details. A more detailed C++ comparison of PicoTree is available with respect to nanoflann.

Available under the MIT license.

Capabilities

• KdTree
  • Nearest neighbors, approximate nearest neighbors, radius, and box searches.
  • Customizable nearest neighbor searches, metrics and tree splitting techniques.
  • Support for topological spaces with identifications. E.g., points on the circle [-pi, pi].
  • Compile time and run time known dimensions.
  • Static tree builds.
  • Thread safe queries.
• PicoTree can interface with different types of points or point sets through a traits class. This can be a custom implementation or one of the traits classes provided by this library:
  • pico_tree::StdTraits<> supports interfacing with any std::vector<PointType>. It requires a specialization of pico_tree::StdPointTraits<> for each PointType. There are default pico_tree::StdPointTraits<> available for Eigen and OpenCV point types.
  • pico_tree::EigenTraits<> supports interfacing with Eigen matrices.
  • pico_tree::CvTraits<> supports interfacing with OpenCV matrices.

The examples show how PicoTree can be used:

• Creating custom pico_tree::StdPointTraits<>.
• pico_tree::StdTraits<> can be used as an example to create a custom traits class.
• Using the KdTree and creating a custom search visitor.
• Support for Eigen and OpenCV data types.
• How to use the KdTree with Python.

Requirements

Minimum:

• A compiler that is compliant with the C++11 standard or higher.
• CMake. It is also possible to just copy and paste the pico_tree directory into an include directory.

Optional:

• Doxygen. Needed for generating documentation.
• Google Test. Used for running unit tests.
• Eigen. To run the example that shows how Eigen data types can be used in combination with PicoTree.
• OpenCV. To run the OpenCV example that shows how to work with OpenCV data types.
• Google Benchmark and a compiler that is compliant with the C++17 standard are needed to run any of the benchmarks. The nanoflann and OpenCV benchmarks also require their respective libraries to be installed.

Python bindings:

• Python. Version 3.5 or higher.
• pybind11. Used to ease the creation of Python bindings. Available under the BSD license and copyright.
• OpenMP. For parallelization of queries.
• numpy. Points and search results are represented by ndarrays.
• scikit-build. Glue between CMake and setuptools.

Build

Build using CMake:

$ mkdir build && cd build
$ cmake ../
$ make
$ make install
$ make pico_tree_doc

Similarly with MSYS2 and MinGW64:

$ ...
$ cmake.exe ../ -G "MinGW Makefiles" -DCMAKE_INSTALL_PREFIX=C:/msys64/mingw64/local
$ mingw32-make.exe
$ ...

find_package(PicoTree REQUIRED)

add_executable(myexe main.cpp)
target_link_libraries(myexe PUBLIC PicoTree::PicoTree)

Install with pip:

$ pip install ./pico_tree

Set a generator for use with MinGW:

$ pip install ./pico_tree --install-option="-GMinGW Makefiles"

References

• Computational Geometry - Algorithms and Applications. Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars, Springer-Verlag, third edition, 2008.
• S. Maneewongvatana and D. M. Mount. It's okay to be skinny, if your friends are fat. 4th Annual CGC Workshop on Computational Geometry, 1999.
• S. Arya and H. Y. Fu. Expected-case complexity of approximate nearest neighbor searching. InProceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms, 2000.
• S. Arya and D. M. Mount. Algorithms for fast vector quantization. In IEEE Data Compression Conference, pages 381–390, March 1993.
• N. Sample, M. Haines, M. Arnold and T. Purcell. Optimizing Search Strategies in k-d Trees. In: 5th WSES/IEEE World Multiconference on Circuits, Systems, Communications & Computers (CSCC 2001), July 2001.
• A. Yershova and S. M. LaValle, Improving Motion-Planning Algorithms by Efficient Nearest-Neighbor Searching. In IEEE Transactions on Robotics, vol. 23, no. 1, pp. 151-157, Feb. 2007.