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 #include <geometry/shape.h>
31 #include <geometry/rtree.h>
32 
33 
43 template <class T>
44 static const SHAPE* shapeFunctor( T aItem )
45 {
46  return aItem->Shape();
47 }
48 
58 template <class T>
59 BOX2I boundingBox( T aObject )
60 {
61  return shapeFunctor( aObject )->BBox();
62 }
63 
73 template <class T, class V>
74 void acceptVisitor( T aObject, V aVisitor )
75 {
76  aVisitor( aObject );
77 }
78 
90 template <class T, class U>
91 bool collide( T aObject, U aAnotherObject, int aMinDistance )
92 {
93  return shapeFunctor( aObject )->Collide( aAnotherObject, aMinDistance );
94 }
95 
96 template <class T, class V>
97 bool queryCallback( T aShape, void* aContext )
98 {
99  V* visitor = (V*) aContext;
100 
101  acceptVisitor<T, V>( aShape, *visitor );
102 
103  return true;
104 }
105 
106 template <class T = SHAPE*>
108 {
109  public:
110  class Iterator
111  {
112  private:
114  RTreeIterator iterator;
115 
123  {
124  aTree->GetFirst( iterator );
125  }
126 
127  public:
135  {
136  Init( aIndex->m_tree );
137  }
138 
145  {
146  return *iterator;
147  }
148 
154  bool operator++()
155  {
156  return ++iterator;
157  }
158 
164  bool operator++( int )
165  {
166  return ++iterator;
167  }
168 
175  bool IsNull()
176  {
177  return iterator.IsNull();
178  }
179 
186  bool IsNotNull()
187  {
188  return iterator.IsNotNull();
189  }
190 
198  T Next()
199  {
200  T object = *iterator;
201  ++iterator;
202 
203  return object;
204  }
205  };
206 
207  SHAPE_INDEX();
208 
209  ~SHAPE_INDEX();
210 
217  void Add( T aShape );
218 
225  void Remove( T aShape );
226 
232  void RemoveAll();
233 
240  template <class V>
241  void Accept( V aVisitor )
242  {
243  Iterator iter = this->Begin();
244 
245  while( !iter.IsNull() )
246  {
247  T shape = *iter;
248  acceptVisitor( shape, aVisitor );
249  iter++;
250  }
251  }
252 
259  void Reindex();
260 
269  template <class V>
270  int Query( const SHAPE *aShape, int aMinDistance, V& aVisitor, bool aExact )
271  {
272  BOX2I box = aShape->BBox();
273  box.Inflate( aMinDistance );
274 
275  int min[2] = { box.GetX(), box.GetY() };
276  int max[2] = { box.GetRight(), box.GetBottom() };
277 
278  return this->m_tree->Search( min, max, aVisitor );
279  }
280 
287  Iterator Begin();
288 
289  private:
291 };
292 
293 /*
294  * Class members implementation
295  */
296 
297 template <class T>
299 {
300  this->m_tree = new RTree<T, int, 2, float>();
301 }
302 
303 template <class T>
305 {
306  delete this->m_tree;
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, float>* newTree;
339  newTree = new RTree<T, int, 2, float>();
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
static const SHAPE * shapeFunctor(T aItem)
shapeFunctor template function
Definition: shape_index.h:44
coord_type GetY() const
Definition: box2.h:179
void RemoveAll()
Function RemoveAll()
Definition: shape_index.h:330
bool collide(T aObject, U aAnotherObject, int aMinDistance)
collide template method
Definition: shape_index.h:91
T
enum T contains all this lexer's tokens.
void Init(RTree< T, int, 2, float > *aTree)
Function Init()
Definition: shape_index.h:122
coord_type GetRight() const
Definition: box2.h:187
RTree< T, int, 2, float >::Iterator RTreeIterator
Definition: shape_index.h:113
virtual const BOX2I BBox(int aClearance=0) const =0
Function BBox()
void Add(T aShape)
Function Add()
Definition: shape_index.h:310
BOX2I boundingBox(T aObject)
boundingBox template method
Definition: shape_index.h:59
RTree< T, int, 2, float > * m_tree
Definition: shape_index.h:290
void Reindex()
Function Reindex()
Definition: shape_index.h:336
bool queryCallback(T aShape, void *aContext)
Definition: shape_index.h:97
void Remove(T aShape)
Function Remove()
Definition: shape_index.h:320
coord_type GetBottom() const
Definition: box2.h:188
Iterator Begin()
Function Begin()
Definition: shape_index.h:358
bool operator++(int)
Operator ++ (postfix)
Definition: shape_index.h:164
void acceptVisitor(T aObject, V aVisitor)
acceptVisitor template method
Definition: shape_index.h:74
Class SHAPE.
Definition: shape.h:57
void Insert(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE &a_dataId)
Insert entry.
Implementation of RTree, a multidimensional bounding rectangle tree.
Definition: rtree.h:79
void GetFirst(Iterator &a_it)
Get 'first' for iteration.
Definition: rtree.h:337
void Accept(V aVisitor)
Function Accept()
Definition: shape_index.h:241
virtual bool Collide(const VECTOR2I &aP, int aClearance=0) const
Function Collide()
Definition: shape.h:106
bool IsNull(Iterator &a_it)
Is iterator NULL, or at end?
Definition: rtree.h:366
Iterator(SHAPE_INDEX *aIndex)
Iterator constructor.
Definition: shape_index.h:134
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:266
#define max(a, b)
Definition: auxiliary.h:86
bool IsNull()
Function IsNull()
Definition: shape_index.h:175
int Query(const SHAPE *aShape, int aMinDistance, V &aVisitor, bool aExact)
Function Query()
Definition: shape_index.h:270
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.
RTreeIterator iterator
Definition: shape_index.h:114
bool operator++()
Operator ++ (prefix)
Definition: shape_index.h:154
coord_type GetX() const
Definition: box2.h:178
bool IsNotNull()
Function IsNotNull()
Definition: shape_index.h:186
T operator*()
Operator * (prefix)
Definition: shape_index.h:144
T Next()
Function Next()
Definition: shape_index.h:198
#define min(a, b)
Definition: auxiliary.h:85