 |
Reference documentation for deal.II version 9.2.0
|
|
Reference documentation for deal.II version 9.2.0
|
#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/K-d_tree):
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.
| 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 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] | pts | A collection of points |
A const accessor to the i'th one among the underlying points.
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 |
1.8.17