KiCad PCB EDA Suite
RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES > Class Template Reference

Implementation of RTree, a multidimensional bounding rectangle tree. More...

#include <rtree.h>

Inheritance diagram for RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >:
KIGFX::VIEW_RTREE

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

 RTree ()
 
virtual ~RTree ()
 
void Insert (const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE &a_dataId)
 Insert entry. More...
 
void 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. More...
 
void RemoveAll ()
 Remove all entries from tree. More...
 
int Count ()
 Count the data elements in this container. This is slow as no internal counter is maintained. More...
 
bool Load (const char *a_fileName)
 Load tree contents from file. More...
 
bool Load (RTFileStream &a_stream)
 Load tree contents from stream. More...
 
bool Save (const char *a_fileName)
 Save tree contents to file. More...
 
bool Save (RTFileStream &a_stream)
 Save tree contents to stream. More...
 
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. More...
 
void GetNext (Iterator &a_it)
 Get Next for iteration. More...
 
bool IsNull (Iterator &a_it)
 Is iterator NULL, or at end? More...
 
DATATYPE & GetAt (Iterator &a_it)
 Get object at iterator position. More...
 

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. More...
 
ELEMTYPEREAL m_unitSphereVolume
 Unit sphere constant for required number of dimensions. More...
 

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.

Definition at line 79 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 88 of file rtree.h.

88  {
89  MAXNODES = TMAXNODES,
90  MINNODES = TMINNODES,
91  };
Min elements in node.
Definition: rtree.h:90
Max elements in node.
Definition: rtree.h:89

Constructor & Destructor Documentation

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RTree ( )
template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
virtual RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::~RTree ( )
virtual

Member Function Documentation

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 >::AddBranch ( Branch a_branch,
Node a_node,
Node **  a_newNode 
)
protected
template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
ListNode* RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::AllocListNode ( )
protected
template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
Node* RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::AllocNode ( )
protected
template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
ELEMTYPEREAL RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::CalcRectVolume ( Rect a_rect)
protected
template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
Statistics RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::CalcStats ( )

Calculate Statistics.

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 >::ChoosePartition ( PartitionVars a_parVars,
int  a_minFill 
)
protected
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 >::Classify ( int  a_index,
int  a_group,
PartitionVars a_parVars 
)
protected
template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
Rect RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::CombineRect ( Rect a_rectA,
Rect a_rectB 
)
protected
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 >::Count ( )

Count the data elements in this container. This is slow as no internal counter is maintained.

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 >::CountRec ( Node a_node,
int &  a_count 
)
protected
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 >::DisconnectBranch ( Node a_node,
int  a_index 
)
protected
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 >::FreeListNode ( ListNode a_listNode)
protected
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 >::FreeNode ( Node a_node)
protected
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 >::GetAt ( Iterator a_it)
inline

Get object at iterator position.

Definition at line 369 of file rtree.h.

369 { return *a_it; }
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 >::GetBranches ( Node a_node,
Branch a_branch,
PartitionVars a_parVars 
)
protected
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 >::GetFirst ( Iterator a_it)
inline

Get 'first' for iteration.

Definition at line 337 of file rtree.h.

Referenced by SHAPE_INDEX< T >::Iterator::Init().

338  {
339  a_it.Init();
340  Node* first = m_root;
341 
342  while( first )
343  {
344  if( first->IsInternalNode() && first->m_count > 1 )
345  {
346  a_it.Push( first, 1 ); // Descend sibling branch later
347  }
348  else if( first->IsLeaf() )
349  {
350  if( first->m_count )
351  {
352  a_it.Push( first, 0 );
353  }
354 
355  break;
356  }
357 
358  first = first->m_branch[0].m_child;
359  }
360  }
Node * m_root
Root of tree.
Definition: rtree.h:522
Node * m_child
Child node.
Definition: rtree.h:387
Branch m_branch[MAXNODES]
Branch.
Definition: rtree.h:400
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 >::GetNext ( Iterator a_it)
inline

Get Next for iteration.

Definition at line 363 of file rtree.h.

363 { ++a_it; }
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 >::InitNode ( Node a_node)
protected
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 >::InitParVars ( PartitionVars a_parVars,
int  a_maxRects,
int  a_minFill 
)
protected
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 >::InitRect ( Rect a_rect)
protected
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.

Referenced by KIGFX::VIEW_RTREE::Insert(), and SHAPE_INDEX< T >::Reindex().

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 >::InsertNNListSorted ( std::vector< NNNode * > *  nodeList,
NNNode newNode 
)
protected
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 >::InsertRect ( Rect a_rect,
const DATATYPE &  a_id,
Node **  a_root,
int  a_level 
)
protected
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 >::InsertRectRec ( Rect a_rect,
const DATATYPE &  a_id,
Node a_node,
Node **  a_newNode,
int  a_level 
)
protected
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 >::IsNull ( Iterator a_it)
inline

Is iterator NULL, or at end?

Definition at line 366 of file rtree.h.

Referenced by SHAPE_INDEX< T >::Reindex().

366 { return a_it.IsNull(); }
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 >::Load ( const char *  a_fileName)

Load tree contents from file.

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 >::Load ( RTFileStream a_stream)

Load tree contents from stream.

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 >::LoadNodes ( Node a_nodeA,
Node a_nodeB,
PartitionVars a_parVars 
)
protected
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 >::LoadRec ( Node a_node,
RTFileStream a_stream 
)
protected
template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
ELEMTYPE RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::MinDist ( const ELEMTYPE  a_point[NUMDIMS],
Rect a_rect 
)
protected
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.
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.
template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
Rect RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::NodeCover ( Node a_node)
protected
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 >::Overlap ( Rect a_rectA,
Rect a_rectB 
)
protected
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 >::PickBranch ( Rect a_rect,
Node a_node 
)
protected
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 >::PickSeeds ( PartitionVars a_parVars)
protected
template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
ELEMTYPEREAL RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RectSphericalVolume ( Rect a_rect)
protected
template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
ELEMTYPEREAL RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RectVolume ( Rect a_rect)
protected
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 >::ReInsert ( Node a_node,
ListNode **  a_listNode 
)
protected
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 >::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.

Referenced by KIGFX::VIEW_RTREE::Remove().

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 >::RemoveAll ( )

Remove all entries from tree.

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 >::RemoveAllRec ( Node a_node)
protected
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 >::RemoveRect ( Rect a_rect,
const DATATYPE &  a_id,
Node **  a_root 
)
protected
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 >::RemoveRectRec ( Rect a_rect,
const DATATYPE &  a_id,
Node a_node,
ListNode **  a_listNode 
)
protected
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 >::Reset ( )
protected
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 >::Save ( const char *  a_fileName)

Save tree contents to file.

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 >::Save ( RTFileStream a_stream)

Save tree contents to stream.

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 >::SaveRec ( Node a_node,
RTFileStream a_stream 
)
protected
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

Referenced by KIGFX::VIEW_RTREE::Query(), SHAPE_INDEX< T >::Query(), and RTree< T, int, 2, float >::Search().

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
template<class VISITOR >
int RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Search ( const ELEMTYPE  a_min[NUMDIMS],
const ELEMTYPE  a_max[NUMDIMS],
VISITOR &  a_visitor 
)
inline

Definition at line 135 of file rtree.h.

136  {
137  #ifdef _DEBUG
138 
139  for( int index = 0; index<NUMDIMS; ++index )
140  {
141  ASSERT( a_min[index] <= a_max[index] );
142  }
143 
144  #endif // _DEBUG
145 
146  Rect rect;
147 
148  for( int axis = 0; axis<NUMDIMS; ++axis )
149  {
150  rect.m_min[axis] = a_min[axis];
151  rect.m_max[axis] = a_max[axis];
152  }
153 
154 
155  // NOTE: May want to return search result another way, perhaps returning the number of found elements here.
156  int cnt;
157 
158  Search( m_root, &rect, a_visitor, cnt );
159 
160  return cnt;
161  }
Node * m_root
Root of tree.
Definition: rtree.h:522
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.
#define ASSERT
Definition: rtree.h:33
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 >::Search ( Node a_node,
Rect a_rect,
int &  a_foundCount,
bool   a_resultCallbackDATATYPE a_data, void *a_context,
void *  a_context 
)
protected
template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
template<class VISITOR >
bool RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Search ( Node a_node,
Rect a_rect,
VISITOR &  a_visitor,
int &  a_foundCount 
)
inlineprotected

Definition at line 477 of file rtree.h.

478  {
479  ASSERT( a_node );
480  ASSERT( a_node->m_level >= 0 );
481  ASSERT( a_rect );
482 
483  if( a_node->IsInternalNode() ) // This is an internal node in the tree
484  {
485  for( int index = 0; index < a_node->m_count; ++index )
486  {
487  if( Overlap( a_rect, &a_node->m_branch[index].m_rect ) )
488  {
489  if( !Search( a_node->m_branch[index].m_child, a_rect, a_visitor, a_foundCount ) )
490  {
491  return false; // Don't continue searching
492  }
493  }
494  }
495  }
496  else // This is a leaf node
497  {
498  for( int index = 0; index < a_node->m_count; ++index )
499  {
500  if( Overlap( a_rect, &a_node->m_branch[index].m_rect ) )
501  {
502  DATATYPE& id = a_node->m_branch[index].m_data;
503 
504  if( !a_visitor( id ) )
505  return false;
506 
507  a_foundCount++;
508  }
509  }
510  }
511 
512  return true; // Continue searching
513  }
bool Overlap(Rect *a_rectA, Rect *a_rectB)
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.
#define ASSERT
Definition: rtree.h:33
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 >::SplitNode ( Node a_node,
Branch a_branch,
Node **  a_newNode 
)
protected

Member Data Documentation

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

Root of tree.

Definition at line 522 of file rtree.h.

Referenced by RTree< T, int, 2, float >::GetFirst(), and RTree< T, int, 2, float >::Search().

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
ELEMTYPEREAL RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::m_unitSphereVolume
protected

Unit sphere constant for required number of dimensions.

Definition at line 523 of file rtree.h.


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