|
|
last update 20 Sep 2009 |
|
#include <cvrKdTree.h>
Inheritance diagram for cvr::kdTree< T, D, U >:
Collaboration diagram for cvr::kdTree< T, D, U >:Classes | |
| class | element |
| At the leave nodes, a list of elements of this type will contain the points and their corresponding data. More... | |
| class | node |
| Class of nodes of the kd-tree. More... | |
Public Types | |
| typedef T::value_type | value_type |
| typedef U::distance_type | distance_type |
| typedef std::multimap < distance_type, element * > | mmap_type |
| typedef int | size_type |
Public Member Functions | |
| kdTree () | |
| kdTree (const kdTree< T, D, U > &other) | |
| virtual | ~kdTree () |
| const std::string & | name () const |
| kdTree< T, D, U > & | copy (const kdTree< T, D, U > &other) |
| kdTree< T, D, U > & | operator= (const kdTree< T, D, U > &other) |
| virtual kdTree< T, D, U > * | clone () const |
| virtual kdTree< T, D, U > * | newInstance () const |
| virtual void | clear () |
| virtual bool | empty () const |
| virtual int | getNumberOfAddedElements () const |
| virtual int | size () const |
| virtual int | getNumberOfLeaves () const |
| virtual int | getNumberOfLevels () const |
| virtual node * | getRoot () |
| void | add (const T &point, const D &data) |
| bool | build (const int bucketSize=1) |
| bool | rebuild (const int bucketSize=1) |
| virtual bool | read (ioHandler &handler, const bool complete=true) |
| virtual bool | write (ioHandler &handler, const bool complete=true) const |
Search methods | |
| bool | searchExactly (const T &key, element &elem) const |
| bool | searchExactly (const T &key, std::list< element > &elems) const |
| bool | searchNearest (const T &key, element *&elem) const |
| bool | searchNearest (const T &key, element *&elem, distance_type &dist) const |
| bool | searchNearest (const T &key, element &elem) const |
| bool | searchNearest (const T &key, element &elem, distance_type &dist) const |
| bool | searchNearest (const T &key, D &data) const |
| bool | searchNearest (const int k, const T &key, std::list< element * > &neighbors) const |
| bool | searchNearest (const int k, const T &key, mmap_type &neighbors) const |
| bool | searchWithin (const T &key, const distance_type &dist, std::list< element * > &elems) const |
| bool | searchWithin (const T &key, const distance_type &dist, mmap_type &neighbors) const |
| bool | searchBestBinFirst (const int k, const T &key, const int emax, std::list< element * > &neighbors) const |
| bool | searchBestBinFirst (const int k, const T &key, const int emax, mmap_type &neighbors) const |
| bool | searchRange (const T &boxMin, const T &boxMax, std::list< element * > &neighbors) const |
Protected Attributes | |
| node * | root_ |
| int | levels_ |
| int | numElements_ |
| int | numAddedElements_ |
| int | numLeaves_ |
| matrix< value_type > | totalBounds_ |
| std::list< element * > | treePoints_ |
| U | distantor_ |
A k-d tree is a generalization of the simple binary tree used for sorting and searching. At each level of the tree, a n-dimensional subspace is split in two subspaces at a given dimension. The leaves of the tree contain a "bucket" of data within the described subspace.
You can consider data for building with the add() method. Then you can either build() the tree from that data, discarding the old data, or rebuild() the tree, which will then contain the data added since the last call to build() or rebuild() plus the newly added data.
This type allows to search in an efficient way for the most similar neighbors of a given point.
The type T describes a point in an n-dimensional space. Usually, you will use vector<float> or vector<double>, but types like rgbPixel, trgbPixel<float>, tpoint<float> are also supported. The type T MUST provide following methods/operators:
(cvr::vector, cvr::tpoint, cvr::tpoint3D, cvr::trgbpixel and cvr::rgbPixel provide this interface)
The type D describes the data contained at each node, which is by default just an integer value. It must provide following methods/operators
The type U specifies a "distantor" policy, i.e. it specifies the distance to be used while computing the nearest neighbors. If not given, the default value will be euclideanSqrDistantor, which provides, as the name says, the square of the euclidean distance. Only Minkowski distances are allowed. If you need your own distance measure you can create your policy following the interfaces of one of the classes cvr::euclideanDistantor, cvr::cityBlockDistantor or euclideanSqrDistantor.
| typedef U::distance_type cvr::kdTree< T, D, U >::distance_type |
Type used to accumulate data of value_type elements.
| typedef std::multimap<distance_type,element*> cvr::kdTree< T, D, U >::mmap_type |
Multimap type.
| typedef int cvr::kdTree< T, D, U >::size_type |
Return type of the size() member.
| typedef T::value_type cvr::kdTree< T, D, U >::value_type |
Value type at each dimension of the space.
| cvr::kdTree< T, D, U >::kdTree | ( | ) |
Default constructor.
| cvr::kdTree< T, D, U >::kdTree | ( | const kdTree< T, D, U > & | other | ) |
| virtual cvr::kdTree< T, D, U >::~kdTree | ( | ) | [virtual] |
Destructor.
| void cvr::kdTree< T, D, U >::add | ( | const T & | point, | |
| const D & | data | |||
| ) |
Consider the given element to be inserted in the tree after calling the build(const int) method.
The dimensionality of each point MUST be equal than the one first added, otherwise an assertion will be thrown when building the tree.
| bool cvr::kdTree< T, D, U >::build | ( | const int | bucketSize = 1 |
) |
Build the kd-Tree for all nodes added with the add() method, using the given bucket size as the maximum number of elements a node can contain.
The previous tree will be destroyed before the new one is constructed.
| bucketSize | maximum size of elements a node can contain (default value is 1). |
| virtual void cvr::kdTree< T, D, U >::clear | ( | ) | [virtual] |
Clear the tree.
All elements belonging to the tree will be removed. Also all elements added until now will be deleted.
| virtual kdTree<T,D,U>* cvr::kdTree< T, D, U >::clone | ( | ) | const [virtual] |
| kdTree<T,D,U>& cvr::kdTree< T, D, U >::copy | ( | const kdTree< T, D, U > & | other | ) |
| virtual bool cvr::kdTree< T, D, U >::empty | ( | ) | const [virtual] |
Check if the tree is empty.
| virtual int cvr::kdTree< T, D, U >::getNumberOfAddedElements | ( | ) | const [virtual] |
| virtual int cvr::kdTree< T, D, U >::getNumberOfLeaves | ( | ) | const [virtual] |
Get the number of leaves in the tree.
Return zero if the tree hasn't been build yet.
| virtual int cvr::kdTree< T, D, U >::getNumberOfLevels | ( | ) | const [virtual] |
Get the number of levels of the tree.
Return zero if the tree hasn't been build yet.
| virtual node* cvr::kdTree< T, D, U >::getRoot | ( | ) | [virtual] |
Get pointer to root node.
Return a null pointer if the tree hasn't been build yet.
| const std::string& cvr::kdTree< T, D, U >::name | ( | ) | const [virtual] |
| virtual kdTree<T,D,U>* cvr::kdTree< T, D, U >::newInstance | ( | ) | const [virtual] |
| kdTree<T,D,U>& cvr::kdTree< T, D, U >::operator= | ( | const kdTree< T, D, U > & | other | ) |
| virtual bool cvr::kdTree< T, D, U >::read | ( | ioHandler & | handler, | |
| const bool | complete = true | |||
| ) | [virtual] |
Read the parameters from the given ioHandler.
| handler | the ioHandler to be used | |
| complete | if true (the default) the enclosing begin/end will be also read, otherwise only the data block will be read. |
Reimplemented from cvr::ioObject.
| bool cvr::kdTree< T, D, U >::rebuild | ( | const int | bucketSize = 1 |
) |
Rebuild the kd-Tree for all elements added with the add() method and those already present in the tree, using the given bucket size as the maximum number of elements a node can contain.
Although the previous tree will be destroyed before the new one is constructed it will contain all elements contained in the old one.
Rebuilding the tree is quite slow since the elements have to be extracted and copied from the existing tree first. This is necessary since a kd-tree needs to know the complete set of data for building.
| bucketSize | maximum size of elements a node can contain (default value is 1). |
| bool cvr::kdTree< T, D, U >::searchBestBinFirst | ( | const int | k, | |
| const T & | key, | |||
| const int | emax, | |||
| mmap_type & | neighbors | |||
| ) | const |
Search the best-bin-first algorithm of Beis and Lowe.
Use this method only if the dimensionality of your data is high enough. The time savings take effect only if the kd-tree is big enough and the dimensionality of the data too. Make a few tests with your data in order to detect if this approximation is good enough and fast enough for you. Otherwise use the traditional search with searchNearest()
| k | number of elements you are looking for | |
| key | the point in the n-dimensional space you are looking for | |
| neighbors | contains the pointers to the found elements. You should NEVER delete these elements. | |
| emax | is the maximal number of visits allowed for leaf nodes. (in the original paper is called  ). |
| bool cvr::kdTree< T, D, U >::searchBestBinFirst | ( | const int | k, | |
| const T & | key, | |||
| const int | emax, | |||
| std::list< element * > & | neighbors | |||
| ) | const |
Search the best-bin-first algorithm of Beis and Lowe.
Use this method only if the dimensionality of your data is high enough. The time savings take effect only if the kd-tree is big enough and the dimensionality of the data too. Make a few tests with your data in order to detect if this approximation is good enough and fast enough for you. Otherwise use the traditional search with searchNearest()
| k | number of elements you are looking for | |
| key | the point in the n-dimensional space you are looking for | |
| neighbors | contains the pointers to the found elements. You should NEVER delete these elements. | |
| emax | is the maximal number of visits allowed for leaf nodes. (in the original paper is called ). Of course there can be more visits than emax if it is necessary to find at least k neighbors. |
| bool cvr::kdTree< T, D, U >::searchExactly | ( | const T & | key, | |
| std::list< element > & | elems | |||
| ) | const |
Search for all elements with exactly the given position in the hyperspace.
This is the classical search in a kd-tree, that assumes that a leaf node contains exactly the given point. If found, the contents of the element will by copied in the elem attributes and true will be returned. Otherwise false will be returned.
| key | point in the n-dimensional space you are looking for. | |
| elems | a list containing copies to all found elements with the given keys |
| bool cvr::kdTree< T, D, U >::searchExactly | ( | const T & | key, | |
| element & | elem | |||
| ) | const |
Search for an element with exactly the given position in the hyperspace.
This is the classical search in a kd-tree, that assumes that a leaf node contains exactly the given point. If found, the contents of the element will by copied in the elem attributes and true will be returned. Otherwise false will be returned.
If the key is present more than once, only the "first" one will be returned, which is the first one the list of points at the left-most node containing it.
| key | point in the n-dimensional space you are looking for. | |
| elem | the contents of the found point will be left here. |
| bool cvr::kdTree< T, D, U >::searchNearest | ( | const int | k, | |
| const T & | key, | |||
| mmap_type & | neighbors | |||
| ) | const |
Search for the nearest k elements in the tree to the given key point.
If you are looking just for the nearest elements (i.e. k=1) use the searchNearest(const T&,D&) or searchNearest(const T&,element&) methods instead. They are optimized for this case and are much faster.
| k | number of elements you are looking for. | |
| key | the point in the n-dimensional space you are looking for. | |
| neighbors | is a multimap containing as access key the square of the euclidean distance or the result of the given distantor between the corresponding element* and the search key. Remember that if you iterate the multimap, the elements will be sorted in increasing order of the distance (i.e. the nearest element first). You should NEVER delete the pointed elements. |
| bool cvr::kdTree< T, D, U >::searchNearest | ( | const int | k, | |
| const T & | key, | |||
| std::list< element * > & | neighbors | |||
| ) | const |
Search for the nearest k elements in the tree to the given key point.
If you are looking just for the nearest elements (i.e. k=1) use the searchNearest(const T&,D&) or searchNearest(const T&,element&) methods instead. They are optimized for this case and are much faster.
| k | number of elements you are looking for | |
| key | the point in the n-dimensional space you are looking for | |
| neighbors | contains the pointers to the found elements. You should NEVER delete these elements. |
| bool cvr::kdTree< T, D, U >::searchNearest | ( | const T & | key, | |
| D & | data | |||
| ) | const |
Search for the nearest element in the tree to the given key point.
If found, the contents of the element will by copied in the elem parameters and true will be returned. Otherwise false will be returned.
| key | point in the n-dimensional space you are looking for. | |
| data | the contents of the found nearest point will be left here. |
| bool cvr::kdTree< T, D, U >::searchNearest | ( | const T & | key, | |
| element & | elem, | |||
| distance_type & | dist | |||
| ) | const |
Search for the nearest element in the tree to the given key point.
If found, the contents of the element will by copied in the elem parameters and true will be returned. Otherwise false will be returned.
| key | point in the n-dimensional space you are looking for. | |
| elem | the contents of the found point will be left here. | |
| dist | distance between the points. The type of distance is determined by the used distanctor (the third template type of the tree, which return per default the square of the euclidean distance). |
| bool cvr::kdTree< T, D, U >::searchNearest | ( | const T & | key, | |
| element & | elem | |||
| ) | const |
Search for the nearest element in the tree to the given key point.
If found, the contents of the element will by copied in the elem parameters and true will be returned. Otherwise false will be returned.
| key | point in the n-dimensional space you are looking for. | |
| elem | the contents of the found point will be left here. |
| bool cvr::kdTree< T, D, U >::searchNearest | ( | const T & | key, | |
| element *& | elem, | |||
| distance_type & | dist | |||
| ) | const |
Search for the nearest element in the tree to the given key point.
If found, a pointer to the element will be written in the elem parameters and true will be returned. Otherwise false will be returned and the pointer will be set to zero.
The pointer is not const to allow you to change the data of the element, but if you also change the point the tree will be corrupted and will not work appropriately. There is no way to change the search keys dynamically in a kd-tree without a heavy load of computation. If that is what you are looking for, you should consider rebuilding the entire tree (expensive!).
| key | point in the n-dimensional space you are looking for. | |
| elem | pointer to the contents of the point found, or zero if not found. You should never delete the pointed data. | |
| dist | distance between the points. The type of distance is determined by the used distantor (the third template type of the tree, which returns per default the square of the euclidean distance). |
| bool cvr::kdTree< T, D, U >::searchNearest | ( | const T & | key, | |
| element *& | elem | |||
| ) | const |
Search for the nearest element in the tree to the given key point.
If found, a pointer to the element will be written in the elem parameters and true will be returned. Otherwise false will be returned and the pointer will be set to zero.
The pointer is not const to allow you to change the data of the element, but if you also change the point, the tree will be corrupted and will not work appropriately. There is no way to change the search keys dynamically in a kd-tree without a heavy load of computation. If that is what you are looking for, you should consider rebuilding the entire tree (expensive!).
| key | point in the n-dimensional space you are looking for. | |
| elem | pointer to the contents of the point found, or zero if not found. You should never delete the pointed data. |
| bool cvr::kdTree< T, D, U >::searchRange | ( | const T & | boxMin, | |
| const T & | boxMax, | |||
| std::list< element * > & | neighbors | |||
| ) | const |
Search for all points lying within the given hyperbox.
| boxMin | point representing the lowest values at each coordinate building the lower limits of the bounding box. | |
| boxMax | point representing the highest values at each coordinate building the upper limits of the bounding box. | |
| neighbors | list of pointer to the elements found until now. |
| bool cvr::kdTree< T, D, U >::searchWithin | ( | const T & | key, | |
| const distance_type & | dist, | |||
| mmap_type & | neighbors | |||
| ) | const |
Search for elements in an hyper-spheric neighbourhood of a given key point, i.e.
search for all elements that reside within a hypersphere with the given radius centered at the given key. Note that the hypersphere is always defined using an Euclidean distance, no matter of the specified distanctor policy.
The returned multimap is always sorted in ascending order of the distances (this is a property of all std::multimaps). If you want to save some time and don't need the sorted data consider using the other searchWithin() method, which stores the result in a std::list.
| key | point at which the hypersphere must be centered | |
| dist | allowed distance from the key point. Note that this represents exaclty the radius of the hypersphere and not the square of it. | |
| neighbors | multimap of elements found. You should NEVER delete the pointed elements. Note that the keys used to sort the multimap are the square of the distances to the given key point. This is done this way to save the time of applying the "sqrt()" function, which takes some time. |
| bool cvr::kdTree< T, D, U >::searchWithin | ( | const T & | key, | |
| const distance_type & | dist, | |||
| std::list< element * > & | elems | |||
| ) | const |
Search for elements in an hyper-spheric neighbourhood of a given key point, i.e.
search for all elements that reside within a hypersphere with the given radius centered at the given key. Note that the hypersphere is always defined using an Euclidean distance, no matter of the specified distanctor policy.
The returned list of elements is not sorted. If you need it sorted you should use the searchWithin() method with the multimap result.
| virtual int cvr::kdTree< T, D, U >::size | ( | ) | const [virtual] |
Get the number of elements in the built tree.
Note that this value can differ substantially from the value returned by getNumberOfAddedElements(). The latter don't belong to the tree yet. Thus, adding elements, then calling build and then adding more elements, generally results in two different values.
The return value is zero if no tree has been built yet.
| virtual bool cvr::kdTree< T, D, U >::write | ( | ioHandler & | handler, | |
| const bool | complete = true | |||
| ) | const [virtual] |
Write the parameters in the given ioHandler.
| handler | the ioHandler to be used | |
| complete | if true (the default) the enclosing begin/end will be also written, otherwise only the data block will be written. |
Reimplemented from cvr::ioObject.
U cvr::kdTree< T, D, U >::distantor_ [protected] |
Instance of the policy class used for computing the distances.
int cvr::kdTree< T, D, U >::levels_ [protected] |
Number of levels in the tree.
int cvr::kdTree< T, D, U >::numAddedElements_ [protected] |
Number of elements added to the tree (see add()).
int cvr::kdTree< T, D, U >::numElements_ [protected] |
Number of elements contained in the tree.
int cvr::kdTree< T, D, U >::numLeaves_ [protected] |
Number of leaf nodes in the tree.
node* cvr::kdTree< T, D, U >::root_ [protected] |
The root node.
matrix<value_type> cvr::kdTree< T, D, U >::totalBounds_ [protected] |
std::list<element*> cvr::kdTree< T, D, U >::treePoints_ [protected] |
Elements that will be contained in the tree.
All nodes contain pointers to the elements objects, that will be transfered to the nodes in the tree with the build method. Thereafter, this list will be empty.
