Horizon
Loading...
Searching...
No Matches
shape_index_list.h
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 * @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_LIST_H
27#define __SHAPE_INDEX_LIST_H
28
29#include <vector>
30
31#include <geometry/shape.h>
32#include <math/box2.h>
33#include <math/vector2d.h>
34
35template <class T>
36const SHAPE* defaultShapeFunctor( const T aItem )
37{
38 return aItem->Shape();
39}
40
41template <class T, const SHAPE* (ShapeFunctor) (const T) = defaultShapeFunctor<T> >
43{
44 struct SHAPE_ENTRY
45 {
46 SHAPE_ENTRY( T aParent )
47 {
48 shape = ShapeFunctor( aParent );
49 bbox = shape->BBox( 0 );
50 parent = aParent;
51 }
52
53 ~SHAPE_ENTRY()
54 {
55 }
56
57 T parent;
58 const SHAPE* shape;
59 BOX2I bbox;
60 };
61
62 typedef std::vector<SHAPE_ENTRY> SHAPE_VEC;
63 typedef typename std::vector<SHAPE_ENTRY>::iterator SHAPE_VEC_ITER;
64
65public:
66 // "Normal" iterator interface, for STL algorithms.
68 {
69 public:
70 iterator()
71 {}
72
73 iterator( SHAPE_VEC_ITER aCurrent ) :
74 m_current( aCurrent )
75 {}
76
77 iterator( const iterator& aB ) :
78 m_current( aB.m_current )
79 {}
80
81 T operator*() const
82 {
83 return (*m_current).parent;
84 }
85
86 void operator++()
87 {
88 ++m_current;
89 }
90
91 iterator& operator++( int aDummy )
92 {
93 ++m_current;
94 return *this;
95 }
96
97 bool operator==( const iterator& aRhs ) const
98 {
99 return m_current == aRhs.m_current;
100 }
101
102 bool operator!=( const iterator& aRhs ) const
103 {
104 return m_current != aRhs.m_current;
105 }
106
107 const iterator& operator=( const iterator& aRhs )
108 {
109 m_current = aRhs.m_current;
110 return *this;
111 }
112
113 private:
114 SHAPE_VEC_ITER m_current;
115 };
116
117 // "Query" iterator, for iterating over a set of spatially matching shapes.
119 {
120 public:
122 {
123 }
124
125 query_iterator( SHAPE_VEC_ITER aCurrent, SHAPE_VEC_ITER aEnd, SHAPE* aShape,
126 int aMinDistance, bool aExact ) :
127 m_end( aEnd ),
128 m_current( aCurrent ),
129 m_shape( aShape ),
130 m_minDistance( aMinDistance ),
131 m_exact( aExact )
132 {
133 if( aShape )
134 {
135 m_refBBox = aShape->BBox();
136 next();
137 }
138 }
139
140 query_iterator( const query_iterator& aB ) :
141 m_end( aB.m_end ),
142 m_current( aB.m_current ),
143 m_shape( aB.m_shape ),
144 m_minDistance( aB.m_minDistance ),
145 m_exact( aB.m_exact ),
146 m_refBBox( aB.m_refBBox )
147 {
148 }
149
150 T operator*() const
151 {
152 return (*m_current).parent;
153 }
154
155 query_iterator& operator++()
156 {
157 ++m_current;
158 next();
159 return *this;
160 }
161
162 query_iterator& operator++( int aDummy )
163 {
164 ++m_current;
165 next();
166 return *this;
167 }
168
169 bool operator==( const query_iterator& aRhs ) const
170 {
171 return m_current == aRhs.m_current;
172 }
173
174 bool operator!=( const query_iterator& aRhs ) const
175 {
176 return m_current != aRhs.m_current;
177 }
178
179 const query_iterator& operator=( const query_iterator& aRhs )
180 {
181 m_end = aRhs.m_end;
182 m_current = aRhs.m_current;
183 m_shape = aRhs.m_shape;
184 m_minDistance = aRhs.m_minDistance;
185 m_exact = aRhs.m_exact;
186 m_refBBox = aRhs.m_refBBox;
187 return *this;
188 }
189
190 private:
191 void next()
192 {
193 while( m_current != m_end )
194 {
195 if( m_refBBox.Distance( m_current->bbox ) <= m_minDistance )
196 {
197 if( !m_exact || m_current->shape->Collide( m_shape, m_minDistance ) )
198 return;
199 }
200
201 ++m_current;
202 }
203 }
204
205 SHAPE_VEC_ITER m_end;
206 SHAPE_VEC_ITER m_current;
207 BOX2I m_refBBox;
208 bool m_exact;
209 SHAPE* m_shape;
210 int m_minDistance;
211 };
212
213 void Add( T aItem )
214 {
215 SHAPE_ENTRY s( aItem );
216
217 m_shapes.push_back( s );
218 }
219
220 void Remove( const T aItem )
221 {
222 SHAPE_VEC_ITER i;
223
224 for( i = m_shapes.begin(); i != m_shapes.end(); ++i )
225 {
226 if( i->parent == aItem )
227 break;
228 }
229
230 if( i == m_shapes.end() )
231 return;
232
233 m_shapes.erase( i );
234 }
235
236 int Size() const
237 {
238 return m_shapes.size();
239 }
240
241 template <class Visitor>
242 int Query( const SHAPE* aShape, int aMinDistance, Visitor& aV, bool aExact = true ) // const
243 {
244 SHAPE_VEC_ITER i;
245 int n = 0;
246 VECTOR2I::extended_type minDistSq = (VECTOR2I::extended_type) aMinDistance * aMinDistance;
247
248 BOX2I refBBox = aShape->BBox();
249
250 for( i = m_shapes.begin(); i != m_shapes.end(); ++i )
251 {
252 if( refBBox.SquaredDistance( i->bbox ) <= minDistSq )
253 {
254 if( !aExact || i->shape->Collide( aShape, aMinDistance ) )
255 {
256 n++;
257
258 if( !aV( i->parent ) )
259 return n;
260 }
261 }
262 }
263
264 return n;
265 }
266
267 void Clear()
268 {
269 m_shapes.clear();
270 }
271
272 query_iterator qbegin( SHAPE* aShape, int aMinDistance, bool aExact )
273 {
274 return query_iterator( m_shapes.begin(), m_shapes.end(), aShape, aMinDistance, aExact );
275 }
276
277 const query_iterator qend()
278 {
279 return query_iterator( m_shapes.end(), m_shapes.end(), nullptr, 0, false );
280 }
281
282 iterator begin()
283 {
284 return iterator( m_shapes.begin() );
285 }
286
287 iterator end()
288 {
289 return iterator( m_shapes.end() );
290 }
291
292private:
293 SHAPE_VEC m_shapes;
294};
295
296#endif
Definition shape_index_list.h:68
Definition shape_index_list.h:119
Definition shape_index_list.h:43
An abstract shape on 2D plane.
Definition shape.h:117
virtual const BOX2I BBox(int aClearance=0) const =0
Compute a bounding box of the shape, with a margin of aClearance a collision.