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  * @author Jacobo Aragunde PĂ©rez
6  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
7  *
8  * This program is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU General Public License
10  * as published by the Free Software Foundation; either version 2
11  * of the License, or (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, you may find one here:
20  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
21  * or you may search the http://www.gnu.org website for the version 2 license,
22  * or you may write to the Free Software Foundation, Inc.,
23  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
24  */
25 
26 #ifndef __SHAPE_INDEX_H
27 #define __SHAPE_INDEX_H
28 
29 #include <vector>
30 
31 #include <geometry/rtree.h>
32 #include <geometry/shape.h>
33 #include <math/box2.h>
34 
44 template <class T>
45 static const SHAPE* shapeFunctor( T aItem )
46 {
47  return aItem->Shape();
48 }
49 
59 template <class T>
60 BOX2I boundingBox( T aObject )
61 {
62  return shapeFunctor( aObject )->BBox();
63 }
64 
74 template <class T, class V>
75 void acceptVisitor( T aObject, V aVisitor )
76 {
77  aVisitor( aObject );
78 }
79 
91 template <class T, class U>
92 bool collide( T aObject, U aAnotherObject, int aMinDistance )
93 {
94  return shapeFunctor( aObject )->Collide( aAnotherObject, aMinDistance );
95 }
96 
97 template <class T, class V>
98 bool queryCallback( T aShape, void* aContext )
99 {
100  V* visitor = (V*) aContext;
101 
102  acceptVisitor<T, V>( aShape, *visitor );
103 
104  return true;
105 }
106 
107 template <class T = SHAPE*>
109 {
110  public:
111  class Iterator
112  {
113  private:
114  typedef typename RTree<T, int, 2, double>::Iterator RTreeIterator;
116 
123  void Init( RTree<T, int, 2, double>* aTree )
124  {
125  aTree->GetFirst( iterator );
126  }
127 
128  public:
136  {
137  Init( aIndex->m_tree );
138  }
139 
146  {
147  return *iterator;
148  }
149 
155  bool operator++()
156  {
157  return ++iterator;
158  }
159 
165  bool operator++( int )
166  {
167  return ++iterator;
168  }
169 
176  bool IsNull() const
177  {
178  return iterator.IsNull();
179  }
180 
187  bool IsNotNull() const
188  {
189  return iterator.IsNotNull();
190  }
191 
199  T Next()
200  {
201  T object = *iterator;
202  ++iterator;
203 
204  return object;
205  }
206  };
207 
208  SHAPE_INDEX();
209 
210  ~SHAPE_INDEX();
211 
218  void Add( T aShape );
219 
225  void Add( T aShape, const BOX2I& aBbox );
226 
233  void Remove( T aShape );
234 
240  void RemoveAll();
241 
248  template <class V>
249  void Accept( V aVisitor )
250  {
251  Iterator iter = this->Begin();
252 
253  while( !iter.IsNull() )
254  {
255  T shape = *iter;
256  acceptVisitor( shape, aVisitor );
257  iter++;
258  }
259  }
260 
267  void Reindex();
268 
277  template <class V>
278  int Query( const SHAPE *aShape, int aMinDistance, V& aVisitor) const
279  {
280  BOX2I box = aShape->BBox();
281  box.Inflate( aMinDistance );
282 
283  int min[2] = { box.GetX(), box.GetY() };
284  int max[2] = { box.GetRight(), box.GetBottom() };
285 
286  return this->m_tree->Search( min, max, aVisitor );
287  }
288 
295  Iterator Begin();
296 
297  private:
298  RTree<T, int, 2, double>* m_tree;
299 };
300 
301 /*
302  * Class members implementation
303  */
304 
305 template <class T>
307 {
308  this->m_tree = new RTree<T, int, 2, double>();
309 }
310 
311 template <class T>
313 {
314  delete this->m_tree;
315 }
316 
317 template <class T>
318 void SHAPE_INDEX<T>::Add( T aShape, const BOX2I& aBbox )
319 {
320  int min[2] = { aBbox.GetX(), aBbox.GetY() };
321  int max[2] = { aBbox.GetRight(), aBbox.GetBottom() };
322 
323  this->m_tree->Insert( min, max, aShape );
324 }
325 
326 template <class T>
327 void SHAPE_INDEX<T>::Add( T aShape )
328 {
329  BOX2I box = boundingBox( aShape );
330  int min[2] = { box.GetX(), box.GetY() };
331  int max[2] = { box.GetRight(), box.GetBottom() };
332 
333  this->m_tree->Insert( min, max, aShape );
334 }
335 
336 template <class T>
337 void SHAPE_INDEX<T>::Remove( T aShape )
338 {
339  BOX2I box = boundingBox( aShape );
340  int min[2] = { box.GetX(), box.GetY() };
341  int max[2] = { box.GetRight(), box.GetBottom() };
342 
343  this->m_tree->Remove( min, max, aShape );
344 }
345 
346 template <class T>
348 {
349  this->m_tree->RemoveAll();
350 }
351 
352 template <class T>
354 {
355  RTree<T, int, 2, double>* newTree;
356  newTree = new RTree<T, int, 2, double>();
357 
358  Iterator iter = this->Begin();
359 
360  while( !iter.IsNull() )
361  {
362  T shape = *iter;
363  BOX2I box = boundingBox( shape );
364  int min[2] = { box.GetX(), box.GetY() };
365  int max[2] = { box.GetRight(), box.GetBottom() };
366  newTree->Insert( min, max, shape );
367  iter++;
368  }
369 
370  delete this->m_tree;
371  this->m_tree = newTree;
372 }
373 
374 template <class T>
376 {
377  return Iterator( this );
378 }
379 
380 #endif /* __SHAPE_INDEX_H */
static const SHAPE * shapeFunctor(T aItem)
shapeFunctor template function
Definition: shape_index.h:45
void RemoveAll()
Function RemoveAll()
Definition: shape_index.h:347
coord_type GetX() const
Definition: box2.h:190
bool collide(T aObject, U aAnotherObject, int aMinDistance)
collide template method
Definition: shape_index.h:92
T operator *()
Operator * (prefix)
Definition: shape_index.h:145
int Query(const SHAPE *aShape, int aMinDistance, V &aVisitor) const
Function Query()
Definition: shape_index.h:278
void Init(RTree< T, int, 2, double > *aTree)
Function Init()
Definition: shape_index.h:123
coord_type GetRight() const
Definition: box2.h:199
coord_type GetBottom() const
Definition: box2.h:200
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const
Function Collide()
Definition: shape.h:176
virtual const BOX2I BBox(int aClearance=0) const =0
Function BBox()
RTree< T, int, 2, double >::Iterator RTreeIterator
Definition: shape_index.h:114
void Add(T aShape)
Function Add()
Definition: shape_index.h:327
BOX2I boundingBox(T aObject)
boundingBox template method
Definition: shape_index.h:60
void Reindex()
Function Reindex()
Definition: shape_index.h:353
bool queryCallback(T aShape, void *aContext)
Definition: shape_index.h:98
void Remove(T aShape)
Function Remove()
Definition: shape_index.h:337
bool IsNull() const
Function IsNull()
Definition: shape_index.h:176
Iterator Begin()
Function Begin()
Definition: shape_index.h:375
bool operator++(int)
Operator ++ (postfix)
Definition: shape_index.h:165
void acceptVisitor(T aObject, V aVisitor)
acceptVisitor template method
Definition: shape_index.h:75
SHAPE.
Definition: shape.h:122
void Accept(V aVisitor)
Function Accept()
Definition: shape_index.h:249
Iterator(SHAPE_INDEX *aIndex)
Iterator constructor.
Definition: shape_index.h:135
coord_type GetY() const
Definition: box2.h:191
RTree< T, int, 2, double > * m_tree
Definition: shape_index.h:298
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:302
RTreeIterator iterator
Definition: shape_index.h:115
bool operator++()
Operator ++ (prefix)
Definition: shape_index.h:155
bool IsNotNull() const
Function IsNotNull()
Definition: shape_index.h:187
T Next()
Function Next()
Definition: shape_index.h:199