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
46template <class T>
47static const SHAPE* shapeFunctor( T aItem )
48{
49 return aItem->Shape();
50}
51
61template <class T>
62static const SHAPE* holeFunctor( T aItem )
63{
64 return aItem->Hole();
65}
66
76template <class T>
77BOX2I 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
96template <class T, class V>
97void acceptVisitor( T aObject, V aVisitor )
98{
99 aVisitor( aObject );
100}
101
113template <class T, class U>
114bool collide( T aObject, U aAnotherObject, int aMinDistance )
115{
116 return shapeFunctor( aObject )->Collide( aAnotherObject, aMinDistance );
117}
118
119template <class T, class V>
120bool queryCallback( T aShape, void* aContext )
121{
122 V* visitor = (V*) aContext;
123
124 acceptVisitor<T, V>( aShape, *visitor );
125
126 return true;
127}
128
129template <class T = SHAPE*>
131{
132 public:
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
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
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
308template <class T>
310{
311 this->m_tree = new RTree<T, int, 2, double>();
312}
313
314template <class T>
316{
317 delete this->m_tree;
318}
319
320template <class T>
321void 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
329template <class T>
330void 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
339template <class T>
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
349template <class T>
351{
352 this->m_tree->RemoveAll();
353}
354
355template <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
377template <class T>
379{
380 return Iterator( this );
381}
382
383#endif /* __SHAPE_INDEX_H */
coord_type GetY() const
Definition: box2.h:181
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:506
coord_type GetX() const
Definition: box2.h:180
coord_type GetRight() const
Definition: box2.h:189
coord_type GetBottom() const
Definition: box2.h:190
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition: box2.h:588
bool operator++()
Shift the iterator to the next element.
Definition: shape_index.h:171
RTree< T, int, 2, double >::Iterator RTreeIterator
Definition: shape_index.h:136
RTreeIterator iterator
Definition: shape_index.h:137
bool IsNotNull() const
Check if the iterator has not reached the end.
Definition: shape_index.h:199
bool operator++(int)
Shift the iterator to the next element.
Definition: shape_index.h:179
T Next()
Return the current element of the iterator and moves to the next position.
Definition: shape_index.h:209
void Init(RTree< T, int, 2, double > *aTree)
Setup the internal tree iterator.
Definition: shape_index.h:144
bool IsNull() const
Check if the iterator has reached the end.
Definition: shape_index.h:189
T operator*()
Return the next data element.
Definition: shape_index.h:163
Iterator(SHAPE_INDEX *aIndex)
Create an iterator for the index object.
Definition: shape_index.h:155
void Remove(T aShape)
Remove a SHAPE from the index.
Definition: shape_index.h:340
RTree< T, int, 2, double > * m_tree
Definition: shape_index.h:301
Iterator Begin()
Create an iterator for the current index object.
Definition: shape_index.h:378
void RemoveAll()
Remove all the contents of the index.
Definition: shape_index.h:350
void Accept(V aVisitor)
Accept a visitor for every SHAPE object contained in this INDEX.
Definition: shape_index.h:255
void Reindex()
Rebuild the index.
Definition: shape_index.h:356
void Add(T aShape)
Add a SHAPE to the index.
Definition: shape_index.h:330
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
An abstract shape on 2D plane.
Definition: shape.h:123
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:178
virtual const BOX2I BBox(int aClearance=0) const =0
Compute a bounding box of the shape, with a margin of aClearance a collision.
bool queryCallback(T aShape, void *aContext)
Definition: shape_index.h:120
BOX2I boundingBox(T aObject)
Used by SHAPE_INDEX to get the bounding box of a generic T object.
Definition: shape_index.h:77
static const SHAPE * shapeFunctor(T aItem)
Used by SHAPE_INDEX to get a SHAPE* from another type.
Definition: shape_index.h:47
bool collide(T aObject, U aAnotherObject, int aMinDistance)
Used by SHAPE_INDEX to implement Query().
Definition: shape_index.h:114
void acceptVisitor(T aObject, V aVisitor)
Used by SHAPE_INDEX to implement Accept().
Definition: shape_index.h:97
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
#define U()