KDTree.h File Reference

#include <cstddef>
#include <cmath>
#include <iterator>
#include <vector>
#include <algorithm>
#include <functional>
#include <cassert>

Include dependency graph for KDTree.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	_Node_base
struct	_Node< _Val >
class	_Node_compare< _Val, _Acc, _Cmp >
struct	_Bracket_accessor< _Val >
struct	always_true< _Tp >
struct	squared_difference< _Tp, _Dist >
struct	squared_difference_counted< _Tp, _Dist >
class	_Alloc_base< _Tp, _Alloc >
class	_Alloc_base< _Tp, _Alloc >::NoLeakAlloc
class	_Base_iterator
class	_Iterator< _Val, _Ref, _Ptr >
struct	_Region< __K, _Val, _SubVal, _Acc, _Cmp >
class	KDTree< __K, _Val, _Acc, _Dist, _Cmp, _Alloc >

Namespaces
	KDTree

Macros
#define	INCLUDE_KDTREE_ACCESSOR_HPP
#define	INCLUDE_KDTREE_ALLOCATOR_HPP
#define	INCLUDE_KDTREE_ITERATOR_HPP
#define	INCLUDE_KDTREE_REGION_HPP
#define	INCLUDE_KDTREE_KDTREE_HPP
#define	KDTREE_VERSION   701
#define	KDTREE_LIB_VERSION   "0_7_1"

Functions
template<typename _ValA , typename _ValB , typename _Cmp , typename _Acc >
bool	_S_node_compare (const size_t __dim, const _Cmp &__cmp, const _Acc &__acc, const _ValA &__a, const _ValB &__b)
template<typename _ValA , typename _ValB , typename _Dist , typename _Acc >
_Dist::distance_type	_S_node_distance (const size_t __dim, const _Dist &__dist, const _Acc &__acc, const _ValA &__a, const _ValB &__b)
template<typename _ValA , typename _ValB , typename _Dist , typename _Acc >
_Dist::distance_type	_S_accumulate_node_distance (const size_t __dim, const _Dist &__dist, const _Acc &__acc, const _ValA &__a, const _ValB &__b)
template<typename _Val , typename _Cmp , typename _Acc , typename NodeType >
const NodeType *	_S_node_descend (const size_t __dim, const _Cmp &__cmp, const _Acc &__acc, const _Val &__val, const NodeType *__node)
template<class SearchVal , typename NodeType , typename _Cmp , typename _Acc , typename _Dist , typename _Predicate >
std::pair< const NodeType *, std::pair< size_t, typename _Dist::distance_type > >	_S_node_nearest (const size_t __k, size_t __dim, SearchVal const &__val, const NodeType *__node, const _Node_base *__end, const NodeType *__best, typename _Dist::distance_type __max, const _Cmp &__cmp, const _Acc &__acc, const _Dist &__dist, _Predicate __p)
template<typename _Val , typename _Ref , typename _Ptr >
bool	operator== (_Iterator< _Val, _Ref, _Ptr > const &, _Iterator< _Val, _Ref, _Ptr > const &)
template<typename _Val >
bool	operator== (_Iterator< _Val, const _Val &, const _Val * > const &, _Iterator< _Val, _Val &, _Val * > const &)
template<typename _Val >
bool	operator== (_Iterator< _Val, _Val &, _Val * > const &, _Iterator< _Val, const _Val &, const _Val * > const &)
template<typename _Val , typename _Ref , typename _Ptr >
bool	operator!= (_Iterator< _Val, _Ref, _Ptr > const &, _Iterator< _Val, _Ref, _Ptr > const &)
template<typename _Val >
bool	operator!= (_Iterator< _Val, const _Val &, const _Val * > const &, _Iterator< _Val, _Val &, _Val * > const &)
template<typename _Val >
bool	operator!= (_Iterator< _Val, _Val &, _Val * > const &, _Iterator< _Val, const _Val &, const _Val * > const &)

Detailed Description

Defines interfaces for nodes as used by the KDTree class.

Author

Martin F. Krafft libkd.nosp@m.tree.nosp@m.@pobo.nosp@m.x.ma.nosp@m.dduck.nosp@m..net

Defines the various functors and interfaces used for KDTree.

Author

Martin F. Krafft libkd.nosp@m.tree.nosp@m.@pobo.nosp@m.x.ma.nosp@m.dduck.nosp@m..net

Sylvain Bougerel sylva.nosp@m.in.b.nosp@m.ouger.nosp@m.el.d.nosp@m.evel@.nosp@m.gmai.nosp@m.l.com

Defines the allocator interface as used by the KDTree class.

Author

Martin F. Krafft libkd.nosp@m.tree.nosp@m.@pobo.nosp@m.x.ma.nosp@m.dduck.nosp@m..net

Defines interfaces for iterators as used by the KDTree class.

Author

Martin F. Krafft libkd.nosp@m.tree.nosp@m.@pobo.nosp@m.x.ma.nosp@m.dduck.nosp@m..net

Defines the interface of the _Region class.

Author

Martin F. Krafft libkd.nosp@m.tree.nosp@m.@pobo.nosp@m.x.ma.nosp@m.dduck.nosp@m..net

Defines the interface for the KDTree class.

Author

Martin F. Krafft libkd.nosp@m.tree.nosp@m.@pobo.nosp@m.x.ma.nosp@m.dduck.nosp@m..net

Paul Harris figured this stuff out (below) Notes: This is similar to a binary tree, but its not the same. There are a few important differences:

• Each level is sorted by a different criteria (this is fundamental to the design).

• It is possible to have children IDENTICAL to its parent in BOTH branches This is different to a binary tree, where identical children are always to the right So, KDTree has the relationships:

  • The left branch is <= its parent (in binary tree, this relationship is a plain < )
  • The right branch is <= its parent (same as binary tree)

  This is done for mostly for performance. Its a LOT easier to maintain a consistent tree if we use the <= relationship. Note that this relationship only makes a difference when searching for an exact item with find() or find_exact, other search, erase and insert functions don't notice the difference.

  In the case of binary trees, you can safely assume that the next identical item will be the child leaf, but in the case of KDTree, the next identical item might be a long way down a subtree, because of the various different sort criteria.

  So to erase() a node from a KDTree could require serious and complicated tree rebalancing to maintain consistency... IF we required binary-tree-like relationships.

  This has no effect on insert()s, a < test is good enough to keep consistency.

  It has an effect on find() searches:

  • Instead of using compare(child,node) for a < relationship and following 1 branch, we must use !compare(node,child) for a <= relationship, and test BOTH branches, as we could potentially go down both branches.

  It has no real effect on bounds-based searches (like find_nearest, find_within_range) as it compares vs a boundary and would follow both branches if required.

  This has no real effect on erase()s, a < test is good enough to keep consistency.

Macro Definition Documentation

INCLUDE_KDTREE_ACCESSOR_HPP

#define INCLUDE_KDTREE_ACCESSOR_HPP

INCLUDE_KDTREE_ALLOCATOR_HPP

#define INCLUDE_KDTREE_ALLOCATOR_HPP

INCLUDE_KDTREE_ITERATOR_HPP

#define INCLUDE_KDTREE_ITERATOR_HPP

INCLUDE_KDTREE_KDTREE_HPP

#define INCLUDE_KDTREE_KDTREE_HPP

INCLUDE_KDTREE_REGION_HPP

#define INCLUDE_KDTREE_REGION_HPP

KDTREE_LIB_VERSION

#define KDTREE_LIB_VERSION   "0_7_1"

KDTREE_VERSION

#define KDTREE_VERSION   701