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 <tomasz.wlostowski@cern.ch>
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
37 /**
38 * Used by #SHAPE_INDEX to get a SHAPE* from another type.
39 *
40 * By default relies on T::GetShape() method, should be specialized if the T object
41 * doesn't allow that method.
42 *
43 * @param aItem generic T object.
44 * @return a SHAPE* object equivalent to object.
45 */
46 template <class T>
shapeFunctor(T aItem)47 static const SHAPE* shapeFunctor( T aItem )
48 {
49 return aItem->Shape();
50 }
51
52 /**
53 * Used by #SHAPE_INDEX to get a SHAPE* for a hole from another type.
54 *
55 * By default relies on T::GetHole() method, should be specialized if the T object
56 * doesn't allow that method.
57 *
58 * @param aItem generic T object.
59 * @return a SHAPE* object equivalent to object.
60 */
61 template <class T>
holeFunctor(T aItem)62 static const SHAPE* holeFunctor( T aItem )
63 {
64 return aItem->Hole();
65 }
66
67 /**
68 * Used by #SHAPE_INDEX to get the bounding box of a generic T object.
69 *
70 * By default relies on T::BBox() method, should be specialized if the T object
71 * doesn't allow that method.
72 *
73 * @param aObject is a generic T object.
74 * @return a BOX2I object containing the bounding box of the T object.
75 */
76 template <class T>
boundingBox(T aObject)77 BOX2I 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
87 /**
88 * Used by #SHAPE_INDEX to implement Accept().
89 *
90 * By default relies on V::operation() redefinition, should be specialized if V class
91 * doesn't have its () operation defined to accept T objects.
92 *
93 * @param aObject is a generic T object.
94 * @param aVisitor is a visitor object.
95 */
96 template <class T, class V>
acceptVisitor(T aObject,V aVisitor)97 void acceptVisitor( T aObject, V aVisitor )
98 {
99 aVisitor( aObject );
100 }
101
102 /**
103 * Used by #SHAPE_INDEX to implement Query().
104 *
105 * By default relies on T::Collide(U) method, should be specialized if the T object
106 * doesn't allow that method.
107 *
108 * @param aObject is a generic T object.
109 * @param aAnotherObject is a generic U object.
110 * @param aMinDistance is the minimum collision distance.
111 * @return true if object and anotherObject collide.
112 */
113 template <class T, class U>
collide(T aObject,U aAnotherObject,int aMinDistance)114 bool collide( T aObject, U aAnotherObject, int aMinDistance )
115 {
116 return shapeFunctor( aObject )->Collide( aAnotherObject, aMinDistance );
117 }
118
119 template <class T, class V>
queryCallback(T aShape,void * aContext)120 bool queryCallback( T aShape, void* aContext )
121 {
122 V* visitor = (V*) aContext;
123
124 acceptVisitor<T, V>( aShape, *visitor );
125
126 return true;
127 }
128
129 template <class T = SHAPE*>
130 class SHAPE_INDEX
131 {
132 public:
133 class Iterator
134 {
135 private:
136 typedef typename RTree<T, int, 2, double>::Iterator RTreeIterator;
137 RTreeIterator iterator;
138
139 /**
140 * Setup the internal tree iterator.
141 *
142 * @param aTree is a #RTREE object/
143 */
Init(RTree<T,int,2,double> * aTree)144 void Init( RTree<T, int, 2, double>* aTree )
145 {
146 aTree->GetFirst( iterator );
147 }
148
149 public:
150 /**
151 * Create an iterator for the index object.
152 *
153 * @param aIndex is a #SHAPE_INDEX object to iterate.
154 */
Iterator(SHAPE_INDEX * aIndex)155 Iterator( SHAPE_INDEX* aIndex )
156 {
157 Init( aIndex->m_tree );
158 }
159
160 /**
161 * Return the next data element.
162 */
163 T operator*()
164 {
165 return *iterator;
166 }
167
168 /**
169 * Shift the iterator to the next element.
170 */
171 bool operator++()
172 {
173 return ++iterator;
174 }
175
176 /**
177 * Shift the iterator to the next element.
178 */
179 bool operator++( int )
180 {
181 return ++iterator;
182 }
183
184 /**
185 * Check if the iterator has reached the end.
186 *
187 * @return true if it is in an invalid position (data finished).
188 */
IsNull()189 bool IsNull() const
190 {
191 return iterator.IsNull();
192 }
193
194 /**
195 * Check if the iterator has not reached the end.
196 *
197 * @return true if it is in an valid position (data not finished).
198 */
IsNotNull()199 bool IsNotNull() const
200 {
201 return iterator.IsNotNull();
202 }
203
204 /**
205 * Return the current element of the iterator and moves to the next position.
206 *
207 * @return a #SHAPE object pointed by the iterator before moving to the next position.
208 */
Next()209 T Next()
210 {
211 T object = *iterator;
212 ++iterator;
213
214 return object;
215 }
216 };
217
218 SHAPE_INDEX();
219
220 ~SHAPE_INDEX();
221
222 /**
223 * Add a #SHAPE to the index.
224 *
225 * @param aShape is the new SHAPE.
226 */
227 void Add( T aShape );
228
229 /**
230 * Add a shape with alternate BBox.
231 *
232 * @param aShape Shape (Item) to add.
233 * @param aBbox alternate bounding box. This should be a subset of the item's bbox
234 */
235 void Add( T aShape, const BOX2I& aBbox );
236
237 /**
238 * Remove a #SHAPE from the index.
239 *
240 * @param aShape is the #SHAPE to remove.
241 */
242 void Remove( T aShape );
243
244 /**
245 * Remove all the contents of the index.
246 */
247 void RemoveAll();
248
249 /**
250 * Accept a visitor for every #SHAPE object contained in this INDEX.
251 *
252 * @param aVisitor is the visitor object to be run.
253 */
254 template <class V>
Accept(V aVisitor)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
267 /**
268 * Rebuild the index.
269 *
270 * This should be used if the geometry of the objects contained by the index has changed.
271 */
272 void Reindex();
273
274 /**
275 * Run a callback on every #SHAPE object contained in the bounding box of (shape).
276 *
277 * @param aShape is the shape to search against.
278 * @param aMinDistance is the distance threshold.
279 * @param aVisitor is the object to be invoked on every object contained in the search area.
280 */
281 template <class V>
Query(const SHAPE * aShape,int aMinDistance,V & aVisitor)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
293 /**
294 * Create an iterator for the current index object.
295 *
296 * @return iterator to the first object.
297 */
298 Iterator Begin();
299
300 private:
301 RTree<T, int, 2, double>* m_tree;
302 };
303
304 /*
305 * Class members implementation
306 */
307
308 template <class T>
SHAPE_INDEX()309 SHAPE_INDEX<T>::SHAPE_INDEX()
310 {
311 this->m_tree = new RTree<T, int, 2, double>();
312 }
313
314 template <class T>
~SHAPE_INDEX()315 SHAPE_INDEX<T>::~SHAPE_INDEX()
316 {
317 delete this->m_tree;
318 }
319
320 template <class T>
Add(T aShape,const BOX2I & aBbox)321 void 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
329 template <class T>
Add(T aShape)330 void 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
339 template <class T>
Remove(T aShape)340 void SHAPE_INDEX<T>::Remove( T aShape )
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
349 template <class T>
RemoveAll()350 void SHAPE_INDEX<T>::RemoveAll()
351 {
352 this->m_tree->RemoveAll();
353 }
354
355 template <class T>
Reindex()356 void SHAPE_INDEX<T>::Reindex()
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
377 template <class T>
Begin()378 typename SHAPE_INDEX<T>::Iterator SHAPE_INDEX<T>::Begin()
379 {
380 return Iterator( this );
381 }
382
383 #endif /* __SHAPE_INDEX_H */
384