KiCad PCB EDA Suite
shape_index.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) 2013 CERN
5  * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors.
6  *
7  * @author Jacobo Aragunde PĂ©rez
8  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
9  *
10  * This program is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU General Public License
12  * as published by the Free Software Foundation; either version 2
13  * of the License, or (at your option) any later version.
14  *
15  * This program is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18  * GNU General Public License for more details.
19  *
20  * You should have received a copy of the GNU General Public License
21  * along with this program; if not, you may find one here:
22  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
23  * or you may search the http://www.gnu.org website for the version 2 license,
24  * or you may write to the Free Software Foundation, Inc.,
25  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
26  */
27 
28 #ifndef __SHAPE_INDEX_H
29 #define __SHAPE_INDEX_H
30 
31 #include <vector>
32 
33 #include <geometry/rtree.h>
34 #include <geometry/shape.h>
35 #include <math/box2.h>
36 
46 template <class T>
47 static const SHAPE* shapeFunctor( T aItem )
48 {
49  return aItem->Shape();
50 }
51 
61 template <class T>
62 BOX2I boundingBox( T aObject )
63 {
64  return shapeFunctor( aObject )->BBox();
65 }
66 
76 template <class T, class V>
77 void acceptVisitor( T aObject, V aVisitor )
78 {
79  aVisitor( aObject );
80 }
81 
93 template <class T, class U>
94 bool collide( T aObject, U aAnotherObject, int aMinDistance )
95 {
96  return shapeFunctor( aObject )->Collide( aAnotherObject, aMinDistance );
97 }
98 
99 template <class T, class V>
100 bool queryCallback( T aShape, void* aContext )
101 {
102  V* visitor = (V*) aContext;
103 
104  acceptVisitor<T, V>( aShape, *visitor );
105 
106  return true;
107 }
108 
109 template <class T = SHAPE*>
111 {
112  public:
113  class Iterator
114  {
115  private:
116  typedef typename RTree<T, int, 2, double>::Iterator RTreeIterator;
118 
124  void Init( RTree<T, int, 2, double>* aTree )
125  {
126  aTree->GetFirst( iterator );
127  }
128 
129  public:
136  {
137  Init( aIndex->m_tree );
138  }
139 
144  {
145  return *iterator;
146  }
147 
151  bool operator++()
152  {
153  return ++iterator;
154  }
155 
159  bool operator++( int )
160  {
161  return ++iterator;
162  }
163 
169  bool IsNull() const
170  {
171  return iterator.IsNull();
172  }
173 
179  bool IsNotNull() const
180  {
181  return iterator.IsNotNull();
182  }
183 
189  T Next()
190  {
191  T object = *iterator;
192  ++iterator;
193 
194  return object;
195  }
196  };
197 
198  SHAPE_INDEX();
199 
200  ~SHAPE_INDEX();
201 
207  void Add( T aShape );
208 
215  void Add( T aShape, const BOX2I& aBbox );
216 
222  void Remove( T aShape );
223 
227  void RemoveAll();
228 
234  template <class V>
235  void Accept( V aVisitor )
236  {
237  Iterator iter = this->Begin();
238 
239  while( !iter.IsNull() )
240  {
241  T shape = *iter;
242  acceptVisitor( shape, aVisitor );
243  iter++;
244  }
245  }
246 
252  void Reindex();
253 
261  template <class V>
262  int Query( const SHAPE *aShape, int aMinDistance, V& aVisitor) const
263  {
264  BOX2I box = aShape->BBox();
265  box.Inflate( aMinDistance );
266 
267  int min[2] = { box.GetX(), box.GetY() };
268  int max[2] = { box.GetRight(), box.GetBottom() };
269 
270  return this->m_tree->Search( min, max, aVisitor );
271  }
272 
278  Iterator Begin();
279 
280  private:
281  RTree<T, int, 2, double>* m_tree;
282 };
283 
284 /*
285  * Class members implementation
286  */
287 
288 template <class T>
290 {
291  this->m_tree = new RTree<T, int, 2, double>();
292 }
293 
294 template <class T>
296 {
297  delete this->m_tree;
298 }
299 
300 template <class T>
301 void SHAPE_INDEX<T>::Add( T aShape, const BOX2I& aBbox )
302 {
303  int min[2] = { aBbox.GetX(), aBbox.GetY() };
304  int max[2] = { aBbox.GetRight(), aBbox.GetBottom() };
305 
306  this->m_tree->Insert( min, max, aShape );
307 }
308 
309 template <class T>
310 void SHAPE_INDEX<T>::Add( T aShape )
311 {
312  BOX2I box = boundingBox( aShape );
313  int min[2] = { box.GetX(), box.GetY() };
314  int max[2] = { box.GetRight(), box.GetBottom() };
315 
316  this->m_tree->Insert( min, max, aShape );
317 }
318 
319 template <class T>
320 void SHAPE_INDEX<T>::Remove( T aShape )
321 {
322  BOX2I box = boundingBox( aShape );
323  int min[2] = { box.GetX(), box.GetY() };
324  int max[2] = { box.GetRight(), box.GetBottom() };
325 
326  this->m_tree->Remove( min, max, aShape );
327 }
328 
329 template <class T>
331 {
332  this->m_tree->RemoveAll();
333 }
334 
335 template <class T>
337 {
338  RTree<T, int, 2, double>* newTree;
339  newTree = new RTree<T, int, 2, double>();
340 
341  Iterator iter = this->Begin();
342 
343  while( !iter.IsNull() )
344  {
345  T shape = *iter;
346  BOX2I box = boundingBox( shape );
347  int min[2] = { box.GetX(), box.GetY() };
348  int max[2] = { box.GetRight(), box.GetBottom() };
349  newTree->Insert( min, max, shape );
350  iter++;
351  }
352 
353  delete this->m_tree;
354  this->m_tree = newTree;
355 }
356 
357 template <class T>
359 {
360  return Iterator( this );
361 }
362 
363 #endif /* __SHAPE_INDEX_H */
static const SHAPE * shapeFunctor(T aItem)
Used by SHAPE_INDEX to get a SHAPE* from another type.
Definition: shape_index.h:47
void RemoveAll()
Remove all the contents of the index.
Definition: shape_index.h:330
coord_type GetX() const
Definition: box2.h:173
bool collide(T aObject, U aAnotherObject, int aMinDistance)
Used by SHAPE_INDEX to implement Query().
Definition: shape_index.h:94
T operator *()
Return the next data element.
Definition: shape_index.h:143
int Query(const SHAPE *aShape, int aMinDistance, V &aVisitor) const
Run a callback on every SHAPE object contained in the bounding box of (shape).
Definition: shape_index.h:262
void Init(RTree< T, int, 2, double > *aTree)
Setup the internal tree iterator.
Definition: shape_index.h:124
coord_type GetRight() const
Definition: box2.h:182
coord_type GetBottom() const
Definition: box2.h:183
A 2D bounding box built on top of an origin point and size vector.
Definition: box2.h:41
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const
Check if the boundary of shape (this) lies closer to the point aP than aClearance,...
Definition: shape.h:165
virtual const BOX2I BBox(int aClearance=0) const =0
Compute a bounding box of the shape, with a margin of aClearance a collision.
RTree< T, int, 2, double >::Iterator RTreeIterator
Definition: shape_index.h:116
void Add(T aShape)
Add a SHAPE to the index.
Definition: shape_index.h:310
BOX2I boundingBox(T aObject)
Used by SHAPE_INDEX to get the bounding box of a generic T object.
Definition: shape_index.h:62
void Reindex()
Rebuild the index.
Definition: shape_index.h:336
bool queryCallback(T aShape, void *aContext)
Definition: shape_index.h:100
void Remove(T aShape)
Remove a SHAPE from the index.
Definition: shape_index.h:320
bool IsNull() const
Check if the iterator has reached the end.
Definition: shape_index.h:169
Iterator Begin()
Create an iterator for the current index object.
Definition: shape_index.h:358
bool operator++(int)
Shift the iterator to the next element.
Definition: shape_index.h:159
void acceptVisitor(T aObject, V aVisitor)
Used by SHAPE_INDEX to implement Accept().
Definition: shape_index.h:77
An abstract shape on 2D plane.
Definition: shape.h:116
void Accept(V aVisitor)
Accept a visitor for every SHAPE object contained in this INDEX.
Definition: shape_index.h:235
Iterator(SHAPE_INDEX *aIndex)
Create an iterator for the index object.
Definition: shape_index.h:135
coord_type GetY() const
Definition: box2.h:174
RTree< T, int, 2, double > * m_tree
Definition: shape_index.h:281
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:281
RTreeIterator iterator
Definition: shape_index.h:117
bool operator++()
Shift the iterator to the next element.
Definition: shape_index.h:151
bool IsNotNull() const
Check if the iterator has not reached the end.
Definition: shape_index.h:179
T Next()
Return the current element of the iterator and moves to the next position.
Definition: shape_index.h:189