te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES > Class Template Reference

A class that represents an R-tree. More...

#include <Index.h>

Public Types

typedef NodeType::BranchType BranchType
 
typedef Node< DATATYPE, MAXNODES, MINNODES > NodeType
 
typedef te::sam::rtree::PartitionVars< BranchType, MAXNODES > PartitionVarsType
 

Public Member Functions

void clear (void)
 
const te::gm::EnvelopegetMBR (void) const
 It returns the bounding box of all elements in the tree. More...
 
 Index ()
 Constructor. More...
 
 Index (const te::gm::Envelope &mbr)
 Constructor. More...
 
void insert (const te::gm::Envelope &mbr, const DATATYPE &data)
 It inserts an item into the tree. More...
 
bool isEmpty (void) const
 It returns true if the tree is empty. More...
 
bool remove (const te::gm::Envelope &mbr, const DATATYPE &data)
 It removes an item from the tree. More...
 
int search (const te::gm::Envelope &mbr, std::vector< DATATYPE > &report) const
 Range search query. More...
 
void setMBR (const te::gm::Envelope &mbr)
 It sets the bounding box of all elements in the tree. More...
 
std::size_t size (void) const
 It returns the number of elements in the tree. More...
 
 ~Index ()
 Destructor. More...
 

Protected Member Functions

bool addBranch (BranchType *branch, NodeType *node, NodeType **newNode) const
 Add a branch to a node. More...
 
bool chooseLeaf (const te::gm::Envelope &mbr, const DATATYPE &data, NodeType *node, NodeType **newNode, int level)
 It inserts a new data rectangle into the index structure. More...
 
void classify (int i, int group, PartitionVarsType &p) const
 
te::gm::Envelope combineRect (const te::gm::Envelope &mbrA, const te::gm::Envelope &mbrB) const
 Combine two rectangles into larger one containing both. More...
 
void disconBranch (NodeType *n, int i)
 It disconnects a dependent node. More...
 
void erase (NodeType *node)
 Erases a node from the tree and all nodes below it. More...
 
void getBranches (NodeType *n, BranchType *b, PartitionVarsType &p) const
 
bool insert (const te::gm::Envelope &mbr, const DATATYPE &data, NodeType **root, int level)
 It inserts a data rectangle into an index structure. More...
 
void loadNodes (NodeType *n, NodeType *q, PartitionVarsType &p) const
 
void methodZero (PartitionVarsType &p) const
 
te::gm::Envelope nodeCover (NodeType *n) const
 Find the smallest rectangle that includes all rectangles in branches of a node. More...
 
int pickBranch (const te::gm::Envelope &mbr, NodeType *node) const
 Pick a branch. More...
 
void pickSeeds (PartitionVarsType &p) const
 
void pigeonhole (PartitionVarsType &p) const
 
bool remove (const te::gm::Envelope &mbr, const DATATYPE &data, NodeType **root)
 It deletes a data rectangle from an index structure. More...
 
bool remove2 (const te::gm::Envelope &mbr, const DATATYPE &data, NodeType *n, std::vector< NodeType * > &ee)
 It deletes a rectangle from non-root part of an index structure. More...
 
void search (const te::gm::Envelope &mbr, NodeType *node, std::vector< DATATYPE > &report, int &foundObjs) const
 Recursive range query. More...
 
void splitNode (NodeType *node, BranchType *branch, NodeType **newNode) const
 Split a node. More...
 

Private Member Functions

 Index (const Index &rhs)
 No copy constructor allowed. More...
 
Indexoperator= (const Index &rhs)
 No assignment operator allowed. More...
 

Private Attributes

te::gm::Envelope m_mbr
 Bounding box of the tree. More...
 
NodeTypem_root
 Pointer to the root node. More...
 
std::size_t m_size
 The size of R-Tree (number of nodes). More...
 

Detailed Description

template<class DATATYPE, int MAXNODES = 8, int MINNODES = MAXNODES / 2>
class te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >

A class that represents an R-tree.

This implementation is based on:

Antonin Guttman. R-Trees: A Dynamic Index Structure for Spatial Searching. ACM SIGMOD: International Conference on Management of Data, 1984, pp. 47-57.

and in his original source code.

Definition at line 56 of file Index.h.

Member Typedef Documentation

template<class DATATYPE, int MAXNODES = 8, int MINNODES = MAXNODES / 2>
typedef NodeType::BranchType te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::BranchType

Definition at line 61 of file Index.h.

template<class DATATYPE, int MAXNODES = 8, int MINNODES = MAXNODES / 2>
typedef Node<DATATYPE, MAXNODES, MINNODES> te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::NodeType

Definition at line 60 of file Index.h.

template<class DATATYPE, int MAXNODES = 8, int MINNODES = MAXNODES / 2>
typedef te::sam::rtree::PartitionVars<BranchType, MAXNODES> te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::PartitionVarsType

Definition at line 62 of file Index.h.

Constructor & Destructor Documentation

template<class DATATYPE , int MAXNODES, int MINNODES>
te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::Index ( )
inline
template<class DATATYPE , int MAXNODES, int MINNODES>
te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::Index ( const te::gm::Envelope mbr)
inline
template<class DATATYPE , int MAXNODES, int MINNODES>
te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::~Index ( )
inline

Destructor.

Definition at line 280 of file Index.h.

template<class DATATYPE, int MAXNODES = 8, int MINNODES = MAXNODES / 2>
te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::Index ( const Index< DATATYPE, MAXNODES, MINNODES > &  rhs)
private

No copy constructor allowed.

Parameters
rhsThe other rtree.

Member Function Documentation

template<class DATATYPE , int MAXNODES, int MINNODES>
bool te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::addBranch ( BranchType branch,
NodeType node,
NodeType **  newNode 
) const
inlineprotected
template<class DATATYPE, int MAXNODES, int MINNODES>
bool te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::chooseLeaf ( const te::gm::Envelope mbr,
const DATATYPE &  data,
NodeType node,
NodeType **  newNode,
int  level 
)
protected
template<class DATATYPE , int MAXNODES, int MINNODES>
void te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::clear ( void  )
inline

It clears all tree nodes and make it ready for new insertions.

Definition at line 299 of file Index.h.

template<class DATATYPE , int MAXNODES, int MINNODES>
te::gm::Envelope te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::combineRect ( const te::gm::Envelope mbrA,
const te::gm::Envelope mbrB 
) const
inlineprotected

Combine two rectangles into larger one containing both.

Definition at line 583 of file Index.h.

References te::gm::Envelope::Union().

template<class DATATYPE , int MAXNODES, int MINNODES>
void te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::disconBranch ( NodeType n,
int  i 
)
protected
template<class DATATYPE , int MAXNODES, int MINNODES>
void te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::erase ( NodeType node)
inlineprotected

Erases a node from the tree and all nodes below it.

Parameters
nodeThe node to be removed.

The node pointer will be invalidated.

Definition at line 879 of file Index.h.

References te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::isLeaf(), te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_branch, te::sam::rtree::Branch< NODE, DATATYPE >::m_child, and te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_count.

template<class DATATYPE , int MAXNODES, int MINNODES>
void te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::getBranches ( NodeType n,
BranchType b,
PartitionVarsType p 
) const
inlineprotected
template<class DATATYPE , int MAXNODES, int MINNODES>
const te::gm::Envelope & te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::getMBR ( void  ) const
inline

It returns the bounding box of all elements in the tree.

Returns
The bounding box of all elements in the tree.

Definition at line 343 of file Index.h.

template<class DATATYPE, int MAXNODES, int MINNODES>
void te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::insert ( const te::gm::Envelope mbr,
const DATATYPE &  data 
)
inline

It inserts an item into the tree.

Parameters
mbrThe object MBR.
dataThe object to be indexed.

Definition at line 313 of file Index.h.

References insert().

template<class DATATYPE, int MAXNODES, int MINNODES>
bool te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::insert ( const te::gm::Envelope mbr,
const DATATYPE &  data,
NodeType **  root,
int  level 
)
inlineprotected

It inserts a data rectangle into an index structure.

Returns
It returns true if root was split, false if it was not.

Definition at line 349 of file Index.h.

References te::sam::rtree::Branch< NODE, DATATYPE >::m_child, te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_level, and te::sam::rtree::Branch< NODE, DATATYPE >::m_mbr.

template<class DATATYPE , int MAXNODES, int MINNODES>
bool te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::isEmpty ( void  ) const
inline

It returns true if the tree is empty.

Returns
True if the tree is empty.

Definition at line 293 of file Index.h.

template<class DATATYPE , int MAXNODES, int MINNODES>
void te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::loadNodes ( NodeType n,
NodeType q,
PartitionVarsType p 
) const
inlineprotected
template<class DATATYPE , int MAXNODES, int MINNODES>
void te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::methodZero ( PartitionVarsType p) const
inlineprotected
template<class DATATYPE , int MAXNODES, int MINNODES>
te::gm::Envelope te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::nodeCover ( NodeType n) const
protected

Find the smallest rectangle that includes all rectangles in branches of a node.

Definition at line 562 of file Index.h.

References te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_branch, te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_count, and te::sam::rtree::Branch< NODE, DATATYPE >::m_mbr.

template<class DATATYPE, int MAXNODES = 8, int MINNODES = MAXNODES / 2>
Index& te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::operator= ( const Index< DATATYPE, MAXNODES, MINNODES > &  rhs)
private

No assignment operator allowed.

Parameters
rhsThe other rtree.
Returns
A reference for this instance.
template<class DATATYPE , int MAXNODES, int MINNODES>
int te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::pickBranch ( const te::gm::Envelope mbr,
NodeType node 
) const
inlineprotected
template<class DATATYPE , int MAXNODES, int MINNODES>
void te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::pickSeeds ( PartitionVarsType p) const
inlineprotected
template<class DATATYPE, int MAXNODES, int MINNODES>
bool te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::remove ( const te::gm::Envelope mbr,
const DATATYPE &  data 
)
inline

It removes an item from the tree.

Parameters
mbrThe object MBR.
dataThe object to be removed from the tree.
Returns
True if the object is found and removed, false otherwise.

Definition at line 320 of file Index.h.

template<class DATATYPE, int MAXNODES, int MINNODES>
bool te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::remove ( const te::gm::Envelope mbr,
const DATATYPE &  data,
NodeType **  root 
)
inlineprotected
template<class DATATYPE, int MAXNODES, int MINNODES>
bool te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::remove2 ( const te::gm::Envelope mbr,
const DATATYPE &  data,
NodeType n,
std::vector< NodeType * > &  ee 
)
inlineprotected
template<class DATATYPE, int MAXNODES, int MINNODES>
int te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::search ( const te::gm::Envelope mbr,
std::vector< DATATYPE > &  report 
) const
inline

Range search query.

Parameters
mbrThe search rectangle.
reportA vector to output the founded objects.
Returns
the number of found objects.

Definition at line 326 of file Index.h.

template<class DATATYPE, int MAXNODES, int MINNODES>
void te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::search ( const te::gm::Envelope mbr,
NodeType node,
std::vector< DATATYPE > &  report,
int &  foundObjs 
) const
protected
template<class DATATYPE , int MAXNODES, int MINNODES>
void te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::setMBR ( const te::gm::Envelope mbr)
inline

It sets the bounding box of all elements in the tree.

Parameters
mbrThe bounding box of all elements in the tree.

Definition at line 337 of file Index.h.

template<class DATATYPE , int MAXNODES, int MINNODES>
std::size_t te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::size ( void  ) const
inline

It returns the number of elements in the tree.

Returns
The number of indexed elements.

Definition at line 287 of file Index.h.

template<class DATATYPE , int MAXNODES, int MINNODES>
void te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::splitNode ( NodeType node,
BranchType branch,
NodeType **  newNode 
) const
inlineprotected

Split a node.

Definition at line 643 of file Index.h.

References te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_level.

Member Data Documentation

template<class DATATYPE, int MAXNODES = 8, int MINNODES = MAXNODES / 2>
te::gm::Envelope te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_mbr
private

Bounding box of the tree.

Definition at line 256 of file Index.h.

Referenced by te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::Index().

template<class DATATYPE, int MAXNODES = 8, int MINNODES = MAXNODES / 2>
NodeType* te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_root
private

Pointer to the root node.

Definition at line 255 of file Index.h.

Referenced by te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::Index().

template<class DATATYPE, int MAXNODES = 8, int MINNODES = MAXNODES / 2>
std::size_t te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_size
mutableprivate

The size of R-Tree (number of nodes).

Definition at line 257 of file Index.h.

Referenced by te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::Index().


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