#include <r-tree.h>
Inherits Spatial_Tree< r_tree_variation, BB_type, BB_container >.
Inheritance diagram for R_tree< r_tree_variation >:
Public Member Functions | |
| R_tree () | |
| R_tree (R_tree_props *props) | |
| virtual | ~R_tree () |
| void | gatherTreeInfo (int *x, int *y) const |
| const BB_type * | getMBR () const |
| virtual void | postBulkLoad () |
| R_tree< r_tree_variation > * | getRoot () |
| virtual vector< int > | containedIn (const BB_type &box) const |
| virtual vector< int > | intersects (const vector< double > &begin, const vector< double > &end) const |
| virtual vector< int > | intersects (const Point &point) const |
| virtual vector< int > | intersects (const vector< double > &a, const double b) const |
| virtual vector< int > | neighboursOf (const BB_container *item) const |
| virtual vector< int > | neighboursOf (const vector< double > &point, const unsigned int k) const |
| void | writeTreeToFile (string fn) const |
| void | readTreeFromFile (string fn) const |
| void | printTreeInfo (ostringstream &oss) const |
| void | printTreeToStdOut (const int x, const void *par) const |
Public Attributes | |
| bool | deleteLeaves |
Protected Types | |
| typedef vector< r_tree_variation * >::const_iterator | childIterator |
Protected Member Functions | |
| void | setElements (vector< BB_container * > newElements, BB_type *newMbr) |
| void | init () |
| bool | full () const |
| double | areaEnlargement (const BB_type bb1, const BB_type bb2) const |
| double | deadSpace (const BB_type bb1, const BB_type bb2) const |
| void | writeTreeToFile (ofstream &ofs) const |
| void | readTreeFromStream (ifstream &ifs) const |
| void | nullifyProperties () |
| void | updateAllMBRs () |
| void | updateMBRLocal () |
| void | updateMBRNode () |
| void * | updateMBR () |
| void | containedIn (const BB_type *box, vector< int > *ret) const |
| void | intersects (const vector< double > &begin, const vector< double > &end, vector< int > *ret) const |
| void | intersects (const Point &point, vector< int > *ret) const |
| void | intersects (const vector< double > &a, const double b, vector< int > *ret) const |
| void | neighboursOf (const BB_container *item, vector< int > *ret) const |
| void | neighboursOf (const vector< double > &point, NearestNeighbours< BB_container > *ns, MinDistTreeOrdering< BB_type, r_tree_variation > *mdt) const |
Protected Attributes | |
| BB_type | mbr |
| R_tree_props * | properties |
Private Member Functions | |
| template<class T> | |
| bool | from_string (T &t, const std::string &s, std::ios_base &(*f)(std::ios_base &)) const |
Friends | |
| class | Basic_R_tree |
Definition at line 70 of file r-tree.h.
typedef vector< r_tree_variation * >::const_iterator R_tree< r_tree_variation >::childIterator [protected] |
Base constructor
Definition at line 1024 of file r-tree.h.
References R_tree< r_tree_variation >::init(), R_tree_props::maximum, R_tree_props::minimum, and R_tree< r_tree_variation >::properties.
| R_tree< r_tree_variation >::R_tree | ( | R_tree_props * | props | ) | [inline] |
Base constructor, does not create its own property class
Definition at line 1032 of file r-tree.h.
References R_tree< r_tree_variation >::init(), and R_tree< r_tree_variation >::properties.
Base deconstructor
Definition at line 1038 of file r-tree.h.
References Tree< BB_container *, r_tree_variation >::children, R_tree< r_tree_variation >::deleteLeaves, Tree< BB_container *, r_tree_variation >::elements, R_tree< r_tree_variation >::nullifyProperties(), and R_tree< r_tree_variation >::properties.
| bool R_tree< r_tree_variation >::from_string | ( | T & | t, | |
| const std::string & | s, | |||
| std::ios_base &(*)(std::ios_base &) | f | |||
| ) | const [inline, private] |
| void R_tree< r_tree_variation >::setElements | ( | vector< BB_container * > | newElements, | |
| BB_type * | newMbr | |||
| ) | [inline, protected] |
Sets the elements of the current node to a given vector.
| newElements | The new elements vector | |
| newMbr | The MBR of the given elements |
Definition at line 1174 of file r-tree.h.
References Tree< BB_container *, r_tree_variation >::children, Tree< BB_container *, r_tree_variation >::elements, and R_tree< r_tree_variation >::mbr.
Referenced by Basic_R_tree::handleOverflow().
| void R_tree< r_tree_variation >::init | ( | ) | [inline, protected] |
Initialises the tree
Definition at line 531 of file r-tree.h.
References Tree< BB_container *, r_tree_variation >::children, R_tree< r_tree_variation >::deleteLeaves, Tree< BB_container *, r_tree_variation >::elements, and Tree< BB_container *, r_tree_variation >::parent.
Referenced by R_tree< r_tree_variation >::R_tree().
| bool R_tree< r_tree_variation >::full | ( | ) | const [inline, protected] |
Checks if the current node is at full capacity.
Definition at line 743 of file r-tree.h.
References Tree< BB_container *, r_tree_variation >::children, R_tree_props::maximum, and R_tree< r_tree_variation >::properties.
Referenced by Basic_R_tree::insert().
| double R_tree< r_tree_variation >::areaEnlargement | ( | const BB_type | bb1, | |
| const BB_type | bb2 | |||
| ) | const [inline, protected] |
Calculates the volume enlargement if a given MBR was to be extended with a second given MBR.
| bb1 | The first MBR. | |
| bb2 | The second MBR. |
Definition at line 728 of file r-tree.h.
References Cubic_Bounding_Box::unionWith(), and Cart::Volume().
| double R_tree< r_tree_variation >::deadSpace | ( | const BB_type | bb1, | |
| const BB_type | bb2 | |||
| ) | const [inline, protected] |
Calculates the dead space of a MBR containing two given MBRs
| bb1 | The first MBR. | |
| bb2 | The second MBR. |
Definition at line 723 of file r-tree.h.
References Cubic_Bounding_Box::unionWith(), and Cart::Volume().
| void R_tree< r_tree_variation >::writeTreeToFile | ( | ofstream & | ofs | ) | const [inline, protected] |
Writes subtree data to a given file stream.
| ofs | The output file stream to write to |
Definition at line 470 of file r-tree.h.
References Tree< BB_container *, r_tree_variation >::children, Tree< BB_container *, r_tree_variation >::elements, R_tree< r_tree_variation >::mbr, and Cubic_Bounding_Box::writeToFile().
Referenced by Basic_R_tree::insert(), and R_tree< r_tree_variation >::writeTreeToFile().
| void R_tree< r_tree_variation >::readTreeFromStream | ( | ifstream & | ifs | ) | const [inline, protected] |
Reads in tree info.
| ifs | The input file stream to read from |
Definition at line 488 of file r-tree.h.
Referenced by R_tree< r_tree_variation >::readTreeFromFile().
| void R_tree< r_tree_variation >::nullifyProperties | ( | ) | [inline, protected] |
Sets the pointer to the properties field to zero. Should only be called when the tree is marked for deletion (by the deconstructor).
Definition at line 761 of file r-tree.h.
References Tree< BB_container *, r_tree_variation >::children, and R_tree< r_tree_variation >::properties.
Referenced by R_tree< r_tree_variation >::~R_tree().
| void R_tree< r_tree_variation >::updateAllMBRs | ( | ) | [inline, protected] |
Updates all MBRs in the current subtree.
Definition at line 769 of file r-tree.h.
References Tree< BB_container *, r_tree_variation >::children, and R_tree< r_tree_variation >::updateMBRLocal().
Referenced by R_tree< r_tree_variation >::updateMBRNode().
| void R_tree< r_tree_variation >::updateMBRLocal | ( | ) | [inline, protected] |
Updates MBR at the current node only.
Definition at line 780 of file r-tree.h.
References Tree< BB_container *, r_tree_variation >::children, Cubic_Bounding_Box::clear(), Cubic_Bounding_Box::contains(), Tree< BB_container *, r_tree_variation >::elements, R_tree< r_tree_variation >::mbr, and Cubic_Bounding_Box::unite().
Referenced by Hilbert_R_tree::handleOverflow(), Basic_R_tree::makeNewRoot(), R_tree< r_tree_variation >::updateAllMBRs(), and R_tree< r_tree_variation >::updateMBR().
| void R_tree< r_tree_variation >::updateMBRNode | ( | ) | [inline, protected] |
This subroutine recursively updates the MBRs of all children of this node. It then proceeds with updating the current node MBR and propagates upward.
Definition at line 829 of file r-tree.h.
References R_tree< r_tree_variation >::updateAllMBRs(), and R_tree< r_tree_variation >::updateMBR().
Referenced by Basic_R_tree::remove().
| void * R_tree< r_tree_variation >::updateMBR | ( | ) | [inline, protected] |
This subroutine updates the MBR of the current node by reconstructing one from the children node MBRs or element MBRs, depending on if the node is an internal one. Propagates upward.
Definition at line 835 of file r-tree.h.
References Tree< BB_container *, r_tree_variation >::parent, and R_tree< r_tree_variation >::updateMBRLocal().
Referenced by Hilbert_R_tree::handleOverflow(), Basic_R_tree::insert(), Basic_R_tree::remove(), and R_tree< r_tree_variation >::updateMBRNode().
| void R_tree< r_tree_variation >::containedIn | ( | const BB_type * | box, | |
| vector< int > * | ret | |||
| ) | const [inline, protected] |
Searches and returns all container IDs which are contained in a given bounding box.
| box | The given bounding box | |
| ret | A pointer to where the query results are stored |
Definition at line 861 of file r-tree.h.
References Tree< BB_container *, r_tree_variation >::children, Tree< BB_container *, r_tree_variation >::elements, and Cubic_Bounding_Box::intersects().
Referenced by R_tree< r_tree_variation >::containedIn().
| void R_tree< r_tree_variation >::intersects | ( | const vector< double > & | begin, | |
| const vector< double > & | end, | |||
| vector< int > * | ret | |||
| ) | const [inline, protected] |
Searches and returns all container IDs which intersect a line defined by its given start- en ending points.
| begin | The starting point of the line | |
| end | The ending point of the line | |
| ret | A pointer to where the query results are stored |
Definition at line 891 of file r-tree.h.
References Tree< BB_container *, r_tree_variation >::children, and Tree< BB_container *, r_tree_variation >::elements.
Referenced by R_tree< r_tree_variation >::intersects().
| void R_tree< r_tree_variation >::intersects | ( | const Point & | point, | |
| vector< int > * | ret | |||
| ) | const [inline, protected] |
Searches and returns all container IDs which intersect a given Point.
| point | The given point | |
| ret | A pointer to where the query results are stored |
Definition at line 927 of file r-tree.h.
References Tree< BB_container *, r_tree_variation >::children, and Tree< BB_container *, r_tree_variation >::elements.
| void R_tree< r_tree_variation >::intersects | ( | const vector< double > & | a, | |
| const double | b, | |||
| vector< int > * | ret | |||
| ) | const [inline, protected] |
Searches and returns all container IDs which intersect an affine hyperplane. A hyperplane is defined as:
a_1 * x_1 + a_2 * x_2 + ... + a_{n-1} * x_{n-1} = b
where n is the dimension of the bounding boxes stored in this tree, a is a vector of length n-1, x are the coordinates in R^{(n-1)} which lie on the hyperplane, b is a scalar.
| a | The n-1 vector a. | |
| b | The scalar b. | |
| ret | A pointer to where the query results are stored |
| void R_tree< r_tree_variation >::neighboursOf | ( | const BB_container * | item, | |
| vector< int > * | ret | |||
| ) | const [inline, protected] |
Searches and returns which container IDs are considered to be neighbours of a given container pointed to by an iterator.
| item | A pointer to the container we wish to know the neighbours of | |
| ret | A pointer to where the query results are stored |
Definition at line 981 of file r-tree.h.
Referenced by R_tree< r_tree_variation >::neighboursOf().
| void R_tree< r_tree_variation >::neighboursOf | ( | const vector< double > & | point, | |
| NearestNeighbours< BB_container > * | ns, | |||
| MinDistTreeOrdering< BB_type, r_tree_variation > * | mdt | |||
| ) | const [inline, protected] |
Searches and returns the polytopes that are the closest neighbours of a given point.
| point | The point we wish to know the neighbours of. | |
| ns | The nearest neighbours currently found. |
Definition at line 984 of file r-tree.h.
References Tree< BB_container *, r_tree_variation >::elements, NearestNeighbours< cur_type >::insert(), NearestNeighbours< cur_type >::max, NearestNeighbours< cur_type >::maxdist, NearestNeighbours< cur_type >::size, and Ordering< cur_tree >::sort().
| void R_tree< r_tree_variation >::gatherTreeInfo | ( | int * | x, | |
| int * | y | |||
| ) | const [inline] |
Gathers the number of internal and leaf nodes.
| x | Pointer to where the number of internal nodes should be stored | |
| y | Pointer to where the number of leaf nodes should be stored |
Definition at line 516 of file r-tree.h.
References Tree< BB_container *, r_tree_variation >::children, and Tree< BB_container *, r_tree_variation >::elements.
Referenced by R_tree< r_tree_variation >::printTreeInfo().
| virtual void R_tree< r_tree_variation >::postBulkLoad | ( | ) | [inline, virtual] |
Method called after a bulk-loading operation. Use this function for R-tree specific invariants enforcement, to be set after the basic tree structure has been decided by an bulk-loading algorithm.
Reimplemented in Hilbert_R_tree.
| R_tree< r_tree_variation >* R_tree< r_tree_variation >::getRoot | ( | ) | [inline] |
Gets the tree root of the current tree.
Reimplemented from Tree< BB_container *, r_tree_variation >.
Reimplemented in Basic_R_tree, and Hilbert_R_tree.
| vector< int > R_tree< r_tree_variation >::containedIn | ( | const BB_type & | box | ) | const [inline, virtual] |
See superclass Spatial_Tree
Implements Spatial_Tree< r_tree_variation, BB_type, BB_container >.
Definition at line 1078 of file r-tree.h.
References R_tree< r_tree_variation >::containedIn().
| vector< int > R_tree< r_tree_variation >::intersects | ( | const vector< double > & | begin, | |
| const vector< double > & | end | |||
| ) | const [inline, virtual] |
See superclass Spatial_Tree
Implements Spatial_Tree< r_tree_variation, BB_type, BB_container >.
Definition at line 1094 of file r-tree.h.
References R_tree< r_tree_variation >::intersects().
| vector< int > R_tree< r_tree_variation >::intersects | ( | const Point & | point | ) | const [inline, virtual] |
See superclass Spatial_Tree
Implements Spatial_Tree< r_tree_variation, BB_type, BB_container >.
Definition at line 1107 of file r-tree.h.
References R_tree< r_tree_variation >::intersects().
| vector< int > R_tree< r_tree_variation >::intersects | ( | const vector< double > & | a, | |
| const double | b | |||
| ) | const [inline, virtual] |
See superclass Spatial_Tree
Implements Spatial_Tree< r_tree_variation, BB_type, BB_container >.
| vector< int > R_tree< r_tree_variation >::neighboursOf | ( | const BB_container * | item | ) | const [inline, virtual] |
See superclass Spatial_Tree
Implements Spatial_Tree< r_tree_variation, BB_type, BB_container >.
| vector< int > R_tree< r_tree_variation >::neighboursOf | ( | const vector< double > & | point, | |
| const unsigned int | k | |||
| ) | const [inline, virtual] |
See superclass Spatial_Tree
Implements Spatial_Tree< r_tree_variation, BB_type, BB_container >.
Definition at line 1140 of file r-tree.h.
References NearestNeighbours< cur_type >::ids, and R_tree< r_tree_variation >::neighboursOf().
| void R_tree< r_tree_variation >::writeTreeToFile | ( | string | fn | ) | const [inline] |
Writes tree data to a file with path and filename given.
| fn | The given file name (and path) |
Definition at line 1062 of file r-tree.h.
References R_tree< r_tree_variation >::writeTreeToFile().
| void R_tree< r_tree_variation >::readTreeFromFile | ( | string | fn | ) | const [inline] |
Reads tree data to a file with path and filename given.
| fn | The given file name (and path) |
Definition at line 1070 of file r-tree.h.
References R_tree< r_tree_variation >::readTreeFromStream().
| void R_tree< r_tree_variation >::printTreeInfo | ( | ostringstream & | oss | ) | const [inline] |
Writes tree info to a supplied string stream.
| oss | The output string stream to write to |
Definition at line 1160 of file r-tree.h.
References R_tree< r_tree_variation >::gatherTreeInfo(), and Tree< BB_container *, r_tree_variation >::getHeight().
| void R_tree< r_tree_variation >::printTreeToStdOut | ( | const int | x, | |
| const void * | par | |||
| ) | const [inline] |
Reimplemented from Tree< BB_container *, r_tree_variation >.
Definition at line 441 of file r-tree.h.
References Tree< BB_container *, r_tree_variation >::children, Tree< BB_container *, r_tree_variation >::isLeaf(), R_tree_props::maximum, R_tree_props::minimum, and R_tree< r_tree_variation >::properties.
friend class Basic_R_tree [friend] |
The Minimum Bounding Rectangle of the current node
Definition at line 209 of file r-tree.h.
Referenced by Hilbert_R_tree::buildNode(), Basic_R_tree::buildNode(), R_tree< Hilbert_R_tree >::getMBR(), Basic_R_tree::handleOverflow(), Basic_R_tree::linearSplitNodes(), Basic_R_tree::remove(), R_tree< r_tree_variation >::setElements(), R_tree< r_tree_variation >::updateMBRLocal(), and R_tree< r_tree_variation >::writeTreeToFile().
R_tree_props* R_tree< r_tree_variation >::properties [protected] |
A pointer to the structure which stores the current R-tree parameters
Definition at line 212 of file r-tree.h.
Referenced by R_tree< r_tree_variation >::full(), R_tree< r_tree_variation >::nullifyProperties(), R_tree< r_tree_variation >::printTreeToStdOut(), R_tree< r_tree_variation >::R_tree(), Basic_R_tree::remove(), and R_tree< r_tree_variation >::~R_tree().
| bool R_tree< r_tree_variation >::deleteLeaves |
Flag indicating if the R-tree should actively delete its leaf elements upon deconstruction.
Definition at line 320 of file r-tree.h.
Referenced by R_tree< r_tree_variation >::init(), and R_tree< r_tree_variation >::~R_tree().
1.5.2