#include <iso_space_rtree.h>
Collaboration diagram for iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >:
Public Types | |
enum | { MAXNODES = TMAXNODES, MINNODES = TMINNODES } |
Public Member Functions | |
RTree (unsigned int pDim) | |
virtual | ~RTree () |
void | Insert (const ELEMTYPE *a_min, const ELEMTYPE *a_max, const DATATYPE &a_dataId) |
void | Remove (const ELEMTYPE *a_min, const ELEMTYPE *a_max, const DATATYPE &a_dataId) |
void | Search (const ELEMTYPE *a_min, const ELEMTYPE *a_max, QVector< DATATYPE > &pSearchResults) |
void | RemoveAll () |
Remove all entries from tree. | |
int | Count () |
Count the data elements in this container. This is slow as no internal counter is maintained. | |
bool | Load (const char *a_fileName) |
Load tree contents from file. | |
bool | Load (RTFileStream &a_stream) |
Load tree contents from stream. | |
bool | Save (const char *a_fileName) |
Save tree contents to file. | |
bool | Save (RTFileStream &a_stream) |
Save tree contents to stream. | |
void | GetFirst (Iterator &a_it) |
Get 'first' for iteration. | |
void | GetNext (Iterator &a_it) |
Get Next for iteration. | |
bool | IsNull (Iterator &a_it) |
Is iterator NULL, or at end? | |
DATATYPE & | GetAt (Iterator &a_it) |
Get object at iterator position. | |
Protected Member Functions | |
Node * | AllocNode () |
void | FreeNode (Node *a_node) |
void | InitNode (Node *a_node) |
void | InitRect (Rect *a_rect) |
bool | InsertRectRec (Rect *a_rect, const DATATYPE &a_id, Node *a_node, Node **a_newNode, int a_level) |
bool | InsertRect (Rect *a_rect, const DATATYPE &a_id, Node **a_root, int a_level) |
Rect | NodeCover (Node *a_node) |
bool | AddBranch (Branch *a_branch, Node *a_node, Node **a_newNode) |
void | DisconnectBranch (Node *a_node, int a_index) |
int | PickBranch (Rect *a_rect, Node *a_node) |
Rect | CombineRect (Rect *a_rectA, Rect *a_rectB) |
void | SplitNode (Node *a_node, Branch *a_branch, Node **a_newNode) |
ELEMTYPEREAL | RectSphericalVolume (Rect *a_rect) |
ELEMTYPEREAL | RectVolume (Rect *a_rect) |
ELEMTYPEREAL | CalcRectVolume (Rect *a_rect) |
void | GetBranches (Node *a_node, Branch *a_branch, PartitionVars *a_parVars) |
void | ChoosePartition (PartitionVars *a_parVars, int a_minFill) |
void | LoadNodes (Node *a_nodeA, Node *a_nodeB, PartitionVars *a_parVars) |
void | InitParVars (PartitionVars *a_parVars, int a_maxRects, int a_minFill) |
void | PickSeeds (PartitionVars *a_parVars) |
void | Classify (int a_index, int a_group, PartitionVars *a_parVars) |
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) |
ListNode * | AllocListNode () |
void | FreeListNode (ListNode *a_listNode) |
bool | Overlap (Rect *a_rectA, Rect *a_rectB) |
void | ReInsert (Node *a_node, ListNode **a_listNode) |
bool | Search (Node *a_node, Rect *a_rect, QVector< DATATYPE > &pSearchResults) |
void | RemoveAllRec (Node *a_node) |
void | Reset () |
void | CountRec (Node *a_node, int &a_count) |
bool | SaveRec (Node *a_node, RTFileStream &a_stream) |
bool | LoadRec (Node *a_node, RTFileStream &a_stream) |
Protected Attributes | |
unsigned int | mDim |
Node * | m_root |
Root of tree. | |
ELEMTYPEREAL | m_unitSphereVolume |
Unit sphere constant for required number of dimensions. | |
Classes | |
class | Branch |
class | Iterator |
Iterator is not remove safe. More... | |
class | ListNode |
A link list of nodes for reinsertion after a delete operation. More... | |
class | Node |
Node for each branch level. More... | |
class | PartitionVars |
Variables for finding a split partition. More... | |
class | Rect |
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 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.
anonymous enum |
iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RTree | ( | unsigned int | pDim | ) |
iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::~RTree | ( | ) | [virtual] |
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Insert | ( | const ELEMTYPE * | a_min, | |
const ELEMTYPE * | a_max, | |||
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. |
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Remove | ( | const ELEMTYPE * | a_min, | |
const ELEMTYPE * | a_max, | |||
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 iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Search | ( | const ELEMTYPE * | a_min, | |
const ELEMTYPE * | a_max, | |||
QVector< DATATYPE > & | pSearchResults | |||
) |
Find all within search rectangle
a_min | Min of search bounding rect | |
a_max | Max of search bounding rect | |
pSearchResults | Search result array. |
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RemoveAll | ( | ) |
Remove all entries from tree.
int iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Count | ( | ) |
Count the data elements in this container. This is slow as no internal counter is maintained.
bool iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Load | ( | const char * | a_fileName | ) |
Load tree contents from file.
bool iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Load | ( | RTFileStream & | a_stream | ) |
Load tree contents from stream.
bool iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Save | ( | const char * | a_fileName | ) |
Save tree contents to file.
bool iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Save | ( | RTFileStream & | a_stream | ) |
Save tree contents to stream.
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::GetFirst | ( | Iterator & | a_it | ) | [inline] |
Get 'first' for iteration.
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::GetNext | ( | Iterator & | a_it | ) | [inline] |
Get Next for iteration.
bool iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::IsNull | ( | Iterator & | a_it | ) | [inline] |
Is iterator NULL, or at end?
DATATYPE& iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::GetAt | ( | Iterator & | a_it | ) | [inline] |
Get object at iterator position.
RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Node * iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::AllocNode | ( | ) | [protected] |
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::FreeNode | ( | Node * | a_node | ) | [protected] |
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::InitNode | ( | Node * | a_node | ) | [protected] |
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::InitRect | ( | Rect * | a_rect | ) | [protected] |
bool iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::InsertRectRec | ( | Rect * | a_rect, | |
const DATATYPE & | a_id, | |||
Node * | a_node, | |||
Node ** | a_newNode, | |||
int | a_level | |||
) | [protected] |
bool iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::InsertRect | ( | Rect * | a_rect, | |
const DATATYPE & | a_id, | |||
Node ** | a_root, | |||
int | a_level | |||
) | [protected] |
RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Rect iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::NodeCover | ( | Node * | a_node | ) | [protected] |
bool iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::AddBranch | ( | Branch * | a_branch, | |
Node * | a_node, | |||
Node ** | a_newNode | |||
) | [protected] |
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::DisconnectBranch | ( | Node * | a_node, | |
int | a_index | |||
) | [protected] |
int iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::PickBranch | ( | Rect * | a_rect, | |
Node * | a_node | |||
) | [protected] |
RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Rect iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::CombineRect | ( | Rect * | a_rectA, | |
Rect * | a_rectB | |||
) | [protected] |
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::SplitNode | ( | Node * | a_node, | |
Branch * | a_branch, | |||
Node ** | a_newNode | |||
) | [protected] |
ELEMTYPEREAL iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RectSphericalVolume | ( | Rect * | a_rect | ) | [protected] |
ELEMTYPEREAL iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RectVolume | ( | Rect * | a_rect | ) | [protected] |
ELEMTYPEREAL iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::CalcRectVolume | ( | Rect * | a_rect | ) | [protected] |
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::GetBranches | ( | Node * | a_node, | |
Branch * | a_branch, | |||
PartitionVars * | a_parVars | |||
) | [protected] |
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::ChoosePartition | ( | PartitionVars * | a_parVars, | |
int | a_minFill | |||
) | [protected] |
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::LoadNodes | ( | Node * | a_nodeA, | |
Node * | a_nodeB, | |||
PartitionVars * | a_parVars | |||
) | [protected] |
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::InitParVars | ( | PartitionVars * | a_parVars, | |
int | a_maxRects, | |||
int | a_minFill | |||
) | [protected] |
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::PickSeeds | ( | PartitionVars * | a_parVars | ) | [protected] |
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Classify | ( | int | a_index, | |
int | a_group, | |||
PartitionVars * | a_parVars | |||
) | [protected] |
bool iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RemoveRect | ( | Rect * | a_rect, | |
const DATATYPE & | a_id, | |||
Node ** | a_root | |||
) | [protected] |
bool iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RemoveRectRec | ( | Rect * | a_rect, | |
const DATATYPE & | a_id, | |||
Node * | a_node, | |||
ListNode ** | a_listNode | |||
) | [protected] |
RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::ListNode * iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::AllocListNode | ( | ) | [protected] |
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::FreeListNode | ( | ListNode * | a_listNode | ) | [protected] |
bool iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Overlap | ( | Rect * | a_rectA, | |
Rect * | a_rectB | |||
) | [protected] |
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::ReInsert | ( | Node * | a_node, | |
ListNode ** | a_listNode | |||
) | [protected] |
bool iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Search | ( | Node * | a_node, | |
Rect * | a_rect, | |||
QVector< DATATYPE > & | pSearchResults | |||
) | [protected] |
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RemoveAllRec | ( | Node * | a_node | ) | [protected] |
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Reset | ( | ) | [protected] |
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::CountRec | ( | Node * | a_node, | |
int & | a_count | |||
) | [protected] |
bool iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::SaveRec | ( | Node * | a_node, | |
RTFileStream & | a_stream | |||
) | [protected] |
bool iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::LoadRec | ( | Node * | a_node, | |
RTFileStream & | a_stream | |||
) | [protected] |
unsigned int iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::mDim [protected] |
Node* iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::m_root [protected] |
Root of tree.
ELEMTYPEREAL iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::m_unitSphereVolume [protected] |
Unit sphere constant for required number of dimensions.