jaybro/pico_tree

A C++ header only library for fast nearest neighbor and range searches using a KdTree. It supports interfacing with Eigen, OpenCV, and custom data types and provides optional Python bindings.

PicoTree

PicoTree is a C++ header only library with Python bindings for fast 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.5.0	2.9s	...	3.2s	...
SciPy KDTree 1.11.0	...	4.5s	...	563.6s
Scikit-learn KDTree 1.2.2	...	6.2s	...	42.2s
pykdtree 1.3.7	...	1.0s	...	6.6s
OpenCV FLANN 4.6.0	1.9s	...	4.7s	...
PicoTree KdTree v0.8.3	0.9s	1.0s	2.8s	3.1s

Two LiDAR based point clouds of sizes 7733372 and 7200863 were used to generate these numbers. The first point cloud was the input to the build algorithm and the second to the query algorithm. All benchmarks were run on a single thread with the following parameters: max_leaf_size=10 and knn=1. A more detailed C++ comparison of PicoTree is available with respect to nanoflann.

Available under the MIT license.

Capabilities

KdTree:

• Nearest neighbor, approximate nearest neighbor, radius, box, and customizable nearest neighbor searches.
• Different metric spaces:
  • Support for topological spaces with identifications. E.g., points on the circle [-pi, pi].
  • Available distance functions: L1, L2Squared, LInf, SO2, and SE2Squared.
  • Metrics can be customized.
• Multiple tree splitting rules: kLongestMedian, kMidpoint and kSlidingMidpoint.
• Compile time and run time known dimensions.
• Static tree builds.
• Thread safe queries.
• Optional Python bindings.

PicoTree can interface with different types of points and point sets through traits classes. These can be custom implementations or one of the pico_tree::SpaceTraits<> and pico_tree::PointTraits<> classes provided by this library.

• Space type support:
  • std::vector<PointType>.
  • pico_tree::SpaceMap<PointType>.
  • Eigen::Matrix<> and Eigen::Map<Eigen::Matrix<>>.
  • cv::Mat.
• Point type support:
  • Fixed size arrays and std::array<>.
  • pico_tree::PointMap<>.
  • Eigen::Vector<> and Eigen::Map<Eigen::Vector<>>.
  • cv::Vec<>.
• pico_tree::SpaceMap<PointType> and pico_tree::PointMap<> allow interfacing with dynamic size arrays. It is assumed that points and their coordinates are laid out contiguously in memory.

Examples

• Minimal working example for building and querying a KdTree.
• Creating a KdTree and having it take the input by value or reference.
• Using the KdTree's search capabilities.
• Working with dynamic size arrays.
• Supporting a custom point type.
• Supporting a custom space type.
• Creating a custom search visitor.
• Saving and loading a KdTree to and from a file.
• Support for Eigen and OpenCV data types.
• Running the KdTree and KdForest on the MNIST and SIFT datasets.
• How to use the KdTree with Python.

Requirements

Minimum:

• A compiler that is compliant with the C++17 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 is 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.7 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 with CMake:

$ mkdir build && cd build
$ cmake ../
$ cmake --build .
$ cmake --build . --target pico_tree_doc
$ cmake --install .

find_package(PicoTree REQUIRED)

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

Install with pip:

$ pip install ./pico_tree

References

• J. L. Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, vol. 18, no. 9, pp. 509–517, 1975.
• S. Arya and D. M. Mount, Algorithms for fast vector quantization, In IEEE Data Compression Conference, pp. 381–390, March 1993.
• 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.
• 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.
• M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars, Computational Geometry - Algorithms and Applications, Springer-Verlag, third edition, 2008.
• C. Silpa-Anan and R. Hartley, Optimised KD-trees for fast image descriptor matching, In CVPR, 2008.

pico_tree's Issues

I am curious if you have benchmarked this against octree approaches

such as Efficient Radius Neighbor Search in Three-dimensional Point Clouds

can not compile on Ubuntu18.04 gcc7.5

get Error while compiling examples

pico_tree/kd_tree.hpp:362:13: error: ‘pico_tree::KdTree<Space_, Metric_, SplittingRule_, Index_>::space_’ has incomplete type
   SpaceType space_

on ubuntu18.04, gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
using cxx standard 17

trying to use with pcl::PointXYZI

Hi, I am trying to use pico_tree with pcl::pointXYZI

looks like I should use both custom spacetraits and custom point. My custom SpaceTraits are as follows:

template <>
struct PointTraits<pcl::PointXYZI> {
  using PointType = pcl::PointXYZI;
  using ScalarType = float;
  // Spatial dimension. Set to pico_tree::kDynamicSize when the dimension is
  // only known at run-time.
  static std::size_t constexpr Dim = 3;

  // Returns a pointer to the coordinates of the input point.
  inline static float const* data(pcl::PointXYZI const& point) { return point.data; }

  // Returns the number of coordinates or spatial dimension of each point.
  inline static constexpr std::size_t size(pcl::PointXYZI const&) { return Dim; }
};

// Provides an interface for an std::deque<std::array>.
template <typename Scalar_, std::size_t Dim_>
struct SpaceTraits<std::deque<pcl::PointXYZI>> {
  using SpaceType = std::deque<pcl::PointXYZI>;
  using PointType = pcl::PointXYZI;
  using ScalarType = Scalar_;
  // Spatial dimension. Set to pico_tree::kDynamicSize when the dimension is
  // only known at run-time.
  static std::size_t constexpr Dim = Dim_;

  // Returns a point from the input space at the specified index.
  template <typename Index_>
  inline static PointType const& PointAt(
      SpaceType const& space, Index_ const index) {
    return space[static_cast<std::size_t>(index)];
  }

  // Returns number of points contained by the space.
  inline static std::size_t size(SpaceType const& space) {
    return space.size();
  }

  // Returns the number of coordinates or spatial dimension of each point.
  inline static constexpr std::size_t sdim(SpaceType const&) { return Dim; }
};

But it reports

 error: template parameters not deducible in partial specialization:
 struct SpaceTraits<std::deque<pcl::PointXYZI>>

Is it possible to use pico_tree this way? How can I use it with pcl library?

OpenCV build disabled in the build-and-test workflow for Windows

The latest version of the windows runner seems to have an updated CMake version. The 3.25 version had problems with try_compile while building OpenCV.

opencv/opencv#22784
actions/runner-images#6627

The build-and-test workflow fails. googletest no longer builds in macos-latest

Python bindings do not respect non-contiguous NumPy arrays

When the Python pico_tree.KdTree constructor is passed a non-contiguous NumPy array, such as the result of a swapaxes operation, the KdTree is constructed with sdim and npts swapped compared to the expected values. It seems that KdTree is not respecting the array strides, but instead is assuming that the array contains a simple block of memory in C-order.

Repro follows:

import pico_tree as pt
import numpy as np

B, N = 2, 1024
knn = 16

xyz = np.random.randn(B, 3, N)
idx = np.broadcast_to(np.arange(knn, dtype=np.int64).reshape(1, 1, knn), (B, N, knn))
points = np.random.randn(B, 8, N)
xyz_p = np.swapaxes(xyz, 2, 1)
xyz_p_contiguous = np.ascontiguousarray(xyz_p)

assert xyz_p.shape == xyz_p_contiguous.shape

contiguous_tree = pt.KdTree(xyz_p_contiguous[0], pt.Metric.L2Squared, 10)
assert contiguous_tree.sdim == 3
assert contiguous_tree.npts == N

noncontiguous_tree = pt.KdTree(xyz_p[0], pt.Metric.L2Squared, 10)
assert noncontiguous_tree.sdim == 3  # Fails, sdim and npts are swapped
assert noncontiguous_tree.npts == N

xyz_p and xyz_p_contiguous contain the same data and act the same using NumPy operations, but the strides are different as xyz_p is non-contiguous. The KdTree built with the non-contiguous array has npts == 3 and sdim == 1024, the opposite to what is expected, whereas the tree built with the contiguous array works as expected.

A workaround is to ensure that arrays are contiguous before passing to pico_tree.KdTree.

The pip workflow fails. CMake no longer finds libomp on macos-latest.