#include <KDTree.h>
It allows efficient point data retrieval (O(lg(n))) and range searching.
KDTree tries to conform to the map interface from the STL where it makes sense. Therefore, you will find it can be used with some STL algorithms.
Definition at line 94 of file KDTree.h.
Public Types | |
| typedef KDTreeTraits< KDTree > | traits |
| typedef KDTreeConstTraits< KDTree > | const_traits |
| typedef Point | key_type |
| typedef Value | mapped_type |
| typedef std::pair< const key_type, mapped_type > | value_type |
| typedef value_type * | pointer |
| typedef pointer const | const_pointer |
| typedef value_type & | reference |
| typedef const reference | const_reference |
| typedef Discriminator | discriminator_type |
| typedef detail::KDTreeRangeSearchIterator< traits > | iterator |
| typedef detail::KDTreeRangeSearchIterator< const_traits > | const_iterator |
| typedef PointTraits< key_type > | point_traits |
| typedef Size | size_type |
| typedef detail::KDTreeNode< traits > | node_type |
| typedef node_type::child_type | child_type |
Public Member Functions | |
| KDTree () | |
| Constructs an empty KDTree. | |
| KDTree (const KDTree &tree) | |
| Constructs a copy of a KDTree. | |
| virtual | ~KDTree () |
| Deallocates the memory allocated by the KDTree. | |
| void | clear () |
| Removes all elements from the container, leaving it empty. | |
| const size_type | size () const |
| Returns the number of point-value mappings in the KDTree. | |
| const size_type | max_size () const |
| Returns the maximum number of elements that can be contained. | |
| bool | empty () const |
| Returns true if the container has no elements, false if it contains one or more elements. | |
| iterator | begin () |
| Returns an iterator pointing to the leftmost bottommost point in the container. | |
| const_iterator | begin () const |
| Returns a const iterator pointing to the leftmost bottommost point in the container. | |
| iterator & | end () |
| Returns an iterator denoting the end of a range. | |
| const const_iterator & | end () const |
| Returns a const iterator denoting the end of a range. | |
| bool | insert (const key_type &point, const mapped_type &value, mapped_type *replaced=0) |
| Inserts a key value pair, replacing any existing value that may be present, and optionally retrieving the replaced value. | |
| std::pair< iterator, bool > | insert (const value_type &mapping) |
| Inserts a key value pair, but--in conformance with the STL container interface--doesn't replace any existing value that may be present. | |
| mapped_type & | operator[] (const key_type &point) |
| Retrieves the value at the given location. | |
| bool | remove (const key_type &point, mapped_type *erased=0) |
| Removes the point-value mapping corresponding to the given point key. | |
| size_type | erase (const key_type &point) |
| Removes the point-value mapping corresponding to the given point key. | |
| void | erase (iterator pos) |
| Removes the point-value mapping at the specified position. | |
| iterator | begin (const key_type &lower, const key_type &upper) |
| Returns an iterator for mappings that are contained in the rectangle defined by the given lower left-hand and upper right-hand corners. | |
| const_iterator | begin (const key_type &lower, const key_type &upper) const |
| Returns a const iterator for mappings that are contained in the rectangle defined by the given lower left-hand and upper right-hand corners. | |
| bool | get (const key_type &point, mapped_type *value=0) const |
| Returns true if the KDTree contains a point-value mapping for the specified point, false if not. | |
| iterator | find (const key_type &point) |
| Returns the location of the point-value mapping for the specified point (slower than get()). | |
| const_iterator | find (const key_type &point) const |
| Returns the location of the point-value mapping for the specified point (slower than get()). | |
| void | optimize () |
| Optimizes the performance of future search operations by balancing the KDTree. | |
Static Public Member Functions | |
| static const unsigned int | dimensions () |
Classes | |
| struct | NodeComparator |
|
|||||
|
|
|
|||||
|
|
|
|||||
|
|
|
|||||
|
|
|
|||||
|
|
|
|||||
|
|
|
|||||
|
|
|
|||||
|
|
|
|||||
|
|
|
|||||
|
|
|
|||||
|
|
|
|||||
|
|
|
|||||
|
|
|
|||||
|
|
|
|||||
|
|
|
|||||
|
|
|
|||||||||
|
Constructs an empty KDTree.
|
|
||||||||||
|
Constructs a copy of a KDTree.
Definition at line 394 of file KDTree.h. References sava::spatial::KDTree< Point, Value, Dimensions, Discriminator, Size >::begin(). |
|
|||||||||
|
Deallocates the memory allocated by the KDTree.
|
|
||||||||||||||||
|
Returns a const iterator for mappings that are contained in the rectangle defined by the given lower left-hand and upper right-hand corners. The mappings returned include those occuring at points on the bounding rectangle, not just those inside.
|
|
||||||||||||||||
|
Returns an iterator for mappings that are contained in the rectangle defined by the given lower left-hand and upper right-hand corners. The mappings returned include those occuring at points on the bounding rectangle, not just those inside.
|
|
|||||||||
|
Returns a const iterator pointing to the leftmost bottommost point in the container. If empty, it equals end().
|
|
|||||||||
|
Returns an iterator pointing to the leftmost bottommost point in the container. If empty, it equals end().
Definition at line 451 of file KDTree.h. Referenced by sava::spatial::KDTree< Point, Value, Dimensions, Discriminator, Size >::KDTree(). |
|
|||||||||
|
Removes all elements from the container, leaving it empty.
|
|
|||||||||
|
|
|
|||||||||
|
Returns true if the container has no elements, false if it contains one or more elements.
|
|
|||||||||
|
Returns a const iterator denoting the end of a range.
|
|
|||||||||
|
Returns an iterator denoting the end of a range.
|
|
||||||||||
|
Removes the point-value mapping at the specified position.
|
|
||||||||||
|
Removes the point-value mapping corresponding to the given point key.
|
|
||||||||||
|
Returns the location of the point-value mapping for the specified point (slower than get()). If there is no mapping present, the iiterator is equivalent to end().
|
|
||||||||||
|
Returns the location of the point-value mapping for the specified point (slower than get()). If there is no mapping present, the iiterator is equivalent to end().
|
|
||||||||||||||||
|
Returns true if the KDTree contains a point-value mapping for the specified point, false if not. Optionally, retrieves the value at the given location (faster than find()).
|
|
||||||||||
|
Inserts a key value pair, but--in conformance with the STL container interface--doesn't replace any existing value that may be present. Note, this method is slower than bool insert(const key_type &, const mapped_type, mapped_type*)
|
|
||||||||||||||||||||
|
Inserts a key value pair, replacing any existing value that may be present, and optionally retrieving the replaced value.
|
|
|||||||||
|
Returns the maximum number of elements that can be contained.
|
|
||||||||||
|
Retrieves the value at the given location. In conformance with the STL map interface, if the point key does not occur in the KDTree, a new value is inserted and returned using the default constructor for KDTree::mapped_type.
|
|
|||||||||
|
Optimizes the performance of future search operations by balancing the KDTree. The balancing operation is relatively expensive, but can significantly improve the performance of searches. Usually, you don't have to optimize a tree which contains random key values inserted in a random order. |
|
||||||||||||||||
|
Removes the point-value mapping corresponding to the given point key. Optionally, retrieves the removed value if a mapping was present.
|
|
|||||||||
|
Returns the number of point-value mappings in the KDTree.
|