Implementation of an RTree with an R* index. More...

#include "RStarTree.h"

Classes
struct	QueryFunctor

struct	RemoveFunctor

struct	RemoveLeafFunctor

struct	VisitFunctor

Public Types
typedef RStarBoundedItem< dimensions >	BoundedItem

typedef BoundedItem::BoundingBox	BoundingBox

typedef RStarNode< BoundedItem >	Node

typedef RStarLeaf< BoundedItem, LeafType >	Leaf

typedef RStarAcceptOverlapping< Node, Leaf >	AcceptOverlapping

typedef RStarAcceptEnclosing< Node, Leaf >	AcceptEnclosing

typedef RStarAcceptAny< Node, Leaf >	AcceptAny

typedef RStarRemoveLeaf< Leaf >	RemoveLeaf

typedef RStarRemoveSpecificLeaf< Leaf >	RemoveSpecificLeaf

Public Member Functions
	RStarTree ()

	~RStarTree ()

void	Insert (LeafType leaf, const BoundingBox &bound)

template<typename Acceptor , typename Visitor >
Visitor	Query (const Acceptor &accept, Visitor visitor)
	Touches each node using the visitor pattern. More...

template<typename Acceptor , typename LeafRemover >
void	Remove (const Acceptor &accept, LeafRemover leafRemover)
	Removes item(s) from the tree. More...

void	RemoveBoundedArea (const BoundingBox &bound)

void	RemoveItem (const LeafType &item, bool removeDuplicates=true)

std::size_t	GetSize () const

std::size_t	GetDimensions () const

Protected Member Functions
Node *	ChooseSubtree (Node node, const BoundingBox bound)

Node *	InsertInternal (Leaf leaf, Node node, bool firstInsert=true)

Node *	OverflowTreatment (Node *level, bool firstInsert)

Node *	Split (Node *node)

void	Reinsert (Node *node)

Private Attributes
Node *	m_root

std::size_t	m_size

Detailed Description

template<typename LeafType, std::size_t dimensions, std::size_t min_child_items, std::size_t max_child_items>
class RStarTree< LeafType, dimensions, min_child_items, max_child_items >

Implementation of an RTree with an R* index.

Template Parameters

LeafType	type of leaves stored in the tree
dimensions	number of dimensions the bounding boxes are described in
min_child_items	m, in the range 2 <= m < M
max_child_items	M, in the range 2 <= m < M
RemoveLeaf	A functor used to remove leaves from the tree

Definition at line 87 of file RStarTree.h.

Member Typedef Documentation

template<typename LeafType, std::size_t dimensions, std::size_t min_child_items, std::size_t max_child_items>

typedef RStarAcceptAny<Node, Leaf> RStarTree< LeafType, dimensions, min_child_items, max_child_items >::AcceptAny

Definition at line 100 of file RStarTree.h.

template<typename LeafType, std::size_t dimensions, std::size_t min_child_items, std::size_t max_child_items>

typedef RStarAcceptEnclosing<Node, Leaf> RStarTree< LeafType, dimensions, min_child_items, max_child_items >::AcceptEnclosing

Definition at line 99 of file RStarTree.h.

template<typename LeafType, std::size_t dimensions, std::size_t min_child_items, std::size_t max_child_items>

typedef RStarAcceptOverlapping<Node, Leaf> RStarTree< LeafType, dimensions, min_child_items, max_child_items >::AcceptOverlapping

Definition at line 98 of file RStarTree.h.

template<typename LeafType, std::size_t dimensions, std::size_t min_child_items, std::size_t max_child_items>

typedef RStarBoundedItem<dimensions> RStarTree< LeafType, dimensions, min_child_items, max_child_items >::BoundedItem

Definition at line 91 of file RStarTree.h.

template<typename LeafType, std::size_t dimensions, std::size_t min_child_items, std::size_t max_child_items>

typedef BoundedItem::BoundingBox RStarTree< LeafType, dimensions, min_child_items, max_child_items >::BoundingBox

Definition at line 92 of file RStarTree.h.

template<typename LeafType, std::size_t dimensions, std::size_t min_child_items, std::size_t max_child_items>

typedef RStarLeaf<BoundedItem, LeafType> RStarTree< LeafType, dimensions, min_child_items, max_child_items >::Leaf

Definition at line 95 of file RStarTree.h.

template<typename LeafType, std::size_t dimensions, std::size_t min_child_items, std::size_t max_child_items>

typedef RStarNode<BoundedItem> RStarTree< LeafType, dimensions, min_child_items, max_child_items >::Node

Definition at line 94 of file RStarTree.h.

template<typename LeafType, std::size_t dimensions, std::size_t min_child_items, std::size_t max_child_items>

typedef RStarRemoveLeaf<Leaf> RStarTree< LeafType, dimensions, min_child_items, max_child_items >::RemoveLeaf

Definition at line 103 of file RStarTree.h.

template<typename LeafType, std::size_t dimensions, std::size_t min_child_items, std::size_t max_child_items>

typedef RStarRemoveSpecificLeaf<Leaf> RStarTree< LeafType, dimensions, min_child_items, max_child_items >::RemoveSpecificLeaf

Definition at line 104 of file RStarTree.h.

Constructor & Destructor Documentation

template<typename LeafType, std::size_t dimensions, std::size_t min_child_items, std::size_t max_child_items>

RStarTree< LeafType, dimensions, min_child_items, max_child_items >::RStarTree ( )

inline

Definition at line 110 of file RStarTree.h.

                     : m_root(NULL), m_size(0) 
         {
         }

template<typename LeafType, std::size_t dimensions, std::size_t min_child_items, std::size_t max_child_items>

RStarTree< LeafType, dimensions, min_child_items, max_child_items >::~RStarTree ( )

inline

Definition at line 115 of file RStarTree.h.

                      { 
                 Remove(
                         AcceptAny(), 
                         RemoveLeaf()
                 );
         }

Member Function Documentation

template<typename LeafType, std::size_t dimensions, std::size_t min_child_items, std::size_t max_child_items>

Node* RStarTree< LeafType, dimensions, min_child_items, max_child_items >::ChooseSubtree	(	Node *	node,
		const BoundingBox *	bound
	)

inlineprotected

Definition at line 292 of file RStarTree.h.

         {
                 // If the child pointers in N point to leaves 
                 if (static_cast<Node*>(node->items[0])->hasLeaves)
                 {
                         // determine the minimum overlap cost
                         if (max_child_items > (RTREE_CHOOSE_SUBTREE_P*2)/3  && node->items.size() > RTREE_CHOOSE_SUBTREE_P)
                         {
                                 // ** alternative algorithm:
                                 // Sort the rectangles in N in increasing order of
                                 // then area enlargement needed to include the new
                                 // data rectangle
                                 
                                 // Let A be the group of the first p entrles
                                 std::partial_sort( node->items.begin(), node->items.begin() + RTREE_CHOOSE_SUBTREE_P, node->items.end(), 
                                         SortBoundedItemsByAreaEnlargement<BoundedItem>(bound));
                                 
                                 // From the items in A, considering all items in
                                 // N, choose the leaf whose rectangle needs least
                                 // overlap enlargement
                                 
                                 return static_cast<Node*>(* std::min_element(node->items.begin(), node->items.begin() + RTREE_CHOOSE_SUBTREE_P,
                                         SortBoundedItemsByOverlapEnlargement<BoundedItem>(bound)));
                         }
 
                         // choose the leaf in N whose rectangle needs least
                         // overlap enlargement to include the new data
                         // rectangle Resolve ties by choosmg the leaf
                         // whose rectangle needs least area enlargement, then
                         // the leaf with the rectangle of smallest area
                         
                         return static_cast<Node*>(* std::min_element(node->items.begin(), node->items.end(),
                                 SortBoundedItemsByOverlapEnlargement<BoundedItem>(bound)));     
                 }
                 
                 // if the chlld pointers in N do not point to leaves
 
                 // [determine the minimum area cost],
                 // choose the leaf in N whose rectangle needs least
                 // area enlargement to include the new data
                 // rectangle. Resolve ties by choosing the leaf
                 // with the rectangle of smallest area
                         
                 return static_cast<Node*>(*     std::min_element( node->items.begin(), node->items.end(),
                                 SortBoundedItemsByAreaEnlargement<BoundedItem>(bound)));
         }

template<typename LeafType, std::size_t dimensions, std::size_t min_child_items, std::size_t max_child_items>

std::size_t RStarTree< LeafType, dimensions, min_child_items, max_child_items >::GetDimensions ( ) const

inline

Definition at line 284 of file RStarTree.h.

284 { return dimensions; }

template<typename LeafType, std::size_t dimensions, std::size_t min_child_items, std::size_t max_child_items>

std::size_t RStarTree< LeafType, dimensions, min_child_items, max_child_items >::GetSize ( ) const

inline

Definition at line 283 of file RStarTree.h.

Referenced by main().

283 { return m_size; }

RStarTree::m_size

std::size_t m_size

Definition: RStarTree.h:761

template<typename LeafType, std::size_t dimensions, std::size_t min_child_items, std::size_t max_child_items>

void RStarTree< LeafType, dimensions, min_child_items, max_child_items >::Insert	(	LeafType	leaf,
		const BoundingBox &	bound
	)

inline

Definition at line 123 of file RStarTree.h.

Referenced by main().

         {
                 // ID1: Invoke Insert starting with the leaf level as a
                 // parameter, to Insert a new data rectangle
                 Leaf * newLeaf = new Leaf();
                 newLeaf->bound = bound;
                 newLeaf->leaf  = leaf;
 
                 // create a new root node if necessary
                 if (!m_root)
                 {
                         m_root = new Node();
                         m_root->hasLeaves = true;
                         
                         // reserve memory
                         m_root->items.reserve(min_child_items);
                         m_root->items.push_back(newLeaf);
                         m_root->bound = bound;
                 }
                 else
                         // start the insertion process
                         InsertInternal(newLeaf, m_root);
                         
                 m_size += 1;
         }

template<typename LeafType, std::size_t dimensions, std::size_t min_child_items, std::size_t max_child_items>

Node* RStarTree< LeafType, dimensions, min_child_items, max_child_items >::InsertInternal	(	Leaf *	leaf,
		Node *	node,
		bool	firstInsert = `true`
	)

inlineprotected

Definition at line 343 of file RStarTree.h.

         {
                 // I4: Adjust all covering rectangles in the insertion path
                 // such that they are minimum bounding boxes
                 // enclosing the children rectangles
                 node->bound.stretch(leaf->bound);
         
         
                 // CS2: If we're at a leaf, then use that level
                 if (node->hasLeaves)
                 {
                         // I2: If N has less than M items, accommodate E in N
                         node->items.push_back(leaf);
                 }
                 else
                 {
                         // I1: Invoke ChooseSubtree. with the level as a parameter,
                         // to find an appropriate node N, m which to place the
                         // new leaf E
                 
                         // of course, this already does all of that recursively. we just need to
                         // determine whether we need to split the overflow or not
                         Node * tmp_node = InsertInternal( leaf, ChooseSubtree(node, &leaf->bound), firstInsert );
                         
                         if (!tmp_node)
                                 return NULL;
                                 
                         // this gets joined to the list of items at this level
                         node->items.push_back(tmp_node);
                 }
                 
                 
                 // If N has M+1 items. invoke OverflowTreatment with the
                 // level of N as a parameter [for reinsertion or split]
                 if (node->items.size() > max_child_items )
                 {
                         
                         // I3: If OverflowTreatment was called and a split was
                         // performed, propagate OverflowTreatment upwards
                         // if necessary
                         
                         // This is implicit, the rest of the algorithm takes place in there
                         return OverflowTreatment(node, firstInsert);
                 }
                         
                 return NULL;
         }

template<typename LeafType, std::size_t dimensions, std::size_t min_child_items, std::size_t max_child_items>

Node* RStarTree< LeafType, dimensions, min_child_items, max_child_items >::OverflowTreatment	(	Node *	level,
		bool	firstInsert
	)

inlineprotected

Definition at line 393 of file RStarTree.h.

         {
                 // OT1: If the level is not the root level AND this is the first
                 // call of OverflowTreatment in the given level during the 
                 // insertion of one data rectangle, then invoke Reinsert
                 if (level != m_root && firstInsert)
                 {
                         Reinsert(level);
                         return NULL;
                 }
                 
                 Node * splitItem = Split(level);
                 
                 // If OverflowTreatment caused a split of the root, create a new root
                 if (level == m_root)
                 {
                         Node * newRoot = new Node();
                         newRoot->hasLeaves = false;
                         
                         // reserve memory
                         newRoot->items.reserve(min_child_items);
                         newRoot->items.push_back(m_root);
                         newRoot->items.push_back(splitItem);
                         
                         // Do I4 here for the new root item
                         newRoot->bound.reset();
                         for_each(newRoot->items.begin(), newRoot->items.end(), StretchBoundingBox<BoundedItem>(&newRoot->bound));
                         
                         // and we're done
                         m_root = newRoot;
                         return NULL;
                 }
 
                 // propagate it upwards
                 return splitItem;
         }

template<typename LeafType, std::size_t dimensions, std::size_t min_child_items, std::size_t max_child_items>

template<typename Acceptor , typename Visitor >

Visitor RStarTree< LeafType, dimensions, min_child_items, max_child_items >::Query	(	const Acceptor &	accept,
		Visitor	visitor
	)

inline

Touches each node using the visitor pattern.

You must specify an acceptor functor that takes a BoundingBox and a visitor that takes a BoundingBox and a const LeafType&.

See RStarVisitor.h for more information about the various visitor types available.

Parameters

acceptor	An acceptor functor that returns true if this branch or leaf of the tree should be considered for visitation.
visitor	A visitor functor that does the visiting

Returns: This will return the Visitor object, so you can retrieve whatever data it has in it if needed (for example, to get the count of items visited). It returns by value, so ensure that the copy is cheap for decent performance.

Definition at line 215 of file RStarTree.h.

Referenced by main().

         {
                 if (m_root)
                 {       
                         QueryFunctor<Acceptor, Visitor> query(accept, visitor);
                         query(m_root);
                 }
                 
                 return visitor;
         }

template<typename LeafType, std::size_t dimensions, std::size_t min_child_items, std::size_t max_child_items>

void RStarTree< LeafType, dimensions, min_child_items, max_child_items >::Reinsert ( Node * node )

inlineprotected

Definition at line 563 of file RStarTree.h.

         {
                 std::vector< BoundedItem* > removed_items;
 
                 const std::size_t n_items = node->items.size();
                 const std::size_t p = (std::size_t)((double)n_items * RTREE_REINSERT_P) > 0 ? (std::size_t)((double)n_items * RTREE_REINSERT_P) : 1;
                 
                 // RI1 For all M+l items of a node N, compute the distance
                 // between the centers of their rectangles and the center
                 // of the bounding rectangle of N
                 assert(n_items == max_child_items + 1);
                 
                 // RI2: Sort the items in increasing order of their distances
                 // computed in RI1
                 std::partial_sort(node->items.begin(), node->items.end() - p, node->items.end(), 
                         SortBoundedItemsByDistanceFromCenter<BoundedItem>(&node->bound));
                         
                 // RI3.A: Remove the last p items from N
                 removed_items.assign(node->items.end() - p, node->items.end());
                 node->items.erase(node->items.end() - p, node->items.end());
                 
                 // RI3.B: adjust the bounding rectangle of N
                 node->bound.reset();
                 for_each(node->items.begin(), node->items.end(), StretchBoundingBox<BoundedItem>(&node->bound));
                 
                 // RI4: In the sort, defined in RI2, starting with the 
                 // minimum distance (= close reinsert), invoke Insert 
                 // to reinsert the items
                 for (typename std::vector< BoundedItem* >::iterator it = removed_items.begin(); it != removed_items.end(); it++)
                         InsertInternal( static_cast<Leaf*>(*it), m_root, false);
         }

template<typename LeafType, std::size_t dimensions, std::size_t min_child_items, std::size_t max_child_items>

template<typename Acceptor , typename LeafRemover >

void RStarTree< LeafType, dimensions, min_child_items, max_child_items >::Remove	(	const Acceptor &	accept,
		LeafRemover	leafRemover
	)

inline

Removes item(s) from the tree.

See RStarVisitor.h for more information about the various visitor types available.

Parameters

acceptor	A node acceptor functor that returns true if this branch or leaf of the tree should be considered for deletion (it does not delete it, however. That is what the LeafRemover does).
leafRemover	A visitor functor that decides whether that individual item should be removed from the tree. If it returns true, then the node holding that item will be deleted.

See also RemoveBoundedArea, RemoveItem for examples of how this function can be called.

Definition at line 245 of file RStarTree.h.

         {
                 std::list<Leaf*> itemsToReinsert;
 
                 if (!m_root)
                         return;
                 
                 RemoveFunctor<Acceptor, LeafRemover> remove(accept, leafRemover, &itemsToReinsert, &m_size);
                 remove(m_root, true);
                 
                 if (!itemsToReinsert.empty())
                 {
                         // reinsert anything that needs to be reinserted
                         typename std::list< Leaf* >::iterator it = itemsToReinsert.begin();
                         typename std::list< Leaf* >::iterator end = itemsToReinsert.end();
                 
                         // TODO: do this whenever that actually works.. 
                         // BulkInsert(itemsToReinsert, m_root);
                         
                         for(;it != end; it++)
                                 InsertInternal(*it, m_root);
                 }
         }

template<typename LeafType, std::size_t dimensions, std::size_t min_child_items, std::size_t max_child_items>

void RStarTree< LeafType, dimensions, min_child_items, max_child_items >::RemoveBoundedArea ( const BoundingBox & bound )

inline

Definition at line 270 of file RStarTree.h.

Referenced by main().

         {
                 Remove(AcceptEnclosing(bound), RemoveLeaf());
         }

template<typename LeafType, std::size_t dimensions, std::size_t min_child_items, std::size_t max_child_items>

void RStarTree< LeafType, dimensions, min_child_items, max_child_items >::RemoveItem	(	const LeafType &	item,
		bool	removeDuplicates = `true`
	)

inline

Definition at line 277 of file RStarTree.h.

         {
                 Remove( AcceptAny(), RemoveSpecificLeaf(item, removeDuplicates));
         }

template<typename LeafType, std::size_t dimensions, std::size_t min_child_items, std::size_t max_child_items>

Node* RStarTree< LeafType, dimensions, min_child_items, max_child_items >::Split ( Node * node )

inlineprotected

Definition at line 436 of file RStarTree.h.

         {
                 Node * newNode = new Node();
                 newNode->hasLeaves = node->hasLeaves;
 
                 const std::size_t n_items = node->items.size();
                 const std::size_t distribution_count = n_items - 2*min_child_items + 1;
                 
                 std::size_t split_axis = dimensions+1, split_edge = 0, split_index = 0;
                 int split_margin = 0;
                 
                 BoundingBox R1, R2;
 
                 // these should always hold true
                 assert(n_items == max_child_items + 1);
                 assert(distribution_count > 0);
                 assert(min_child_items + distribution_count-1 <= n_items);
                 
                 // S1: Invoke ChooseSplitAxis to determine the axis,
                 // perpendicular to which the split 1s performed
                 // S2: Invoke ChooseSplitIndex to determine the best
                 // distribution into two groups along that axis
                 
                 // NOTE: We don't compare against node->bound, so it gets overwritten
                 // at the end of the loop
                 
                 // CSA1: For each axis
                 for (std::size_t axis = 0; axis < dimensions; axis++)
                 {
                         // initialize per-loop items
                         int margin = 0;
                         double overlap = 0, dist_area, dist_overlap;
                         std::size_t dist_edge = 0, dist_index = 0;
                 
                         dist_area = dist_overlap = std::numeric_limits<double>::max();
                         
                         
                         // Sort the items by the lower then by the upper
                         // edge of their bounding box on this particular axis and 
                         // determine all distributions as described . Compute S. the
                         // sum of all margin-values of the different
                         // distributions
                 
                         // lower edge == 0, upper edge = 1
                         for (std::size_t edge = 0; edge < 2; edge++)
                         {
                                 // sort the items by the correct key (upper edge, lower edge)
                                 if (edge == 0)
                                         std::sort(node->items.begin(), node->items.end(), SortBoundedItemsByFirstEdge<BoundedItem>(axis));
                                 else
                                         std::sort(node->items.begin(), node->items.end(), SortBoundedItemsBySecondEdge<BoundedItem>(axis));
                 
                                 // Distributions: pick a point m in the middle of the thing, call the left
                                 // R1 and the right R2. Calculate the bounding box of R1 and R2, then 
                                 // calculate the margins. Then do it again for some more points 
                                 for (std::size_t k = 0; k < distribution_count; k++)
                         {
                                         double area = 0;
                                 
                                         // calculate bounding box of R1
                                         R1.reset();
                                         for_each(node->items.begin(), node->items.begin()+(min_child_items+k), StretchBoundingBox<BoundedItem>(&R1));
                                                         
                                         // then do the same for R2
                                         R2.reset();
                                         for_each(node->items.begin()+(min_child_items+k+1), node->items.end(), StretchBoundingBox<BoundedItem>(&R2));
                                         
                                         
                                         // calculate the three values
                                         margin  += R1.edgeDeltas() + R2.edgeDeltas();
                                         area    += R1.area() + R2.area();               // TODO: need to subtract.. overlap?
                                         overlap =  R1.overlap(R2);
                                         
                                         
                                         // CSI1: Along the split axis, choose the distribution with the 
                                         // minimum overlap-value. Resolve ties by choosing the distribution
                                         // with minimum area-value. 
                                         if (overlap < dist_overlap || (overlap == dist_overlap && area < dist_area))
                                         {
                                                 // if so, store the parameters that allow us to recreate it at the end
                                                 dist_edge =     edge;
                                                 dist_index =    min_child_items+k;
                                                 dist_overlap =  overlap;
                                                 dist_area =     area;
                                         }               
                                 }
                         }
                         
                         // CSA2: Choose the axis with the minimum S as split axis
                         if (split_axis == dimensions+1 || split_margin > margin )
                         {
                                 split_axis              = axis;
                                 split_margin    = margin;
                                 split_edge              = dist_edge;
                                 split_index     = dist_index;
                         }
                 }
         
                 // S3: Distribute the items into two groups
         
                 // ok, we're done, and the best distribution on the selected split
                 // axis has been recorded, so we just have to recreate it and
                 // return the correct index
                 
                 if (split_edge == 0)
                         std::sort(node->items.begin(), node->items.end(), SortBoundedItemsByFirstEdge<BoundedItem>(split_axis));
 
                 // only reinsert the sort key if we have to
                 else if (split_axis != dimensions-1)
                         std::sort(node->items.begin(), node->items.end(), SortBoundedItemsBySecondEdge<BoundedItem>(split_axis));       
                 
                 // distribute the end of the array to the new node, then erase them from the original node
                 newNode->items.assign(node->items.begin() + split_index, node->items.end());
                 node->items.erase(node->items.begin() + split_index, node->items.end());
                 
                 // adjust the bounding box for each 'new' node
                 node->bound.reset();
                 std::for_each(node->items.begin(), node->items.end(), StretchBoundingBox<BoundedItem>(&node->bound));
                 
                 newNode->bound.reset();
                 std::for_each(newNode->items.begin(), newNode->items.end(), StretchBoundingBox<BoundedItem>(&newNode->bound));
                 
                 return newNode;
         }

Member Data Documentation

template<typename LeafType, std::size_t dimensions, std::size_t min_child_items, std::size_t max_child_items>

Node* RStarTree< LeafType, dimensions, min_child_items, max_child_items >::m_root

private

Definition at line 759 of file RStarTree.h.

template<typename LeafType, std::size_t dimensions, std::size_t min_child_items, std::size_t max_child_items>

std::size_t RStarTree< LeafType, dimensions, min_child_items, max_child_items >::m_size

private

Definition at line 761 of file RStarTree.h.

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

larreco/v06_64_02/source/larreco/ClusterFinder/RStarTree/RStarTree.h

Classes

Public Types

Public Member Functions

Protected Member Functions

Private Attributes

Detailed Description

template<typename LeafType, std::size_t dimensions, std::size_t min_child_items, std::size_t max_child_items> class RStarTree< LeafType, dimensions, min_child_items, max_child_items >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename LeafType, std::size_t dimensions, std::size_t min_child_items, std::size_t max_child_items>
class RStarTree< LeafType, dimensions, min_child_items, max_child_items >