KDTreeBase< CRTP, Coordinate, Dimension, Region, Distance, NodeCmp > Class Template Reference

Detailed Description

template<typename CRTP, typename Coordinate, std::size_t Dimension, typename Region = BoundingRegion<Coordinate>, typename Distance = SquaredDistance<Coordinate, Dimension>, typename NodeCmp = NodeCmp<Dimension>>
class maliput::math::details::KDTreeBase< CRTP, Coordinate, Dimension, Region, Distance, NodeCmp >

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

The tree is built from a set of points, where each point is a vector of length k. The tree is built balanced, to guarantee an average of O(log(n)) time for nearest-neighbor queries.

Inspired on https://rosettacode.org/wiki/K-d_tree.

Template Parameters

CRTP	Derived class. It follows the curiously recurring template pattern.
Coordinate	Data type being used, must have: operator[] for accessing the value in each dimension.
Dimension	Dimension of the KD-tree.
Region	The type of the region.
Distance	A functor used for getting the distance between two coordinates. By default, details::SquaredDistance is used.
NodeCmp	A functor used for comparing two nodes at certain index/dimension. By default, details::NodeCmp is used.

#include <include/maliput/math/kd_tree.h>

Public Member Functions
template<typename Iterator >
	KDTreeBase (Iterator begin, Iterator end)
	Constructs a KDTreeBase taking a pair of iterators. More...
template<typename Collection >
	KDTreeBase (Collection &&points)
	Constructs a KDTreeBase taking a vector of points. More...
const Coordinate &	nearest_point (const Coordinate &point) const
	Finds the nearest point in the tree to the given point. More...
const Coordinate &	nearest_point (const Coordinate &point, double tolerance) const
	Finds the nearest point in the tree to the given point. More...

Protected Types
using	Node = details::Node< Coordinate, Region >

Protected Member Functions
void	nearest_point (const Node *node, const Coordinate &point, std::size_t index, double tolerance, Node *&nearest_neighbour_node, double *nearest_neighbour_distance) const

Protected Attributes
Node *	root_ = nullptr
std::deque< Node >	nodes_

Member Typedef Documentation

Node

using Node = details::Node<Coordinate, Region>

protected

Constructor & Destructor Documentation

KDTreeBase() [1/2]

KDTreeBase	(	Iterator	begin,
		Iterator	end
	)

Constructs a KDTreeBase taking a pair of iterators.

Adds each point in the range [begin, end) to the tree.

Parameters

begin	start of range
end	end of range

Template Parameters

Iterator

type of the iterator.

Exceptions

maliput::common::assertion_error

When the range is empty.

KDTreeBase() [2/2]

KDTreeBase

(

Collection &&

points

)

Constructs a KDTreeBase taking a vector of points.

Parameters

points

Vector of points

Template Parameters

Collection

type of the collection.

Exceptions

maliput::common::assertion_error

When the range is empty.

Member Function Documentation

nearest_point() [1/3]

const Coordinate& nearest_point

(

const Coordinate &

point

)

const

Finds the nearest point in the tree to the given point.

(Nearest Neighbour (NN)) Tolerance being used is std::numeric_limits<double>::min(). It is not valid to call this function if the tree is empty.

Parameters

point

a point.

Returns

the nearest point in the tree to the given point

nearest_point() [2/3]

const Coordinate& nearest_point	(	const Coordinate &	point,
		double	tolerance
	)		const

Finds the nearest point in the tree to the given point.

(Nearest Neighbour (NN)) It is not valid to call this function if the tree is empty.

Parameters

point	a point.
tolerance	the maximum distance to the nearest neighbour to be considered a match.

Returns

the nearest point in the tree to the given point

Exceptions

maliput::common::assertion_error	When tree is empty.
maliput::common::assertion_error	When tolerance is negative.

nearest_point() [3/3]

void nearest_point ( const Node *  node, const Coordinate &  point, std::size_t  index, double  tolerance, Node *&  nearest_neighbour_node, double *  nearest_neighbour_distance  ) const

protected

Member Data Documentation

nodes_

std::deque<Node> nodes_

protected

root_

Node* root_ = nullptr

protected

---

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

• kd_tree.h