Class Acts::KDTree

template<std::size_t Dims, typename Type, typename Scalar = double, template<typename, std::size_t> typename Vector = std::array, std::size_t LeafSize = 4>
class KDTree

A general k-d tree with fast range search.

This is a generalized k-d tree, with a configurable number of dimension, scalar type, content type, index type, vector type, and leaf size. This class is purposefully generalized to support a wide range of use cases.

A k-d tree is, in essence, a k-dimensional binary search tree. Each interal node splits the content of the tree in half, with the pivot point being an orthogonal hyperplane in one of the k dimensions. This allows us to efficiently look up points within certain k-dimensional ranges.

This particular class is mostly a wrapper class around an underlying node class which does all the actual work.

Note

This type is completely immutable after construction.

Template Parameters
  • Dims – The number of dimensions.

  • Type – The type of value contained in the tree.

  • Scalar – The scalar type used to construct position vectors.

  • Vector – The general vector type used to construct coordinates.

  • LeafSize – The maximum number of elements stored in a leaf node.

Public Types

using const_iterator_t = typename vector_t::const_iterator
using coordinate_t = Vector<Scalar, Dims>

The type of coordinates for points.

using iterator_t = typename vector_t::iterator

The type of iterators in our vectors.

using pair_t = std::pair<coordinate_t, Type>

The type of coordinate-value pairs.

using range_t = RangeXD<Dims, Scalar, Vector>

The type describing a multi-dimensional orthogonal range.

using value_t = Type

The type of value contained in this k-d tree.

using vector_t = std::vector<pair_t>

The type of a vector of coordinate-value pairs.

Public Functions

KDTree() = delete
inline KDTree(vector_t &&d)

Construct a k-d tree from a vector of position-value pairs.

This constructor takes an r-value reference to a vector of position-value pairs and constructs a k-d tree from those pairs.

Parameters

d – The vector of position-value pairs to construct the k-d tree from.

inline const_iterator_t begin(void) const
inline const_iterator_t end(void) const
inline std::vector<Type> rangeSearch(const range_t &r) const

Perform an orthogonal range search within the k-d tree.

A range search operation is one that takes a k-d tree and an orthogonal range, and returns all values associated with coordinates in the k-d tree that lie within the orthogonal range. k-d trees can do this operation quickly.

Parameters

r – The range to search for.

Returns

The vector of all values that lie within the given range.

inline void rangeSearch(const range_t &r, std::vector<Type> &v) const

Perform an in-place orthogonal range search within the k-d tree.

This range search module operates in place, writing its results to the given output vector.

Parameters
  • r – The range to search for.

  • v – The vector to write the output to.

template<typename OutputIt>
inline void rangeSearchInserter(const range_t &r, OutputIt i) const

Perform an orthogonal range search within the k-d tree, writing the resulting values to an output iterator.

This method allows the user more control in where the result is written to.

Template Parameters

OutputIt – The type of the output iterator.

Parameters
  • r – The range to search for.

  • i – The iterator to write the output to.

template<typename OutputIt>
inline void rangeSearchInserterWithKey(const range_t &r, OutputIt i) const

Perform an orthogonal range search within the k-d tree, writing the resulting values to an output iterator, including the keys.

Performs the same operation as the keyless version, but includes the key in the output.

Template Parameters

OutputIt – The type of the output iterator.

Parameters
  • r – The range to search for.

  • i – The iterator to write the output to.

template<typename Result>
inline std::vector<Result> rangeSearchMap(const range_t &r, std::function<Result(const coordinate_t&, const Type&)> f) const

Perform an orthogonal range search within the k-d tree, applying a mapping function to the values found.

In some cases, we may wish to transform the values in some way. This method allows the user to provide a mapping function which takes a set of coordinates and a value and transforms them to a new value, which is returned.

Note

Your compiler may not be able to deduce the result type automatically, in which case you will need to specify it manually.

Template Parameters

Result – The return type of the map operation.

Parameters
  • r – The range to search for.

  • f – The mapping function to apply to key-value pairs.

Returns

A vector of elements matching the range after the application of the mapping function.

template<typename Callable>
inline void rangeSearchMapDiscard(const range_t &r, Callable &&f) const

Perform an orthogonal range search within the k-d tree, applying a a void-returning function with side-effects to each key-value pair.

This is the most general version of range search in this class, and every other operation can be reduced to this operation as long as we allow arbitrary side-effects.

Functional programmers will know this method as mapM_.

Parameters
  • r – The range to search for.

  • f – The mapping function to apply to key-value pairs.

template<typename Result, typename OutputIt>
inline void rangeSearchMapInserter(const range_t &r, std::function<Result(const coordinate_t&, const Type&)> f, OutputIt i) const

Perform an orthogonal range search within the k-d tree, applying a mapping function to the values found, and inserting them into an inserter.

Performs the same operation as the interter-less version, but allows the user additional control over the insertion process.

Note

Your compiler may not be able to deduce the result type automatically, in which case you will need to specify it manually.

Template Parameters
  • Result – The return type of the map operation.

  • OutputIt – The type of the output iterator.

Parameters
  • r – The range to search for.

  • f – The mapping function to apply to key-value pairs.

  • i – The inserter to insert the results into.

inline std::vector<pair_t> rangeSearchWithKey(const range_t &r) const

Perform an orthogonal range search within the k-d tree, returning keys as well as values.

Performs the same logic as the keyless version, but includes a copy of the key with each element.

Parameters

r – The range to search for.

Returns

The vector of all key-value pairs that lie within the given range.

inline void rangeSearchWithKey(const range_t &r, std::vector<pair_t> &v) const

Perform an in-place orthogonal range search within the k-d tree, including keys in the result.

Performs the same operation as the keyless version, but includes the keys in the results.

Parameters
  • r – The range to search for.

  • v – The vector to write the output to.

inline std::size_t size(void) const

Return the number of elements in the k-d tree.

We simply defer this method to the root node of the k-d tree.

Returns

The number of elements in the k-d tree.