|
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) |
|
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>
virtual int RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Search |
( |
const ELEMTYPE |
a_min[NUMDIMS], |
|
|
const ELEMTYPE |
a_max[NUMDIMS], |
|
|
const CONTEXT & |
c |
|
) |
| |
|
virtual |
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 TraCIRTree::Search(), and SUMORTree::Search().
template<class DATATYPE, class DATATYPENP, class ELEMTYPE, int NUMDIMS, class CONTEXT, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
Node* RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::m_root |
|
protected |
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.