Templated rtree class. More...

#include <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) const
	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
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 242 of file vgl_rtree.h.