KiCad PCB EDA Suite
shape_collisions.cpp
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  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * as published by the Free Software Foundation; either version 2
10  * of the License, or (at your option) any later version.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, you may find one here:
19  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
20  * or you may search the http://www.gnu.org website for the version 2 license,
21  * or you may write to the Free Software Foundation, Inc.,
22  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
23  */
24 
25 
26 #include <assert.h> // for assert
27 #include <cmath>
28 #include <limits.h> // for INT_MAX
29 
30 #include <geometry/seg.h> // for SEG
31 #include <geometry/shape.h>
32 #include <geometry/shape_arc.h>
34 #include <geometry/shape_circle.h>
35 #include <geometry/shape_rect.h>
36 #include <geometry/shape_segment.h>
37 #include <geometry/shape_simple.h>
39 #include <math/vector2d.h>
40 
42 
43 static inline bool Collide( const SHAPE_CIRCLE& aA, const SHAPE_CIRCLE& aB, int aClearance,
44  int* aActual, VECTOR2I* aMTV )
45 {
46  ecoord min_dist = aClearance + aA.GetRadius() + aB.GetRadius();
47  ecoord min_dist_sq = min_dist * min_dist;
48 
49  const VECTOR2I delta = aB.GetCenter() - aA.GetCenter();
50 
51  ecoord dist_sq = delta.SquaredEuclideanNorm();
52 
53  if( dist_sq >= min_dist_sq )
54  return false;
55 
56  if( aActual )
57  *aActual = std::max( 0, (int) sqrt( dist_sq ) - aA.GetRadius() - aB.GetRadius() );
58 
59  if( aMTV )
60  *aMTV = delta.Resize( min_dist - sqrt( dist_sq ) + 3 ); // fixme: apparent rounding error
61 
62  return true;
63 }
64 
65 
66 static inline bool Collide( const SHAPE_RECT& aA, const SHAPE_CIRCLE& aB, int aClearance,
67  int* aActual, VECTOR2I* aMTV )
68 {
69  const VECTOR2I c = aB.GetCenter();
70  const VECTOR2I p0 = aA.GetPosition();
71  const VECTOR2I size = aA.GetSize();
72  const int r = aB.GetRadius();
73  const int min_dist = aClearance + r;
74  const ecoord min_dist_sq = (ecoord) min_dist * min_dist;
75 
76  const VECTOR2I vts[] =
77  {
78  VECTOR2I( p0.x, p0.y ),
79  VECTOR2I( p0.x, p0.y + size.y ),
80  VECTOR2I( p0.x + size.x, p0.y + size.y ),
81  VECTOR2I( p0.x + size.x, p0.y ),
82  VECTOR2I( p0.x, p0.y )
83  };
84 
85  ecoord nearest_side_dist_sq = VECTOR2I::ECOORD_MAX;
86  VECTOR2I nearest;
87 
88  bool inside = c.x >= p0.x && c.x <= ( p0.x + size.x )
89  && c.y >= p0.y && c.y <= ( p0.y + size.y );
90 
91  // If we're not looking for MTV, short-circuit once we find a hard collision
92  if( !aMTV && inside )
93  {
94  if( aActual )
95  *aActual = 0;
96 
97  return true;
98  }
99 
100  for( int i = 0; i < 4; i++ )
101  {
102  const SEG side( vts[i], vts[ i + 1] );
103 
104  VECTOR2I pn = side.NearestPoint( c );
105  ecoord side_dist_sq = ( pn - c ).SquaredEuclideanNorm();
106 
107  // If we're not looking for MTV or actual, short-circuit once we find any collision
108  if( !aMTV && !aActual && ( side_dist_sq == 0 || side_dist_sq < min_dist_sq ) )
109  return true;
110 
111  if( side_dist_sq < nearest_side_dist_sq )
112  {
113  nearest = pn;
114  nearest_side_dist_sq = side_dist_sq;
115  }
116  }
117 
118  if( !inside && nearest_side_dist_sq >= min_dist_sq )
119  return false;
120 
121  VECTOR2I delta = c - nearest;
122 
123  if( aActual )
124  *aActual = std::max( 0, (int) sqrt( nearest_side_dist_sq ) - r );
125 
126  if( aMTV )
127  {
128  if( inside )
129  *aMTV = -delta.Resize( abs( min_dist + 1 + sqrt( nearest_side_dist_sq ) ) + 1 );
130  else
131  *aMTV = delta.Resize( abs( min_dist + 1 - sqrt( nearest_side_dist_sq ) ) + 1 );
132  }
133 
134 
135  return true;
136 }
137 
138 
139 static VECTOR2I pushoutForce( const SHAPE_CIRCLE& aA, const SEG& aB, int aClearance )
140 {
141  VECTOR2I f( 0, 0 );
142 
143  const VECTOR2I c = aA.GetCenter();
144  const VECTOR2I nearest = aB.NearestPoint( c );
145 
146  const int r = aA.GetRadius();
147 
148  int dist = ( nearest - c ).EuclideanNorm();
149  int min_dist = aClearance + r;
150 
151  if( dist < min_dist )
152  {
153  for( int corr = 0; corr < 5; corr++ )
154  {
155  f = ( aA.GetCenter() - nearest ).Resize( min_dist - dist + corr );
156 
157  if( aB.Distance( c + f ) >= min_dist )
158  break;
159  }
160  }
161 
162  return f;
163 }
164 
165 #if 0
166 static inline bool Collide( const SHAPE_CIRCLE& aA, const SHAPE_LINE_CHAIN_BASE& aB, int aClearance,
167  int* aActual, VECTOR2I* aMTV )
168 {
169  bool collided = false;
170 
171  for( int s = 0; s < aB.GetSegmentCount(); s++ )
172  {
173  if( aA.Collide( aB.GetSegment( s ), aClearance, aActual ) )
174  {
175  collided = true;
176  break;
177  }
178  }
179 
180  if( !collided )
181  return false;
182 
183  if( aMTV )
184  {
185  SHAPE_CIRCLE cmoved( aA );
186  VECTOR2I f_total( 0, 0 );
187 
188  for( int s = 0; s < aB.GetSegmentCount(); s++ )
189  {
190  VECTOR2I f = pushoutForce( cmoved, aB.GetSegment( s ), aClearance );
191  cmoved.SetCenter( cmoved.GetCenter() + f );
192  f_total += f;
193  }
194 
195  *aMTV = f_total;
196  }
197 
198  return true;
199 }
200 #endif
201 
202 static inline bool Collide( const SHAPE_CIRCLE& aA, const SHAPE_LINE_CHAIN_BASE& aB, int aClearance,
203  int* aActual, VECTOR2I* aMTV )
204 {
205  int min_dist = aClearance + aA.GetRadius();
206  ecoord dist_sq = aB.SquaredDistance( aA.GetCenter() );
207 
208  if( dist_sq > (ecoord) min_dist * min_dist )
209  return false;
210 
211  if( aActual )
212  *aActual = std::max( 0, (int) sqrt( dist_sq ) - aA.GetRadius() );
213 
214  if( aMTV )
215  {
216  SHAPE_CIRCLE cmoved( aA );
217  VECTOR2I f_total( 0, 0 );
218 
219  for( int s = 0; s < aB.GetSegmentCount(); s++ )
220  {
221  VECTOR2I f = pushoutForce( cmoved, aB.GetSegment( s ), aClearance );
222  cmoved.SetCenter( cmoved.GetCenter() + f );
223  f_total += f;
224  }
225 
226  *aMTV = f_total;
227  }
228  return true;
229 }
230 
231 
232 static inline bool Collide( const SHAPE_CIRCLE& aA, const SHAPE_SEGMENT& aSeg, int aClearance,
233  int* aActual, VECTOR2I* aMTV )
234 {
235  if( !aA.Collide( aSeg.GetSeg(), aClearance + aSeg.GetWidth() / 2, aActual ) )
236  return false;
237 
238  if( aMTV )
239  *aMTV = -pushoutForce( aA, aSeg.GetSeg(), aClearance + aSeg.GetWidth() / 2);
240 
241  return true;
242 }
243 
244 
245 static inline bool Collide( const SHAPE_LINE_CHAIN_BASE& aA, const SHAPE_LINE_CHAIN_BASE& aB, int aClearance,
246  int* aActual, VECTOR2I* aMTV )
247 {
248  // TODO: why doesn't this handle MTV?
249  // TODO: worse, why this doesn't handle closed shapes?
250 
251  for( int i = 0; i < aB.GetSegmentCount(); i++ )
252  {
253  if( aA.Collide( aB.GetSegment( i ), aClearance, aActual ) )
254  return true;
255  }
256 
257  return false;
258 }
259 
260 
261 static inline bool Collide( const SHAPE_RECT& aA, const SHAPE_LINE_CHAIN_BASE& aB, int aClearance,
262  int* aActual, VECTOR2I* aMTV )
263 {
264  int minActual = INT_MAX;
265  int actual;
266 
267  for( int s = 0; s < aB.GetSegmentCount(); s++ )
268  {
269  if( aA.Collide( aB.GetSegment( s ), aClearance, &actual ) )
270  {
271  minActual = std::min( minActual, actual );
272 
273  // If we're not looking for MTV or Actual, short-circuit after any collision
274  if( !aActual && !aMTV )
275  return true;
276  }
277  }
278 
279  if( aActual )
280  *aActual = std::max( 0, minActual );
281 
282  // TODO: why doesn't this handle MTV?
283 
284  return minActual < INT_MAX;
285 }
286 
287 
288 static inline bool Collide( const SHAPE_RECT& aA, const SHAPE_SEGMENT& aSeg, int aClearance,
289  int* aActual, VECTOR2I* aMTV )
290 {
291  int actual;
292 
293  if( aA.Collide( aSeg.GetSeg(), aClearance + aSeg.GetWidth() / 2, &actual ) )
294  {
295  if( aActual )
296  *aActual = std::max( 0, actual - aSeg.GetWidth() / 2 );
297 
298  // TODO: why doesn't this handle MTV?
299 
300  return true;
301  }
302 
303  return false;
304 }
305 
306 
307 static inline bool Collide( const SHAPE_SEGMENT& aA, const SHAPE_SEGMENT& aB, int aClearance,
308  int* aActual, VECTOR2I* aMTV )
309 {
310  int actual;
311 
312  if( aA.Collide( aB.GetSeg(), aClearance + aB.GetWidth() / 2, &actual ) )
313  {
314  if( aActual )
315  *aActual = std::max( 0, actual - aB.GetWidth() / 2 );
316 
317  // TODO: why doesn't this handle MTV?
318 
319  return true;
320  }
321 
322  return false;
323 }
324 
325 
326 static inline bool Collide( const SHAPE_LINE_CHAIN_BASE& aA, const SHAPE_SEGMENT& aB, int aClearance,
327  int* aActual, VECTOR2I* aMTV )
328 {
329  int actual;
330 
331  if( aA.Collide( aB.GetSeg(), aClearance + aB.GetWidth() / 2, &actual ) )
332  {
333  if( aActual )
334  *aActual = std::max( 0, actual - aB.GetWidth() / 2 );
335 
336  // TODO: why doesn't this handle MTV?
337 
338  return true;
339  }
340 
341  return false;
342 }
343 
344 
345 static inline bool Collide( const SHAPE_RECT& aA, const SHAPE_RECT& aB, int aClearance,
346  int* aActual, VECTOR2I* aMTV )
347 {
348  return Collide( aA.Outline(), aB.Outline(), aClearance, aActual, aMTV );
349 }
350 
351 static inline bool Collide( const SHAPE_ARC& aA, const SHAPE_RECT& aB, int aClearance,
352  int* aActual, VECTOR2I* aMTV )
353 {
354  const auto lc = aA.ConvertToPolyline();
355  return Collide( lc, aB.Outline(), aClearance, aActual, aMTV );
356 }
357 
358 static inline bool Collide( const SHAPE_ARC& aA, const SHAPE_CIRCLE& aB, int aClearance,
359  int* aActual, VECTOR2I* aMTV )
360 {
361  const auto lc = aA.ConvertToPolyline();
362  bool rv = Collide( aB, lc, aClearance, aActual, aMTV );
363 
364  if( rv && aMTV )
365  *aMTV = - *aMTV ;
366 
367  return rv;
368 }
369 
370 static inline bool Collide( const SHAPE_ARC& aA, const SHAPE_LINE_CHAIN& aB, int aClearance,
371  int* aActual, VECTOR2I* aMTV )
372 {
373  const auto lc = aA.ConvertToPolyline();
374  return Collide( lc, aB, aClearance, aActual, aMTV );
375 }
376 
377 static inline bool Collide( const SHAPE_ARC& aA, const SHAPE_SEGMENT& aB, int aClearance,
378  int* aActual, VECTOR2I* aMTV )
379 {
380  const auto lc = aA.ConvertToPolyline();
381  return Collide( lc, aB, aClearance, aActual, aMTV );
382 }
383 
384 static inline bool Collide( const SHAPE_ARC& aA, const SHAPE_LINE_CHAIN_BASE& aB, int aClearance,
385  int* aActual, VECTOR2I* aMTV )
386 {
387  const auto lc = aA.ConvertToPolyline();
388 
389  return Collide( lc, aB, aClearance, aActual, aMTV );
390 }
391 
392 static inline bool Collide( const SHAPE_ARC& aA, const SHAPE_ARC& aB, int aClearance,
393  int* aActual, VECTOR2I* aMTV )
394 {
395  const auto lcA = aA.ConvertToPolyline();
396  const auto lcB = aB.ConvertToPolyline();
397  return Collide( lcA, lcB, aClearance, aActual, aMTV );
398 }
399 
400 template<class T_a, class T_b>
401 inline bool CollCase( const SHAPE* aA, const SHAPE* aB, int aClearance, int* aActual,
402  VECTOR2I* aMTV )
403 
404 {
405  return Collide( *static_cast<const T_a*>( aA ), *static_cast<const T_b*>( aB ),
406  aClearance, aActual, aMTV);
407 }
408 
409 template<class T_a, class T_b>
410 inline bool CollCaseReversed ( const SHAPE* aA, const SHAPE* aB, int aClearance, int* aActual,
411  VECTOR2I* aMTV )
412 {
413  bool rv = Collide( *static_cast<const T_b*>( aB ), *static_cast<const T_a*>( aA ),
414  aClearance, aActual, aMTV);
415 
416  if( rv && aMTV)
417  *aMTV = - *aMTV;
418 
419  return rv;
420 }
421 
422 
423 static bool collideSingleShapes( const SHAPE* aA, const SHAPE* aB, int aClearance, int* aActual, VECTOR2I* aMTV )
424 {
425 
426 
427  switch( aA->Type() )
428  {
429  case SH_NULL:
430  return false;
431 
432  case SH_RECT:
433  switch( aB->Type() )
434  {
435  case SH_RECT:
436  return CollCase<SHAPE_RECT, SHAPE_RECT>( aA, aB, aClearance, aActual, aMTV );
437 
438  case SH_CIRCLE:
439  return CollCase<SHAPE_RECT, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aMTV );
440 
441  case SH_LINE_CHAIN:
442  return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aMTV );
443 
444  case SH_SEGMENT:
445  return CollCase<SHAPE_RECT, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aMTV );
446 
447  case SH_SIMPLE:
449  return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aMTV );
450 
451  case SH_ARC:
452  return CollCaseReversed<SHAPE_RECT, SHAPE_ARC>( aA, aB, aClearance, aActual, aMTV );
453 
454  case SH_NULL:
455  return false;
456 
457  default:
458  break;
459  }
460  break;
461 
462  case SH_CIRCLE:
463  switch( aB->Type() )
464  {
465  case SH_RECT:
466  return CollCaseReversed<SHAPE_CIRCLE, SHAPE_RECT>( aA, aB, aClearance, aActual, aMTV );
467 
468  case SH_CIRCLE:
469  return CollCase<SHAPE_CIRCLE, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aMTV );
470 
471  case SH_LINE_CHAIN:
472  return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aMTV );
473 
474  case SH_SEGMENT:
475  return CollCase<SHAPE_CIRCLE, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aMTV );
476 
477  case SH_SIMPLE:
479  return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aMTV );
480 
481  case SH_ARC:
482  return CollCaseReversed<SHAPE_CIRCLE, SHAPE_ARC>( aA, aB, aClearance, aActual, aMTV );
483 
484  case SH_NULL:
485  return false;
486 
487  default:
488  break;
489  }
490  break;
491 
492  case SH_LINE_CHAIN:
493  switch( aB->Type() )
494  {
495  case SH_RECT:
496  return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN>( aB, aA, aClearance, aActual, aMTV );
497 
498  case SH_CIRCLE:
499  return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN>( aB, aA, aClearance, aActual, aMTV );
500 
501  case SH_LINE_CHAIN:
502  return CollCase<SHAPE_LINE_CHAIN, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aMTV );
503 
504  case SH_SEGMENT:
505  return CollCase<SHAPE_LINE_CHAIN, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aMTV );
506 
507  case SH_SIMPLE:
509  return CollCase<SHAPE_LINE_CHAIN, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aMTV );
510 
511  case SH_ARC:
512  return CollCaseReversed<SHAPE_LINE_CHAIN, SHAPE_ARC>( aA, aB, aClearance, aActual, aMTV );
513 
514  case SH_NULL:
515  return false;
516 
517  default:
518  break;
519  }
520  break;
521 
522  case SH_SEGMENT:
523  switch( aB->Type() )
524  {
525  case SH_RECT:
526  return CollCase<SHAPE_RECT, SHAPE_SEGMENT>( aB, aA, aClearance, aActual, aMTV );
527 
528  case SH_CIRCLE:
529  return CollCaseReversed<SHAPE_SEGMENT, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aMTV );
530 
531  case SH_LINE_CHAIN:
532  return CollCase<SHAPE_LINE_CHAIN, SHAPE_SEGMENT>( aB, aA, aClearance, aActual, aMTV );
533 
534  case SH_SEGMENT:
535  return CollCase<SHAPE_SEGMENT, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aMTV );
536 
537  case SH_SIMPLE:
539  return CollCase<SHAPE_LINE_CHAIN_BASE, SHAPE_SEGMENT>( aB, aA, aClearance, aActual, aMTV );
540 
541  case SH_ARC:
542  return CollCaseReversed<SHAPE_SEGMENT, SHAPE_ARC>( aA, aB, aClearance, aActual, aMTV );
543 
544  case SH_NULL:
545  return false;
546 
547  default:
548  break;
549  }
550  break;
551 
552  case SH_SIMPLE:
554  switch( aB->Type() )
555  {
556  case SH_RECT:
557  return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN_BASE>( aB, aA, aClearance, aActual, aMTV );
558 
559  case SH_CIRCLE:
560  return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN_BASE>( aB, aA, aClearance, aActual, aMTV );
561 
562  case SH_LINE_CHAIN:
563  return CollCase<SHAPE_LINE_CHAIN, SHAPE_LINE_CHAIN_BASE>( aB, aA, aClearance, aActual, aMTV );
564 
565  case SH_SEGMENT:
566  return CollCase<SHAPE_LINE_CHAIN_BASE, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aMTV );
567 
568  case SH_SIMPLE:
570  return CollCase<SHAPE_LINE_CHAIN_BASE, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aMTV );
571 
572  case SH_ARC:
573  return CollCaseReversed<SHAPE_LINE_CHAIN_BASE, SHAPE_ARC>( aA, aB, aClearance, aActual, aMTV );
574 
575  case SH_NULL:
576  return false;
577 
578  default:
579  break;
580  }
581  break;
582 
583  case SH_ARC:
584  switch( aB->Type() )
585  {
586  case SH_RECT:
587  return CollCase<SHAPE_ARC, SHAPE_RECT>( aA, aB, aClearance, aActual, aMTV );
588 
589  case SH_CIRCLE:
590  return CollCase<SHAPE_ARC, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aMTV );
591 
592  case SH_LINE_CHAIN:
593  return CollCase<SHAPE_ARC, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aMTV );
594 
595  case SH_SEGMENT:
596  return CollCase<SHAPE_ARC, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aMTV );
597 
598  case SH_SIMPLE:
600  return CollCase<SHAPE_ARC, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aMTV );
601 
602  case SH_ARC:
603  return CollCase<SHAPE_ARC, SHAPE_ARC>( aA, aB, aClearance, aActual, aMTV );
604 
605  case SH_NULL:
606  return false;
607 
608  default:
609  break;
610  }
611  break;
612 
613  default:
614  break;
615  }
616 
617  bool unsupported_collision = true;
618  (void) unsupported_collision; // make gcc quiet
619 
620  assert( unsupported_collision == false );
621 
622  return false;
623 }
624 
625 static bool collideShapes( const SHAPE* aA, const SHAPE* aB, int aClearance, int* aActual, VECTOR2I* aMTV )
626 {
627  int currentActual = std::numeric_limits<int>::max();
628  VECTOR2I currentMTV(0, 0);
629  bool colliding = false;
630 
631  bool exitOnFirstCollision = aActual == nullptr && aMTV == nullptr;
632 
633  auto collideCompoundSubshapes = [&] ( const SHAPE* elemA, const SHAPE* elemB, int clearance ) -> bool
634  {
635  int actual;
636  VECTOR2I mtv;
637 
638  bool c = collideSingleShapes( elemA, elemB,
639  clearance,
640  aActual ? &actual : nullptr,
641  aMTV ? &mtv : nullptr );
642  if(c)
643  {
644  if (aActual)
645  {
646  currentActual = std::min( actual, currentActual );
647  }
648  if( aMTV )
649  {
650  if( mtv.SquaredEuclideanNorm() > currentMTV.SquaredEuclideanNorm() )
651  currentMTV = mtv;
652  }
653  }
654 
655  return c;
656  };
657 
658  if (aA->Type() == SH_COMPOUND && aB->Type() == SH_COMPOUND )
659  {
660  auto cmpA = static_cast<const SHAPE_COMPOUND*>( aA );
661  auto cmpB = static_cast<const SHAPE_COMPOUND*>( aB );
662 
663  for( auto elemA : cmpA->Shapes() )
664  {
665  for( auto elemB : cmpB->Shapes() )
666  {
667  if( collideCompoundSubshapes( elemA, elemB, aClearance ) )
668  {
669  colliding = true;
670  if ( exitOnFirstCollision )
671  break;
672  }
673  }
674  if( colliding && exitOnFirstCollision )
675  break;
676  }
677  }
678  else if ( aA->Type() == SH_COMPOUND )
679  {
680  auto cmpA = static_cast<const SHAPE_COMPOUND*>( aA );
681  for( auto elemA : cmpA->Shapes() )
682  {
683  if( collideCompoundSubshapes( elemA, aB, aClearance ) )
684  {
685  colliding = true;
686  if ( exitOnFirstCollision )
687  break;
688  }
689  }
690  }
691  else if ( aB->Type() == SH_COMPOUND )
692  {
693  auto cmpB = static_cast<const SHAPE_COMPOUND*>( aB );
694  for( auto elemB : cmpB->Shapes() )
695  {
696  if( collideCompoundSubshapes( aA, elemB, aClearance ) )
697  {
698  colliding = true;
699  if ( exitOnFirstCollision )
700  break;
701  }
702  }
703  }
704  else
705  {
706  return collideSingleShapes( aA, aB, aClearance, aActual, aMTV );
707  }
708 
709  if( colliding )
710  {
711  if( aActual )
712  *aActual = currentActual;
713  if( aMTV )
714  *aMTV = currentMTV;
715  }
716 
717  return colliding;
718 }
719 
720 bool SHAPE::Collide( const SHAPE* aShape, int aClearance, VECTOR2I* aMTV ) const
721 {
722  return collideShapes( this, aShape, aClearance, nullptr, aMTV );
723 }
724 
725 
726 bool SHAPE::Collide( const SHAPE* aShape, int aClearance, int* aActual ) const
727 {
728  return collideShapes( this, aShape, aClearance, aActual, nullptr );
729 }
730 
731 
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:133
VECTOR2_TRAITS< int >::extended_type extended_type
Definition: vector2d.h:77
set of polygons (with holes, etc.)
Definition: shape.h:48
bool Collide(const SEG &aSeg, int aClearance=0, int *aActual=nullptr) const override
Function Collide()
Definition: shape_circle.h:68
bool Collide(const SHAPE *aShape, int aClearance, VECTOR2I *aMTV) const override
Function Collide()
Definition: shape_rect.h:93
void SetCenter(const VECTOR2I &aCenter)
Definition: shape_circle.h:89
static bool Collide(const SHAPE_CIRCLE &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:207
const SHAPE_LINE_CHAIN Outline() const
Definition: shape_rect.h:174
int GetRadius() const
Definition: shape_circle.h:94
SEG::ecoord SquaredDistance(const VECTOR2I &aP, bool aOutlineOnly=false) const
VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:61
extended_type SquaredEuclideanNorm() const
Function Squared Euclidean Norm computes the squared euclidean norm of the vector,...
Definition: vector2d.h:306
const VECTOR2I GetCenter() const
Definition: shape_circle.h:99
virtual size_t GetSegmentCount() const =0
static bool collideSingleShapes(const SHAPE *aA, const SHAPE *aB, int aClearance, int *aActual, VECTOR2I *aMTV)
VECTOR2< int > VECTOR2I
Definition: vector2d.h:594
const SEG & GetSeg() const
const VECTOR2I GetSize() const
Function GetSize()
Definition: shape_rect.h:121
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:80
bool CollCase(const SHAPE *aA, const SHAPE *aB, int aClearance, int *aActual, VECTOR2I *aMTV)
const VECTOR2I & GetPosition() const
Function GetPosition()
Definition: shape_rect.h:111
VECTOR2I::extended_type ecoord
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
Definition: seg.h:395
compound shape, consisting of multiple simple shapes
Definition: shape.h:49
bool CollCaseReversed(const SHAPE *aA, const SHAPE *aB, int aClearance, int *aActual, VECTOR2I *aMTV)
SHAPE.
Definition: shape.h:120
static VECTOR2I pushoutForce(const SHAPE_CIRCLE &aA, const SEG &aB, int aClearance)
line chain (polyline)
Definition: shape.h:45
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr) const override
Function Collide()
Definition: seg.h:39
virtual const SEG GetSegment(int aIndex) const =0
VECTOR2< T > Resize(T aNewLength) const
Function Resize returns a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:392
empty shape (no shape...),
Definition: shape.h:51
static bool collideShapes(const SHAPE *aA, const SHAPE *aB, int aClearance, int *aActual, VECTOR2I *aMTV)
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr) const
Function Collide()
Definition: shape.h:172
SHAPE_LINE_CHAIN.
circular arc
Definition: shape.h:50
line segment
Definition: shape.h:44
Definition: shape.h:42
int GetWidth() const
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=500.0) const
Constructs a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:231
bool Collide(const SHAPE *aShape, int aClearance, VECTOR2I *aMTV) const override
Function Collide()
Definition: shape_segment.h:59
circle
Definition: shape.h:46
SHAPE_TYPE Type() const
Function Type()
Definition: shape.h:96
axis-aligned rectangle
Definition: shape.h:43