SUMO - Simulation of Urban MObility
|
#include <RTree.h>
Data Structures | |
struct | Branch |
class | Iterator |
Iterator is not remove safe. More... | |
struct | ListNode |
A link list of nodes for reinsertion after a delete operation. More... | |
struct | Node |
Node for each branch level. More... | |
struct | PartitionVars |
Variables for finding a split partition. More... | |
struct | Rect |
Minimal bounding rectangle (n-dimensional) More... | |
Public Types | |
enum | { MAXNODES = TMAXNODES, MINNODES = TMINNODES } |
typedef void(DATATYPENP::* | Operation )(const CONTEXT &) const |
Public Member Functions | |
int | Count () |
Count the data elements in this container. This is slow as no internal counter is maintained. | |
DATATYPE & | GetAt (Iterator &a_it) |
Get object at iterator position. | |
void | GetFirst (Iterator &a_it) |
Get 'first' for iteration. | |
void | GetNext (Iterator &a_it) |
Get Next for iteration. | |
void | Insert (const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE &a_dataId) |
bool | IsNull (Iterator &a_it) |
Is iterator NULL, or at end? | |
void | Remove (const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE &a_dataId) |
void | RemoveAll () |
DK 15.10.2008 - end. | |
RTree (Operation operation) | |
int | Search (const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const CONTEXT &c) |
DK 15.10.2008 - begin. | |
virtual | ~RTree () |
Protected Member Functions | |
bool | AddBranch (Branch *a_branch, Node *a_node, Node **a_newNode) |
ListNode * | AllocListNode () |
Node * | AllocNode () |
ELEMTYPEREAL | CalcRectVolume (Rect *a_rect) |
void | ChoosePartition (PartitionVars *a_parVars, int a_minFill) |
void | Classify (int a_index, int a_group, PartitionVars *a_parVars) |
Rect | CombineRect (Rect *a_rectA, Rect *a_rectB) |
void | CountRec (Node *a_node, int &a_count) |
void | DisconnectBranch (Node *a_node, int a_index) |
void | FreeListNode (ListNode *a_listNode) |
void | FreeNode (Node *a_node) |
void | GetBranches (Node *a_node, Branch *a_branch, PartitionVars *a_parVars) |
void | InitNode (Node *a_node) |
void | InitParVars (PartitionVars *a_parVars, int a_maxRects, int a_minFill) |
void | InitRect (Rect *a_rect) |
bool | InsertRect (Rect *a_rect, const DATATYPE &a_id, Node **a_root, int a_level) |
bool | InsertRectRec (Rect *a_rect, const DATATYPE &a_id, Node *a_node, Node **a_newNode, int a_level) |
void | LoadNodes (Node *a_nodeA, Node *a_nodeB, PartitionVars *a_parVars) |
Rect | NodeCover (Node *a_node) |
bool | Overlap (Rect *a_rectA, Rect *a_rectB) |
int | PickBranch (Rect *a_rect, Node *a_node) |
void | PickSeeds (PartitionVars *a_parVars) |
template<> | |
float | RectSphericalVolume (Rect *a_rect) |
ELEMTYPEREAL | RectSphericalVolume (Rect *a_rect) |
ELEMTYPEREAL | RectVolume (Rect *a_rect) |
void | ReInsert (Node *a_node, ListNode **a_listNode) |
void | RemoveAllRec (Node *a_node) |
bool | RemoveRect (Rect *a_rect, const DATATYPE &a_id, Node **a_root) |
bool | RemoveRectRec (Rect *a_rect, const DATATYPE &a_id, Node *a_node, ListNode **a_listNode) |
void | Reset () |
bool | Search (Node *a_node, Rect *a_rect, int &a_foundCount, const CONTEXT &c) |
void | SplitNode (Node *a_node, Branch *a_branch, Node **a_newNode) |
Protected Attributes | |
Node * | m_root |
Root of tree. | |
ELEMTYPEREAL | m_unitSphereVolume |
Unit sphere constant for required number of dimensions. | |
Operation | myOperation |
Implementation of RTree, a multidimensional bounding rectangle tree. Example usage: For a 3-dimensional tree use RTree<Object*, float, 3> myTree;
This modified, templated C++ version by Greg Douglas at Auran (http://www.auran.com)
DATATYPE Referenced data, should be int, void*, obj* etc. no larger than sizeof<void*> and simple type ELEMTYPE Type of element such as int or float NUMDIMS Number of dimensions such as 2 or 3 ELEMTYPEREAL Type of element that allows fractional and large values such as float or double, for use in volume calcs
NOTES: Inserting and removing data requires the knowledge of its constant Minimal Bounding Rectangle. This version uses new/delete for nodes, I recommend using a fixed size allocator for efficiency. Instead of using a callback function for returned results, I recommend and efficient pre-sized, grow-only memory array similar to MFC CArray or STL Vector for returning search query result.
typedef void(DATATYPENP::* RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Operation)(const CONTEXT &) const |
anonymous enum |
RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RTree | ( | Operation | operation | ) |
virtual RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::~RTree | ( | ) | [virtual] |
bool RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::AddBranch | ( | Branch * | a_branch, |
Node * | a_node, | ||
Node ** | a_newNode | ||
) | [protected] |
ListNode* RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::AllocListNode | ( | ) | [protected] |
Node* RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::AllocNode | ( | ) | [protected] |
ELEMTYPEREAL RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::CalcRectVolume | ( | Rect * | a_rect | ) | [protected] |
void RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::ChoosePartition | ( | PartitionVars * | a_parVars, |
int | a_minFill | ||
) | [protected] |
void RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Classify | ( | int | a_index, |
int | a_group, | ||
PartitionVars * | a_parVars | ||
) | [protected] |
Rect RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::CombineRect | ( | Rect * | a_rectA, |
Rect * | a_rectB | ||
) | [protected] |
int RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Count | ( | ) |
Count the data elements in this container. This is slow as no internal counter is maintained.
void RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::CountRec | ( | Node * | a_node, |
int & | a_count | ||
) | [protected] |
void RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::DisconnectBranch | ( | Node * | a_node, |
int | a_index | ||
) | [protected] |
void RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::FreeListNode | ( | ListNode * | a_listNode | ) | [protected] |
void RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::FreeNode | ( | Node * | a_node | ) | [protected] |
DATATYPE& RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::GetAt | ( | Iterator & | a_it | ) | [inline] |
void RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::GetBranches | ( | Node * | a_node, |
Branch * | a_branch, | ||
PartitionVars * | a_parVars | ||
) | [protected] |
void RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::GetFirst | ( | Iterator & | a_it | ) | [inline] |
void RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::GetNext | ( | Iterator & | a_it | ) | [inline] |
void RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::InitNode | ( | Node * | a_node | ) | [protected] |
void RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::InitParVars | ( | PartitionVars * | a_parVars, |
int | a_maxRects, | ||
int | a_minFill | ||
) | [protected] |
void RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::InitRect | ( | Rect * | a_rect | ) | [protected] |
void RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Insert | ( | const ELEMTYPE | a_min[NUMDIMS], |
const ELEMTYPE | a_max[NUMDIMS], | ||
const DATATYPE & | a_dataId | ||
) |
Insert entry
a_min | Min of bounding rect |
a_max | Max of bounding rect |
a_dataId | Positive Id of data. Maybe zero, but negative numbers not allowed. |
Referenced by GUINet::initGUIStructures().
bool RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::InsertRect | ( | Rect * | a_rect, |
const DATATYPE & | a_id, | ||
Node ** | a_root, | ||
int | a_level | ||
) | [protected] |
bool RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::InsertRectRec | ( | Rect * | a_rect, |
const DATATYPE & | a_id, | ||
Node * | a_node, | ||
Node ** | a_newNode, | ||
int | a_level | ||
) | [protected] |
bool RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::IsNull | ( | Iterator & | a_it | ) | [inline] |
void RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::LoadNodes | ( | Node * | a_nodeA, |
Node * | a_nodeB, | ||
PartitionVars * | a_parVars | ||
) | [protected] |
Rect RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::NodeCover | ( | Node * | a_node | ) | [protected] |
bool RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Overlap | ( | Rect * | a_rectA, |
Rect * | a_rectB | ||
) | [protected] |
int RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::PickBranch | ( | Rect * | a_rect, |
Node * | a_node | ||
) | [protected] |
void RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::PickSeeds | ( | PartitionVars * | a_parVars | ) | [protected] |
float RTree< GUIGlObject *, GUIGlObject, float, 2, GUIVisualizationSettings, float, 8, 4 >::RectSphericalVolume | ( | Rect * | a_rect | ) | [inline, protected] |
ELEMTYPEREAL RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RectSphericalVolume | ( | Rect * | a_rect | ) | [protected] |
ELEMTYPEREAL RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RectVolume | ( | Rect * | a_rect | ) | [protected] |
void RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::ReInsert | ( | Node * | a_node, |
ListNode ** | a_listNode | ||
) | [protected] |
void RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Remove | ( | const ELEMTYPE | a_min[NUMDIMS], |
const ELEMTYPE | a_max[NUMDIMS], | ||
const DATATYPE & | a_dataId | ||
) |
Remove entry
a_min | Min of bounding rect |
a_max | Max of bounding rect |
a_dataId | Positive Id of data. Maybe zero, but negative numbers not allowed. |
void RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RemoveAll | ( | ) |
DK 15.10.2008 - end.
Remove all entries from tree
void RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RemoveAllRec | ( | Node * | a_node | ) | [protected] |
bool RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RemoveRect | ( | Rect * | a_rect, |
const DATATYPE & | a_id, | ||
Node ** | a_root | ||
) | [protected] |
bool RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RemoveRectRec | ( | Rect * | a_rect, |
const DATATYPE & | a_id, | ||
Node * | a_node, | ||
ListNode ** | a_listNode | ||
) | [protected] |
void RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Reset | ( | ) | [protected] |
int RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Search | ( | const ELEMTYPE | a_min[NUMDIMS], |
const ELEMTYPE | a_max[NUMDIMS], | ||
const CONTEXT & | c | ||
) |
DK 15.10.2008 - begin.
Find all within search rectangle
a_min | Min of search bounding rect |
a_max | Max of search bounding rect |
a_searchResult | Search result array. Caller should set grow size. Function will reset, not append to array. |
a_resultCallback | Callback function to return result. Callback should return 'true' to continue searching |
a_context | User context to pass as parameter to a_resultCallback |
Referenced by GUIViewTraffic::doPaintGL(), and GUISUMOAbstractView::makeSnapshot().
bool RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Search | ( | Node * | a_node, |
Rect * | a_rect, | ||
int & | a_foundCount, | ||
const CONTEXT & | c | ||
) | [protected] |
void RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::SplitNode | ( | Node * | a_node, |
Branch * | a_branch, | ||
Node ** | a_newNode | ||
) | [protected] |
Node* RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::m_root [protected] |
Root of tree.
Definition at line 359 of file RTree.h.
Referenced by RTree< GUIGlObject *, GUIGlObject, float, 2, GUIVisualizationSettings >::GetFirst().
ELEMTYPEREAL RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::m_unitSphereVolume [protected] |
Operation RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::myOperation [protected] |