KDTree< T, N, Object, NodeData > Class Template Reference

A hierarchical spatial index. More...

#include <geomc/shape/KDTree.h>

Classes
class	KDNodeIterator
struct	KDStructureParams
	Structure encapsulating the tree balancing parameters. More...

Public Types
typedef KDNodeIterator< true >	const_node_iterator
	Const iterator over the internal tree nodes.
typedef std::list< Object >::const_iterator	const_object_iterator
	Const iterator over objects.
typedef KDNodeIterator< false >	node_iterator
	Iterator over the internal tree nodes.
typedef std::list< Object >::iterator	object_iterator
	Iterator over objects.

Public Member Functions
	KDTree ()
	Construct an empty KDTree with the default structure parameters for this dimension.
	KDTree (Object *objs, index_t nobjs, const KDStructureParams params=DefaultParameters)
	Construct a KDTree initialized with objs.
template<typename ObjectIterator>
	KDTree (ObjectIterator begin, ObjectIterator end, const KDStructureParams params=DefaultParameters)
	Construct a KDTree initialized with the objects contained in the interval [begin, end).
node_iterator	begin ()
const_node_iterator	begin () const
void	clear (const node_iterator &node)
node_iterator	end ()
const_node_iterator	end () const
node_iterator	erase (const node_iterator &node)
object_iterator	erase (const object_iterator &obj, const node_iterator &node)
void	flatten (const node_iterator &node)
const KDStructureParams &	getStructureParams ()
	Get the parameters describing the current tree-balancing strategy.
object_iterator	insert (const node_iterator &node, const Object &obj)
node_iterator	insertChild (const node_iterator &node)
Object &	nearest (const Vec< T, N > &p)
const Object &	nearest (const Vec< T, N > &p) const
index_t	nobjects () const
	Number of data objects in the tree.
void	rebalance ()
void	rebalance (const KDStructureParams &newParams)
void	rebalance (const node_iterator &node)

Detailed Description

template<typename T, index_t N, typename Object, typename NodeData>
class geom::KDTree< T, N, Object, NodeData >

A hierarchical spatial index.

Template Parameters

T	Numeric type.
N	Dimensionality of data.
Object	Spatial object to be indexed. May be a Vec<T,N>, a Bounded<T,N>, or a std::pair<K,V> with K either of the former.
NodeData	Optional data to store with each internal node of the tree.

Member Function Documentation

begin() [1/2]

template<typename T, index_t N, typename Object, typename NodeData>

node_iterator begin ( )

inline

Return an iterator pointing at the root tree node. Use +i and -i to ascend and descend to the first-child and parent nodes respectively. ++i and --i navigate the tree in breadth-first order, and can therefore be used to find the next and previous siblings.

begin() [2/2]

template<typename T, index_t N, typename Object, typename NodeData>

const_node_iterator begin ( ) const

inline

Return a const iterator pointing at the root tree node. Use +i and -i to ascend and descend to the first-child and parent nodes respectively. ++i and --i navigate the tree in breadth-first order, and can therefore be used to find the next and previous siblings.

clear()

template<typename T, index_t N, typename Object, typename NodeData>

void clear ( const node_iterator & node )

inline

Empty the given node of all its objects, and delete all its child nodes. Runs in O(n) time on the node count of the emptied subtree.

Any iterators pointing to nodes or objects in the deleted subtree are invalidated.

end() [1/2]

template<typename T, index_t N, typename Object, typename NodeData>

node_iterator end ( )

inline

Return an iterator pointing beyond the last node in the tree; conceptually the parent of the root.

end() [2/2]

template<typename T, index_t N, typename Object, typename NodeData>

const_node_iterator end ( ) const

inline

Return a const iterator pointing beyond the last node in the tree in breadth-first order; conceptually the parent of the root.

erase() [1/2]

template<typename T, index_t N, typename Object, typename NodeData>

node_iterator erase ( const node_iterator & node )

inline

Remove the given node, all of its children, and all the objects it contains. Runs in O(n) time on the node count of the deleted subtree.

The root node cannot be erased. If it is passed as an argument, it is returned without deletion.

Any iterators pointing to this node, any of its descendents, or the objects contained therein are invalidated. If deleting this node leaves one remaining sibling, then the sibling will be absorbed into its parent and its iterator will be invalidated.

Returns

The node after the deleted node, in breadth-first order.

erase() [2/2]

template<typename T, index_t N, typename Object, typename NodeData>

object_iterator erase ( const object_iterator & obj, const node_iterator & node )

inline

Remove the object at the given iterator from the given leaf node.

If the node is not a leaf or does not contain the object, no change is made and the original iterator is returned. Otherwise, an iterator to the next object is returned.

Both iterators may be invalidated by this operation.

flatten()

template<typename T, index_t N, typename Object, typename NodeData>

void flatten ( const node_iterator & node )

inline

Delete all the child nodes of the given node, and assign all the objects below to it. Runs in O(n) time on the node count of the emptied subtree.

Any iterators pointing to nodes in the deleted subtree are invalidated.

insert()

template<typename T, index_t N, typename Object, typename NodeData>

object_iterator insert ( const node_iterator & node, const Object & obj )

inline

Insert the given object into the tree under the given node. The tree will be descended recursively until the best leaf is found.

insertChild()

template<typename T, index_t N, typename Object, typename NodeData>

node_iterator insertChild ( const node_iterator & node )

inline

Insert a new tree node under the given node. If the created node is the first child of node, then it will contain all of node's objects, otherwise it will be empty.

Returns

The inserted node.

nearest() [1/2]

template<typename T, index_t N, typename Object, typename NodeData>

Object & nearest ( const Vec< T, N > & p )

inline

Return the object in the tree closest to the query point q.

nearest() [2/2]

template<typename T, index_t N, typename Object, typename NodeData>

const Object & nearest ( const Vec< T, N > & p ) const

inline

Return the object in the tree closest to the query point q.

rebalance() [1/3]

template<typename T, index_t N, typename Object, typename NodeData>

void rebalance ( )

inline

Rebuild the entire tree.

All iterators are invalidated.

rebalance() [2/3]

template<typename T, index_t N, typename Object, typename NodeData>

void rebalance ( const KDStructureParams & newParams )

inline

Change the balancing parameters of the tree, and rebuild it according to the new artings.

rebalance() [3/3]

template<typename T, index_t N, typename Object, typename NodeData>

void rebalance ( const node_iterator & node )

inline

Rebuild the given subtree according to its current balancing parameters, in O(n log(n)) time. If rebuilding from the root, it is more efficient to call rebalance() with no args.

Any iterators pointing to descendents of the given node are invalidated.

---

The documentation for this class was generated from the following file:

• geomc/shape/KDTree.h