KiCad PCB EDA Suite
Loading...
Searching...
No Matches
shape_index_list.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 * @author Tomasz Wlostowski <[email protected]>
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{
45 {
46 SHAPE_ENTRY( T aParent )
47 {
48 shape = ShapeFunctor( aParent );
49 bbox = shape->BBox( 0 );
50 parent = aParent;
51 }
52
54 {
55 }
56
58 const SHAPE* shape;
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:
71 {}
72
74 m_current( aCurrent )
75 {}
76
77 iterator( const iterator& aB ) :
79 {}
80
81 T operator*() const
82 {
83 return (*m_current).parent;
84 }
85
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:
115 };
116
117 // "Query" iterator, for iterating over a set of spatially matching shapes.
119 {
120 public:
122 {
123 }
124
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
141 m_end( aB.m_end ),
142 m_current( aB.m_current ),
143 m_shape( aB.m_shape ),
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
156 {
157 ++m_current;
158 next();
159 return *this;
160 }
161
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
180 {
181 m_end = aRhs.m_end;
182 m_current = aRhs.m_current;
183 m_shape = aRhs.m_shape;
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
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 {
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 {
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
278 {
279 return query_iterator( m_shapes.end(), m_shapes.end(), nullptr, 0, false );
280 }
281
283 {
284 return iterator( m_shapes.begin() );
285 }
286
288 {
289 return iterator( m_shapes.end() );
290 }
291
292private:
294};
295
296#endif
ecoord_type Distance(const Vec &aP) const
Definition: box2.h:797
constexpr ecoord_type SquaredDistance(const Vec &aP) const
Definition: box2.h:786
iterator(SHAPE_VEC_ITER aCurrent)
const iterator & operator=(const iterator &aRhs)
iterator(const iterator &aB)
bool operator!=(const iterator &aRhs) const
iterator & operator++(int aDummy)
bool operator==(const iterator &aRhs) const
query_iterator(SHAPE_VEC_ITER aCurrent, SHAPE_VEC_ITER aEnd, SHAPE *aShape, int aMinDistance, bool aExact)
query_iterator & operator++(int aDummy)
bool operator==(const query_iterator &aRhs) const
bool operator!=(const query_iterator &aRhs) const
query_iterator(const query_iterator &aB)
const query_iterator & operator=(const query_iterator &aRhs)
void Add(T aItem)
const query_iterator qend()
int Query(const SHAPE *aShape, int aMinDistance, Visitor &aV, bool aExact=true)
query_iterator qbegin(SHAPE *aShape, int aMinDistance, bool aExact)
std::vector< SHAPE_ENTRY >::iterator SHAPE_VEC_ITER
void Remove(const T aItem)
std::vector< SHAPE_ENTRY > SHAPE_VEC
An abstract shape on 2D plane.
Definition: shape.h:126
virtual const BOX2I BBox(int aClearance=0) const =0
Compute a bounding box of the shape, with a margin of aClearance a collision.
VECTOR2_TRAITS< int32_t >::extended_type extended_type
Definition: vector2d.h:73
const SHAPE * defaultShapeFunctor(const T aItem)
~SHAPE_ENTRY()
BOX2I bbox
SHAPE_ENTRY(T aParent)
T parent
const SHAPE * shape