pbat::geometry::KdTree< Dims > Class Template Reference

KDTree class. More...

#include <KdTree.h>

Public Member Functions
template<class TDerivedP>
	KdTree (Eigen::DenseBase< TDerivedP > const &P, Index maxPointsInLeaf=8)
	Construct a k-D tree from a set of points.
template<class TDerivedP>
void	Construct (Eigen::DenseBase< TDerivedP > const &P, Index maxPointsInLeaf)
	Construct a k-D tree from a set of points.
template<class FVisit>
void	DepthFirstSearch (FVisit visit, Index root=0) const
	Depth-first search over the k-D tree.
std::vector< KdTreeNode > const &	Nodes () const
	Returns the nodes of the k-D tree.
IndexVectorX const &	Permutation () const
	Returns the permutation of the points in the k-D tree.
auto	PointsInNode (Index const nodeIdx) const
	Returns the points in a node.
auto	PointsInNode (KdTreeNode const &node) const
	Returns the points in a node.
Index constexpr	Root () const
	Returns the root node index.

Detailed Description

template<int Dims>
class pbat::geometry::KdTree< Dims >

KDTree class.

Template Parameters

Dims	Number of dimensions of the points' coordinate system in the k-D tree

Constructor & Destructor Documentation

KdTree()

template<int Dims>

template<class TDerivedP>

pbat::geometry::KdTree< Dims >::KdTree ( Eigen::DenseBase< TDerivedP > const & P, Index maxPointsInLeaf = 8 )

inline

Construct a k-D tree from a set of points.

Template Parameters

TDerivedP

Eigen dense expression type

Parameters

P	Points to construct the k-D tree from
maxPointsInLeaf	Maximum number of points in a leaf node

Member Function Documentation

Construct()

template<int Dims>

template<class TDerivedP>

void pbat::geometry::KdTree< Dims >::Construct ( Eigen::DenseBase< TDerivedP > const & P, Index maxPointsInLeaf )

inline

Construct a k-D tree from a set of points.

Implements a top-down median splitting strategy to construct the k-D tree. The median is chosen along the largest axis at each node of the tree, where the left child will inherit the parent node's points less than the median and the right child will inherit the rest. At each node, we use std::nth_element, i.e. introselect, which has \( O(n) \) average complexity (and \( O(n) \) worst-case complexity in recent compiler versions, i.e. Microsoft STL), to partition the points in-place. The largest k-D tree occurs when maxPointsInLeaf == 1, and the tree is always a full binary tree with \( 2n - 1 \) nodes.

Thus, tree construction has \( O(n log(n)) \) average, and \( O(n log^2 n) \) worst-case time complexity.

Note

For fast construction, radix tree is potentially a better choice. However, our radix tree does not support multiple points per leaf.

We could parallelize construction quite easily in the future, since the node ranges are non-overlapping.

Template Parameters

TDerivedP

Eigen dense expression type

Parameters

P	Points to construct the k-D tree from
maxPointsInLeaf	Maximum number of points in a leaf node

DepthFirstSearch()

template<int Dims>

template<class FVisit>

void pbat::geometry::KdTree< Dims >::DepthFirstSearch ( FVisit visit, Index root = 0 ) const

inline

Depth-first search over the k-D tree.

Template Parameters

FVisit	Callable with signature bool(Index, KdTreeNode const&)
FStop	Callable with signature bool(Index, KdTreeNode const&)

Parameters

visit	Callback invoked when visiting a node. Returns true if the node's sub-tree should be visited, false otherwise.
root	Index of the root node to start the search from

Nodes()

template<int Dims>

std::vector< KdTreeNode > const & pbat::geometry::KdTree< Dims >::Nodes ( ) const

inline

Returns the nodes of the k-D tree.

Returns

Nodes of the k-D tree

Permutation()

template<int Dims>

IndexVectorX const & pbat::geometry::KdTree< Dims >::Permutation ( ) const

inline

Returns the permutation of the points in the k-D tree.

The permutation is such that mPermutation[i] gives the index of point i in the original point set given to Construct().

Returns

Permutation of the points in the k-D tree

PointsInNode() [1/2]

template<int Dims>

auto pbat::geometry::KdTree< Dims >::PointsInNode ( Index const nodeIdx ) const

inline

Returns the points in a node.

Parameters

nodeIdx

Index of the node

Returns

Range of points in the node

PointsInNode() [2/2]

template<int Dims>

auto pbat::geometry::KdTree< Dims >::PointsInNode ( KdTreeNode const & node ) const

inline

Returns the points in a node.

Parameters

node	Reference to k-D tree node

Returns

Range of points in the node

Root()

template<int Dims>

Index constexpr pbat::geometry::KdTree< Dims >::Root ( ) const

inlineconstexpr

Returns the root node index.

Returns

Root node index

---

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

• C:/git/PhysicsBasedAnimationToolkit/source/pbat/geometry/KdTree.h