vgl_rtree< V, B, C > Class Template Reference

#include <vgl_rtree.h>

List of all members.

---

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 &) const;
   bool  C::meet  (B const &, B const &) const;
   float C::volume(B const &) const;

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

Definition at line 240 of file vgl_rtree.h.

Public Types
typedef vgl_rtree_probe< V, B, C >	probe
typedef vgl_rtree_iterator< V, B, C >	iterator
	iterators.
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.
void	remove (V const &v)
	remove one element from the rtree.
bool	contains (V const &v)
	return true iff the rtree contains an element equal to v.
void	erase (iterator i)
	erase the element pointed to by the iterator.
void	get (B const &region, vcl_vector< V > &vs) const
	get elements in the given region.
void	get (vgl_rtree_probe< V, B, C > const &region, vcl_vector< V > &vs) const
	get elements which meet the given probe.
void	get_all (vcl_vector< V > &vs) const
	get all elements in the tree.
bool	empty () const
	return true iff the tree has no elements.
unsigned	size () const
	return number of elements stored in the tree.
unsigned	nodes () const
	return number of nodes used by the tree.
node *	secret_get_root () const
Private Member Functions
void	operator= (vgl_rtree< V, B, C > const &)
	vgl_rtree (vgl_rtree< V, B, C > const &)
Private Attributes
node *	root

---

Member Typedef Documentation

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 255 of file vgl_rtree.h.

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

iterators. Definition at line 254 of file vgl_rtree.h.

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

Definition at line 343 of file vgl_rtree.h.

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

Definition at line 251 of file vgl_rtree.h.

---

Constructor & Destructor Documentation

template<class V, class B, class C> vgl_rtree< V, B, C >::vgl_rtree (   )  [inline]

Definition at line 243 of file vgl_rtree.h.

template<class V, class B, class C> vgl_rtree< V, B, C >::~vgl_rtree (   )  [inline]

Definition at line 244 of file vgl_rtree.h.

template<class V, class B, class C> vgl_rtree< V, B, C >::vgl_rtree (  vgl_rtree< V, B, C > const &   )  [inline, private]

Definition at line 350 of file vgl_rtree.h.

---

Member Function Documentation

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 264 of file vgl_rtree.h.

template<class V, class B, class C> const_iterator vgl_rtree< V, B, C >::begin (   )  const [inline]

Definition at line 258 of file vgl_rtree.h.

template<class V, class B, class C> iterator vgl_rtree< V, B, C >::begin (   )  [inline]

Definition at line 257 of file vgl_rtree.h.

template<class V, class B, class C> bool vgl_rtree< V, B, C >::contains (  V const &  v  )  [inline]

return true iff the rtree contains an element equal to v. Definition at line 289 of file vgl_rtree.h.

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 328 of file vgl_rtree.h.

template<class V, class B, class C> const_iterator vgl_rtree< V, B, C >::end (   )  const [inline]

Definition at line 261 of file vgl_rtree.h.

template<class V, class B, class C> iterator vgl_rtree< V, B, C >::end (   )  [inline]

Definition at line 260 of file vgl_rtree.h.

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 301 of file vgl_rtree.h.

template<class V, class B, class C> void vgl_rtree< V, B, C >::get (  vgl_rtree_probe< V, B, C > const &  region, vcl_vector< V > &  vs )  const [inline]

get elements which meet the given probe. Definition at line 316 of file vgl_rtree.h.

template<class V, class B, class C> void vgl_rtree< V, B, C >::get (  B const &  region, vcl_vector< V > &  vs )  const [inline]

get elements in the given region. Definition at line 310 of file vgl_rtree.h.

template<class V, class B, class C> void vgl_rtree< V, B, C >::get_all (  vcl_vector< V > &  vs  )  const [inline]

get all elements in the tree. Definition at line 322 of file vgl_rtree.h.

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 338 of file vgl_rtree.h.

template<class V, class B, class C> void vgl_rtree< V, B, C >::operator= (  vgl_rtree< V, B, C > const &   )  [inline, private]

Definition at line 349 of file vgl_rtree.h.

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 272 of file vgl_rtree.h.

template<class V, class B, class C> node* vgl_rtree< V, B, C >::secret_get_root (   )  const [inline]

Definition at line 344 of file vgl_rtree.h.

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 333 of file vgl_rtree.h.

---

Member Data Documentation

template<class V, class B, class C> node* vgl_rtree< V, B, C >::root [private]

Definition at line 347 of file vgl_rtree.h.

---

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

• core/vgl/algo/vgl_rtree.h

---