RStarTree< LeafType, dimensions, min_child_items, max_child_items > Class Template Reference

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.

{ 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.

{ return m_size; }

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.

        {
                // 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.

        {
                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.

        {
                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/larreco/ClusterFinder/RStarTree/RStarTree.h