maliput
maliput::math::details Namespace Reference

## Classes

class  KDTreeBase
KDTree provides a space-partitioning data structure for organizing points in a k-dimensional space. More...

class  Node
Represents a node in a kd-tree data structure. More...

struct  NodeCmp
Functor for comparing points according to the given dimension being evaluated at that point. More...

struct  SquaredDistance
Calculates the squared distance between two points. More...

## Functions

template<std::size_t Dimension, typename Node , typename NodeCmp >
NodeMakeKdTree (std::size_t begin, std::size_t end, std::size_t index, std::deque< Node > &nodes)
Makes a balanced kd-tree from a range of points already loaded in a collection. More...

template<typename Node >
void Initialize3dRegions (bool left, Node *node)
Computes the regions corresponding to each node in a tree and stores them in the nodes. More...

## ◆ Initialize3dRegions()

 void maliput::math::details::Initialize3dRegions ( bool left, Node * node )

Computes the regions corresponding to each node in a tree and stores them in the nodes.

The region corresponding to the left child(lc) of a node v at even depth can be computed as follows:

region(lc(v)) = region(v) ∩ sp(v)^left


where sp(v) is the splitting plane stored at v, and sp(v)^left is the half-space to the left of and including sp(v). For the right child the computation is analogous.

Template Parameters
 Node A node in a tree. It must have the following methods: get_coordinate(): For getting the underlying point. get_parent(): For getting the parent of the node. get_left(): For getting the left sub-node. get_right(): For getting the right sub-node.
Parameters
 left True if the node is the left child of its parent. node The node to compute the region for.

## ◆ MakeKdTree()

 Node* maliput::math::details::MakeKdTree ( std::size_t begin, std::size_t end, std::size_t index, std::deque< Node > & nodes )

Makes a balanced kd-tree from a range of points already loaded in a collection.

This method is called recursively for building the subtrees.

The nodes will be configured via their API for representing a kd-tree.

Template Parameters
 Dimension Dimensions of the tree. Node A node in a tree. It must have the following methods: get_coordinate(): For getting the underlying point. set_left(Node*): For setting the left sub-node. set_right(Node*): For setting the right sub-node. NodeCmp A functor for comparing two nodes at certain index/dimension: NodeCmp::NodeCmp(int index) Constructor. NodeCmp::operator()(Node* a, Node* b) Comparison operator.
Parameters
 begin Is the start of range. end Is the end of range. index Is the dimension being evaluated. nodes Is a list of non-connected nodes to be sorted and configured.
Returns
A pointer to the root node of the tree.