Reference documentation for deal.II version 9.1.1

#include <deal.II/numerics/kdtree.h>
Classes  
struct  PointCloudAdaptor 
Public Types  
using  NanoFlannKDTree = typename nanoflann::KDTreeSingleIndexAdaptor< nanoflann::L2_Simple_Adaptor< double, PointCloudAdaptor >, PointCloudAdaptor, dim, unsigned int > 
Public Member Functions  
KDTree (const unsigned int max_leaf_size=10, const std::vector< Point< dim >> &pts={})  
void  set_points (const std::vector< Point< dim >> &pts) 
const Point< dim > &  operator[] (const unsigned int i) const 
unsigned int  size () const 
std::vector< std::pair< unsigned int, double > >  get_points_within_ball (const Point< dim > &target, const double radius, const bool sorted=false) const 
std::vector< std::pair< unsigned int, double > >  get_closest_points (const Point< dim > &target, const unsigned int n_points) const 
Private Attributes  
const unsigned int  max_leaf_size 
std::unique_ptr< PointCloudAdaptor >  adaptor 
std::unique_ptr< NanoFlannKDTree >  kdtree 
A wrapper for the nanoflann library, used to compute the distance from a collection of points, and to efficiently return nearest neighbors to a target point. This class uses nanoflann to efficiently partition the space in a \(k\)dimensional tree. The cost of each query is then roughly of order \(\log(n)\), where \(n\) is the number of points stored in this class.
The wrapper provides methods that give access to some of the functionalities of the nanoflann library, like searching the \(p\) nearest neighbors of a given point, or searching the points that fall within a radius of a target point.
From wikipedia (https://en.wikipedia.org/wiki/Kd_tree):
A kd tree is a binary tree in which every node is a \(k\)dimensional point. Every nonleaf node can be thought of as implicitly generating a splitting hyperplane that divides the space into two parts, known as halfspaces. Points to the left of this hyperplane are represented by the left subtree of that node and points right of the hyperplane are represented by the right subtree. The hyperplane direction is chosen in the following way: every node in the tree is associated with one of the \(k\)dimensions, with the hyperplane perpendicular to that dimension's axis. So, for example, if for a particular split the "x" axis is chosen, all points in the subtree with a smaller "x" value than the node will appear in the left subtree and all points with larger "x" value will be in the right subtree. In such a case, the hyperplane would be set by the \(x\)value of the point, and its normal would be the unit \(x\)axis.
boost::geometry::index::rtree
.using KDTree< dim >::NanoFlannKDTree = typename nanoflann::KDTreeSingleIndexAdaptor< nanoflann::L2_Simple_Adaptor<double, PointCloudAdaptor>, PointCloudAdaptor, dim, unsigned int> 
KDTree< dim >::KDTree  (  const unsigned int  max_leaf_size = 10 , 
const std::vector< Point< dim >> &  pts = {} 

) 
Constructor.
[in]  max_leaf_size  A number denoting how many points per leaf are used in the kdtree algorithm. 
[in]  pts  A vector of points that are to be represented by the current object. If no points are passed to this constructor (or if the default value of the argument is used), then you have to pass them later to this object by calling the set_points() method. 
Access to any of the methods without first passing a reference to a vector of points will result in an exception. Only a reference to the points is stored, so you should make sure that the life of the vector you pass is longer than the life of this class, or you will get undefined behaviour.
Store a reference to the passed points. After you called this method, you can call the value() method to compute the minimum distance between an evaluation point and the collection of points you passed to this method, or the get_points_within_ball() and the get_closest_points() methods.
Notice that the constructor calls this method internally if you pass it a nonempty vector of points.
Whenever your points change, you should call this method again, since this is the method responsible for building the index and storing the actual tree internally. If you change your points and don't call again this method, any function you call later will happily return wrong values without you noticing.
[in]  pts  A collection of points 
A const accessor to the i'th
one among the underlying points.
unsigned int KDTree< dim >::size  (  )  const 
The number of points currently stored by this class.
std::vector< std::pair< unsigned int, double > > KDTree< dim >::get_points_within_ball  (  const Point< dim > &  target, 
const double  radius,  
const bool  sorted = false 

)  const 
Fill and return a vector with the indices and the distance of the points that are at distance less than or equal to the given radius from the target point.
[in]  target  The target point 
[in]  radius  The radius of the ball 
[in]  sorted  If true , sort the output results in ascending order with respect to distance 
target
of the matching points std::vector< std::pair< unsigned int, double > > KDTree< dim >::get_closest_points  (  const Point< dim > &  target, 
const unsigned int  n_points  
)  const 
Fill and return a vector with the indices and distances of the closest n_points
points to the given target point.
[in]  target  The target point 
[in]  n_points  The number of requested points 

private 

private 

private 