VoxelFarm::RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES > Class Template Reference

#include <RTree.h>

Classes

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 }
 

Public Member Functions

void Insert (const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE &a_dataId)
 
void Remove (const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE &a_dataId)
 
int Search (const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], bool __cdecl a_resultCallback(DATATYPE a_data, void *a_context), void *a_context)
 
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.
 
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, int &a_foundCount, bool __cdecl a_resultCallback(DATATYPE a_data, void *a_context), void *a_context)
 
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)
 

Public Attributes

Nodem_root
 Root of tree.
 
ELEMTYPEREAL m_unitSphereVolume
 Unit sphere constant for required number of dimensions.
 

Detailed Description

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
class VoxelFarm::RTree< DATATYPE, ELEMTYPE, NUMDIMS, 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 49 of file RTree.h.

Member Enumeration Documentation

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

Max elements in node.

MINNODES 

Min elements in node.

Definition at line 59 of file RTree.h.

Member Function Documentation

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
void VoxelFarm::RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Insert ( const ELEMTYPE  a_min[NUMDIMS],
const ELEMTYPE  a_max[NUMDIMS],
const DATATYPE &  a_dataId 
)

Insert entry

Parameters
a_minMin of bounding rect
a_maxMax of bounding rect
a_dataIdPositive Id of data. Maybe zero, but negative numbers not allowed.
template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
void VoxelFarm::RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Remove ( const ELEMTYPE  a_min[NUMDIMS],
const ELEMTYPE  a_max[NUMDIMS],
const DATATYPE &  a_dataId 
)

Remove entry

Parameters
a_minMin of bounding rect
a_maxMax of bounding rect
a_dataIdPositive Id of data. Maybe zero, but negative numbers not allowed.
template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
int VoxelFarm::RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Search ( const ELEMTYPE  a_min[NUMDIMS],
const ELEMTYPE  a_max[NUMDIMS],
bool __cdecl   a_resultCallbackDATATYPE a_data, void *a_context,
void *  a_context 
)

Find all within search rectangle

Parameters
a_minMin of search bounding rect
a_maxMax of search bounding rect
a_searchResultSearch result array. Caller should set grow size. Function will reset, not append to array.
a_resultCallbackCallback function to return result. Callback should return 'true' to continue searching
a_contextUser context to pass as parameter to a_resultCallback
Returns
Returns the number of entries found

The documentation for this class was generated from the following file: