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 <[email protected]>
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 static const SHAPE* holeFunctor( T aItem )
63 {
64  return aItem->Hole();
65 }
66 
76 template <class T>
77 BOX2I boundingBox( T aObject )
78 {
79  BOX2I bbox = shapeFunctor( aObject )->BBox();
80 
81  if( holeFunctor( aObject ) )
82  bbox.Merge( holeFunctor( aObject )->BBox() );
83 
84  return bbox;
85 }
86 
96 template <class T, class V>
97 void acceptVisitor( T aObject, V aVisitor )
98 {
99  aVisitor( aObject );
100 }
101 
113 template <class T, class U>
114 bool collide( T aObject, U aAnotherObject, int aMinDistance )
115 {
116  return shapeFunctor( aObject )->Collide( aAnotherObject, aMinDistance );
117 }
118 
119 template <class T, class V>
120 bool queryCallback( T aShape, void* aContext )
121 {
122  V* visitor = (V*) aContext;
123 
124  acceptVisitor<T, V>( aShape, *visitor );
125 
126  return true;
127 }
128 
129 template <class T = SHAPE*>
131 {
132  public:
133  class Iterator
134  {
135  private:
136  typedef typename RTree<T, int, 2, double>::Iterator RTreeIterator;
138 
144  void Init( RTree<T, int, 2, double>* aTree )
145  {
146  aTree->GetFirst( iterator );
147  }
148 
149  public:
156  {
157  Init( aIndex->m_tree );
158  }
159 
164  {
165  return *iterator;
166  }
167 
171  bool operator++()
172  {
173  return ++iterator;
174  }
175 
179  bool operator++( int )
180  {
181  return ++iterator;
182  }
183 
189  bool IsNull() const
190  {
191  return iterator.IsNull();
192  }
193 
199  bool IsNotNull() const
200  {
201  return iterator.IsNotNull();
202  }
203 
209  T Next()
210  {
211  T object = *iterator;
212  ++iterator;
213 
214  return object;
215  }
216  };
217 
218  SHAPE_INDEX();
219 
220  ~SHAPE_INDEX();
221 
227  void Add( T aShape );
228 
235  void Add( T aShape, const BOX2I& aBbox );
236 
242  void Remove( T aShape );
243 
247  void RemoveAll();
248 
254  template <class V>
255  void Accept( V aVisitor )
256  {
257  Iterator iter = this->Begin();
258 
259  while( !iter.IsNull() )
260  {
261  T shape = *iter;
262  acceptVisitor( shape, aVisitor );
263  iter++;
264  }
265  }
266 
272  void Reindex();
273 
281  template <class V>
282  int Query( const SHAPE *aShape, int aMinDistance, V& aVisitor) const
283  {
284  BOX2I box = aShape->BBox();
285  box.Inflate( aMinDistance );
286 
287  int min[2] = { box.GetX(), box.GetY() };
288  int max[2] = { box.GetRight(), box.GetBottom() };
289 
290  return this->m_tree->Search( min, max, aVisitor );
291  }
292 
298  Iterator Begin();
299 
300  private:
301  RTree<T, int, 2, double>* m_tree;
302 };
303 
304 /*
305  * Class members implementation
306  */
307 
308 template <class T>
310 {
311  this->m_tree = new RTree<T, int, 2, double>();
312 }
313 
314 template <class T>
316 {
317  delete this->m_tree;
318 }
319 
320 template <class T>
321 void SHAPE_INDEX<T>::Add( T aShape, const BOX2I& aBbox )
322 {
323  int min[2] = { aBbox.GetX(), aBbox.GetY() };
324  int max[2] = { aBbox.GetRight(), aBbox.GetBottom() };
325 
326  this->m_tree->Insert( min, max, aShape );
327 }
328 
329 template <class T>
330 void SHAPE_INDEX<T>::Add( T aShape )
331 {
332  BOX2I box = boundingBox( aShape );
333  int min[2] = { box.GetX(), box.GetY() };
334  int max[2] = { box.GetRight(), box.GetBottom() };
335 
336  this->m_tree->Insert( min, max, aShape );
337 }
338 
339 template <class T>
340 void SHAPE_INDEX<T>::Remove( T aShape )
341 {
342  BOX2I box = boundingBox( aShape );
343  int min[2] = { box.GetX(), box.GetY() };
344  int max[2] = { box.GetRight(), box.GetBottom() };
345 
346  this->m_tree->Remove( min, max, aShape );
347 }
348 
349 template <class T>
351 {
352  this->m_tree->RemoveAll();
353 }
354 
355 template <class T>
357 {
358  RTree<T, int, 2, double>* newTree;
359  newTree = new RTree<T, int, 2, double>();
360 
361  Iterator iter = this->Begin();
362 
363  while( !iter.IsNull() )
364  {
365  T shape = *iter;
366  BOX2I box = boundingBox( shape );
367  int min[2] = { box.GetX(), box.GetY() };
368  int max[2] = { box.GetRight(), box.GetBottom() };
369  newTree->Insert( min, max, shape );
370  iter++;
371  }
372 
373  delete this->m_tree;
374  this->m_tree = newTree;
375 }
376 
377 template <class T>
379 {
380  return Iterator( this );
381 }
382 
383 #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:350
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:114
T operator *()
Return the next data element.
Definition: shape_index.h:163
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:282
void Init(RTree< T, int, 2, double > *aTree)
Setup the internal tree iterator.
Definition: shape_index.h:144
static const SHAPE * holeFunctor(T aItem)
Used by SHAPE_INDEX to get a SHAPE* for a hole from another type.
Definition: shape_index.h:62
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:136
void Add(T aShape)
Add a SHAPE to the index.
Definition: shape_index.h:330
BOX2I boundingBox(T aObject)
Used by SHAPE_INDEX to get the bounding box of a generic T object.
Definition: shape_index.h:77
void Reindex()
Rebuild the index.
Definition: shape_index.h:356
bool queryCallback(T aShape, void *aContext)
Definition: shape_index.h:120
void Remove(T aShape)
Remove a SHAPE from the index.
Definition: shape_index.h:340
bool IsNull() const
Check if the iterator has reached the end.
Definition: shape_index.h:189
Iterator Begin()
Create an iterator for the current index object.
Definition: shape_index.h:378
bool operator++(int)
Shift the iterator to the next element.
Definition: shape_index.h:179
void acceptVisitor(T aObject, V aVisitor)
Used by SHAPE_INDEX to implement Accept().
Definition: shape_index.h:97
An abstract shape on 2D plane.
Definition: shape.h:116
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition: box2.h:363
void Accept(V aVisitor)
Accept a visitor for every SHAPE object contained in this INDEX.
Definition: shape_index.h:255
Iterator(SHAPE_INDEX *aIndex)
Create an iterator for the index object.
Definition: shape_index.h:155
coord_type GetY() const
Definition: box2.h:174
RTree< T, int, 2, double > * m_tree
Definition: shape_index.h:301
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:137
bool operator++()
Shift the iterator to the next element.
Definition: shape_index.h:171
bool IsNotNull() const
Check if the iterator has not reached the end.
Definition: shape_index.h:199
T Next()
Return the current element of the iterator and moves to the next position.
Definition: shape_index.h:209