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()
177  {
178  return iterator.IsNull();
179  }
180 
187  bool IsNotNull()
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 
226  void Remove( T aShape );
227 
233  void RemoveAll();
234 
241  template <class V>
242  void Accept( V aVisitor )
243  {
244  Iterator iter = this->Begin();
245 
246  while( !iter.IsNull() )
247  {
248  T shape = *iter;
249  acceptVisitor( shape, aVisitor );
250  iter++;
251  }
252  }
253 
260  void Reindex();
261 
270  template <class V>
271  int Query( const SHAPE *aShape, int aMinDistance, V& aVisitor, bool aExact )
272  {
273  BOX2I box = aShape->BBox();
274  box.Inflate( aMinDistance );
275 
276  int min[2] = { box.GetX(), box.GetY() };
277  int max[2] = { box.GetRight(), box.GetBottom() };
278 
279  return this->m_tree->Search( min, max, aVisitor );
280  }
281 
288  Iterator Begin();
289 
290  private:
291  RTree<T, int, 2, double>* m_tree;
292 };
293 
294 /*
295  * Class members implementation
296  */
297 
298 template <class T>
300 {
301  this->m_tree = new RTree<T, int, 2, double>();
302 }
303 
304 template <class T>
306 {
307  delete this->m_tree;
308 }
309 
310 template <class T>
311 void SHAPE_INDEX<T>::Add( T aShape )
312 {
313  BOX2I box = boundingBox( aShape );
314  int min[2] = { box.GetX(), box.GetY() };
315  int max[2] = { box.GetRight(), box.GetBottom() };
316 
317  this->m_tree->Insert( min, max, aShape );
318 }
319 
320 template <class T>
321 void SHAPE_INDEX<T>::Remove( T aShape )
322 {
323  BOX2I box = boundingBox( aShape );
324  int min[2] = { box.GetX(), box.GetY() };
325  int max[2] = { box.GetRight(), box.GetBottom() };
326 
327  this->m_tree->Remove( min, max, aShape );
328 }
329 
330 template <class T>
332 {
333  this->m_tree->RemoveAll();
334 }
335 
336 template <class T>
338 {
339  RTree<T, int, 2, double>* newTree;
340  newTree = new RTree<T, int, 2, double>();
341 
342  Iterator iter = this->Begin();
343 
344  while( !iter.IsNull() )
345  {
346  T shape = *iter;
347  BOX2I box = boundingBox( shape );
348  int min[2] = { box.GetX(), box.GetY() };
349  int max[2] = { box.GetRight(), box.GetBottom() };
350  newTree->Insert( min, max, shape );
351  iter++;
352  }
353 
354  delete this->m_tree;
355  this->m_tree = newTree;
356 }
357 
358 template <class T>
360 {
361  return Iterator( this );
362 }
363 
364 #endif
static const SHAPE * shapeFunctor(T aItem)
shapeFunctor template function
Definition: shape_index.h:45
void RemoveAll()
Function RemoveAll()
Definition: shape_index.h:331
coord_type GetX() const
Definition: box2.h:189
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
void Init(RTree< T, int, 2, double > *aTree)
Function Init()
Definition: shape_index.h:123
coord_type GetRight() const
Definition: box2.h:198
coord_type GetBottom() const
Definition: box2.h:199
virtual bool Collide(const VECTOR2I &aP, int aClearance=0) const
Function Collide()
Definition: shape.h:109
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:311
BOX2I boundingBox(T aObject)
boundingBox template method
Definition: shape_index.h:60
void Reindex()
Function Reindex()
Definition: shape_index.h:337
bool queryCallback(T aShape, void *aContext)
Definition: shape_index.h:98
void Remove(T aShape)
Function Remove()
Definition: shape_index.h:321
Iterator Begin()
Function Begin()
Definition: shape_index.h:359
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:60
void Accept(V aVisitor)
Function Accept()
Definition: shape_index.h:242
Iterator(SHAPE_INDEX *aIndex)
Iterator constructor.
Definition: shape_index.h:135
coord_type GetY() const
Definition: box2.h:190
RTree< T, int, 2, double > * m_tree
Definition: shape_index.h:291
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:301
bool IsNull()
Function IsNull()
Definition: shape_index.h:176
int Query(const SHAPE *aShape, int aMinDistance, V &aVisitor, bool aExact)
Function Query()
Definition: shape_index.h:271
RTreeIterator iterator
Definition: shape_index.h:115
bool operator++()
Operator ++ (prefix)
Definition: shape_index.h:155
bool IsNotNull()
Function IsNotNull()
Definition: shape_index.h:187
T Next()
Function Next()
Definition: shape_index.h:199