maliput

KDTree provides a spacepartitioning data structure for organizing points in a kdimensional 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 nearestneighbor queries.
Inspired on https://rosettacode.org/wiki/Kd_tree.
CRTP  Derived class. It follows the curiously recurring template pattern. 
Coordinate  Data type being used, must have:

Dimension  Dimension of the KDtree. 
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_ 

protected 
KDTreeBase  (  Iterator  begin, 
Iterator  end  
) 
Constructs a KDTreeBase taking a pair of iterators.
Adds each point in the range [begin, end) to the tree.
begin  start of range 
end  end of range 
Iterator  type of the iterator. 
maliput::common::assertion_error  When the range is empty. 
KDTreeBase  (  Collection &&  points  ) 
Constructs a KDTreeBase taking a vector of points.
points  Vector of points 
Collection  type of the collection. 
maliput::common::assertion_error  When the range is empty. 
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.
point  a point. 
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.
point  a point. 
tolerance  the maximum distance to the nearest neighbour to be considered a match. 
maliput::common::assertion_error  When tree is empty. 
maliput::common::assertion_error  When tolerance is negative. 

protected 

protected 

protected 