A general k-d tree with fast range search. More...

#include <Acts/Utilities/KDTree.hpp>

Inheritance diagram for Acts::KDTree< Dims, Type, Scalar, Vector, LeafSize >:

Public Types
using	const_iterator_t = typename vector_t::const_iterator
	Type alias for const iterator over coordinate-value pairs.
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>
	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 Member Functions
	KDTree ()=delete
	KDTree (vector_t &&d)
	Construct a k-d tree from a vector of position-value pairs.
const_iterator_t	begin (void) const
	Get iterator to first element.
const_iterator_t	end (void) const
	Get iterator to one past the last element.
std::vector< Type >	rangeSearch (const range_t &r) const
	Perform an orthogonal range search within the k-d tree.
void	rangeSearch (const range_t &r, std::vector< Type > &v) const
	Perform an in-place orthogonal range search within the k-d tree.
template<typename OutputIt>
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.
template<typename OutputIt>
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.
template<typename Result>
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.
template<typename Callable>
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.
template<typename Result, typename OutputIt>
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.
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.
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.
std::size_t	size (void) const
	Return the number of elements in the k-d tree.

Detailed Description

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 Acts::KDTree< Dims, Type, Scalar, Vector, LeafSize >

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

Member Typedef Documentation

◆ const_iterator_t

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

using Acts::KDTree< Dims, Type, Scalar, Vector, LeafSize >::const_iterator_t = typename vector_t::const_iterator

Type alias for const iterator over coordinate-value pairs.

◆ coordinate_t

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

using Acts::KDTree< Dims, Type, Scalar, Vector, LeafSize >::coordinate_t = Vector<Scalar, Dims>

The type of coordinates for points.

◆ iterator_t

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

using Acts::KDTree< Dims, Type, Scalar, Vector, LeafSize >::iterator_t = typename vector_t::iterator

The type of iterators in our vectors.

◆ pair_t

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

using Acts::KDTree< Dims, Type, Scalar, Vector, LeafSize >::pair_t = std::pair<coordinate_t, Type>

The type of coordinate-value pairs.

◆ range_t

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

using Acts::KDTree< Dims, Type, Scalar, Vector, LeafSize >::range_t = RangeXD<Dims, Scalar>

The type describing a multi-dimensional orthogonal range.

◆ value_t

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

using Acts::KDTree< Dims, Type, Scalar, Vector, LeafSize >::value_t = Type

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

◆ vector_t

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

using Acts::KDTree< Dims, Type, Scalar, Vector, LeafSize >::vector_t = std::vector<pair_t>

The type of a vector of coordinate-value pairs.

Constructor & Destructor Documentation

◆ KDTree() [1/2]

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

Acts::KDTree< Dims, Type, Scalar, Vector, LeafSize >::KDTree ( )

delete

◆ KDTree() [2/2]

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

Acts::KDTree< Dims, Type, Scalar, Vector, LeafSize >::KDTree ( vector_t && d )

explicit

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.

Member Function Documentation

◆ begin()

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

const_iterator_t Acts::KDTree< Dims, Type, Scalar, Vector, LeafSize >::begin ( void ) const

Get iterator to first element.

Returns: Const iterator to the beginning of the tree elements

◆ end()

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

const_iterator_t Acts::KDTree< Dims, Type, Scalar, Vector, LeafSize >::end ( void ) const

Get iterator to one past the last element.

Returns: Const iterator to the end of the tree elements

◆ rangeSearch() [1/2]

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

std::vector< Type > Acts::KDTree< Dims, Type, Scalar, Vector, LeafSize >::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.

◆ rangeSearch() [2/2]

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

void Acts::KDTree< Dims, Type, Scalar, Vector, LeafSize >::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.

◆ rangeSearchInserter()

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

template<typename OutputIt>

void Acts::KDTree< Dims, Type, Scalar, Vector, LeafSize >::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.

◆ rangeSearchInserterWithKey()

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

template<typename OutputIt>

void Acts::KDTree< Dims, Type, Scalar, Vector, LeafSize >::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.

◆ rangeSearchMap()

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

template<typename Result>

std::vector< Result > Acts::KDTree< Dims, Type, Scalar, Vector, LeafSize >::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.

◆ rangeSearchMapDiscard()

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

template<typename Callable>

void Acts::KDTree< Dims, Type, Scalar, Vector, LeafSize >::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.

◆ rangeSearchMapInserter()

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

template<typename Result, typename OutputIt>

void Acts::KDTree< Dims, Type, Scalar, Vector, LeafSize >::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.

◆ rangeSearchWithKey() [1/2]

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

std::vector< pair_t > Acts::KDTree< Dims, Type, Scalar, Vector, LeafSize >::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.

◆ rangeSearchWithKey() [2/2]

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

void Acts::KDTree< Dims, Type, Scalar, Vector, LeafSize >::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.

◆ size()

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

std::size_t Acts::KDTree< Dims, Type, Scalar, Vector, LeafSize >::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.

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ const_iterator_t

◆ coordinate_t

◆ iterator_t

◆ pair_t

◆ range_t

◆ value_t

◆ vector_t

Constructor & Destructor Documentation

◆ KDTree() [1/2]

◆ KDTree() [2/2]

Member Function Documentation

◆ begin()

◆ end()

◆ rangeSearch() [1/2]

◆ rangeSearch() [2/2]

◆ rangeSearchInserter()

◆ rangeSearchInserterWithKey()

◆ rangeSearchMap()

◆ rangeSearchMapDiscard()

◆ rangeSearchMapInserter()

◆ rangeSearchWithKey() [1/2]

◆ rangeSearchWithKey() [2/2]

◆ size()