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

◆ CN_RTREE()

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

◆ ~CN_RTREE()

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

◆ Insert()

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.

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 GetX() const
Definition: box2.h:188
coord_type GetRight() const
Definition: box2.h:197
coord_type GetBottom() const
Definition: box2.h:198
RTree< T, int, 3, double > * m_tree
int Start() const
Definition: pns_layerset.h:83
int End() const
Definition: pns_layerset.h:88
void Insert(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE &a_dataId)
Insert entry.
coord_type GetY() const
Definition: box2.h:189
Class LAYER_RANGE.
Definition: pns_layerset.h:32

Referenced by CN_LIST::addItemtoTree().

◆ Query()

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.

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 GetX() const
Definition: box2.h:188
coord_type GetRight() const
Definition: box2.h:197
coord_type GetBottom() const
Definition: box2.h:198
RTree< T, int, 3, double > * m_tree
int Start() const
Definition: pns_layerset.h:83
int End() const
Definition: pns_layerset.h:88
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.
coord_type GetY() const
Definition: box2.h:189

Referenced by CN_LIST::FindNearby().

◆ Remove()

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 GetX() const
Definition: box2.h:188
coord_type GetRight() const
Definition: box2.h:197
coord_type GetBottom() const
Definition: box2.h:198
RTree< T, int, 3, double > * m_tree
int Start() const
Definition: pns_layerset.h:83
int End() const
Definition: pns_layerset.h:88
coord_type GetY() const
Definition: box2.h:189
Class LAYER_RANGE.
Definition: pns_layerset.h:32

Referenced by CN_LIST::RemoveInvalidItems().

◆ RemoveAll()

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.

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

Referenced by CN_LIST::Clear().

Member Data Documentation

◆ m_tree


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