KD-tree, a binary space-partitioning tree. More...
#include <shark/Models/Trees/KDTree.h>
Inheritance diagram for shark::KDTree< InputT >:
Public Member Functions | |
| KDTree (Data< InputT > const &dataset, TreeConstruction tc=TreeConstruction()) | |
| double | lower (std::size_t dim) const |
| double | upper (std::size_t dim) const |
| double | squaredDistanceLowerBound (InputT const &reference) const |
| Public Member Functions inherited from shark::BinaryTree< InputT > | |
| BinaryTree (std::size_t size) | |
| Root node constructor: build the tree from data. More... | |
| virtual | ~BinaryTree () |
| Destroy the tree and its internal data structures. More... | |
| BinaryTree * | parent () |
| parent node More... | |
| const BinaryTree * | parent () const |
| parent node More... | |
| bool | hasChildren () const |
| bool | isLeaf () const |
| BinaryTree * | left () |
| "left" sub-node of the binary tree More... | |
| const BinaryTree * | left () const |
| "left" sub-node of the binary tree More... | |
| BinaryTree * | right () |
| "right" sub-node of the binary tree More... | |
| const BinaryTree * | right () const |
| "right" sub-node of the binary tree More... | |
| std::size_t | size () const |
| number of points inside the space represented by this node More... | |
| std::size_t | nodes () const |
| number of sub-nodes in this tree (including the node itself) More... | |
| std::size_t | index (std::size_t point) const |
| double | distanceFromPlane (value_type const &point) const |
| Function describing the separation of space. More... | |
| double | threshold () const |
| Separation threshold. More... | |
| bool | isLeft (value_type const &point) const |
| bool | isRight (value_type const &point) const |
| virtual AbstractKernelFunction< value_type > const * | kernel () const |
| If the tree uses a kernel metric, returns a pointer to the kernel object, else NULL. More... | |
Protected Member Functions | |
| KDTree (KDTree *parent, std::size_t *list, std::size_t size) | |
| (internal) construction of a non-root node More... | |
| template<class Range > | |
| void | buildTree (TreeConstruction tc, Range &points) |
| template<class Range > | |
| std::size_t | calculateCuttingDimension (Range const &points) const |
| Calculate the dimension which should be cut by this node. More... | |
| double | funct (InputT const &reference) const |
| Protected Member Functions inherited from shark::BinaryTree< InputT > | |
| BinaryTree (BinaryTree *parent, std::size_t *list, std::size_t size) | |
| Sub-node constructor. More... | |
| template<class Range1 , class Range2 > | |
| Range2::iterator | splitList (Range1 &values, Range2 &points) |
| Split the data in the point list and calculate the treshold accordingly. More... | |
Protected Attributes | |
| std::size_t | m_cutDim |
| split/cut dimension of this node More... | |
| Protected Attributes inherited from shark::BinaryTree< InputT > | |
| BinaryTree * | mep_parent |
| parent node More... | |
| BinaryTree * | mp_left |
| "left" child node More... | |
| BinaryTree * | mp_right |
| "right" child node More... | |
| std::size_t * | mp_indexList |
| list of indices to points in the dataset More... | |
| std::size_t | m_size |
| number of points in this node More... | |
| std::size_t | m_nodes |
| number of nodes in the sub-tree represented by this node More... | |
| double | m_threshold |
| threshold for the separating function More... | |
Detailed Description
template<class InputT>
class shark::KDTree< InputT >
KD-tree, a binary space-partitioning tree.
- KD-tree data structure for efficient nearest neighbor searches in low-dimensional spaces. Low-dimensional means << 10 dimensions.
- The tree is constructed from data by splitting the dimension with largest extent (in the data covered, not space represented by the cell), recursively. An approximate median is used as the cutting point, where the maximal number of points used to estimate the median can be controlled with the template parameter MedianAccuracy.
- The bucket size for the tree is aleays one, such that there is a unique point in each leaf cell.
Constructor & Destructor Documentation
◆ KDTree() [1/2]
|
inline |
Construct the tree from data. It is assumed that the container exceeds the lifetime of the KDTree (which holds only references to the points), and that the memory locations of the points remain unchanged.
Definition at line 82 of file KDTree.h.
References shark::KDTree< InputT >::buildTree(), shark::BinaryTree< InputT >::m_size, and shark::BinaryTree< InputT >::mp_indexList.
◆ KDTree() [2/2]
|
inlineprotected |
Member Function Documentation
◆ buildTree()
|
inlineprotected |
(internal) construction method: median-cuts of the dimension with widest spread
Definition at line 198 of file KDTree.h.
References shark::KDTree< InputT >::calculateCuttingDimension(), shark::KDTree< InputT >::m_cutDim, shark::BinaryTree< InputT >::m_nodes, shark::BinaryTree< InputT >::m_size, shark::TreeConstruction::maxBucketSize(), and shark::TreeConstruction::maxDepth().
Referenced by shark::KDTree< InputT >::KDTree().
◆ calculateCuttingDimension()
|
inlineprotected |
Calculate the dimension which should be cut by this node.
The KD-Tree calculates the Axis-Aligned-Bounding-Box surrounding the points and splits the longest dimension
Definition at line 243 of file KDTree.h.
References shark::BinaryTree< InputT >::m_size.
Referenced by shark::KDTree< InputT >::buildTree().
◆ funct()
|
inlineprotectedvirtual |
Function describing the separating hyperplane as its zero set. It is guaranteed that the gradient has norm one, thus the absolute value of the function indicates distance from the hyperplane.
Implements shark::BinaryTree< InputT >.
Definition at line 285 of file KDTree.h.
References shark::KDTree< InputT >::m_cutDim.
◆ lower()
|
inline |
lower bound on the box-shaped space represented by this cell
Definition at line 103 of file KDTree.h.
References shark::KDTree< InputT >::lower(), shark::KDTree< InputT >::m_cutDim, shark::BinaryTree< InputT >::mep_parent, shark::BinaryTree< InputT >::mp_right, shark::BinaryTree< InputT >::parent(), and shark::BinaryTree< InputT >::threshold().
Referenced by shark::KDTree< InputT >::lower(), and shark::KDTree< InputT >::squaredDistanceLowerBound().
◆ squaredDistanceLowerBound()
|
inlinevirtual |
- Compute the squared Euclidean distance of this cell to the given reference point, or alternatively a lower bound on this value.
- In the case of the kd-tree the computation is exact, however, only a lower bound is required in general, and other space partitioning trees used in the future may only be able to provide a lower bound, at least with reasonable computational efforts.
Implements shark::BinaryTree< InputT >.
Definition at line 137 of file KDTree.h.
References shark::BinaryTree< InputT >::index(), shark::BinaryTree< InputT >::isLeaf(), shark::KDTree< InputT >::lower(), shark::KDTree< InputT >::m_cutDim, shark::BinaryTree< InputT >::m_nodes, shark::BinaryTree< InputT >::m_size, shark::BinaryTree< InputT >::mep_parent, shark::BinaryTree< InputT >::mp_indexList, shark::BinaryTree< InputT >::mp_left, shark::BinaryTree< InputT >::mp_right, shark::BinaryTree< InputT >::size(), shark::sqr(), shark::BinaryTree< InputT >::threshold(), and shark::KDTree< InputT >::upper().
◆ upper()
|
inline |
upper bound on the box-shaped space represented by this cell
Definition at line 115 of file KDTree.h.
References shark::KDTree< InputT >::m_cutDim, shark::BinaryTree< InputT >::mep_parent, shark::BinaryTree< InputT >::mp_left, shark::BinaryTree< InputT >::parent(), shark::BinaryTree< InputT >::threshold(), and shark::KDTree< InputT >::upper().
Referenced by shark::KDTree< InputT >::squaredDistanceLowerBound(), and shark::KDTree< InputT >::upper().
Member Data Documentation
◆ m_cutDim
|
protected |
split/cut dimension of this node
Definition at line 290 of file KDTree.h.
Referenced by shark::KDTree< InputT >::buildTree(), shark::KDTree< InputT >::funct(), shark::KDTree< InputT >::lower(), shark::KDTree< InputT >::squaredDistanceLowerBound(), and shark::KDTree< InputT >::upper().
The documentation for this class was generated from the following file:
- include/shark/Models/Trees/KDTree.h