#include <basic-r-tree.h>
Inherits R_tree< Basic_R_tree >.
Inheritance diagram for Basic_R_tree:
Public Member Functions | |
Basic_R_tree () | |
Basic_R_tree (R_tree_props *props) | |
virtual Basic_R_tree * | remove (BB_container *element) |
virtual Basic_R_tree * | getRoot () |
virtual const Basic_R_tree * | getRoot () const |
virtual Basic_R_tree * | insert (BB_container *element) |
virtual Basic_R_tree * | search (BB_container *element) |
Protected Types | |
typedef vector< Basic_R_tree * >::const_iterator | childIterator |
typedef vector< BB_container * >::const_iterator | elemIterator |
Protected Member Functions | |
Basic_R_tree * | chooseLeaf (Basic_R_tree *v, const BB_type bb) const |
Basic_R_tree * | handleOverflow (Basic_R_tree *node, BB_container *element) |
void | linearSplitElements (vector< BB_container * > oldItems, BB_container *newItem, vector< BB_container * > *set_one, vector< BB_container * > *set_two, BB_type *mbr_one, BB_type *mbr_two, int dimension) |
void | linearSplitNodes (vector< Basic_R_tree * > oldItems, Basic_R_tree *newItem, vector< Basic_R_tree * > *set_one, vector< Basic_R_tree * > *set_two, BB_type *mbr_one, BB_type *mbr_two, int dimension) |
void | quadraticSplitElements (vector< BB_container * > oldItems, BB_container *newItem, vector< BB_container * > *set_one, vector< BB_container * > *set_two, BB_type *mbr_one, BB_type *mbr_two, int dimension) |
void | quadraticSplitNodes (vector< Basic_R_tree * > oldItems, Basic_R_tree *newItem, vector< Basic_R_tree * > *set_one, vector< Basic_R_tree * > *set_two, BB_type *mbr_one, BB_type *mbr_two, int dimension) |
Basic_R_tree * | insert (Basic_R_tree *node) |
Basic_R_tree * | buildNode (vector< BB_container * > input, BB_type *newMbr) const |
Basic_R_tree * | buildNode (vector< Basic_R_tree * > input, BB_type *newMbr) const |
void | reinsert (vector< Basic_R_tree * > s) |
void | reinsert (Basic_R_tree *walk, Basic_R_tree *at) |
Basic_R_tree * | handleOverflow (Basic_R_tree *node) |
Basic_R_tree * | makeNewRoot (Basic_R_tree *child) |
void | setChildren (vector< Basic_R_tree * > newChildren, BB_type *newMbr) |
void | removeChild (Basic_R_tree *toRemove) |
Basic_R_tree * | remove (Basic_R_tree *node, BB_container *element) |
Definition at line 20 of file basic-r-tree.h.
typedef vector< Basic_R_tree* >::const_iterator Basic_R_tree::childIterator [protected] |
Defines the type of an iterator on the child nodes of this tree, const variation.
Reimplemented from R_tree< Basic_R_tree >.
Definition at line 25 of file basic-r-tree.h.
typedef vector< BB_container* >::const_iterator Basic_R_tree::elemIterator [protected] |
Defines the type of an iterator on the elements stored at this node, const variation.
Definition at line 28 of file basic-r-tree.h.
Basic_R_tree::Basic_R_tree | ( | ) | [inline] |
Base constructor. Calls super constructor.
Definition at line 229 of file basic-r-tree.h.
Referenced by buildNode(), and makeNewRoot().
Basic_R_tree::Basic_R_tree | ( | R_tree_props * | props | ) | [inline] |
Base constructor, does not create its own property class.
props | The properties the current R-tree will use. |
Definition at line 236 of file basic-r-tree.h.
Basic_R_tree * Basic_R_tree::chooseLeaf | ( | Basic_R_tree * | v, | |
const BB_type | bb | |||
) | const [protected] |
This algorithm chooses a leaf to add an element with a given MBR to.
v | The (sub)tree at which to add the element | |
bb | The MBR of the element to be added |
Definition at line 1713 of file basic-r-tree.h.
References R_tree< Basic_R_tree >::areaEnlargement(), Tree< BB_container *, Basic_R_tree >::children, Tree< stored_type, tree_type >::isLeaf(), and Cart::Volume().
Referenced by insert().
Basic_R_tree * Basic_R_tree::handleOverflow | ( | Basic_R_tree * | node, | |
BB_container * | element | |||
) | [protected] |
This algorithm handles an overflow occuring at a given node at which a given container was to be added. This algorithm may employ different splitting strategies, as defined by the flag SPLIT_STRATEGY in r-tree.h. This algorithms results in the given node to be split in two. Both of these new nodes are added to the parent node. If this causes an overflow there as well, the handleOverflow algorithm is called recursively. If the given node does not have a parent (i.e., is root), a new root node is constructed with the two nodes resulting from the split as its children.
node | The full node at which the given element should be added | |
element | The to be added element |
Definition at line 1607 of file basic-r-tree.h.
References buildNode(), Tree< stored_type, tree_type >::elements, Tree< BB_container *, Basic_R_tree >::elements, EXPONENTIAL_SPLIT, Cubic_Bounding_Box::getDimension(), insert(), Tree< stored_type, tree_type >::isRoot(), LINEAR_SPLIT, linearSplitElements(), makeNewRoot(), Tree< stored_type, tree_type >::parent, QUADRATIC_SPLIT, quadraticSplitElements(), R_tree< r_tree_variation >::setElements(), and SPLIT_STRATEGY.
Referenced by insert().
void Basic_R_tree::linearSplitElements | ( | vector< BB_container * > | oldItems, | |
BB_container * | newItem, | |||
vector< BB_container * > * | set_one, | |||
vector< BB_container * > * | set_two, | |||
BB_type * | mbr_one, | |||
BB_type * | mbr_two, | |||
int | dimension | |||
) | [protected] |
This algorithm does the actual splitting according to the linearSplit algorithm. It creates two sets which denote the resulting split. The algorithm as implemented as present, only considers the ordering based on maximum and minimum coordinates (and not, for example, center coordinates).
oldItems | A set of items to which a new item is to be added. | |
newItem | The new item to be added. | |
set_one | The first split set. | |
set_two | The second set split set. | |
mbr_one | Pointer to where the first set MBR should be stored | |
mbr_two | Pointer to where the second set MBR should be stored | |
dimension | The item dimensions |
Definition at line 1320 of file basic-r-tree.h.
References Cubic_Bounding_Box::_mins, R_tree< Basic_R_tree >::areaEnlargement(), Cubic_Bounding_Box::become(), R_tree_props::minimum, R_tree< Basic_R_tree >::properties, Cubic_Bounding_Box::toString(), and Cubic_Bounding_Box::unite().
Referenced by handleOverflow().
void Basic_R_tree::linearSplitNodes | ( | vector< Basic_R_tree * > | oldItems, | |
Basic_R_tree * | newItem, | |||
vector< Basic_R_tree * > * | set_one, | |||
vector< Basic_R_tree * > * | set_two, | |||
BB_type * | mbr_one, | |||
BB_type * | mbr_two, | |||
int | dimension | |||
) | [protected] |
This algorithm does the actual splitting according to the linearSplit algorithm. It creates two sets which denote the resulting split. The algorithm as implemented as present, only considers the ordering based on maximum and minimum coordinates (and not, for example, center coordinates).
oldItems | A set of items to which a new item is to be added. | |
newItem | The new item to be added. | |
set_one | The first split set. | |
set_two | The second set split set. | |
mbr_one | Pointer to where the first set MBR should be stored | |
mbr_two | Pointer to where the second set MBR should be stored | |
dimension | The item dimensions |
Definition at line 1034 of file basic-r-tree.h.
References Cubic_Bounding_Box::_mins, R_tree< Basic_R_tree >::areaEnlargement(), Cubic_Bounding_Box::become(), R_tree< Basic_R_tree >::mbr, R_tree< r_tree_variation >::mbr, R_tree_props::minimum, R_tree< Basic_R_tree >::properties, and Cubic_Bounding_Box::toString().
Referenced by handleOverflow().
void Basic_R_tree::quadraticSplitElements | ( | vector< BB_container * > | oldItems, | |
BB_container * | newItem, | |||
vector< BB_container * > * | set_one, | |||
vector< BB_container * > * | set_two, | |||
BB_type * | mbr_one, | |||
BB_type * | mbr_two, | |||
int | dimension | |||
) | [protected] |
This algorithm does the actual splitting according to the quadraticSplit algorithm. It creates two sets which denote the resulting split. The algorithm as implemented as present, only considers the ordering based on maximum and minimum coordinates (and not, for example, center coordinates).
oldItems | A set of items to which a new item is to be added. | |
newItem | The new item to be added. | |
set_one | The first split set. | |
set_two | The second set split set. | |
mbr_one | Pointer to where the first set MBR should be stored | |
mbr_two | Pointer to where the second set MBR should be stored | |
dimension | Current dimensions of the BBs stored |
Definition at line 763 of file basic-r-tree.h.
References Cubic_Bounding_Box::become(), R_tree< Basic_R_tree >::deadSpace(), R_tree_props::minimum, R_tree< Basic_R_tree >::properties, Cubic_Bounding_Box::unionWith(), and Cart::Volume().
Referenced by handleOverflow().
void Basic_R_tree::quadraticSplitNodes | ( | vector< Basic_R_tree * > | oldItems, | |
Basic_R_tree * | newItem, | |||
vector< Basic_R_tree * > * | set_one, | |||
vector< Basic_R_tree * > * | set_two, | |||
BB_type * | mbr_one, | |||
BB_type * | mbr_two, | |||
int | dimension | |||
) | [protected] |
This algorithm does the actual splitting according to the quadraticSplit algorithm. It creates two sets which denote the resulting split. The algorithm as implemented as present, only considers the ordering based on maximum and minimum coordinates (and not, for example, center coordinates).
oldItems | A set of items to which a new item is to be added. | |
newItem | The new item to be added. | |
set_one | The first split set. | |
set_two | The second set split set. | |
mbr_one | Pointer to where the first set MBR should be stored | |
mbr_two | Pointer to where the second set MBR should be stored | |
dimension | Current dimensions of the BBs stored |
Definition at line 898 of file basic-r-tree.h.
References Cubic_Bounding_Box::become(), R_tree< Basic_R_tree >::deadSpace(), R_tree< Basic_R_tree >::mbr, R_tree_props::minimum, R_tree< Basic_R_tree >::properties, Cubic_Bounding_Box::unionWith(), and Cart::Volume().
Referenced by handleOverflow().
Basic_R_tree * Basic_R_tree::insert | ( | Basic_R_tree * | node | ) | [protected] |
This procedure is called when a given node should be added to the *current* *internal* node. Calls the overflow handling algorithm if so required.
node | The to be added node child |
Definition at line 702 of file basic-r-tree.h.
References Tree< BB_container *, Basic_R_tree >::children, R_tree< Basic_R_tree >::full(), getRoot(), handleOverflow(), Tree< BB_container *, Basic_R_tree >::parent, Tree< stored_type, tree_type >::parent, and R_tree< Basic_R_tree >::updateMBR().
Referenced by handleOverflow(), and reinsert().
Basic_R_tree * Basic_R_tree::buildNode | ( | vector< BB_container * > | input, | |
BB_type * | newMbr | |||
) | const [protected] |
Builds a leaf node from a collection of container data elements.
input | The data elements to be stored at the new leaf node | |
newMbr | The minimum bounding rectangle containing all input elements |
Definition at line 573 of file basic-r-tree.h.
References Basic_R_tree(), Tree< stored_type, tree_type >::elements, R_tree< r_tree_variation >::mbr, and R_tree< Basic_R_tree >::properties.
Referenced by handleOverflow().
Basic_R_tree * Basic_R_tree::buildNode | ( | vector< Basic_R_tree * > | input, | |
BB_type * | newMbr | |||
) | const [protected] |
Builds an internal node from a collection of other R-tree nodes.
input | The subtrees to be stored at the new internal node | |
newMbr | The minimum bounding rectangle containing all input subtrees MBRs |
Definition at line 595 of file basic-r-tree.h.
References Basic_R_tree(), Tree< stored_type, tree_type >::children, R_tree< r_tree_variation >::mbr, and R_tree< Basic_R_tree >::properties.
void Basic_R_tree::reinsert | ( | vector< Basic_R_tree * > | s | ) | [protected] |
Re-inserts all elements stored in the subtrees with roots given in a supplied vector.
s | A collection of subtrees |
Definition at line 526 of file basic-r-tree.h.
References insert().
Referenced by reinsert(), and remove().
void Basic_R_tree::reinsert | ( | Basic_R_tree * | walk, | |
Basic_R_tree * | at | |||
) | [protected] |
Re-inserts all elements stored in a given subtree at a given node
walk | The subtree which elements are to be re-inserted | |
at | The tree at which the elements are to be re-inserted |
Definition at line 561 of file basic-r-tree.h.
References Tree< BB_container *, Basic_R_tree >::children, Tree< BB_container *, Basic_R_tree >::elements, insert(), Tree< stored_type, tree_type >::isLeaf(), and reinsert().
Basic_R_tree * Basic_R_tree::handleOverflow | ( | Basic_R_tree * | node | ) | [protected] |
This algorithm handles an overflow occuring at the *current* *internal* node, at which a given node has to be added. The algorithm is completely the same as for the leaf nodes, with the only difference being that it operates on internal nodes, instead of elements, obviously.
node | The to be added node |
Definition at line 619 of file basic-r-tree.h.
References buildNode(), Tree< BB_container *, Basic_R_tree >::children, EXPONENTIAL_SPLIT, Cubic_Bounding_Box::getDimension(), insert(), LINEAR_SPLIT, linearSplitNodes(), makeNewRoot(), R_tree< r_tree_variation >::mbr, Tree< BB_container *, Basic_R_tree >::parent, QUADRATIC_SPLIT, quadraticSplitNodes(), setChildren(), and SPLIT_STRATEGY.
Basic_R_tree * Basic_R_tree::makeNewRoot | ( | Basic_R_tree * | child | ) | [protected] |
Creates a new root and makes the current and the given node children of this new root.
child | The second child of the new root |
Definition at line 476 of file basic-r-tree.h.
References Basic_R_tree(), Tree< stored_type, tree_type >::children, Tree< stored_type, tree_type >::parent, Tree< BB_container *, Basic_R_tree >::parent, R_tree< Basic_R_tree >::properties, and R_tree< r_tree_variation >::updateMBRLocal().
Referenced by handleOverflow().
void Basic_R_tree::setChildren | ( | vector< Basic_R_tree * > | newChildren, | |
BB_type * | newMbr | |||
) | [protected] |
Sets a collection of nodes to be the children of this node.
newChildren | The collection of new children | |
newMbr | The minimum bounding rectangle of newChildren |
Definition at line 370 of file basic-r-tree.h.
References Tree< BB_container *, Basic_R_tree >::children, Tree< BB_container *, Basic_R_tree >::elements, Tree< BB_container *, Basic_R_tree >::isLeaf(), R_tree< Basic_R_tree >::mbr, and R_tree< Basic_R_tree >::setElements().
Referenced by handleOverflow().
void Basic_R_tree::removeChild | ( | Basic_R_tree * | toRemove | ) | [protected] |
Removes a given child node from the current node.
toRemove | The child node to be removed. |
Definition at line 352 of file basic-r-tree.h.
References Tree< BB_container *, Basic_R_tree >::children.
Referenced by remove().
Basic_R_tree * Basic_R_tree::remove | ( | Basic_R_tree * | node, | |
BB_container * | element | |||
) | [protected] |
Removes a given element from a given node. Only call this method directly if the node at which the to-be removed element was known beforehand. Otherwise, simply call remove( BB_container *container).
node | The node the supplied element is stored at | |
element | The pointer to the container to-be deleted |
Definition at line 283 of file basic-r-tree.h.
References Tree< stored_type, tree_type >::children, Tree< stored_type, tree_type >::elements, Cubic_Bounding_Box_Container::getID(), Tree< stored_type, tree_type >::isLeaf(), Tree< stored_type, tree_type >::isRoot(), R_tree< r_tree_variation >::mbr, R_tree_props::minimum, Tree< stored_type, tree_type >::parent, R_tree< r_tree_variation >::properties, R_tree< Basic_R_tree >::properties, reinsert(), removeChild(), and R_tree< r_tree_variation >::updateMBRNode().
Basic_R_tree * Basic_R_tree::remove | ( | BB_container * | element | ) | [virtual] |
Removes a stored polytope from the R-tree structure. A pointer to the polytope must be explicitly given. If the polytope cannot be found within the R-tree, a warning is printed to stderr but no further action is taken.
element | The element to be removed from the R-tree. |
Implements Spatial_Tree< Basic_R_tree, BB_type, BB_container >.
Definition at line 1873 of file basic-r-tree.h.
References getRoot(), search(), and R_tree< r_tree_variation >::updateMBR().
Basic_R_tree * Basic_R_tree::getRoot | ( | ) | [virtual] |
Searches and returns the root of the R-tree the current node is in.
Reimplemented from R_tree< Basic_R_tree >.
Definition at line 1861 of file basic-r-tree.h.
References Tree< BB_container *, Basic_R_tree >::children, and Tree< BB_container *, Basic_R_tree >::elements.
const Basic_R_tree * Basic_R_tree::getRoot | ( | ) | const [virtual] |
Searches and returns the root of the R-tree the current node is in. Const version.
Definition at line 1849 of file basic-r-tree.h.
References Tree< BB_container *, Basic_R_tree >::children, and Tree< BB_container *, Basic_R_tree >::elements.
Basic_R_tree * Basic_R_tree::insert | ( | BB_container * | element | ) | [virtual] |
Insert a given container element into the R-trree structure.
element | The to be added element |
Implements Spatial_Tree< Basic_R_tree, BB_type, BB_container >.
Definition at line 1786 of file basic-r-tree.h.
References chooseLeaf(), Tree< stored_type, tree_type >::elements, R_tree< r_tree_variation >::full(), getRoot(), handleOverflow(), Tree< stored_type, tree_type >::isLeaf(), R_tree< r_tree_variation >::updateMBR(), and R_tree< r_tree_variation >::writeTreeToFile().
Basic_R_tree * Basic_R_tree::search | ( | BB_container * | element | ) | [virtual] |
Searches the R-tree for a given polytope, and returns the leaf node at which it is stored.
element | The element to be found |
Implements Tree< BB_container *, Basic_R_tree >.
Definition at line 1752 of file basic-r-tree.h.
References Tree< BB_container *, Basic_R_tree >::children, Tree< BB_container *, Basic_R_tree >::elements, Cubic_Bounding_Box_Container::getID(), and Cubic_Bounding_Box::intersects().
Referenced by remove().