template<class T>
class pcl::KDTree< T >
An n-dimensional K-d tree is a specialized binary tree for partitioning of a set of points in an n-dimensional space. K-d trees have important applications in computational geometry problems requiring efficient rectangular range searching.
This class implements a bucket point region K-d tree structure (see Reference 2).
The template type argument T represents the type of a point object stored in a KDTree structure. The type T must have the following properties:
- The standard default and copy constructors are required:
T::T()
T::T( const T& )
- The
T::component subtype must be defined. It represents a component of an object of type T. For example, if T is a vector type, T::component must be the type of a vector component.
- The array subscript operator must be defined as follows:
component T::operator []( int i ) const
This operator must return the value of the i-th component of an object being stored in the K-d tree, such that 0 <= i < N, where N > 0 is the dimension of the point space.
- Note
- We use this implementation of K-d trees in some essential PixInsight tools with success (e.g., StarAlignment), and hopefully it will be also useful for you, but we don't claim it to be complete. This is a practical and relatively simple implementation, where only the construction, destruction and range search operations are available. In particular, this implementation does not include point addition, deletion and iteration operations. Future versions of PCL will include more complete implementations of this fundamental data structure.
References
- 1. Mark de Berg et al., Computational Geometry: Algorithms and Applications Third Edition, Springer, 2010, Section 5.2.
- 2. Hanan Samet, Foundations of Multidimensional and Metric Data Structures, Morgan Kaufmann, 2006, Section 1.5.
- See also
- QuadTree
Definition at line 119 of file KDTree.h.
Constructs a K-d tree and builds it for the specified list of points.
- Parameters
-
| points | A list of points that will be stored in this K-d tree. |
| bucketCapacity | The maximum number of points in a leaf tree node. Must be >= 1. The default value is 16. |
The dimension of the point space is taken as the length of the first point in the list (by calling points[0].Length()), and must be > 0. All points in the points list must be able to provide at least dimension components through a zero-based array subscript operator.
If the specified list of points is empty, this constructor yields an empty K-d tree. If the dimension of the point space is less than one, an Error exception is thrown.
Definition at line 167 of file KDTree.h.
Constructs a K-d tree of the specified dimension and builds it for a list of points.
- Parameters
-
| points | A list of points that will be stored in this K-d tree. |
| dimension | The dimension of the point space. Must be > 0. |
| bucketCapacity | The maximum number of points in a leaf tree node. Must be >= 1. |
All points in the points list must be able to provide at least dimension components through a zero-based array subscript operator.
If the specified list of points is empty, this constructor yields an empty K-d tree. If the dimension of the point space is less than one, an Error exception is thrown.
Definition at line 191 of file KDTree.h.
Builds a new K-d tree for the specified list of points.
- Parameters
-
| points | A list of points that will be stored in this K-d tree. |
| bucketCapacity | The maximum number of points in a leaf tree node. Must be >= 1. The default value is 16. |
The dimension of the point space is taken as the length of the first point in the list (by calling points[0].Length()), and must be > 0. All points in the points list must be able to provide at least dimension components through a zero-based array subscript operator.
If the tree stores point objects before calling this function, they are destroyed and removed before building a new tree.
If the specified list of points is empty, this member function yields an empty K-d tree. If the dimension of the point space is less than one, an Error exception is thrown.
Definition at line 280 of file KDTree.h.
Builds a new K-d tree of the specified dimension for a list of points.
- Parameters
-
| points | A list of points that will be stored in this K-d tree. |
| dimension | The dimension of the point space. Must be > 0. |
| bucketCapacity | The maximum number of points in a leaf tree node. Must be >= 1. |
All points in the points list must be able to provide at least dimension components through a zero-based array subscript operator.
If the tree stores point objects before calling this function, they are destroyed and removed before building a new tree.
If the specified list of points is empty, this member function yields an empty K-d tree. If the dimension of the point space is less than one, an Error exception is thrown.
Definition at line 315 of file KDTree.h.
Performs a range search in this K-d tree.
- Parameters
-
| pt | Reference to the point being searched for. The coordinates of this point define the center of the hyper-rectangular search range in the N-dimensional point space. |
| epsilon | Search tolerance, or half-side of the search hyperrectangle. |
Returns a (possibly empty) list with all the points found in the tree within the search range. In two dimensions, the search range would be the rectangle defined by the points:
(pt[0] - epsilon, pt[1] - epsilon) and
(pt[0] + epsilon, pt[1] + epsilon)
with an obvious extension to higher dimensions. If epsilon is zero, the search can only return the set of stored points that are identical to the specified search point.
Definition at line 345 of file KDTree.h.
template<class T >
template<class F >
Performs a range search in this K-d tree.
- Parameters
-
| pt | Reference to the point being searched for. The coordinates of this point define the center of the hyper-rectangular search range in the N-dimensional point space. |
| epsilon | Search tolerance, or half-side of the search hyperrectangle. |
| callback | Callback functional. |
| data | Callback data. |
The callback function prototype should be:
void callback(
const point& pt,
void* data )
The callback function will be called once for each point found in the tree within the specified search range. In two dimensions, the search range would be the rectangle defined by the points:
(pt[0] - epsilon, pt[1] - epsilon) and
(pt[0] + epsilon, pt[1] + epsilon)
with an obvious extension to higher dimensions. If epsilon is zero, the search can only return the set of stored points that are identical to the specified search point.
Definition at line 390 of file KDTree.h.
1.9.1