Class Acts::KDTree::KDTreeNode

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


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.


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.

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


The number of elements below this node.