KiCad PCB EDA Suite
Loading...
Searching...
No Matches
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>
62BOX2I boundingBox( T aObject )
63{
64 BOX2I bbox = shapeFunctor( aObject )->BBox();
65
66 return bbox;
67}
68
78template <class T, class V>
79void acceptVisitor( T aObject, V aVisitor )
80{
81 aVisitor( aObject );
82}
83
95template <class T, class U>
96bool collide( T aObject, U aAnotherObject, int aMinDistance )
97{
98 return shapeFunctor( aObject )->Collide( aAnotherObject, aMinDistance );
99}
100
101template <class T, class V>
102bool queryCallback( T aShape, void* aContext )
103{
104 V* visitor = (V*) aContext;
105
106 acceptVisitor<T, V>( aShape, *visitor );
107
108 return true;
109}
110
111template <class T = SHAPE*>
113{
114 public:
116 {
117 private:
118 typedef typename RTree<T, int, 2, double>::Iterator RTreeIterator;
120
126 void Init( RTree<T, int, 2, double>* aTree )
127 {
128 aTree->GetFirst( iterator );
129 }
130
131 public:
138 {
139 Init( aIndex->m_tree );
140 }
141
146 {
147 return *iterator;
148 }
149
154 {
155 return ++iterator;
156 }
157
161 bool operator++( int )
162 {
163 return ++iterator;
164 }
165
171 bool IsNull() const
172 {
173 return iterator.IsNull();
174 }
175
181 bool IsNotNull() const
182 {
183 return iterator.IsNotNull();
184 }
185
192 {
193 T object = *iterator;
194 ++iterator;
195
196 return object;
197 }
198 };
199
200 SHAPE_INDEX();
201
202 ~SHAPE_INDEX();
203
209 void Add( T aShape );
210
217 void Add( T aShape, const BOX2I& aBbox );
218
224 void Remove( T aShape );
225
229 void RemoveAll();
230
236 template <class V>
237 void Accept( V aVisitor )
238 {
239 Iterator iter = this->Begin();
240
241 while( !iter.IsNull() )
242 {
243 T shape = *iter;
244 acceptVisitor( shape, aVisitor );
245 iter++;
246 }
247 }
248
254 void Reindex();
255
263 template <class V>
264 int Query( const SHAPE *aShape, int aMinDistance, V& aVisitor) const
265 {
266 BOX2I box = aShape->BBox();
267 box.Inflate( aMinDistance );
268
269 int min[2] = { box.GetX(), box.GetY() };
270 int max[2] = { box.GetRight(), box.GetBottom() };
271
272 return this->m_tree->Search( min, max, aVisitor );
273 }
274
280 Iterator Begin();
281
282 private:
283 RTree<T, int, 2, double>* m_tree;
284};
285
286/*
287 * Class members implementation
288 */
289
290template <class T>
292{
293 this->m_tree = new RTree<T, int, 2, double>();
294}
295
296template <class T>
298{
299 delete this->m_tree;
300}
301
302template <class T>
303void SHAPE_INDEX<T>::Add( T aShape, const BOX2I& aBbox )
304{
305 int min[2] = { aBbox.GetX(), aBbox.GetY() };
306 int max[2] = { aBbox.GetRight(), aBbox.GetBottom() };
307
308 this->m_tree->Insert( min, max, aShape );
309}
310
311template <class T>
312void SHAPE_INDEX<T>::Add( T aShape )
313{
314 BOX2I box = boundingBox( aShape );
315 int min[2] = { box.GetX(), box.GetY() };
316 int max[2] = { box.GetRight(), box.GetBottom() };
317
318 this->m_tree->Insert( min, max, aShape );
319}
320
321template <class T>
323{
324 BOX2I box = boundingBox( aShape );
325 int min[2] = { box.GetX(), box.GetY() };
326 int max[2] = { box.GetRight(), box.GetBottom() };
327
328 this->m_tree->Remove( min, max, aShape );
329}
330
331template <class T>
333{
334 this->m_tree->RemoveAll();
335}
336
337template <class T>
339{
340 RTree<T, int, 2, double>* newTree;
341 newTree = new RTree<T, int, 2, double>();
342
343 Iterator iter = this->Begin();
344
345 while( !iter.IsNull() )
346 {
347 T shape = *iter;
348 BOX2I box = boundingBox( shape );
349 int min[2] = { box.GetX(), box.GetY() };
350 int max[2] = { box.GetRight(), box.GetBottom() };
351 newTree->Insert( min, max, shape );
352 iter++;
353 }
354
355 delete this->m_tree;
356 this->m_tree = newTree;
357}
358
359template <class T>
361{
362 return Iterator( this );
363}
364
365#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
bool operator++()
Shift the iterator to the next element.
Definition: shape_index.h:153
RTree< T, int, 2, double >::Iterator RTreeIterator
Definition: shape_index.h:118
RTreeIterator iterator
Definition: shape_index.h:119
bool IsNotNull() const
Check if the iterator has not reached the end.
Definition: shape_index.h:181
bool operator++(int)
Shift the iterator to the next element.
Definition: shape_index.h:161
T Next()
Return the current element of the iterator and moves to the next position.
Definition: shape_index.h:191
void Init(RTree< T, int, 2, double > *aTree)
Setup the internal tree iterator.
Definition: shape_index.h:126
bool IsNull() const
Check if the iterator has reached the end.
Definition: shape_index.h:171
T operator*()
Return the next data element.
Definition: shape_index.h:145
Iterator(SHAPE_INDEX *aIndex)
Create an iterator for the index object.
Definition: shape_index.h:137
void Remove(T aShape)
Remove a SHAPE from the index.
Definition: shape_index.h:322
RTree< T, int, 2, double > * m_tree
Definition: shape_index.h:283
Iterator Begin()
Create an iterator for the current index object.
Definition: shape_index.h:360
void RemoveAll()
Remove all the contents of the index.
Definition: shape_index.h:332
void Accept(V aVisitor)
Accept a visitor for every SHAPE object contained in this INDEX.
Definition: shape_index.h:237
void Reindex()
Rebuild the index.
Definition: shape_index.h:338
void Add(T aShape)
Add a SHAPE to the index.
Definition: shape_index.h:312
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:264
An abstract shape on 2D plane.
Definition: shape.h:124
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:179
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:102
BOX2I boundingBox(T aObject)
Used by SHAPE_INDEX to get the bounding box of a generic T object.
Definition: shape_index.h:62
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:96
void acceptVisitor(T aObject, V aVisitor)
Used by SHAPE_INDEX to implement Accept().
Definition: shape_index.h:79