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

#include <acts/blob/sPHENIX/Core/include/Acts/Utilities/KDTree.hpp>

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

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

Public Types
using	value_t = Type
	The type of value contained in this k-d tree.

using	range_t = RangeXD< Dims, Scalar, Vector >
	The type describing a multi-dimensional orthogonal range.

using	coordinate_t = Vector< Scalar, Dims >
	The type of coordinates for points.

using	pair_t = std::pair< coordinate_t, Type >
	The type of coordinate-value pairs.

using	vector_t = std::vector< pair_t >
	The type of a vector of coordinate-value pairs.

using	iterator_t = typename vector_t::iterator
	The type of iterators in our vectors.

using	const_iterator_t = typename vector_t::const_iterator

Public Member Functions
	KDTree ()=delete

	KDTree (vector_t &&d)
	Construct a k-d tree from a vector of position-value pairs.

std::vector< Type >	rangeSearch (const range_t &r) const
	Perform an orthogonal range search within the k-d tree.

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	rangeSearch (const range_t &r, std::vector< Type > &v) const
	Perform an in-place orthogonal range search within the k-d tree.

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.

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

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.

std::size_t	size (void) const
	Return the number of elements in the k-d tree.

const_iterator_t	begin (void) const

const_iterator_t	end (void) const

Static Private Member Functions
static Scalar	nextRepresentable (Scalar v)

static range_t	boundingBox (iterator_t b, iterator_t e)

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

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.

Definition at line 46 of file KDTree.hpp.

View newest version in sPHENIX GitHub at line 46 of file KDTree.hpp

Member Typedef Documentation

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

Definition at line 66 of file KDTree.hpp.

View newest version in sPHENIX GitHub at line 66 of file KDTree.hpp

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.

Definition at line 55 of file KDTree.hpp.

View newest version in sPHENIX GitHub at line 55 of file KDTree.hpp

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.

Definition at line 64 of file KDTree.hpp.

View newest version in sPHENIX GitHub at line 64 of file KDTree.hpp

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.

Definition at line 58 of file KDTree.hpp.

View newest version in sPHENIX GitHub at line 58 of file KDTree.hpp

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, Vector>

The type describing a multi-dimensional orthogonal range.

Definition at line 52 of file KDTree.hpp.

View newest version in sPHENIX GitHub at line 52 of file KDTree.hpp

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.

Definition at line 49 of file KDTree.hpp.

View newest version in sPHENIX GitHub at line 49 of file KDTree.hpp

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.

Definition at line 61 of file KDTree.hpp.

View newest version in sPHENIX GitHub at line 61 of file KDTree.hpp

Constructor & Destructor Documentation

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

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 )

inline

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.

Definition at line 78 of file KDTree.hpp.

View newest version in sPHENIX GitHub at line 78 of file KDTree.hpp

Member Function Documentation

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

inline

Definition at line 265 of file KDTree.hpp.

View newest version in sPHENIX GitHub at line 265 of file KDTree.hpp

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

static range_t Acts::KDTree< Dims, Type, Scalar, Vector, LeafSize >::boundingBox	(	iterator_t	b,
		iterator_t	e
	)

inlinestaticprivate

Definition at line 284 of file KDTree.hpp.

View newest version in sPHENIX GitHub at line 284 of file KDTree.hpp

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

inline

Definition at line 267 of file KDTree.hpp.

View newest version in sPHENIX GitHub at line 267 of file KDTree.hpp

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

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

inlinestaticprivate

Definition at line 270 of file KDTree.hpp.

View newest version in sPHENIX GitHub at line 270 of file KDTree.hpp

Referenced by Acts::KDTree< 3, int, double >::boundingBox().

Here is the caller graph for this function:

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

inline

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.

Definition at line 106 of file KDTree.hpp.

View newest version in sPHENIX GitHub at line 106 of file KDTree.hpp

Referenced by Acts::Test::BOOST_AUTO_TEST_CASE(), and Acts::KDTree< 3, int, double >::rangeSearch().

Here is the caller graph for this function:

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

inline

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.

Definition at line 139 of file KDTree.hpp.

View newest version in sPHENIX GitHub at line 139 of file KDTree.hpp

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

inline

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.

Definition at line 166 of file KDTree.hpp.

View newest version in sPHENIX GitHub at line 166 of file KDTree.hpp

Referenced by Acts::KDTree< 3, int, double >::rangeSearch().

Here is the caller graph for this function:

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

inline

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.

Definition at line 182 of file KDTree.hpp.

View newest version in sPHENIX GitHub at line 182 of file KDTree.hpp

Referenced by Acts::KDTree< 3, int, double >::rangeSearchWithKey().

Here is the caller graph for this function:

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

inline

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.

Definition at line 207 of file KDTree.hpp.

View newest version in sPHENIX GitHub at line 207 of file KDTree.hpp

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

inline

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.

Definition at line 254 of file KDTree.hpp.

View newest version in sPHENIX GitHub at line 254 of file KDTree.hpp

Referenced by Acts::SeedFinderOrthogonal< external_spacepoint_t >::processFromMiddleSP(), Acts::KDTree< 3, int, double >::rangeSearchInserter(), Acts::KDTree< 3, int, double >::rangeSearchInserterWithKey(), and Acts::KDTree< 3, int, double >::rangeSearchMapInserter().

Here is the caller graph for this function:

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

inline

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.

Definition at line 234 of file KDTree.hpp.

View newest version in sPHENIX GitHub at line 234 of file KDTree.hpp

Referenced by Acts::KDTree< 3, int, double >::rangeSearchMap().

Here is the caller graph for this function:

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

inline

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.

Definition at line 124 of file KDTree.hpp.

View newest version in sPHENIX GitHub at line 124 of file KDTree.hpp

Referenced by Acts::KDTree< 3, int, double >::rangeSearchWithKey(), and Acts::KDTreeTrackingGeometryBuilder::translateLayer().

Here is the caller graph for this function:

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

inline

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.

Definition at line 151 of file KDTree.hpp.

View newest version in sPHENIX GitHub at line 151 of file KDTree.hpp

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

inline

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.

Definition at line 263 of file KDTree.hpp.

View newest version in sPHENIX GitHub at line 263 of file KDTree.hpp

Member Data Documentation

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

vector_t Acts::KDTree< Dims, Type, Scalar, Vector, LeafSize >::m_elems

private

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

Definition at line 497 of file KDTree.hpp.

View newest version in sPHENIX GitHub at line 497 of file KDTree.hpp

Referenced by Acts::KDTree< 3, int, double >::begin(), Acts::KDTree< 3, int, double >::end(), and Acts::KDTree< 3, int, double >::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>

std::unique_ptr<KDTreeNode> Acts::KDTree< Dims, Type, Scalar, Vector, LeafSize >::m_root

private

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

Definition at line 500 of file KDTree.hpp.

View newest version in sPHENIX GitHub at line 500 of file KDTree.hpp

Referenced by Acts::KDTree< 3, int, double >::KDTree(), Acts::KDTree< 3, int, double >::rangeSearchMapDiscard(), and Acts::KDTree< 3, int, double >::size().

The documentation for this class was generated from the following file:

acts/blob/sPHENIX/Core/include/Acts/Utilities/KDTree.hpp

Classes

Public Types

Public Member Functions

Static Private Member Functions

Private Attributes

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 >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

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 >