Horizon
shape_index.h
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
43template <class T>
44static const SHAPE* shapeFunctor( T aItem )
45{
46 return aItem->Shape();
47}
48
58template <class T>
59BOX2I boundingBox( T aObject )
60{
61 return shapeFunctor( aObject )->BBox();
62}
63
73template <class T, class V>
74void acceptVisitor( T aObject, V aVisitor )
75{
76 aVisitor( aObject );
77}
78
90template <class T, class U>
91bool collide( T aObject, U aAnotherObject, int aMinDistance )
92{
93 return shapeFunctor( aObject )->Collide( aAnotherObject, aMinDistance );
94}
95
96template <class T, class V>
97bool queryCallback( T aShape, void* aContext )
98{
99 V* visitor = (V*) aContext;
100
101 acceptVisitor<T, V>( aShape, *visitor );
102
103 return true;
104}
105
106template <class T = SHAPE*>
108{
109 public:
111 {
112 private:
113 typedef typename RTree<T, int, 2, double>::Iterator RTreeIterator;
114 RTreeIterator iterator;
115
122 void Init( RTree<T, int, 2, double>* aTree )
123 {
124 aTree->GetFirst( iterator );
125 }
126
127 public:
135 {
136 Init( aIndex->m_tree );
137 }
138
145 {
146 return *iterator;
147 }
148
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
187 {
188 return iterator.IsNotNull();
189 }
190
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
297template <class T>
299{
300 this->m_tree = new RTree<T, int, 2, double>();
301}
302
303template <class T>
305{
306 delete this->m_tree;
307}
308
309template <class T>
310void 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
319template <class T>
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
329template <class T>
331{
332 this->m_tree->RemoveAll();
333}
334
335template <class T>
337{
339 newTree = new RTree<T, int, 2, double>();
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
357template <class T>
359{
360 return Iterator( this );
361}
362
363#endif
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:300
Implementation of RTree, a multidimensional bounding rectangle tree.
Definition: rtree.h:77
int Search(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], std::function< bool(const DATATYPE &)> a_callback) const
Find all within search rectangle.
void Insert(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE &a_dataId)
Insert entry.
void GetFirst(Iterator &a_it)
Get 'first' for iteration.
Definition: rtree.h:333
Definition: shape_index.h:111
bool operator++()
Operator ++ (prefix)
Definition: shape_index.h:154
bool IsNotNull()
Function IsNotNull()
Definition: shape_index.h:186
bool IsNull()
Function IsNull()
Definition: shape_index.h:175
bool operator++(int)
Operator ++ (postfix)
Definition: shape_index.h:164
T Next()
Function Next()
Definition: shape_index.h:198
T operator*()
Operator * (prefix)
Definition: shape_index.h:144
Iterator(SHAPE_INDEX *aIndex)
Iterator constructor.
Definition: shape_index.h:134
Definition: shape_index.h:108
int Query(const SHAPE *aShape, int aMinDistance, V &aVisitor, bool aExact)
Function Query()
Definition: shape_index.h:270
void Remove(T aShape)
Function Remove()
Definition: shape_index.h:320
Iterator Begin()
Function Begin()
Definition: shape_index.h:358
void RemoveAll()
Function RemoveAll()
Definition: shape_index.h:330
void Accept(V aVisitor)
Function Accept()
Definition: shape_index.h:241
void Reindex()
Function Reindex()
Definition: shape_index.h:336
void Add(T aShape)
Function Add()
Definition: shape_index.h:310
Class SHAPE.
Definition: shape.h:59
virtual bool Collide(const VECTOR2I &aP, int aClearance=0) const
Function Collide()
Definition: shape.h:107
virtual const BOX2I BBox(int aClearance=0) const =0
Function BBox()