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 
29 #include <geometry/rtree.h>
30 
31 
37 template< class T >
38 class CN_RTREE
39 {
40 public:
41 
43  {
44  this->m_tree = new RTree<T, int, 2, float>();
45  }
46 
48  {
49  delete this->m_tree;
50  }
51 
56  void Insert( T aItem )
57  {
58  const BOX2I& bbox = aItem->BBox();
59  const int mmin[2] = { bbox.GetX(), bbox.GetY() };
60  const int mmax[2] = { bbox.GetRight(), bbox.GetBottom() };
61 
62  m_tree->Insert( mmin, mmax, aItem );
63  }
64 
70  void Remove( T aItem )
71  {
72 
73  // First, attempt to remove the item using its given BBox
74  const BOX2I& bbox = aItem->BBox();
75  const int mmin[2] = { bbox.GetX(), bbox.GetY() };
76  const int mmax[2] = { bbox.GetRight(), bbox.GetBottom() };
77 
78  // If we are not successful ( 1 == not found ), then we expand
79  // the search to the full tree
80  if( m_tree->Remove( mmin, mmax, aItem ) )
81  {
82  // N.B. We must search the whole tree for the pointer to remove
83  // because the item may have been moved before we have the chance to
84  // delete it from the tree
85  const int mmin2[2] = { INT_MIN, INT_MIN };
86  const int mmax2[2] = { INT_MAX, INT_MAX };
87  m_tree->Remove( mmin2, mmax2, aItem );
88  }
89  }
90 
95  void RemoveAll( )
96  {
97  m_tree->RemoveAll();
98  }
99 
105  template <class Visitor>
106  void Query( const BOX2I& aBounds, Visitor& aVisitor )
107  {
108  const int mmin[2] = { aBounds.GetX(), aBounds.GetY() };
109  const int mmax[2] = { aBounds.GetRight(), aBounds.GetBottom() };
110 
111  m_tree->Search( mmin, mmax, aVisitor );
112  }
113 
114 private:
115 
117 };
118 
119 
120 #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:179
coord_type GetRight() const
Definition: box2.h:187
void RemoveAll()
Remove all entries from tree.
RTree< T, int, 2, float > * m_tree
void Insert(T aItem)
Function Insert() Inserts an item into the tree.
void RemoveAll()
Function RemoveAll() Removes all items from the RTree.
Class CN_RTREE - Implements an R-tree for fast spatial indexing of connectivity items.
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.
void Remove(T aItem)
Function Remove() Removes an item from the tree.
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
void Query(const BOX2I &aBounds, Visitor &aVisitor)
Function Query() Executes a function object aVisitor for each item whose bounding box intersects with...