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) |
template<class DATATYPE, class DATATYPENP, class ELEMTYPE, int NUMDIMS, class CONTEXT, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
class RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >
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.
Definition at line 61 of file RTree.h.
template<class DATATYPE, class DATATYPENP, class ELEMTYPE, int NUMDIMS, class CONTEXT, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
DATATYPE& RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::GetAt |
( |
Iterator & |
a_it | ) |
|
|
inline |
Get object at iterator position.
Definition at line 263 of file RTree.h.
template<class DATATYPE, class DATATYPENP, class ELEMTYPE, int NUMDIMS, class CONTEXT, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
void RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::GetFirst |
( |
Iterator & |
a_it | ) |
|
|
inline |
Get 'first' for iteration.
Definition at line 246 of file RTree.h.
template<class DATATYPE, class DATATYPENP, class ELEMTYPE, int NUMDIMS, class CONTEXT, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
bool RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::IsNull |
( |
Iterator & |
a_it | ) |
|
|
inline |
Is iterator NULL, or at end?
Definition at line 260 of file RTree.h.
template<class DATATYPE, class DATATYPENP, class ELEMTYPE, int NUMDIMS, class CONTEXT, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
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
- Parameters:
-
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 |
- Returns:
- Returns the number of entries found
Referenced by GUIViewTraffic::doPaintGL(), and GUISUMOAbstractView::makeSnapshot().
template<class DATATYPE, class DATATYPENP, class ELEMTYPE, int NUMDIMS, class CONTEXT, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
ELEMTYPEREAL RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::m_unitSphereVolume |
|
protected |
Unit sphere constant for required number of dimensions.
Definition at line 360 of file RTree.h.