spatial::kd_tree< Point, Value, Discriminator, Size > Class Template Reference
A k-d tree divides a k-dimensional space relative to the points it contains by storing them in a binary tree, discriminating by a different dimension at each level of the tree. More...
#include <kd_tree.h>
Classes | |
| struct | node_comparator |
Public Types | |
| typedef kd_tree_traits< kd_tree > | traits |
| typedef kd_tree_const_traits < kd_tree > | 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 rectangle_region < key_type > | default_region_type |
| typedef detail::kd_tree_range_search_iterator < traits, default_region_type > | iterator |
| typedef detail::kd_tree_range_search_iterator < const_traits, default_region_type > | const_iterator |
| typedef Size | size_type |
| typedef detail::kd_tree_node < traits > | node_type |
Public Member Functions | |
| kd_tree () | |
| Constructs an empty kd_tree. | |
| kd_tree (const kd_tree &tree) | |
| Constructs a copy of a kd_tree. | |
| virtual | ~kd_tree () |
| Deallocates the memory allocated by the kd_tree. | |
| void | clear () |
| Removes all elements from the container, leaving it empty. | |
| kd_tree & | operator= (const kd_tree &tree) |
| Copies the contents of a kd_tree, destroying all existing values. | |
| const size_type | size () const |
| Returns the number of point-value mappings in the kd_tree. | |
| 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 *const 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 *const 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. | |
| iterator | 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. | |
| template<typename Region > | |
| detail::kd_tree_range_search_iterator < traits, Region > | begin (const Region ®ion) |
| template<typename Region > | |
| detail::kd_tree_range_search_iterator < traits, Region > | end () |
| template<typename Region > | |
| detail::kd_tree_range_search_iterator < const_traits, Region > | begin (const Region ®ion) const |
| template<typename Region > | |
| detail::kd_tree_range_search_iterator < const_traits, Region > | end () const |
| bool | get (const key_type &point, mapped_type *const value=0) const |
| Returns true if the kd_tree 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 kd_tree. | |
| iterator | find_nearest_neighbor (const key_type &point, const bool omit_query_point=true) |
| Returns the location of the point-value mapping closest to the specified point in Euclidean space where the Euclidean distance between the points is non-zero (unless omit_query_point is set to false). | |
Friends | |
| bool | operator== (const kd_tree &tree1, const kd_tree &tree2) |
| Tests if two kd_tree instances contain exactly the same key-value pairs, but not necessarily in the same hierarchical arrangement. | |
Detailed Description
template<typename Point, typename Value, typename Discriminator = unsigned char, typename Size = unsigned int>
class spatial::kd_tree< Point, Value, Discriminator, Size >
A k-d tree divides a k-dimensional space relative to the points it contains by storing them in a binary tree, discriminating by a different dimension at each level of the tree.
It allows efficient point data retrieval (O(lg(n))) and range searching.
kd_tree 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.
Member Typedef Documentation
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| typedef detail::kd_tree_range_search_iterator<const_traits, default_region_type> spatial::kd_tree< Point, Value, Discriminator, Size >::const_iterator |
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| typedef pointer const spatial::kd_tree< Point, Value, Discriminator, Size >::const_pointer |
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| typedef const reference spatial::kd_tree< Point, Value, Discriminator, Size >::const_reference |
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| typedef kd_tree_const_traits<kd_tree> spatial::kd_tree< Point, Value, Discriminator, Size >::const_traits |
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| typedef rectangle_region<key_type> spatial::kd_tree< Point, Value, Discriminator, Size >::default_region_type |
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| typedef Discriminator spatial::kd_tree< Point, Value, Discriminator, Size >::discriminator_type |
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| typedef detail::kd_tree_range_search_iterator<traits, default_region_type> spatial::kd_tree< Point, Value, Discriminator, Size >::iterator |
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| typedef Point spatial::kd_tree< Point, Value, Discriminator, Size >::key_type |
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| typedef Value spatial::kd_tree< Point, Value, Discriminator, Size >::mapped_type |
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| typedef detail::kd_tree_node<traits> spatial::kd_tree< Point, Value, Discriminator, Size >::node_type |
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| typedef value_type* spatial::kd_tree< Point, Value, Discriminator, Size >::pointer |
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| typedef value_type& spatial::kd_tree< Point, Value, Discriminator, Size >::reference |
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| typedef Size spatial::kd_tree< Point, Value, Discriminator, Size >::size_type |
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| typedef kd_tree_traits<kd_tree> spatial::kd_tree< Point, Value, Discriminator, Size >::traits |
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| typedef std::pair<const key_type, mapped_type> spatial::kd_tree< Point, Value, Discriminator, Size >::value_type |
Constructor & Destructor Documentation
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| spatial::kd_tree< Point, Value, Discriminator, Size >::kd_tree | ( | ) | [inline, explicit] |
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| spatial::kd_tree< Point, Value, Discriminator, Size >::kd_tree | ( | const kd_tree< Point, Value, Discriminator, Size > & | tree | ) | [inline] |
Constructs a copy of a kd_tree.
- Parameters:
-
tree The kd_tree to copy.
Definition at line 430 of file kd_tree.h.
References spatial::kd_tree< Point, Value, Discriminator, Size >::begin().
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| virtual spatial::kd_tree< Point, Value, Discriminator, Size >::~kd_tree | ( | ) | [inline, virtual] |
Member Function Documentation
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| iterator spatial::kd_tree< Point, Value, Discriminator, Size >::begin | ( | ) | [inline] |
Returns an 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 501 of file kd_tree.h.
Referenced by spatial::kd_tree< Point, Value, Discriminator, Size >::kd_tree(), and spatial::kd_tree< Point, Value, Discriminator, Size >::operator=().
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| iterator spatial::kd_tree< Point, Value, Discriminator, Size >::begin | ( | const key_type & | lower, |
| const key_type & | upper | ||
| ) | [inline] |
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.
- Parameters:
-
lower The lower left-hand corner of the bounding rectangle. upper The upper right-hand corner of the bounding rectangle.
- Returns:
- A kd_tree::iterator for mappings that are contained in the specified rectangle.
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| const_iterator spatial::kd_tree< Point, Value, Discriminator, Size >::begin | ( | const key_type & | lower, |
| const key_type & | upper | ||
| ) | const [inline] |
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.
- Parameters:
-
lower The lower left-hand corner of the bounding rectangle. upper The upper right-hand corner of the bounding rectangle.
- Returns:
- A kd_tree::const_iterator for mappings that are contained in the specified rectangle.
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
template<typename Region >
| detail::kd_tree_range_search_iterator<traits, Region> spatial::kd_tree< Point, Value, Discriminator, Size >::begin | ( | const Region & | region | ) | [inline] |
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
template<typename Region >
| detail::kd_tree_range_search_iterator<const_traits, Region> spatial::kd_tree< Point, Value, Discriminator, Size >::begin | ( | const Region & | region | ) | const [inline] |
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| const_iterator spatial::kd_tree< Point, Value, Discriminator, Size >::begin | ( | ) | const [inline] |
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| void spatial::kd_tree< Point, Value, Discriminator, Size >::clear | ( | ) | [inline] |
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| bool spatial::kd_tree< Point, Value, Discriminator, Size >::empty | ( | ) | const [inline] |
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| iterator& spatial::kd_tree< Point, Value, Discriminator, Size >::end | ( | ) | [inline] |
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| const const_iterator& spatial::kd_tree< Point, Value, Discriminator, Size >::end | ( | ) | const [inline] |
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
template<typename Region >
| detail::kd_tree_range_search_iterator<traits, Region> spatial::kd_tree< Point, Value, Discriminator, Size >::end | ( | ) | [inline] |
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
template<typename Region >
| detail::kd_tree_range_search_iterator<const_traits, Region> spatial::kd_tree< Point, Value, Discriminator, Size >::end | ( | ) | const [inline] |
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| size_type spatial::kd_tree< Point, Value, Discriminator, Size >::erase | ( | const key_type & | point | ) | [inline] |
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| iterator spatial::kd_tree< Point, Value, Discriminator, Size >::erase | ( | iterator | pos | ) | [inline] |
Removes the point-value mapping at the specified position.
The supplied iterator becomes invalid upon a successful erasure.
- Parameters:
-
pos The kd_tree::iterator denoting the location of the mapping.
- Returns:
- An iterator pointing to the next element after pos in the range search sequence containing pos. If no such element exists, or if the element pointed to by pos is not contained in the tree (making it impossible to remove from the tree), end() is returned.
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| iterator spatial::kd_tree< Point, Value, Discriminator, Size >::find | ( | const key_type & | point | ) | [inline] |
Returns the location of the point-value mapping for the specified point (slower than get()).
If there is no mapping present, the iterator is equivalent to end().
- Parameters:
-
point The key of the poinit-value mapping to find.
- Returns:
- A kd_tree::iterator for the location of the point-value mapping matching the specified point. end() if there is no mapping.
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| const_iterator spatial::kd_tree< Point, Value, Discriminator, Size >::find | ( | const key_type & | point | ) | const [inline] |
Returns the location of the point-value mapping for the specified point (slower than get()).
If there is no mapping present, the iterator is equivalent to end().
- Parameters:
-
point The key of the poinit-value mapping to find.
- Returns:
- A kd_tree::const_iterator for the location of the point-value mapping matching the specified point. end() if there is no mapping.
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| iterator spatial::kd_tree< Point, Value, Discriminator, Size >::find_nearest_neighbor | ( | const key_type & | point, |
| const bool | omit_query_point = true |
||
| ) | [inline] |
Returns the location of the point-value mapping closest to the specified point in Euclidean space where the Euclidean distance between the points is non-zero (unless omit_query_point is set to false).
If there is more than one mapping at the same closest distance, one of the mappings will be returned, but which mapping is returned is unspecified.
Note, this implementation is efficient for low dimensionalities. High-dimensional data is better served by an approximation algorithm. An approximation algorithm for high-dimensional data will be provided in a future release after a satisfactory refactoring is achieved to separate specialized search algorithms from the kd_tree class template.
- Parameters:
-
point The nearest neighbor query point. omit_query_point If true, mappings at a distance of zero are omitted from the result. If false, mappings at a distance of zero are included. The default value of this parameter is true because our most common usage is to search for neighbors of points already contained in the tree.
- Returns:
- A kd_tree::iterator for the location of the point-value mapping closest to the query point. end() if there is no such mapping (e.g., the tree is empty).
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| bool spatial::kd_tree< Point, Value, Discriminator, Size >::get | ( | const key_type & | point, |
| mapped_type *const | value = 0 |
||
| ) | const [inline] |
Returns true if the kd_tree contains a point-value mapping for the specified point, false if not.
Optionally, retrieves the value at the given location (faster than find()).
- Parameters:
-
point The location from which to retrieve the value. value A pointer to a kd_tree::mapped_type in which to store the retrieved value. This pointer may be null if you do not want to retrieve the value and only want to see if the point is present in the kd_tree.
- Returns:
- true if the kd_tree contains a point-value mapping for the specified point, false if not.
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| bool spatial::kd_tree< Point, Value, Discriminator, Size >::insert | ( | const key_type & | point, |
| const mapped_type & | value, | ||
| mapped_type *const | replaced = 0 |
||
| ) | [inline] |
Inserts a key value pair, replacing any existing value that may be present, and optionally retrieving the replaced value.
- Parameters:
-
point The key corresponding to the value to be inserted value The value to be inserted. replaced If you want to retrieve a value that was replaced, have this parameter point to a valid object to store the value. If not, its default value of zero will prevent it from being retrieved.
- Returns:
- true if value is replaced, false if not.
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| std::pair<iterator,bool> spatial::kd_tree< Point, Value, Discriminator, Size >::insert | ( | const value_type & | mapping | ) | [inline] |
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*)
- Returns:
- A pair containing the iterator pointing to the inserted value and true if the mapping is inserted. If the value is not inserted, a pair containing the iterator pointing to the existing value and false.
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| const size_type spatial::kd_tree< Point, Value, Discriminator, Size >::max_size | ( | ) | const [inline] |
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| kd_tree& spatial::kd_tree< Point, Value, Discriminator, Size >::operator= | ( | const kd_tree< Point, Value, Discriminator, Size > & | tree | ) | [inline] |
Copies the contents of a kd_tree, destroying all existing values.
- Parameters:
-
tree The kd_tree to copy.
- Returns:
- *this
Definition at line 458 of file kd_tree.h.
References spatial::kd_tree< Point, Value, Discriminator, Size >::begin().
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| mapped_type& spatial::kd_tree< Point, Value, Discriminator, Size >::operator[] | ( | const key_type & | point | ) | [inline] |
Retrieves the value at the given location.
In conformance with the STL map interface, if the point key does not occur in the kd_tree, a new value is inserted and returned using the default constructor for kd_tree::mapped_type.
- Parameters:
-
point The location from which to retrieve the value.
- Returns:
- The value at the given location.
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| void spatial::kd_tree< Point, Value, Discriminator, Size >::optimize | ( | ) | [inline] |
Optimizes the performance of future search operations by balancing the kd_tree.
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.
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| bool spatial::kd_tree< Point, Value, Discriminator, Size >::remove | ( | const key_type & | point, |
| mapped_type *const | erased = 0 |
||
| ) | [inline] |
Removes the point-value mapping corresponding to the given point key.
Optionally, retrieves the removed value if a mapping was present.
- Parameters:
-
point The point key of the mapping to remove. erased A pointer to a mapped_type in which to store the erased value. This pointer may be null if you do not want to retrieve the removed value and only want to remove the mapping.
- Returns:
- true if a mapping was present and removed, false if not.
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| const size_type spatial::kd_tree< Point, Value, Discriminator, Size >::size | ( | ) | const [inline] |
Friends And Related Function Documentation
template<typename Point , typename Value , typename Discriminator = unsigned char, typename Size = unsigned int>
| bool operator== | ( | const kd_tree< Point, Value, Discriminator, Size > & | tree1, |
| const kd_tree< Point, Value, Discriminator, Size > & | tree2 | ||
| ) | [friend] |
Tests if two kd_tree instances contain exactly the same key-value pairs, but not necessarily in the same hierarchical arrangement.
Note, this is an expensive operation that we don't expect will ever be used except in support of unit tests.
Use namespace std::rel_ops from <utility> to gain the != operator.
- Parameters:
-
tree1 The first tree to compare. tree2 The second tree to compare.
- Returns:
- true if the two trees are equal, false if not.
The documentation for this class was generated from the following file:
Copyright © 2003-2005 Daniel F. Savarese.
Copyright © 2006-2009 Savarese Software Research Corporation.
Copyright © 2006-2009 Savarese Software Research Corporation.