File KDTree.hpp¶

namespace Acts

Set the Geometry Context PLUGIN.

Set the Calibration Context PLUGIN.

Convenience functions to ease creation of and Acts::InterpolatedMaterialMap and to avoid code duplication.

Set the Mangetic Field Context PLUGIN.

Convenience functions to ease creation of and Acts::InterpolatedBFieldMap and to avoid code duplication.

Currently implemented for the two most common formats: rz and xyz.

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.

tparam Dims: The number of dimensions.
tparam Type: The type of value contained in the tree.
tparam Scalar: The scalar type used to construct position vectors.
tparam Vector: The general vector type used to construct coordinates.
tparam LeafSize: The maximum number of elements stored in a leaf node.

Public Types

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 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.

inline void rangeSearchMapDiscard(const range_t &r, std::function<void(const coordinate_t&, const Type&)> 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.

inline std::string toString(void) const

Return a string representing the structure of the k-d tree.

Used mostly for debugging purposes. You probably do not want to call this in actual code.

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<KDTreeAbstractNode> 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 KDTreeAbstractNode¶

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 Functions

inline KDTreeAbstractNode(iterator_t _b, iterator_t _e)¶

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.

virtual ~KDTreeAbstractNode(void) = default¶: Destroy this node in the k-d tree, and indirectly all of its children.

inline const range_t &range(void) 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.

virtual void rangeSearchMapDiscard(const range_t &r, std::function<void(const coordinate_t&, const Type&)> f) const = 0¶

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(void) 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.

virtual std::string toString(std::size_t d) const = 0¶

Debugging method that gives a textual representation of a k-d tree.

It is probably best not to use this method in real code. It is designed for debugging purposes only.

Parameters: d – The depth of this node (for indentation).

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¶

const range_t m_range¶: The axis-aligned bounding box of the coordinates under this node.

class KDTreeLeaf : public Acts::KDTree<Dims, Type, Scalar, Vector, LeafSize>::KDTreeAbstractNode¶

Public Functions

inline KDTreeLeaf(iterator_t _b, iterator_t _e)¶

Construct a leaf node from a range of elements.

This doesn’t actually do anything that the abstract base constructor doesn’t do.

Parameters

_b – The begin iterator of the range of values.
_e – The end iterator of the range of values.

inline virtual void rangeSearchMapDiscard(const range_t &r, std::function<void(const coordinate_t&, const Type&)> f) const override¶

Perform a range on this leaf node.

Performing a range search on a leaf node is rather simple, because we just need to check whether each of the elements in the node is actually inside the range.

Parameters

r – The range to search for.
f – The mapping function to apply.

inline virtual std::string toString(std::size_t i) const override¶

Debugging string method for this (sub-)k-d tree.

This prints information to stdout about the structure of the (sub-)tree defined by this node. Not designed for use in real code.

Parameters: i – The amount of indentation to use.

class KDTreeNode : public Acts::KDTree<Dims, Type, Scalar, Vector, LeafSize>::KDTreeAbstractNode¶

A non-leaf node in the k-d tree.

These nodes are not the direct parents of any coordinate-value pairs, but rather they are the parents of two other nodes. This means that this type of node represents a split of the candidate space across a particular dimension.

Public Functions

inline KDTreeNode(iterator_t _b, iterator_t _e)¶

Constract an internal node from a range of coordinate-value pairs.

The element range passed to this constructor is a subrange of the set of coordinate-value pairs owned by the outer-most parent node. The constructor rearranges the elements of this range.

Parameters

_b – The iterator for the start of the range of elements.
_e – The iterator for the end of the range of elements.

inline virtual void rangeSearchMapDiscard(const range_t &r, std::function<void(const coordinate_t&, const Type&)> f) const override¶

Perform a range search in this (sub-)k-d tree.

Performing a range search on an inner node is essentially the same as performing that same range search on both its children and appending them. However, we can also do some optimisations.

Parameters

r – The orthogonal range to search for.
f – The mapping function to execute.

inline virtual std::string toString(std::size_t i) const override¶

Debugging string method for this (sub-)k-d tree.

This prints information to stdout about the structure of the (sub-)tree defined by this node. Not designed for use in real code.

Parameters: i – The amount of indentation to use.

Private Members

std::size_t m_dim¶: The index of the pivot dimension.

std::unique_ptr<KDTreeAbstractNode> m_lhs¶: Pointers to the left and right children.

Scalar m_mid¶: The value of the pivot in the pivot dimension.

std::unique_ptr<KDTreeAbstractNode> m_rhs¶