KiCad PCB EDA Suite
connectivity_rtree.h
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2018 KiCad Developers, see AUTHORS.txt for contributors.
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, you may find one here:
18  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
19  * or you may search the http://www.gnu.org website for the version 2 license,
20  * or you may write to the Free Software Foundation, Inc.,
21  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
22  */
23 
24 #ifndef PCBNEW_CONNECTIVITY_RTREE_H_
25 #define PCBNEW_CONNECTIVITY_RTREE_H_
26 
27 #include <math/box2.h>
28 #include <router/pns_layerset.h>
29 
30 #include <geometry/rtree.h>
31 
32 
38 template< class T >
39 class CN_RTREE
40 {
41 public:
42 
44  {
45  this->m_tree = new RTree<T, int, 3, double>();
46  }
47 
49  {
50  delete this->m_tree;
51  }
52 
57  void Insert( T aItem )
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  }
67 
73  void Remove( T aItem )
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  }
94 
99  void RemoveAll( )
100  {
101  m_tree->RemoveAll();
102  }
103 
109  template <class Visitor>
110  void Query( const BOX2I& aBounds, const LAYER_RANGE& aRange, Visitor& aVisitor )
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  }
117 
118 private:
119 
121 };
122 
123 
124 #endif /* PCBNEW_CONNECTIVITY_RTREE_H_ */
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
void RemoveAll()
Remove all entries from tree.
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.
void Insert(T aItem)
Function Insert() Inserts an item into the tree.
void RemoveAll()
Function RemoveAll() Removes all items from the RTree.
RTree< T, int, 3, double > * m_tree
int End() const
Definition: pns_layerset.h:88
Class CN_RTREE - Implements an R-tree for fast spatial indexing of connectivity items.
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.
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...
void Remove(T aItem)
Function Remove() Removes an item from the tree.
coord_type GetX() const
Definition: box2.h:188
Class LAYER_RANGE.
Definition: pns_layerset.h:32