#include <RTree.h>
Public Types | |
| typedef const _DataType & | DataRef |
| typedef _DataType | DataType |
| typedef _DataTypeCallback | DataTypeCallback |
| typedef unsigned int | pageid_t |
Public Member Functions | |
| AreaType | calcOverlap () const |
| calculate the sum of all overlaps in all levels | |
| void | calcStats (Stats &s) const |
| calculate the statistics of the tree | |
| AreaType | calcWasteArea () const |
| calculate the sum of all "wasted" areas in all levels | |
| void | clear () |
| reset the R-Tree by removing all elements | |
| bool | deleteRect (const DataRef rmdata) |
| delete function of the R-Tree | |
| bool | empty () const |
| check if the tree is empty | |
| void | insertRect (const DataRef newdata) |
| insert function of the R-Tree | |
| bool | loadSnapshot (std::istream &s) |
| reload the serialized representation | |
| Tree & | operator= (const Tree &o) |
| assigns the data of the rtree, does not copy the callback | |
| template<typename NNVisitor> | |
| void | queryNearestNeighbor (const Point &point, NNVisitor &vis) const |
| query the R-Tree for the nearest neighbor rectangles to a certain point. | |
| template<typename Visitor> | |
| void | queryRange (const Rect &range, Visitor &vis) const |
| query the R-Tree for all rectangles which intersect with the given search rectangle. | |
| void | saveSnapshot (std::ostream &s) const |
| save a serialized representation to the file | |
| void | setCallback (DataTypeCallback *newcb) |
| change the callback | |
| void | setReinsertNum (int rn) |
| change reinsert number | |
| unsigned int | size () const |
| return the number of elements in the R-Tree | |
| bool | testTree () const |
| assertion of various tree invariants | |
| Tree (const Tree &o) | |
| copy construct a tree, copies the callback | |
| Tree (DataTypeCallback *cb) | |
| void | writeFig (bool writefigheader, std::ostream &o, int maxlevel) const |
| write the rectangles out in the fig format. stop at a given level (0 are the leaves) | |
Public Attributes | |
| unsigned int | reinsertnum |
Static Public Attributes | |
| static const unsigned int | pageminfill = 12 |
| static const unsigned int | pagesize = 32 |
Protected Member Functions | |
| template<typename NodeData> | |
| void | reinsertRect (NodeData &newdata, unsigned int maxlevel, char *overflowedLevel) |
| reinsert used by the R*-Tree algorithm. inserts a data element into the tree at maxlevel | |
Classes | |
| class | InnerNode |
| structure used to access fields of an inner node page of the R-Tree More... | |
| struct | InnerNodeData |
| data struct of the elements found in each inner node More... | |
| class | LeafNode |
| structure used to access fields of a leaf node page of the R-Tree More... | |
| class | LeafNodeData |
| data struct of the elements in the leaf nodes. it is based on the template parameter More... | |
| class | NNPQData |
| class containing the data and ordering function of the nearest neighbor priority queue More... | |
| class | Node |
| node page augmented by a data type: either the childMBR + childPageId for InnerNodes or the childData for LeafNodes. More... | |
| class | NodeHead |
| common data structures found at the beginning of each node page. More... | |
| class | PageManager |
| poor man's page manager. used so that no pointers are saved in the R-Tree data More... | |
| struct | ReinsertDist |
| data structed used to order children to reinsert More... | |
Definition at line 309 of file RTree.h.
| typedef const _DataType& VGServer::RTree::Tree< _DataType, _DataTypeCallback >::DataRef |
| typedef _DataType VGServer::RTree::Tree< _DataType, _DataTypeCallback >::DataType |
| typedef _DataTypeCallback VGServer::RTree::Tree< _DataType, _DataTypeCallback >::DataTypeCallback |
| typedef unsigned int VGServer::RTree::Tree< _DataType, _DataTypeCallback >::pageid_t |
| VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Tree | ( | DataTypeCallback * | cb | ) | [inline, explicit] |
Definition at line 2178 of file RTree.h.
References VGServer::RTree::Tree< _DataType, _DataTypeCallback >::NodeHead::initializeRoot().
| VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Tree | ( | const Tree< _DataType, _DataTypeCallback > & | o | ) | [inline] |
copy construct a tree, copies the callback
Definition at line 2194 of file RTree.h.
References VGServer::RTree::Tree< _DataType, _DataTypeCallback >::DTCallback, VGServer::RTree::Tree< _DataType, _DataTypeCallback >::entries, VGServer::RTree::Tree< _DataType, _DataTypeCallback >::levels, VGServer::RTree::Tree< _DataType, _DataTypeCallback >::pageman, VGServer::RTree::Tree< _DataType, _DataTypeCallback >::reinsertnum, and VGServer::RTree::Tree< _DataType, _DataTypeCallback >::rootpage.
| AreaType VGServer::RTree::Tree< _DataType, _DataTypeCallback >::calcOverlap | ( | ) | const [inline] |
calculate the sum of all overlaps in all levels
Definition at line 2518 of file RTree.h.
References VGServer::RTree::Tree< _DataType, _DataTypeCallback >::NodeHead::level.
| void VGServer::RTree::Tree< _DataType, _DataTypeCallback >::calcStats | ( | Stats & | s | ) | const [inline] |
calculate the statistics of the tree
Definition at line 2502 of file RTree.h.
References VGServer::RTree::Tree< _DataType, _DataTypeCallback >::NodeHead::level, and VGServer::RTree::Stats::level.
| AreaType VGServer::RTree::Tree< _DataType, _DataTypeCallback >::calcWasteArea | ( | ) | const [inline] |
calculate the sum of all "wasted" areas in all levels
Definition at line 2531 of file RTree.h.
References VGServer::RTree::Tree< _DataType, _DataTypeCallback >::NodeHead::level.
| void VGServer::RTree::Tree< _DataType, _DataTypeCallback >::clear | ( | ) | [inline] |
reset the R-Tree by removing all elements
Definition at line 2219 of file RTree.h.
References VGServer::RTree::Tree< _DataType, _DataTypeCallback >::NodeHead::initializeRoot().
| bool VGServer::RTree::Tree< _DataType, _DataTypeCallback >::deleteRect | ( | const DataRef | rmdata | ) | [inline] |
delete function of the R-Tree
Definition at line 2282 of file RTree.h.
References VGServer::RTree::Tree< _DataType, _DataTypeCallback >::LeafNode::deleteDataLeaf(), and VGServer::RTree::Tree< _DataType, _DataTypeCallback >::NodeHead::level.
| bool VGServer::RTree::Tree< _DataType, _DataTypeCallback >::empty | ( | ) | const [inline] |
| void VGServer::RTree::Tree< _DataType, _DataTypeCallback >::insertRect | ( | const DataRef | newdata | ) | [inline] |
insert function of the R-Tree
Definition at line 2248 of file RTree.h.
References VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >::insertChild(), and VGServer::RTree::Tree< _DataType, _DataTypeCallback >::NodeHead::level.
| bool VGServer::RTree::Tree< _DataType, _DataTypeCallback >::loadSnapshot | ( | std::istream & | s | ) | [inline] |
| Tree& VGServer::RTree::Tree< _DataType, _DataTypeCallback >::operator= | ( | const Tree< _DataType, _DataTypeCallback > & | o | ) | [inline] |
assigns the data of the rtree, does not copy the callback
Definition at line 2206 of file RTree.h.
References VGServer::RTree::Tree< _DataType, _DataTypeCallback >::entries, VGServer::RTree::Tree< _DataType, _DataTypeCallback >::levels, VGServer::RTree::Tree< _DataType, _DataTypeCallback >::pageman, VGServer::RTree::Tree< _DataType, _DataTypeCallback >::reinsertnum, and VGServer::RTree::Tree< _DataType, _DataTypeCallback >::rootpage.
| void VGServer::RTree::Tree< _DataType, _DataTypeCallback >::queryNearestNeighbor | ( | const Point & | point, | |
| NNVisitor & | vis | |||
| ) | const [inline] |
query the R-Tree for the nearest neighbor rectangles to a certain point.
call the visitor template class for narrowing it down.
Definition at line 2621 of file RTree.h.
References VGServer::RTree::Tree< _DataType, _DataTypeCallback >::NodeHead::childnum, VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >::children, VGServer::RTree::Point::getMinimumDistanceSquare(), and VGServer::RTree::Tree< _DataType, _DataTypeCallback >::NodeHead::level.
| void VGServer::RTree::Tree< _DataType, _DataTypeCallback >::queryRange | ( | const Rect & | range, | |
| Visitor & | vis | |||
| ) | const [inline] |
query the R-Tree for all rectangles which intersect with the given search rectangle.
call the template class for each of them.
Definition at line 2554 of file RTree.h.
References VGServer::RTree::Tree< _DataType, _DataTypeCallback >::NodeHead::childnum, VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< _NodeData >::children, VGServer::RTree::Tree< _DataType, _DataTypeCallback >::NodeHead::level, and VGServer::RTree::Rect::valid().
| void VGServer::RTree::Tree< _DataType, _DataTypeCallback >::reinsertRect | ( | NodeData & | newdata, | |
| unsigned int | maxlevel, | |||
| char * | overflowedLevel | |||
| ) | [inline, protected] |
reinsert used by the R*-Tree algorithm. inserts a data element into the tree at maxlevel
Definition at line 2000 of file RTree.h.
References VGServer::RTree::Tree< _DataType, _DataTypeCallback >::NodeHead::level.
Referenced by VGServer::RTree::Tree< _DataType, _DataTypeCallback >::LeafNode::deleteDataLeaf(), and VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< VGServer::RTree::Tree::InnerNodeData >::reinsertData().
| void VGServer::RTree::Tree< _DataType, _DataTypeCallback >::saveSnapshot | ( | std::ostream & | s | ) | const [inline] |
| void VGServer::RTree::Tree< _DataType, _DataTypeCallback >::setCallback | ( | DataTypeCallback * | newcb | ) | [inline] |
| void VGServer::RTree::Tree< _DataType, _DataTypeCallback >::setReinsertNum | ( | int | rn | ) | [inline] |
| unsigned int VGServer::RTree::Tree< _DataType, _DataTypeCallback >::size | ( | ) | const [inline] |
| bool VGServer::RTree::Tree< _DataType, _DataTypeCallback >::testTree | ( | ) | const [inline] |
assertion of various tree invariants
Definition at line 2485 of file RTree.h.
References VGServer::RTree::Tree< _DataType, _DataTypeCallback >::NodeHead::level.
| void VGServer::RTree::Tree< _DataType, _DataTypeCallback >::writeFig | ( | bool | writefigheader, | |
| std::ostream & | o, | |||
| int | maxlevel | |||
| ) | const [inline] |
write the rectangles out in the fig format. stop at a given level (0 are the leaves)
Definition at line 2315 of file RTree.h.
References VGServer::RTree::Tree< _DataType, _DataTypeCallback >::NodeHead::level, VGServer::RTree::Tree< _DataType, _DataTypeCallback >::NodeHead::nodeMBR, VGServer::RTree::Rect::x1, VGServer::RTree::Rect::x2, VGServer::RTree::Rect::y1, and VGServer::RTree::Rect::y2.
Referenced by VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< VGServer::RTree::Tree::InnerNodeData >::writeFig().
const unsigned int VGServer::RTree::Tree< _DataType, _DataTypeCallback >::pageminfill = 12 [static] |
const unsigned int VGServer::RTree::Tree< _DataType, _DataTypeCallback >::pagesize = 32 [static] |
| unsigned int VGServer::RTree::Tree< _DataType, _DataTypeCallback >::reinsertnum |
Definition at line 325 of file RTree.h.
Referenced by VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< VGServer::RTree::Tree::InnerNodeData >::insertChild(), VGServer::RTree::Tree< _DataType, _DataTypeCallback >::operator=(), VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Node< VGServer::RTree::Tree::InnerNodeData >::reinsertData(), and VGServer::RTree::Tree< _DataType, _DataTypeCallback >::Tree().
1.4.7