Reference documentation for deal.II version Git 10f3285 2019-01-18 22:14:04 -0700
Classes | Public Types | Public Member Functions | Private Attributes | List of all members
KDTree< dim > Class Template Reference

#include <deal.II/numerics/kdtree.h>

Inheritance diagram for KDTree< dim >:


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< PointCloudAdaptoradaptor
std::unique_ptr< NanoFlannKDTreekdtree

Detailed Description

template<int dim>
class KDTree< dim >

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 (

A k-d tree is a binary tree in which every node is a \(k\)-dimensional point. Every non-leaf node can be thought of as implicitly generating a splitting hyperplane that divides the space into two parts, known as half-spaces. 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.

Luca Heltai, 2017.

Definition at line 62 of file kdtree.h.

Member Typedef Documentation

template<int dim>
using KDTree< dim >::NanoFlannKDTree = typename nanoflann::KDTreeSingleIndexAdaptor< nanoflann::L2_Simple_Adaptor<double, PointCloudAdaptor>, PointCloudAdaptor, dim, unsigned int>

An alias for the actual KDTree object.

Definition at line 161 of file kdtree.h.

Constructor & Destructor Documentation

template<int dim>
KDTree< dim >::KDTree ( const unsigned int  max_leaf_size = 10,
const std::vector< Point< dim >> &  pts = {} 


[in]max_leaf_sizeA number denoting how many points per leaf are used in the kdtree algorithm.
[in]ptsA 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.

If you change the contents of the vector of points that you passed either to the constructor or to set_points(), remember to call the set_points() method again. The tree and the index are constructed only once when you pass the points (either at construction time, or when you call set_points()). If you update your points, and do not call set_points() again, then all following results will likely be wrong.

Definition at line 26 of file

Member Function Documentation

template<int dim>
void KDTree< dim >::set_points ( const std::vector< Point< dim >> &  pts)

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 non-empty 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]ptsA collection of points

Definition at line 84 of file

template<int dim>
const Point<dim>& KDTree< dim >::operator[] ( const unsigned int  i) const

A const accessor to the i'th one among the underlying points.

template<int dim>
unsigned int KDTree< dim >::size ( ) const

The number of points currently stored by this class.

template<int dim>
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]targetThe target point
[in]radiusThe radius of the ball
[in]sortedIf true, sort the output results in ascending order with respect to distance
A vector of indices and distances to target of the matching points

Definition at line 38 of file

template<int dim>
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]targetThe target point
[in]n_pointsThe number of requested points
A vector of pairs of indices and distances of the matching points

Definition at line 60 of file

Member Data Documentation

template<int dim>
const unsigned int KDTree< dim >::max_leaf_size

Max number of points per leaf as set in the constructor.

Definition at line 233 of file kdtree.h.

template<int dim>
std::unique_ptr<PointCloudAdaptor> KDTree< dim >::adaptor

A point cloud adaptor, to be filled when set points is called.

Definition at line 239 of file kdtree.h.

template<int dim>
std::unique_ptr<NanoFlannKDTree> KDTree< dim >::kdtree

The actual kdtree.

Definition at line 245 of file kdtree.h.

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