Horizon
Classes | Public Types | Public Member Functions | Protected Member Functions | Protected Attributes | List of all members
RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES > Class Template Reference

#include <rtree.h>

Classes

struct  Branch
 May be data or may be another subtree The parents level determines this. More...
 
class  Iterator
 Iterator is not remove safe. More...
 
struct  ListNode
 A link list of nodes for reinsertion after a delete operation. More...
 
struct  NNNode
 Data structure used for Nearest Neighbor search implementation. 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...
 
struct  Statistics
 

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)
 Insert entry. More...
 
bool Remove (const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE &a_dataId)
 Remove entry. More...
 
int Search (const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], bool a_resultCallback(DATATYPE a_data, void *a_context), void *a_context)
 Find all within search rectangle. More...
 
template<class VISITOR >
int Search (const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], VISITOR &a_visitor)
 
Statistics CalcStats ()
 Calculate Statistics.
 
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.
 
DATATYPE NearestNeighbor (const ELEMTYPE a_point[NUMDIMS])
 Find the nearest neighbor of a specific point. More...
 
DATATYPE NearestNeighbor (const ELEMTYPE a_point[NUMDIMS], ELEMTYPE a_squareDistanceCallback(const ELEMTYPE a_point[NUMDIMS], DATATYPE a_data), ELEMTYPE *a_squareDistance)
 Find the nearest neighbor of a specific point. More...
 
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)
 
ELEMTYPE MinDist (const ELEMTYPE a_point[NUMDIMS], Rect *a_rect)
 
void InsertNNListSorted (std::vector< NNNode * > *nodeList, NNNode *newNode)
 
bool Search (Node *a_node, Rect *a_rect, int &a_foundCount, bool a_resultCallback(DATATYPE a_data, void *a_context), void *a_context)
 
template<class VISITOR >
bool Search (Node *a_node, Rect *a_rect, VISITOR &a_visitor, int &a_foundCount)
 
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

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

Member Enumeration Documentation

◆ anonymous enum

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.

Member Function Documentation

◆ Insert()

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
void 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.

◆ NearestNeighbor() [1/2]

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
DATATYPE RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::NearestNeighbor ( const ELEMTYPE  a_point[NUMDIMS])

Find the nearest neighbor of a specific point.

It uses the MINDIST method, simplifying the one from "R-Trees: Theory and Applications" by Yannis Manolopoulos et al. The bounding rectangle is used to calculate the distance to the DATATYPE.

Parameters
a_pointpoint to start the search
Returns
Returns the DATATYPE located closest to a_point, 0 if the tree is empty.

◆ NearestNeighbor() [2/2]

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
DATATYPE RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::NearestNeighbor ( const ELEMTYPE  a_point[NUMDIMS],
ELEMTYPE   a_squareDistanceCallbackconst ELEMTYPE a_point[NUMDIMS], DATATYPE a_data,
ELEMTYPE *  a_squareDistance 
)

Find the nearest neighbor of a specific point.

It uses the MINDIST method, simplifying the one from "R-Trees: Theory and Applications" by Yannis Manolopoulos et al. It receives a callback function to calculate the distance to a DATATYPE object, instead of using the bounding rectangle.

Parameters
a_pointpoint to start the search
a_squareDistanceCallbackfunction that performs the square distance calculation for the selected DATATYPE.
a_squareDistancePointer in which the square distance to the nearest neighbour will be returned.
Returns
Returns the DATATYPE located closest to a_point, 0 if the tree is empty.

◆ Remove()

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
bool 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.
Returns
1 if record not found, 0 if success.

◆ Search()

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
int RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Search ( const ELEMTYPE  a_min[NUMDIMS],
const ELEMTYPE  a_max[NUMDIMS],
bool   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_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: