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

Function Documentation

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.