KiCad PCB EDA Suite
KIGFX::VIEW_RTREE Class Reference

Class VIEW_RTREE - Implements an R-tree for fast spatial indexing of VIEW items. More...

#include <view_rtree.h>

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

Public Types

enum  { MAXNODES = TMAXNODES, MINNODES = TMINNODES }
 

Public Member Functions

void Insert (VIEW_ITEM *aItem)
 Function Insert() Inserts an item into the tree. More...
 
void Remove (VIEW_ITEM *aItem)
 Function Remove() Removes an item from the tree. More...
 
template<class Visitor >
void Query (const BOX2I &aBounds, Visitor &aVisitor)
 Function Query() Executes a function object aVisitor for each item whose bounding box intersects with aBounds. More...
 
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

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

Class VIEW_RTREE - Implements an R-tree for fast spatial indexing of VIEW items.

Non-owning.

Definition at line 41 of file view_rtree.h.

Member Enumeration Documentation

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

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

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

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 
)
protectedinherited
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 
)
protectedinherited
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)
protectedinherited
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)
protectedinherited
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)
inlineinherited

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 
)
protectedinherited
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)
inlineinherited

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

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)
protectedinherited
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 
)
protectedinherited
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)
protectedinherited
void KIGFX::VIEW_RTREE::Insert ( VIEW_ITEM aItem)
inline

Function Insert() Inserts an item into the tree.

Item's bounding box is taken via its ViewBBox() method.

Definition at line 49 of file view_rtree.h.

References BOX2< Vec >::GetBottom(), BOX2< Vec >::GetRight(), BOX2< Vec >::GetX(), BOX2< Vec >::GetY(), RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Insert(), and KIGFX::VIEW_ITEM::ViewBBox().

Referenced by KIGFX::VIEW::Add(), KIGFX::VIEW::updateBbox(), and KIGFX::VIEW::updateLayers().

50  {
51  const BOX2I& bbox = aItem->ViewBBox();
52  const int mmin[2] = { bbox.GetX(), bbox.GetY() };
53  const int mmax[2] = { bbox.GetRight(), bbox.GetBottom() };
54 
55  VIEW_RTREE_BASE::Insert( mmin, mmax, aItem );
56  }
coord_type GetY() const
Definition: box2.h:179
coord_type GetRight() const
Definition: box2.h:187
coord_type GetBottom() const
Definition: box2.h:188
void Insert(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE &a_dataId)
Insert entry.
coord_type GetX() const
Definition: box2.h:178
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 
)
inherited

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 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 
)
protectedinherited
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 
)
protectedinherited
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 
)
protectedinherited
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)
inlineinherited

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

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

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 
)
protectedinherited
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 
)
protectedinherited
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 
)
protectedinherited
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])
inherited

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

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)
protectedinherited
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 
)
protectedinherited
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 
)
protectedinherited
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)
protectedinherited
template<class Visitor >
void KIGFX::VIEW_RTREE::Query ( const BOX2I aBounds,
Visitor &  aVisitor 
)
inline

Function Query() Executes a function object aVisitor for each item whose bounding box intersects with aBounds.

Definition at line 80 of file view_rtree.h.

References BOX2< Vec >::GetBottom(), BOX2< Vec >::GetRight(), BOX2< Vec >::GetX(), BOX2< Vec >::GetY(), and RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Search().

Referenced by KIGFX::VIEW::clearGroupCache(), KIGFX::VIEW::RecacheAllItems(), and KIGFX::VIEW::UpdateAllLayersColor().

81  {
82  const int mmin[2] = { aBounds.GetX(), aBounds.GetY() };
83  const int mmax[2] = { aBounds.GetRight(), aBounds.GetBottom() };
84 
85  VIEW_RTREE_BASE::Search( mmin, mmax, aVisitor );
86  }
coord_type GetY() const
Definition: box2.h:179
coord_type GetRight() const
Definition: box2.h:187
coord_type GetBottom() const
Definition: box2.h:188
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.
coord_type GetX() const
Definition: box2.h:178
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)
protectedinherited
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)
protectedinherited
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 
)
protectedinherited
void KIGFX::VIEW_RTREE::Remove ( VIEW_ITEM aItem)
inline

Function Remove() Removes an item from the tree.

Removal is done by comparing pointers, attepmting to remove a copy of the item will fail.

Definition at line 63 of file view_rtree.h.

References RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Remove().

Referenced by KIGFX::VIEW::Remove(), KIGFX::VIEW::updateBbox(), and KIGFX::VIEW::updateLayers().

64  {
65  // const BOX2I& bbox = aItem->ViewBBox();
66 
67  // FIXME: use cached bbox or ptr_map to speed up pointer <-> node lookups.
68  const int mmin[2] = { INT_MIN, INT_MIN };
69  const int mmax[2] = { INT_MAX, INT_MAX };
70 
71  VIEW_RTREE_BASE::Remove( mmin, mmax, aItem );
72  }
void Remove(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE &a_dataId)
Remove entry.
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 
)
inherited

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

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

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

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 
)
protectedinherited
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 
)
inherited

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

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 
)
protectedinherited
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 
)
inlineprotectedinherited

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

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
protectedinherited

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
protectedinherited

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: