v1.0.0

PicoTree v1.0.0 is released to celebrate a change in code style (a change that will never happen again...). Besides having an updated style, the biggest change to the kd_tree has been made to its construction parameters. The SplittingRule class template parameter has been replaced by a constructor parameter. Additionally, there are two new parameters that help influence how the kd_tree is constructed. The complete set of parameters is now as follows:

• splitter_rule_t can be one of median_max_side, midpoint_max_side, or sliding_midpoint_max_side.
• splitter_start_bounds_t can be one of bounds_from_space or bounds_t. The latter allows setting a custom or precomputed input bounds.
• splitter_stop_condition_t can be one of max_leaf_size_t or max_leaf_depth_t.

C++ changes:

• Added extra parameters to the kd_tree constructor (see above).
  • The kd_tree_creation.cpp example has been updated to reflect the new changes.
• Added the leaf_ranges method to the kd_tree. It returns a range of indices per leaf.
• Metrics with the topological_space_tag now support search_box queries.
  • Support for metrics with a topological_space_tag is now identical to those with a euclidean_space_tag.
• Simplified the interface for Euclidean and topological metrics (reduced interface function requirements).
  • See the new kd_tree_custom_metric.cpp example for more details.
• The input range for all S¹ distance functions has been updated from [-pi...+pi] to [0...1].
  • This simplifies implementation details, but also the use of S¹ and related spaces.
• Added the <pico_tree/distance.hpp> header that contains various distance functions.
  • It was mostly added to support creating custom metrics.
• Added metric_lninf supporting negative infinity.
• Renamed metric_linf to metric_lpinf (positive infinity).
• Renamed MatWrapper to opencv_mat_map.
  • opencv_mat_map adds support for interfacing with a const cv::Mat on top of the previous non-const support.
• Renamed dynamic_size to dynamic_extent to avoid name collisions (with size).
• pico_toolshed classes have been moved inside the pico_tree namespace.
• From Camels to Snakes in the year of the snake.
• Fix: metric_se2_squared called the incorrect distance function.
• Fix: space_traits<dynamic_space> defined sdim incorrectly.

Python changes:

• Reduced the compile time of the Python module by 40%.
• Added the save_kd_tree and load_kd_tree functions to the Python interface.
  • The kd_tree.py example has been updated to demonstrate the new functionality.
• Renamed LInf to LPInf (positive infinity).
• Replaced several std::runtime_error exceptions by std::invalid_argument.
• Updated the minimum Python version to 3.10.

v0.8.3

Added support for class template argument deduction (CTAD). This means that the space type can now be deduced from the KdTree's constructor argument:

std::size_t max_leaf_size = 10;
std::vector<std::array<double, 2>> points{{0.0, 1.0}, {2.0, 3.0}};

// Deduces to:
// pico_tree::KdTree<std::reference_wrapper<std::vector<std::array<double, 2>>>>
pico_tree::KdTree tree(std::ref(points), max_leaf_size);

If we want to change the metric type or any of the other template arguments of the KdTree, then it's not possible to use the previous deduction method for determining the space type. In this case we can use the pico_tree::MakeKdTree<> helper function to avoid having to explicitly specify the space type and make life a bit easier.

std::size_t max_leaf_size = 10;
std::vector<std::array<double, 2>> points{{0.0, 1.0}, {2.0, 3.0}};

auto tree = 
    pico_tree::MakeKdTree<pico_tree::LInf>(std::ref(points), max_leaf_size);

v0.8.2

This release consolidates various small improvements:

• Fix: added a missing include for std::reference_wrapper<>.
• Reworked the mnist example into the kd_forest example.
  • Fix: the example now checks the correct filename for the existence of a ground truth file.
  • The example adds the use of the SIFT dataset on top of the MNIST dataset.

v0.8.1

The biggest change introduced by this release moves the responsibility of filtering points from the KdTree to the search visitor. Previously, the KdTree would use a visitor's max() method to filter both the nodes of the tree as well as the points residing in the non-filtered nodes. Moving this responsibility makes it possible for the visitor to inspect all the points of the non-filtered nodes instead of just a sub-set, giving the visitor more control and information during a query. This allows, for example, the implementation of the following features:

• An approximate radius search. This was impossible with an older version (equal to setting a smaller search radius).
• Knowing the exact amount of points encountered during a query (see kd_tree_custom_search_visitor.cpp).

Filtering in the visitor also improved the existing approximate k nearest neighbor query. Of all the points that are visited during a query, it will now be guaranteed to return k the nearest.

WARNING! To those who implemented a custom search visitor: Make sure to add extra filtering to avoid having the best nearest neighbor candidate being overwritten by a worse candidate!

Other changes:

• The LInf metric has been added for both C++ and Python.
• Updated the search_box interface for Python to obtain a small performance improvement.
• Removed an unsupported SpaceMap constructor.
• Interfacing with an Eigen::Map of const Eigen::Matrix added. There was only support for non-const matrices.
• Added the approximate version of SearchNn (C++), SearchRadius (C++), and search_radius (Python).
• Updated various examples and added KdTree serialization and MNIST examples.

v0.8.0

This release introduces an improved and simplified interface while at the same time cleaning up some of the internals. The main motivation for changing the interface was to reduce work related to creating traits while at the same time reducing and cleaning up their responsibilities. A traits class like StdTraits or EigenTraits was responsible for three things:

1. Interfacing with a space (point set).
2. Interfacing with a point.
3. Specifying the index type stored in the KdTree.

A point interface was also available through StdPointTraits and often times a class like StdTraits simply used StdPointTraits, essentially showing that an implementer had to do duplicate work. It was also somewhat unclear if the interface should just support the point type stored by its respective space or if it should support other point types as well. This issue has been resolved by splitting up the "main" traits class into both SpaceTraits and PointTraits (the latter previously StdPointTraits). And well, if the interface gets broken anyway, we may as well change a bunch of other things 🥳

Interface changes:

• The "main" traits classes have been split-up into SpaceTraits and PointTraits plus the index type has been moved to the KdTree.
• Renamed StdPointTraits to PointTraits.
• Removed the KdTree Dim template argument.
• KdTree Splitter argument changed from a template class to an enum value: kLongestMedian, kMidpoint and kSlidingMidpoint.
• kDynamicDim renamed to kDynamicSize to be more generic and its type changed from int to pico_tree::Size.
• Metrics:
  • Metrics now use iterators instead of points.
  • Eigen metrics removed.
• CvMatRow replaced by PointMap.
• Updated Aknn functions to be overloads of the Knn functions for both the C++ and Python interface.
• The KdTree now takes a Space as the first a template argument instead of a Traits. This makes setting the argument a bit more simple.
• More consistent interface between points, spaces and their traits.
• Google Code Guide update for output function arguments (from pointers to references).
• Traits related header files renamed.
• Minimum required C++ standard updated from C++11 to C++17.

Additional features:

• Added the SpaceMap and PointMap classes to support interfacing with raw pointers.
• Added the Midpoint splitting rule.
• Added the SE2Squared metric.
• Added a default SpaceTraits<> overload for std::reference_wrapper<SpaceType>. This means that any supported space can be wrapped in an std::reference_wrapper<SpaceType>.
• Added support to interface with fixed size arrays and std::array<>.

v0.7.5

This release consolidates various quality of life improvements.

Changes:

• Updates to the build algorithm, data management and memory management.
  • These updates resulted in small changes in the binary format of the KdTree and the Splitter interface, plus a small speedup of the build algorithm.
• Improvements to the GitHub workflows.

v0.7.4

The KdTree components that handled box utilization and mapping of raw pointers have been refactored, resulting in various performance improvements.

Changes:

• Performance for KdTrees having a dynamic spatial dimension improved:
  • Builds are about 10% faster.
  • Range queries (using SearchBox) are now more than 10 times faster.
• The build and query algorithms of the Python KdTree have become a bit faster.
• Fixed a bug for KdTrees with a dynamic spatial dimension that would incorrectly Load and Save its contents.

v0.7.3

Added support for topological spaces with identifications. This allows KdTree searches to support manifolds such as circles or cylinders that "wrap around" near points that can be expressed with different sets of coordinate values. Also improved query times at the price of increased build times. The overall performance of the KdTree is improved.

Changes:

• Metrics now require a SpaceTag. It identifies which type of space is supported and it changes the behavior of the SearchNearest algorithms.
• Metrics belonging to topological spaces have a slightly different interface compared to ones of Euclidean spaces (see SO2 metric).
• Added the SO2 metric that can be used to search for points on a circle.
• Updated the KdTree references to include background information on the changes of this release.

v0.7.2

While working on a technique to speed up nearest neighbor queries, it became clear that the benchmarks were not representative for showing what the performance would be when matching between two different point clouds. Instead, they showed the performance of queries when the same point cloud was used for both building a tree and querying it. A benchmark using two different clouds is more indicative of tree performance and PicoTree was not the fastest in this scenario. This release addresses the issues with both the benchmarks and query performance.

Changes:

• Improved query speed for both the C++ and Python libraries at the price of reduced metric support.
• Removed L2 and EigenL2 metric support. The KdTree now only supports distance functions that don't apply a final exponent when determining the length of a vector (e.g. ^(1/2) for the L2 metric).
• All benchmarks now test matching performance using two different point clouds.

v0.7.1

Changes:

• OpenCV related code is now part of the test-and-build workflow.
• OpenCV interfacing code moved from the examples to the main library.