iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES > Class Template Reference

#include <iso_space_rtree.h>

Collaboration diagram for iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >:

Collaboration graph
[legend]
List of all members.

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

NodeAllocNode ()
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)
ListNodeAllocListNode ()
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
Nodem_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

Detailed Description

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
class iso::space::RTree< DATATYPE, ELEMTYPE, 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 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.


Member Enumeration Documentation

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
anonymous enum

Enumerator:
MAXNODES  Max elements in node.
MINNODES  Min elements in node.


Constructor & Destructor Documentation

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RTree ( unsigned int  pDim  ) 

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::~RTree (  )  [virtual]


Member Function Documentation

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Insert ( const ELEMTYPE *  a_min,
const ELEMTYPE *  a_max,
const DATATYPE &  a_dataId 
)

Insert entry

Parameters:
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.

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Remove ( const ELEMTYPE *  a_min,
const ELEMTYPE *  a_max,
const DATATYPE &  a_dataId 
)

Remove entry

Parameters:
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.

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
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

Parameters:
a_min Min of search bounding rect
a_max Max of search bounding rect
pSearchResults Search result array.

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RemoveAll (  ) 

Remove all entries from tree.

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
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.

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
bool iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Load ( const char *  a_fileName  ) 

Load tree contents from file.

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
bool iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Load ( RTFileStream a_stream  ) 

Load tree contents from stream.

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
bool iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Save ( const char *  a_fileName  ) 

Save tree contents to file.

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
bool iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Save ( RTFileStream a_stream  ) 

Save tree contents to stream.

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::GetFirst ( Iterator a_it  )  [inline]

Get 'first' for iteration.

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::GetNext ( Iterator a_it  )  [inline]

Get Next for iteration.

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
bool iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::IsNull ( Iterator a_it  )  [inline]

Is iterator NULL, or at end?

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
DATATYPE& iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::GetAt ( Iterator a_it  )  [inline]

Get object at iterator position.

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Node * iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::AllocNode (  )  [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::FreeNode ( Node a_node  )  [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::InitNode ( Node a_node  )  [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::InitRect ( Rect a_rect  )  [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
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]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
bool iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::InsertRect ( Rect a_rect,
const DATATYPE &  a_id,
Node **  a_root,
int  a_level 
) [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Rect iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::NodeCover ( Node a_node  )  [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
bool iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::AddBranch ( Branch a_branch,
Node a_node,
Node **  a_newNode 
) [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::DisconnectBranch ( Node a_node,
int  a_index 
) [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
int iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::PickBranch ( Rect a_rect,
Node a_node 
) [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Rect iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::CombineRect ( Rect a_rectA,
Rect a_rectB 
) [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::SplitNode ( Node a_node,
Branch a_branch,
Node **  a_newNode 
) [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
ELEMTYPEREAL iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RectSphericalVolume ( Rect a_rect  )  [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
ELEMTYPEREAL iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RectVolume ( Rect a_rect  )  [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
ELEMTYPEREAL iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::CalcRectVolume ( Rect a_rect  )  [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::GetBranches ( Node a_node,
Branch a_branch,
PartitionVars a_parVars 
) [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::ChoosePartition ( PartitionVars a_parVars,
int  a_minFill 
) [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::LoadNodes ( Node a_nodeA,
Node a_nodeB,
PartitionVars a_parVars 
) [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::InitParVars ( PartitionVars a_parVars,
int  a_maxRects,
int  a_minFill 
) [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::PickSeeds ( PartitionVars a_parVars  )  [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Classify ( int  a_index,
int  a_group,
PartitionVars a_parVars 
) [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
bool iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RemoveRect ( Rect a_rect,
const DATATYPE &  a_id,
Node **  a_root 
) [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
bool iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RemoveRectRec ( Rect a_rect,
const DATATYPE &  a_id,
Node a_node,
ListNode **  a_listNode 
) [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::ListNode * iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::AllocListNode (  )  [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::FreeListNode ( ListNode a_listNode  )  [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
bool iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Overlap ( Rect a_rectA,
Rect a_rectB 
) [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::ReInsert ( Node a_node,
ListNode **  a_listNode 
) [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
bool iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Search ( Node a_node,
Rect a_rect,
QVector< DATATYPE > &  pSearchResults 
) [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RemoveAllRec ( Node a_node  )  [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Reset (  )  [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
void iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::CountRec ( Node a_node,
int &  a_count 
) [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
bool iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::SaveRec ( Node a_node,
RTFileStream a_stream 
) [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
bool iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::LoadRec ( Node a_node,
RTFileStream a_stream 
) [protected]


Member Data Documentation

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
unsigned int iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::mDim [protected]

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
Node* iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::m_root [protected]

Root of tree.

template<class DATATYPE, class ELEMTYPE, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
ELEMTYPEREAL iso::space::RTree< DATATYPE, ELEMTYPE, ELEMTYPEREAL, TMAXNODES, TMINNODES >::m_unitSphereVolume [protected]

Unit sphere constant for required number of dimensions.


The documentation for this class was generated from the following file:
Generated on Fri Feb 25 14:08:15 2011 for iso_space by  doxygen 1.5.1