Templated rtree class. More...

#include <vgl_algo_fwd.h>

Public Types
typedef vgl_rtree_probe< V, B, C >	probe

typedef vgl_rtree_iterator< V, B, C >	iterator
	iterators. More...

typedef vgl_rtree_const_iterator< V, B, C >	const_iterator

typedef vgl_rtree_node< V, B, C >	node

Public Member Functions
	vgl_rtree ()

	~vgl_rtree ()

iterator	begin ()

const_iterator	begin () const

iterator	end ()

const_iterator	end () const

void	add (V const &v)
	add an element to the rtree. More...

void	remove (V const &v)
	remove one element from the rtree. More...

bool	contains (V const &v) const
	return true iff the rtree contains an element equal to v. More...

void	erase (iterator i)
	erase the element pointed to by the iterator. More...

void	get (B const &region, std::vector< V > &vs) const
	get elements in the given region. More...

void	get (vgl_rtree_probe< V, B, C > const &region, std::vector< V > &vs) const
	get elements which meet the given probe. More...

void	get_all (std::vector< V > &vs) const
	get all elements in the tree. More...

bool	empty () const
	return true iff the tree has no elements. More...

unsigned	size () const
	return number of elements stored in the tree. More...

unsigned	nodes () const
	return number of nodes used by the tree. More...

node *	secret_get_root () const

void	print () const

Private Member Functions
vgl_rtree< V, B, C > &	operator= (vgl_rtree< V, B, C > const &)

	vgl_rtree (vgl_rtree< V, B, C > const &)

Private Attributes
node *	root

Detailed Description

template<class V, class B, class C>
class vgl_rtree< V, B, C >

Templated rtree class.

The rtree is templated over the element type V, the type B of the bounding region used (e.g. axis-aligned bounding boxes are common but there are other possibilities such as boxes which are axis-aligned ones or even bounding ellipsoids) and a type C which is used as a namespace for some functionality needed by the rtree.

The rtree is a container of Vs which may contain multiple copies of the same element. The container for client use is called vgl_rtree<V, B, C> and is defined at the bottom of the file.

Note that the iterators are bidirectional but only forward advancement has been implement so far (it's tedious work). Moreover, beware that changing an element through an iterator will not update the rtree, so may lead to the data structure being corrupted.

V : element type
B : bounds type
C : mystery type

The C-device makes it possible to have an rtree of Vs using Bs without having to modify the class definitions of V or B. It may be better to have C's signatures non-static and store a C on every tree node, but I don't know about this.

It is assumed that the cost of copying (e.g. by assignment) Vs and Bs is not too high. In any case, I suggest you inline and optimize heavily when compiling this source file.

V must have the following signatures:

V::V();
V::V(V const &);
V::operator==(V const &) or operator==(V const &, V const &);

B must have the following signatures :

B::B();
B::B(const &);
B::operator==(V const &) or operator==(B const &, B const &);

C must have the following (static method) signatures :

void  C::init  (B &, V const &);
void  C::update(B &, V const &);
void  C::update(B &, B const &);
bool  C::meet  (B const &, V const &);
bool  C::meet  (B const &, B const &);
float C::volume(B const &);

The volume() method is used by the rtree to make decisions about where to put new elements.

Definition at line 35 of file vgl_algo_fwd.h.

Member Typedef Documentation

◆ const_iterator

template<class V , class B , class C >

typedef vgl_rtree_const_iterator<V, B, C> vgl_rtree< V, B, C >::const_iterator

Definition at line 257 of file vgl_rtree.h.

◆ iterator

template<class V , class B , class C >

typedef vgl_rtree_iterator<V, B, C> vgl_rtree< V, B, C >::iterator

iterators.

Definition at line 256 of file vgl_rtree.h.

◆ node

template<class V , class B , class C >

typedef vgl_rtree_node<V, B, C> vgl_rtree< V, B, C >::node

Definition at line 345 of file vgl_rtree.h.

◆ probe

template<class V , class B , class C >

typedef vgl_rtree_probe<V, B, C> vgl_rtree< V, B, C >::probe

Definition at line 253 of file vgl_rtree.h.

Constructor & Destructor Documentation

◆ vgl_rtree() [1/2]

template<class V , class B , class C >

vgl_rtree< V, B, C >::vgl_rtree ( )

inline

Definition at line 245 of file vgl_rtree.h.

◆ ~vgl_rtree()

template<class V , class B , class C >

vgl_rtree< V, B, C >::~vgl_rtree ( )

inline

Definition at line 246 of file vgl_rtree.h.

◆ vgl_rtree() [2/2]

template<class V , class B , class C >

vgl_rtree< V, B, C >::vgl_rtree ( vgl_rtree< V, B, C > const & )

inlineprivate

Definition at line 356 of file vgl_rtree.h.

Member Function Documentation

◆ add()

template<class V , class B , class C >

void vgl_rtree< V, B, C >::add ( V const & v )

inline

add an element to the rtree.

Definition at line 266 of file vgl_rtree.h.

◆ begin() [1/2]

template<class V , class B , class C >

iterator vgl_rtree< V, B, C >::begin ( )

inline

Definition at line 259 of file vgl_rtree.h.

◆ begin() [2/2]

template<class V , class B , class C >

const_iterator vgl_rtree< V, B, C >::begin ( ) const

inline

Definition at line 260 of file vgl_rtree.h.

◆ contains()

template<class V , class B , class C >

bool vgl_rtree< V, B, C >::contains ( V const & v ) const

inline

return true iff the rtree contains an element equal to v.

Definition at line 291 of file vgl_rtree.h.

◆ empty()

template<class V , class B , class C >

bool vgl_rtree< V, B, C >::empty ( ) const

inline

return true iff the tree has no elements.

Definition at line 330 of file vgl_rtree.h.

◆ end() [1/2]

template<class V , class B , class C >

iterator vgl_rtree< V, B, C >::end ( )

inline

Definition at line 262 of file vgl_rtree.h.

◆ end() [2/2]

template<class V , class B , class C >

const_iterator vgl_rtree< V, B, C >::end ( ) const

inline

Definition at line 263 of file vgl_rtree.h.

◆ erase()

template<class V , class B , class C >

void vgl_rtree< V, B, C >::erase ( iterator i )

inline

erase the element pointed to by the iterator.

may invalidate all iterators into the rtree.

Definition at line 303 of file vgl_rtree.h.

◆ get() [1/2]

template<class V , class B , class C >

void vgl_rtree< V, B, C >::get	(	B const &	region,
		std::vector< V > &	vs
	)		const

inline

get elements in the given region.

Definition at line 312 of file vgl_rtree.h.

◆ get() [2/2]

template<class V , class B , class C >

void vgl_rtree< V, B, C >::get	(	vgl_rtree_probe< V, B, C > const &	region,
		std::vector< V > &	vs
	)		const

inline

get elements which meet the given probe.

Definition at line 318 of file vgl_rtree.h.

◆ get_all()

template<class V , class B , class C >

void vgl_rtree< V, B, C >::get_all ( std::vector< V > & vs ) const

inline

get all elements in the tree.

Definition at line 324 of file vgl_rtree.h.

◆ nodes()

template<class V , class B , class C >

unsigned vgl_rtree< V, B, C >::nodes ( ) const

inline

return number of nodes used by the tree.

Definition at line 340 of file vgl_rtree.h.

◆ operator=()

template<class V , class B , class C >

vgl_rtree<V, B, C>& vgl_rtree< V, B, C >::operator= ( vgl_rtree< V, B, C > const & )

inlineprivate

Definition at line 355 of file vgl_rtree.h.

◆ print()

template<class V , class B , class C >

void vgl_rtree< V, B, C >::print ( ) const

inline

Definition at line 348 of file vgl_rtree.h.

◆ remove()

template<class V , class B , class C >

void vgl_rtree< V, B, C >::remove ( V const & v )

inline

remove one element from the rtree.

Definition at line 274 of file vgl_rtree.h.

◆ secret_get_root()

template<class V , class B , class C >

node* vgl_rtree< V, B, C >::secret_get_root ( ) const

inline

Definition at line 346 of file vgl_rtree.h.

◆ size()

template<class V , class B , class C >

unsigned vgl_rtree< V, B, C >::size ( ) const

inline

return number of elements stored in the tree.

Definition at line 335 of file vgl_rtree.h.

Member Data Documentation

◆ root

template<class V , class B , class C >

node* vgl_rtree< V, B, C >::root

private

Definition at line 353 of file vgl_rtree.h.

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

core/vgl/algo/vgl_algo_fwd.h
core/vgl/algo/vgl_rtree.h

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<class V, class B, class C> class vgl_rtree< V, B, C >

Member Typedef Documentation

◆ const_iterator

◆ iterator

◆ node

◆ probe

Constructor & Destructor Documentation

◆ vgl_rtree() [1/2]

◆ ~vgl_rtree()

◆ vgl_rtree() [2/2]

Member Function Documentation

◆ add()

◆ begin() [1/2]

◆ begin() [2/2]

◆ contains()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ erase()

◆ get() [1/2]

◆ get() [2/2]

◆ get_all()

◆ nodes()

◆ operator=()

◆ print()

◆ remove()

◆ secret_get_root()

◆ size()

Member Data Documentation

◆ root

template<class V, class B, class C>
class vgl_rtree< V, B, C >