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::Envelope & | getMBR (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... | |
Index & | operator= (const Index &rhs) |
No assignment operator allowed. More... | |
Private Attributes | |
te::gm::Envelope | m_mbr |
Bounding box of the tree. More... | |
NodeType * | m_root |
Pointer to the root node. More... | |
std::size_t | m_size |
The size of R-Tree (number of nodes). More... | |
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.
typedef NodeType::BranchType te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::BranchType |
typedef Node<DATATYPE, MAXNODES, MINNODES> te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::NodeType |
typedef te::sam::rtree::PartitionVars<BranchType, MAXNODES> te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::PartitionVarsType |
|
inline |
Constructor.
Definition at line 261 of file Index.h.
References te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_level, te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_root, and te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_size.
|
inline |
Constructor.
mbr | The MBR of all elements in the R-tree. |
Definition at line 270 of file Index.h.
References te::gm::Envelope::isValid(), te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_level, te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_mbr, te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_root, and te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_size.
|
inline |
Destructor.
Definition at line 280 of file Index.h.
References te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::clear(), and te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_root.
|
private |
No copy constructor allowed.
rhs | The other rtree. |
|
inlineprotected |
Add a branch to a node.
Definition at line 591 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::Index< DATATYPE, MAXNODES, MINNODES >::splitNode().
Referenced by te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::chooseLeaf(), te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::insert(), and te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::loadNodes().
|
protected |
It inserts a new data rectangle into the index structure.
Definition at line 482 of file Index.h.
References te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::addBranch(), te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::combineRect(), te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_branch, te::sam::rtree::Branch< NODE, DATATYPE >::m_child, te::sam::rtree::Branch< NODE, DATATYPE >::m_data, te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_level, te::sam::rtree::Branch< NODE, DATATYPE >::m_mbr, te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::nodeCover(), and te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::pickBranch().
Referenced by te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::insert().
|
inlineprotected |
Definition at line 790 of file Index.h.
References te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::combineRect(), te::gm::Envelope::getArea(), te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_area, te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_branchBuf, te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_count, te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_cover, te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_partition, and te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_taken.
Referenced by te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::pickSeeds(), and te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::pigeonhole().
|
inline |
It clears all tree nodes and make it ready for new insertions.
Definition at line 299 of file Index.h.
References te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::erase(), te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_level, te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_root, and te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_size.
Referenced by te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::~Index().
|
inlineprotected |
Combine two rectangles into larger one containing both.
Definition at line 583 of file Index.h.
References te::gm::Envelope::Union().
Referenced by te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::chooseLeaf(), te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::classify(), te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::getBranches(), te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::nodeCover(), te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::pickBranch(), and te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::pigeonhole().
|
protected |
It disconnects a dependent node.
Definition at line 473 of file Index.h.
References te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_branch, and te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_count.
Referenced by te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::remove2().
|
inlineprotected |
Erases a node from the tree and all nodes below it.
node | The 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.
Referenced by te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::clear().
|
inlineprotected |
Definition at line 665 of file Index.h.
References te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::combineRect(), te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::init(), te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_branch, te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_branchBuf, and te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_coverSplit.
Referenced by te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::splitNode().
|
inline |
It returns the bounding box of all elements in the tree.
Definition at line 343 of file Index.h.
References te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_mbr.
|
inline |
It inserts an item into the tree.
mbr | The object MBR. |
data | The object to be indexed. |
Definition at line 313 of file Index.h.
References te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_mbr, te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_root, and te::gm::Envelope::Union().
Referenced by te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::remove().
|
inlineprotected |
It inserts a data rectangle into an index structure.
Definition at line 349 of file Index.h.
References te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::addBranch(), te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::chooseLeaf(), te::sam::rtree::Branch< NODE, DATATYPE >::m_child, te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_level, te::sam::rtree::Branch< NODE, DATATYPE >::m_mbr, te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_size, and te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::nodeCover().
|
inline |
It returns true if the tree is empty.
Definition at line 293 of file Index.h.
References te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_count, and te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_root.
|
inlineprotected |
Definition at line 865 of file Index.h.
References te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::addBranch(), te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_branchBuf, and te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_partition.
Referenced by te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::splitNode().
|
inlineprotected |
Definition at line 685 of file Index.h.
References te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::init(), te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::pickSeeds(), and te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::pigeonhole().
Referenced by te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::splitNode().
|
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::Index< DATATYPE, MAXNODES, MINNODES >::combineRect(), 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.
Referenced by te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::chooseLeaf(), te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::insert(), and te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::remove2().
|
private |
No assignment operator allowed.
rhs | The other rtree. |
|
inlineprotected |
Pick a branch.
Definition at line 607 of file Index.h.
References te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::combineRect(), te::gm::Envelope::getArea(), 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.
Referenced by te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::chooseLeaf().
|
inlineprotected |
Definition at line 693 of file Index.h.
References te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::classify(), te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_branchBuf, te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_coverSplit, te::gm::Envelope::m_llx, te::gm::Envelope::m_lly, te::gm::Envelope::m_urx, and te::gm::Envelope::m_ury.
Referenced by te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::methodZero().
|
inlineprotected |
Definition at line 806 of file Index.h.
References te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::classify(), te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::combineRect(), te::gm::Envelope::getArea(), te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_area, te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_branchBuf, te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_count, te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_cover, and te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_taken.
Referenced by te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::methodZero().
|
inline |
It removes an item from the tree.
mbr | The object MBR. |
data | The object to be removed from the tree. |
Definition at line 320 of file Index.h.
References te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_root.
|
inlineprotected |
It deletes a data rectangle from an index structure.
Definition at line 385 of file Index.h.
References te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::insert(), te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_branch, te::sam::rtree::Branch< NODE, DATATYPE >::m_child, te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_count, te::sam::rtree::Branch< NODE, DATATYPE >::m_data, te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_level, te::sam::rtree::Branch< NODE, DATATYPE >::m_mbr, te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_size, and te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::remove2().
|
inlineprotected |
It deletes a rectangle from non-root part of an index structure.
Definition at line 429 of file Index.h.
References te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::disconBranch(), te::gm::Envelope::intersects(), te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::isInternalNode(), te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_branch, te::sam::rtree::Branch< NODE, DATATYPE >::m_child, te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_count, te::sam::rtree::Branch< NODE, DATATYPE >::m_data, te::sam::rtree::Branch< NODE, DATATYPE >::m_mbr, and te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::nodeCover().
Referenced by te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::remove().
|
inline |
Range search query.
mbr | The search rectangle. |
report | A vector to output the founded objects. |
Definition at line 326 of file Index.h.
References te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_root.
Referenced by te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::search().
|
protected |
Recursive range query.
Definition at line 530 of file Index.h.
References te::gm::Envelope::intersects(), te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::isInternalNode(), te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_branch, te::sam::rtree::Branch< NODE, DATATYPE >::m_child, te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_count, te::sam::rtree::Branch< NODE, DATATYPE >::m_data, te::sam::rtree::Branch< NODE, DATATYPE >::m_mbr, and te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::search().
|
inline |
It sets the bounding box of all elements in the tree.
mbr | The bounding box of all elements in the tree. |
Definition at line 337 of file Index.h.
References te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_mbr.
|
inline |
It returns the number of elements in the tree.
Definition at line 287 of file Index.h.
References te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_size.
|
inlineprotected |
Split a node.
Definition at line 643 of file Index.h.
References te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::getBranches(), te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::loadNodes(), te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_level, te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_size, and te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::methodZero().
Referenced by te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::addBranch().
|
private |
Bounding box of the tree.
Definition at line 256 of file Index.h.
Referenced by te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::getMBR(), te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::Index(), te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::insert(), and te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::setMBR().
|
private |
Pointer to the root node.
Definition at line 255 of file Index.h.
Referenced by te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::clear(), te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::Index(), te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::insert(), te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::isEmpty(), te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::remove(), te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::search(), and te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::~Index().
|
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 >::clear(), te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::Index(), te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::insert(), te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::remove(), te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::size(), and te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::splitNode().