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...
 
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], std::function< bool(const DATATYPE &)> a_callback) const
 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) const
 
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, std::function< bool(const DATATYPE &)> a_callback) const
 
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 76 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 85 of file rtree.h.

85  {
86  MAXNODES = TMAXNODES,
87  MINNODES = TMINNODES,
88  };
Min elements in node.
Definition: rtree.h:87
Max elements in node.
Definition: rtree.h:86

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

Referenced by RTFileStream::ReadArray().

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

Referenced by RTFileStream::ReadArray().

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

Referenced by RTFileStream::ReadArray().

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

Referenced by RTFileStream::ReadArray().

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

Referenced by RTFileStream::ReadArray().

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

Referenced by RTFileStream::ReadArray().

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

Referenced by RTFileStream::ReadArray().

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.

Referenced by RTree< T, int, 2, double >::Search().

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

Referenced by RTFileStream::ReadArray().

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

Referenced by RTFileStream::ReadArray().

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

Referenced by RTFileStream::ReadArray().

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 365 of file rtree.h.

365 { 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

Referenced by RTFileStream::ReadArray().

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 333 of file rtree.h.

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

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

359 { ++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

Referenced by RTFileStream::ReadArray().

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

Referenced by RTFileStream::ReadArray().

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

Referenced by RTFileStream::ReadArray().

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 SHAPE_INDEX< T >::Add(), KIGFX::VIEW_RTREE::Insert(), CN_RTREE< CN_ITEM * >::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

Referenced by RTFileStream::ReadArray().

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

Referenced by RTFileStream::ReadArray().

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

Referenced by RTFileStream::ReadArray().

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 362 of file rtree.h.

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

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

Referenced by RTFileStream::ReadArray(), and RTree< T, int, 2, double >::Search().

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

Referenced by RTFileStream::ReadArray().

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

Referenced by RTFileStream::ReadArray().

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.

Referenced by RTFileStream::ReadArray(), and RTree< T, int, 2, double >::Search().

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

Referenced by RTFileStream::ReadArray().

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 
) const
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

Referenced by RTFileStream::ReadArray().

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

Referenced by RTFileStream::ReadArray().

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

Referenced by RTFileStream::ReadArray().

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

Referenced by RTFileStream::ReadArray().

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

Referenced by RTFileStream::ReadArray().

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.

Referenced by KIGFX::VIEW_RTREE::Remove(), CN_RTREE< CN_ITEM * >::Remove(), and SHAPE_INDEX< T >::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 ( )
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

Referenced by RTFileStream::ReadArray().

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

Referenced by RTFileStream::ReadArray().

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.

Referenced by RTFileStream::ReadArray(), and RTree< T, int, 2, double >::Search().

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],
std::function< bool(const DATATYPE &)>  a_callback 
) const

Find all within search rectangle.

Parameters
a_minMin of search bounding rect
a_maxMax of search bounding rect
a_callbackCallback function to return result. Callback should return 'true' to continue searching
Returns
Returns the number of entries found

Referenced by KIGFX::VIEW_RTREE::Query(), CN_RTREE< CN_ITEM * >::Query(), SHAPE_INDEX< T >::Query(), RTFileStream::ReadArray(), and RTree< T, int, 2, double >::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 131 of file rtree.h.

132  {
133  #ifdef _DEBUG
134 
135  for( int index = 0; index<NUMDIMS; ++index )
136  {
137  ASSERT( a_min[index] <= a_max[index] );
138  }
139 
140  #endif // _DEBUG
141 
142  Rect rect;
143 
144  for( int axis = 0; axis<NUMDIMS; ++axis )
145  {
146  rect.m_min[axis] = a_min[axis];
147  rect.m_max[axis] = a_max[axis];
148  }
149 
150 
151  // NOTE: May want to return search result another way, perhaps returning the number of found elements here.
152  int cnt = 0;
153 
154  Search( m_root, &rect, a_visitor, cnt );
155 
156  return cnt;
157  }
Node * m_root
Root of tree.
Definition: rtree.h:517
int Search(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], std::function< bool(const DATATYPE &)> a_callback) const
Find all within search rectangle.
#define ASSERT
Definition: rtree.h:36
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,
std::function< bool(const DATATYPE &)>  a_callback 
) const
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 472 of file rtree.h.

473  {
474  ASSERT( a_node );
475  ASSERT( a_node->m_level >= 0 );
476  ASSERT( a_rect );
477 
478  if( a_node->IsInternalNode() ) // This is an internal node in the tree
479  {
480  for( int index = 0; index < a_node->m_count; ++index )
481  {
482  if( Overlap( a_rect, &a_node->m_branch[index].m_rect ) )
483  {
484  if( !Search( a_node->m_branch[index].m_child, a_rect, a_visitor, a_foundCount ) )
485  {
486  return false; // Don't continue searching
487  }
488  }
489  }
490  }
491  else // This is a leaf node
492  {
493  for( int index = 0; index < a_node->m_count; ++index )
494  {
495  if( Overlap( a_rect, &a_node->m_branch[index].m_rect ) )
496  {
497  DATATYPE& id = a_node->m_branch[index].m_data;
498 
499  if( !a_visitor( id ) )
500  return false;
501 
502  a_foundCount++;
503  }
504  }
505  }
506 
507  return true; // Continue searching
508  }
bool Overlap(Rect *a_rectA, Rect *a_rectB) const
int Search(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], std::function< bool(const DATATYPE &)> a_callback) const
Find all within search rectangle.
#define ASSERT
Definition: rtree.h:36
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

Referenced by RTFileStream::ReadArray().

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
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 518 of file rtree.h.

Referenced by RTFileStream::ReadArray().


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