File KDTree.hpp

namespace Acts

Note

This file is foreseen for the Geometry module to replace Extent

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

#include <Acts/Utilities/KDTree.hpp>

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.

Private Members

vector_t m_elems

Vector containing all of the elements in this k-d tree, including the elements managed by the nodes inside of it.

std::unique_ptr<KDTreeNode> m_root

Pointer to the root node of this k-d tree.

Private Static Functions

static inline range_t boundingBox(iterator_t b, iterator_t e)

static inline Scalar nextRepresentable(Scalar v)

class KDTreeNode

An abstract class containing common features of k-d tree node types.

A k-d tree consists of two different node types: leaf nodes and inner nodes. These nodes have some common functionality, which is captured by this common parent node type.

Public Types

enum NodeType

Enumeration type for the possible node types (internal and leaf).

Values:

enumerator Internal

enumerator Leaf

Public Functions

inline KDTreeNode(iterator_t _b, iterator_t _e, NodeType _t, std::size_t _d)

Construct the common data for all node types.

The node types share a few concepts, like an n-dimensional range, and a begin and end of the range of elements managed. This constructor calculates these things so that the individual child constructors don’t have to.

inline const range_t &range() const

The axis-aligned bounding box containing all elements in this node.

Returns

The minimal axis-aligned bounding box that contains all the elements under this node.

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

Perform a range search in the k-d tree, mapping the key-value pairs to a side-effecting function.

This is the most powerful range search method we have, assuming that we can use arbitrary side effects, which we can. All other range search methods are implemented in terms of this particular function.

Parameters

• r – The range to search for.

• f – The mapping function to apply to matching elements.

inline std::size_t size() const

Determine the number of elements managed by this node.

Conveniently, this number is always equal to the distance between the begin iterator and the end iterator, so we can simply delegate to the relevant standard library method.

Returns

The number of elements below this node.

Protected Attributes

const iterator_t m_begin_it

The start and end of the range of coordinate-value pairs under this node.

const iterator_t m_end_it

std::unique_ptr<KDTreeNode> m_lhs

Pointers to the left and right children.

const range_t m_range

The axis-aligned bounding box of the coordinates under this node.

std::unique_ptr<KDTreeNode> m_rhs

NodeType m_type