KiCad PCB EDA Suite
CN_RTREE< T > Class Template Reference

Class CN_RTREE - Implements an R-tree for fast spatial indexing of connectivity items. More...

#include <connectivity_rtree.h>

Public Member Functions

 CN_RTREE ()
 
 ~CN_RTREE ()
 
void Insert (T aItem)
 Function Insert() Inserts an item into the tree. More...
 
void Remove (T aItem)
 Function Remove() Removes an item from the tree. More...
 
void RemoveAll ()
 Function RemoveAll() Removes all items from the RTree. More...
 
template<class Visitor >
void Query (const BOX2I &aBounds, const LAYER_RANGE &aRange, Visitor &aVisitor)
 Function Query() Executes a function object aVisitor for each item whose bounding box intersects with aBounds. More...
 

Private Attributes

RTree< T, int, 3, double > * m_tree
 

Detailed Description

template<class T>
class CN_RTREE< T >

Class CN_RTREE - Implements an R-tree for fast spatial indexing of connectivity items.

Non-owning.

Definition at line 39 of file connectivity_rtree.h.

Constructor & Destructor Documentation

template<class T>
CN_RTREE< T >::CN_RTREE ( )
inline

Definition at line 43 of file connectivity_rtree.h.

44  {
45  this->m_tree = new RTree<T, int, 3, double>();
46  }
RTree< T, int, 3, double > * m_tree
template<class T>
CN_RTREE< T >::~CN_RTREE ( )
inline

Definition at line 48 of file connectivity_rtree.h.

49  {
50  delete this->m_tree;
51  }
RTree< T, int, 3, double > * m_tree

Member Function Documentation

template<class T>
void CN_RTREE< T >::Insert ( aItem)
inline

Function Insert() Inserts an item into the tree.

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

Definition at line 57 of file connectivity_rtree.h.

Referenced by CN_LIST::addItemtoTree().

58  {
59  const BOX2I& bbox = aItem->BBox();
60  const LAYER_RANGE layers = aItem->Layers();
61 
62  const int mmin[3] = { layers.Start(), bbox.GetX(), bbox.GetY() };
63  const int mmax[3] = { layers.End(), bbox.GetRight(), bbox.GetBottom() };
64 
65  m_tree->Insert( mmin, mmax, aItem );
66  }
coord_type GetY() const
Definition: box2.h:189
coord_type GetRight() const
Definition: box2.h:197
RTree< T, int, 3, double > * m_tree
int End() const
Definition: pns_layerset.h:88
coord_type GetBottom() const
Definition: box2.h:198
int Start() const
Definition: pns_layerset.h:83
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:188
Class LAYER_RANGE.
Definition: pns_layerset.h:32
template<class T>
template<class Visitor >
void CN_RTREE< T >::Query ( const BOX2I aBounds,
const LAYER_RANGE aRange,
Visitor &  aVisitor 
)
inline

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

Definition at line 110 of file connectivity_rtree.h.

Referenced by CN_LIST::FindNearby().

111  {
112  const int mmin[3] = { aRange.Start(), aBounds.GetX(), aBounds.GetY() };
113  const int mmax[3] = { aRange.End(), aBounds.GetRight(), aBounds.GetBottom() };
114 
115  m_tree->Search( mmin, mmax, aVisitor );
116  }
coord_type GetY() const
Definition: box2.h:189
coord_type GetRight() const
Definition: box2.h:197
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.
RTree< T, int, 3, double > * m_tree
int End() const
Definition: pns_layerset.h:88
coord_type GetBottom() const
Definition: box2.h:198
int Start() const
Definition: pns_layerset.h:83
coord_type GetX() const
Definition: box2.h:188
template<class T>
void CN_RTREE< T >::Remove ( aItem)
inline

Function Remove() Removes an item from the tree.

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

Definition at line 73 of file connectivity_rtree.h.

74  {
75 
76  // First, attempt to remove the item using its given BBox
77  const BOX2I& bbox = aItem->BBox();
78  const LAYER_RANGE layers = aItem->Layers();
79  const int mmin[3] = { layers.Start(), bbox.GetX(), bbox.GetY() };
80  const int mmax[3] = { layers.End(), bbox.GetRight(), bbox.GetBottom() };
81 
82  // If we are not successful ( 1 == not found ), then we expand
83  // the search to the full tree
84  if( m_tree->Remove( mmin, mmax, aItem ) )
85  {
86  // N.B. We must search the whole tree for the pointer to remove
87  // because the item may have been moved before we have the chance to
88  // delete it from the tree
89  const int mmin2[3] = { INT_MIN, INT_MIN, INT_MIN };
90  const int mmax2[3] = { INT_MAX, INT_MAX, INT_MAX };
91  m_tree->Remove( mmin2, mmax2, aItem );
92  }
93  }
bool Remove(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE &a_dataId)
Remove entry.
coord_type GetY() const
Definition: box2.h:189
coord_type GetRight() const
Definition: box2.h:197
RTree< T, int, 3, double > * m_tree
int End() const
Definition: pns_layerset.h:88
coord_type GetBottom() const
Definition: box2.h:198
int Start() const
Definition: pns_layerset.h:83
coord_type GetX() const
Definition: box2.h:188
Class LAYER_RANGE.
Definition: pns_layerset.h:32
template<class T>
void CN_RTREE< T >::RemoveAll ( )
inline

Function RemoveAll() Removes all items from the RTree.

Definition at line 99 of file connectivity_rtree.h.

Referenced by CN_LIST::Clear().

100  {
101  m_tree->RemoveAll();
102  }
void RemoveAll()
Remove all entries from tree.
RTree< T, int, 3, double > * m_tree

Member Data Documentation


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