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  * Copyright (C) 2015-2020 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 #include <cmath>
27 #include <limits.h> // for INT_MAX
28 
29 #include <geometry/seg.h> // for SEG
30 #include <geometry/shape.h>
31 #include <geometry/shape_arc.h>
33 #include <geometry/shape_circle.h>
34 #include <geometry/shape_rect.h>
35 #include <geometry/shape_segment.h>
37 #include <math/vector2d.h>
38 
40 
41 
42 static inline bool Collide( const SHAPE_CIRCLE& aA, const SHAPE_CIRCLE& aB, int aClearance,
43  int* aActual, VECTOR2I* aLocation, VECTOR2I* aMTV )
44 {
45  ecoord min_dist = aClearance + aA.GetRadius() + aB.GetRadius();
46  ecoord min_dist_sq = min_dist * min_dist;
47 
48  const VECTOR2I delta = aB.GetCenter() - aA.GetCenter();
49  ecoord dist_sq = delta.SquaredEuclideanNorm();
50 
51  if( dist_sq == 0 || dist_sq < min_dist_sq )
52  {
53  if( aActual )
54  *aActual = std::max( 0, (int) sqrt( dist_sq ) - aA.GetRadius() - aB.GetRadius() );
55 
56  if( aLocation )
57  *aLocation = ( aA.GetCenter() + aB.GetCenter() ) / 2;
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  return false;
66 }
67 
68 
69 static inline bool Collide( const SHAPE_RECT& aA, const SHAPE_CIRCLE& aB, int aClearance,
70  int* aActual, VECTOR2I* aLocation, VECTOR2I* aMTV )
71 {
72  const VECTOR2I c = aB.GetCenter();
73  const VECTOR2I p0 = aA.GetPosition();
74  const VECTOR2I size = aA.GetSize();
75  const int r = aB.GetRadius();
76  const int min_dist = aClearance + r;
77  const ecoord min_dist_sq = SEG::Square( min_dist );
78 
79  const VECTOR2I vts[] =
80  {
81  VECTOR2I( p0.x, p0.y ),
82  VECTOR2I( p0.x, p0.y + size.y ),
83  VECTOR2I( p0.x + size.x, p0.y + size.y ),
84  VECTOR2I( p0.x + size.x, p0.y ),
85  VECTOR2I( p0.x, p0.y )
86  };
87 
88  ecoord nearest_side_dist_sq = VECTOR2I::ECOORD_MAX;
89  VECTOR2I nearest;
90 
91  bool inside = c.x >= p0.x && c.x <= ( p0.x + size.x )
92  && c.y >= p0.y && c.y <= ( p0.y + size.y );
93 
94  // If we're not looking for MTV or actual, short-circuit once we find a hard collision
95  if( inside && !aActual && !aLocation && !aMTV )
96  return true;
97 
98  for( int i = 0; i < 4; i++ )
99  {
100  const SEG side( vts[i], vts[ i + 1] );
101 
102  VECTOR2I pn = side.NearestPoint( c );
103  ecoord side_dist_sq = ( pn - c ).SquaredEuclideanNorm();
104 
105  if( side_dist_sq < nearest_side_dist_sq )
106  {
107  nearest = pn;
108  nearest_side_dist_sq = side_dist_sq;
109 
110  if( aMTV )
111  continue;
112 
113  if( nearest_side_dist_sq == 0 )
114  break;
115 
116  // If we're not looking for aActual then any collision will do
117  if( nearest_side_dist_sq < min_dist_sq && !aActual )
118  break;
119  }
120  }
121 
122  if( inside || nearest_side_dist_sq == 0 || nearest_side_dist_sq < min_dist_sq )
123  {
124  if( aLocation )
125  *aLocation = nearest;
126 
127  if( aActual )
128  *aActual = std::max( 0, (int) sqrt( nearest_side_dist_sq ) - r );
129 
130  if( aMTV )
131  {
132  VECTOR2I delta = c - nearest;
133 
134  if( inside )
135  *aMTV = -delta.Resize( abs( min_dist + 1 + sqrt( nearest_side_dist_sq ) ) + 1 );
136  else
137  *aMTV = delta.Resize( abs( min_dist + 1 - sqrt( nearest_side_dist_sq ) ) + 1 );
138  }
139 
140  return true;
141  }
142 
143  return false;
144 }
145 
146 
147 static VECTOR2I pushoutForce( const SHAPE_CIRCLE& aA, const SEG& aB, int aClearance )
148 {
149  VECTOR2I f( 0, 0 );
150 
151  const VECTOR2I c = aA.GetCenter();
152  const VECTOR2I nearest = aB.NearestPoint( c );
153 
154  const int r = aA.GetRadius();
155 
156  int dist = ( nearest - c ).EuclideanNorm();
157  int min_dist = aClearance + r;
158 
159  if( dist < min_dist )
160  {
161  for( int corr = 0; corr < 5; corr++ )
162  {
163  f = ( aA.GetCenter() - nearest ).Resize( min_dist - dist + corr );
164 
165  if( aB.Distance( c + f ) >= min_dist )
166  break;
167  }
168  }
169 
170  return f;
171 }
172 
173 
174 static inline bool Collide( const SHAPE_CIRCLE& aA, const SHAPE_LINE_CHAIN_BASE& aB,
175  int aClearance, int* aActual, VECTOR2I* aLocation, VECTOR2I* aMTV )
176 {
177  int closest_dist = INT_MAX;
178  int closest_mtv_dist = INT_MAX;
179  VECTOR2I nearest;
180  int closest_mtv_seg = -1;
181 
182  if( aB.IsClosed() && aB.PointInside( aA.GetCenter() ) )
183  {
184  nearest = aA.GetCenter();
185  closest_dist = 0;
186 
187  if( aMTV )
188  {
189  for( int s = 0; s < aB.GetSegmentCount(); s++ )
190  {
191  int dist = aB.GetSegment(s).Distance( aA.GetCenter() );
192 
193  if( dist < closest_mtv_dist )
194  {
195  closest_mtv_dist = dist;
196  closest_mtv_seg = s;
197  }
198  }
199  }
200 
201  }
202  else
203  {
204  for( size_t s = 0; s < aB.GetSegmentCount(); s++ )
205  {
206  int collision_dist = 0;
207  VECTOR2I pn;
208 
209  if( aA.Collide( aB.GetSegment( s ), aClearance,
210  aActual || aLocation ? &collision_dist : nullptr,
211  aLocation ? &pn : nullptr ) )
212  {
213  if( collision_dist < closest_dist )
214  {
215  nearest = pn;
216  closest_dist = collision_dist;
217  }
218 
219  if( closest_dist == 0 )
220  break;
221 
222  // If we're not looking for aActual then any collision will do
223  if( !aActual )
224  break;
225  }
226  }
227  }
228 
229  if( closest_dist == 0 || closest_dist < aClearance )
230  {
231  if( aLocation )
232  *aLocation = nearest;
233 
234  if( aActual )
235  *aActual = closest_dist;
236 
237  if( aMTV )
238  {
239  SHAPE_CIRCLE cmoved( aA );
240  VECTOR2I f_total( 0, 0 );
241 
242  VECTOR2I f;
243 
244  if (closest_mtv_seg >= 0)
245  {
246  SEG cs = aB.GetSegment( closest_mtv_seg );
247  VECTOR2I np = cs.NearestPoint( aA.GetCenter() );
248  f = ( np - aA.GetCenter() ) + ( np - aA.GetCenter() ).Resize( aA.GetRadius() );
249  }
250 
251  cmoved.SetCenter( cmoved.GetCenter() + f );
252  f_total += f;
253 
254  for( int s = 0; s < aB.GetSegmentCount(); s++ )
255  {
256  VECTOR2I f = pushoutForce( cmoved, aB.GetSegment( s ), aClearance );
257  cmoved.SetCenter( cmoved.GetCenter() + f );
258  f_total += f;
259  }
260 
261  *aMTV = f_total;
262  }
263 
264  return true;
265  }
266 
267  return false;
268 }
269 
270 
271 static inline bool Collide( const SHAPE_CIRCLE& aA, const SHAPE_SEGMENT& aSeg, int aClearance,
272  int* aActual, VECTOR2I* aLocation, VECTOR2I* aMTV )
273 {
274  if( aA.Collide( aSeg.GetSeg(), aClearance + aSeg.GetWidth() / 2, aActual, aLocation ) )
275  {
276  if( aMTV )
277  *aMTV = -pushoutForce( aA, aSeg.GetSeg(), aClearance + aSeg.GetWidth() / 2);
278 
279  if( aActual )
280  *aActual = std::max( 0, *aActual - aSeg.GetWidth() / 2 );
281 
282  return true;
283  }
284 
285  return false;
286 }
287 
288 
289 static inline bool Collide( const SHAPE_LINE_CHAIN_BASE& aA, const SHAPE_LINE_CHAIN_BASE& aB,
290  int aClearance, int* aActual, VECTOR2I* aLocation, VECTOR2I* aMTV )
291 {
292  wxASSERT_MSG( !aMTV, wxString::Format( "MTV not implemented for %s : %s collisions",
293  aA.Type(),
294  aB.Type() ) );
295 
296  int closest_dist = INT_MAX;
297  VECTOR2I nearest;
298 
299  if( aB.IsClosed() && aA.GetPointCount() > 0 && aB.PointInside( aA.GetPoint( 0 ) ) )
300  {
301  closest_dist = 0;
302  nearest = aA.GetPoint( 0 );
303  }
304  else
305  {
306  for( size_t i = 0; i < aB.GetSegmentCount(); i++ )
307  {
308  int collision_dist = 0;
309  VECTOR2I pn;
310 
311  if( aA.Collide( aB.GetSegment( i ), aClearance,
312  aActual || aLocation ? &collision_dist : nullptr,
313  aLocation ? &pn : nullptr ) )
314  {
315  if( collision_dist < closest_dist )
316  {
317  nearest = pn;
318  closest_dist = collision_dist;
319  }
320 
321  if( closest_dist == 0 )
322  break;
323 
324  // If we're not looking for aActual then any collision will do
325  if( !aActual )
326  break;
327  }
328  }
329  }
330 
331  if( closest_dist == 0 || closest_dist < aClearance )
332  {
333  if( aLocation )
334  *aLocation = nearest;
335 
336  if( aActual )
337  *aActual = closest_dist;
338 
339  return true;
340  }
341 
342  return false;
343 }
344 
345 
346 static inline bool Collide( const SHAPE_RECT& aA, const SHAPE_LINE_CHAIN_BASE& aB, int aClearance,
347  int* aActual, VECTOR2I* aLocation, VECTOR2I* aMTV )
348 {
349  wxASSERT_MSG( !aMTV, wxString::Format( "MTV not implemented for %s : %s collisions",
350  aA.Type(),
351  aB.Type() ) );
352 
353  int closest_dist = INT_MAX;
354  VECTOR2I nearest;
355 
356  if( aB.IsClosed() && aB.PointInside( aA.Centre() ) )
357  {
358  nearest = aA.Centre();
359  closest_dist = 0;
360  }
361  else
362  {
363  for( size_t s = 0; s < aB.GetSegmentCount(); s++ )
364  {
365  int collision_dist = 0;
366  VECTOR2I pn;
367 
368  if( aA.Collide( aB.GetSegment( s ), aClearance,
369  aActual || aLocation ? &collision_dist : nullptr,
370  aLocation ? &pn : nullptr ) )
371  {
372  if( collision_dist < closest_dist )
373  {
374  nearest = pn;
375  closest_dist = collision_dist;
376  }
377 
378  if( closest_dist == 0 )
379  break;
380 
381  // If we're not looking for aActual then any collision will do
382  if( !aActual )
383  break;
384  }
385  }
386  }
387 
388  if( closest_dist == 0 || closest_dist < aClearance )
389  {
390  if( aLocation )
391  *aLocation = nearest;
392 
393  if( aActual )
394  *aActual = closest_dist;
395 
396  return true;
397  }
398 
399  return false;
400 }
401 
402 
403 static inline bool Collide( const SHAPE_RECT& aA, const SHAPE_SEGMENT& aB, int aClearance,
404  int* aActual, VECTOR2I* aLocation, VECTOR2I* aMTV )
405 {
406  wxASSERT_MSG( !aMTV, wxString::Format( "MTV not implemented for %s : %s collisions",
407  aA.Type(),
408  aB.Type() ) );
409 
410  bool rv = aA.Collide( aB.GetSeg(), aClearance + aB.GetWidth() / 2, aActual, aLocation );
411 
412  if( aActual )
413  *aActual = std::max( 0, *aActual - aB.GetWidth() / 2 );
414 
415  return rv;
416 }
417 
418 
419 static inline bool Collide( const SHAPE_SEGMENT& aA, const SHAPE_SEGMENT& aB, int aClearance,
420  int* aActual, VECTOR2I* aLocation, VECTOR2I* aMTV )
421 {
422  wxASSERT_MSG( !aMTV, wxString::Format( "MTV not implemented for %s : %s collisions",
423  aA.Type(),
424  aB.Type() ) );
425 
426  bool rv = aA.Collide( aB.GetSeg(), aClearance + aB.GetWidth() / 2, aActual, aLocation );
427 
428  if( aActual )
429  *aActual = std::max( 0, *aActual - aB.GetWidth() / 2 );
430 
431  return rv;
432 }
433 
434 
435 static inline bool Collide( const SHAPE_LINE_CHAIN_BASE& aA, const SHAPE_SEGMENT& aB,
436  int aClearance, int* aActual, VECTOR2I* aLocation, VECTOR2I* aMTV )
437 {
438  wxASSERT_MSG( !aMTV, wxString::Format( "MTV not implemented for %s : %s collisions",
439  aA.Type(),
440  aB.Type() ) );
441 
442  bool rv = aA.Collide( aB.GetSeg(), aClearance + aB.GetWidth() / 2, aActual, aLocation );
443 
444  if( aActual )
445  *aActual = std::max( 0, *aActual - aB.GetWidth() / 2 );
446 
447  return rv;
448 }
449 
450 
451 static inline bool Collide( const SHAPE_RECT& aA, const SHAPE_RECT& aB, int aClearance,
452  int* aActual, VECTOR2I* aLocation, VECTOR2I* aMTV )
453 {
454  return Collide( aA.Outline(), aB.Outline(), aClearance, aActual, aLocation, aMTV );
455 }
456 
457 
458 static inline bool Collide( const SHAPE_ARC& aA, const SHAPE_RECT& aB, int aClearance,
459  int* aActual, VECTOR2I* aLocation, VECTOR2I* aMTV )
460 {
461  wxASSERT_MSG( !aMTV, wxString::Format( "MTV not implemented for %s : %s collisions",
462  aA.Type(),
463  aB.Type() ) );
464 
465  const SHAPE_LINE_CHAIN lc = aA.ConvertToPolyline();
466 
467  bool rv = Collide( lc, aB.Outline(), aClearance + aA.GetWidth() / 2, aActual, aLocation, aMTV );
468 
469  if( rv && aActual )
470  *aActual = std::max( 0, *aActual - aA.GetWidth() / 2 );
471 
472  return rv;
473 }
474 
475 
476 static inline bool Collide( const SHAPE_ARC& aA, const SHAPE_CIRCLE& aB, int aClearance,
477  int* aActual, VECTOR2I* aLocation, VECTOR2I* aMTV )
478 {
479  wxASSERT_MSG( !aMTV, wxString::Format( "MTV not implemented for %s : %s collisions",
480  aA.Type(),
481  aB.Type() ) );
482 
483  const SHAPE_LINE_CHAIN lc = aA.ConvertToPolyline();
484 
485  bool rv = Collide( aB, lc, aClearance + aA.GetWidth() / 2, aActual, aLocation, aMTV );
486 
487  if( rv && aActual )
488  *aActual = std::max( 0, *aActual - aA.GetWidth() / 2 );
489 
490  return rv;
491 }
492 
493 
494 static inline bool Collide( const SHAPE_ARC& aA, const SHAPE_LINE_CHAIN& aB, int aClearance,
495  int* aActual, VECTOR2I* aLocation, VECTOR2I* aMTV )
496 {
497  wxASSERT_MSG( !aMTV, wxString::Format( "MTV not implemented for %s : %s collisions",
498  aA.Type(),
499  aB.Type() ) );
500 
501  const SHAPE_LINE_CHAIN lc = aA.ConvertToPolyline();
502 
503  bool rv = Collide( lc, aB, aClearance + aA.GetWidth() / 2, aActual, aLocation, aMTV );
504 
505  if( rv && aActual )
506  *aActual = std::max( 0, *aActual - aA.GetWidth() / 2 );
507 
508  return rv;
509 }
510 
511 
512 static inline bool Collide( const SHAPE_ARC& aA, const SHAPE_SEGMENT& aB, int aClearance,
513  int* aActual, VECTOR2I* aLocation, VECTOR2I* aMTV )
514 {
515  wxASSERT_MSG( !aMTV, wxString::Format( "MTV not implemented for %s : %s collisions",
516  aA.Type(),
517  aB.Type() ) );
518 
519  const SHAPE_LINE_CHAIN lc = aA.ConvertToPolyline();
520 
521  bool rv = Collide( lc, aB, aClearance + aA.GetWidth() / 2, aActual, aLocation, aMTV );
522 
523  if( rv && aActual )
524  *aActual = std::max( 0, *aActual - aA.GetWidth() / 2 );
525 
526  return rv;
527 }
528 
529 
530 static inline bool Collide( const SHAPE_ARC& aA, const SHAPE_LINE_CHAIN_BASE& aB, int aClearance,
531  int* aActual, VECTOR2I* aLocation, VECTOR2I* aMTV )
532 {
533  wxASSERT_MSG( !aMTV, wxString::Format( "MTV not implemented for %s : %s collisions",
534  aA.Type(),
535  aB.Type() ) );
536 
537  const SHAPE_LINE_CHAIN lc = aA.ConvertToPolyline();
538 
539  bool rv = Collide( lc, aB, aClearance + aA.GetWidth() / 2, aActual, aLocation, aMTV );
540 
541  if( rv && aActual )
542  *aActual = std::max( 0, *aActual - aA.GetWidth() / 2 );
543 
544  return rv;
545 }
546 
547 
548 static inline bool Collide( const SHAPE_ARC& aA, const SHAPE_ARC& aB, int aClearance,
549  int* aActual, VECTOR2I* aLocation, VECTOR2I* aMTV )
550 {
551  wxASSERT_MSG( !aMTV, wxString::Format( "MTV not implemented for %s : %s collisions",
552  aA.Type(),
553  aB.Type() ) );
554 
555  const SHAPE_LINE_CHAIN lcA = aA.ConvertToPolyline();
556  const SHAPE_LINE_CHAIN lcB = aB.ConvertToPolyline();
557  int widths = ( aA.GetWidth() / 2 ) + ( aB.GetWidth() / 2 );
558 
559  bool rv = Collide( lcA, lcB, aClearance + widths, aActual, aLocation, aMTV );
560 
561  if( rv && aActual )
562  *aActual = std::max( 0, *aActual - widths );
563 
564  return rv;
565 }
566 
567 
568 template<class T_a, class T_b>
569 inline bool CollCase( const SHAPE* aA, const SHAPE* aB, int aClearance, int* aActual,
570  VECTOR2I* aLocation, VECTOR2I* aMTV )
571 
572 {
573  return Collide( *static_cast<const T_a*>( aA ), *static_cast<const T_b*>( aB ),
574  aClearance, aActual, aLocation, aMTV);
575 }
576 
577 
578 template<class T_a, class T_b>
579 inline bool CollCaseReversed ( const SHAPE* aA, const SHAPE* aB, int aClearance, int* aActual,
580  VECTOR2I* aLocation, VECTOR2I* aMTV )
581 {
582  bool rv = Collide( *static_cast<const T_b*>( aB ), *static_cast<const T_a*>( aA ),
583  aClearance, aActual, aLocation, aMTV);
584 
585  if( rv && aMTV)
586  *aMTV = - *aMTV;
587 
588  return rv;
589 }
590 
591 
592 static bool collideSingleShapes( const SHAPE* aA, const SHAPE* aB, int aClearance, int* aActual,
593  VECTOR2I* aLocation, VECTOR2I* aMTV )
594 {
595  switch( aA->Type() )
596  {
597  case SH_NULL:
598  return false;
599 
600  case SH_RECT:
601  switch( aB->Type() )
602  {
603  case SH_RECT:
604  return CollCase<SHAPE_RECT, SHAPE_RECT>( aA, aB, aClearance, aActual, aLocation, aMTV );
605 
606  case SH_CIRCLE:
607  return CollCase<SHAPE_RECT, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aLocation, aMTV );
608 
609  case SH_LINE_CHAIN:
610  return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aLocation, aMTV );
611 
612  case SH_SEGMENT:
613  return CollCase<SHAPE_RECT, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
614 
615  case SH_SIMPLE:
617  return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
618 
619  case SH_ARC:
620  return CollCaseReversed<SHAPE_RECT, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
621 
622  case SH_NULL:
623  return false;
624 
625  default:
626  break;
627  }
628  break;
629 
630  case SH_CIRCLE:
631  switch( aB->Type() )
632  {
633  case SH_RECT:
634  return CollCaseReversed<SHAPE_CIRCLE, SHAPE_RECT>( aA, aB, aClearance, aActual, aLocation, aMTV );
635 
636  case SH_CIRCLE:
637  return CollCase<SHAPE_CIRCLE, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aLocation, aMTV );
638 
639  case SH_LINE_CHAIN:
640  return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aLocation, aMTV );
641 
642  case SH_SEGMENT:
643  return CollCase<SHAPE_CIRCLE, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
644 
645  case SH_SIMPLE:
647  return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
648 
649  case SH_ARC:
650  return CollCaseReversed<SHAPE_CIRCLE, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
651 
652  case SH_NULL:
653  return false;
654 
655  default:
656  break;
657  }
658  break;
659 
660  case SH_LINE_CHAIN:
661  switch( aB->Type() )
662  {
663  case SH_RECT:
664  return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN>( aB, aA, aClearance, aActual, aLocation, aMTV );
665 
666  case SH_CIRCLE:
667  return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN>( aB, aA, aClearance, aActual, aLocation, aMTV );
668 
669  case SH_LINE_CHAIN:
670  return CollCase<SHAPE_LINE_CHAIN, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aLocation, aMTV );
671 
672  case SH_SEGMENT:
673  return CollCase<SHAPE_LINE_CHAIN, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
674 
675  case SH_SIMPLE:
677  return CollCase<SHAPE_LINE_CHAIN, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
678 
679  case SH_ARC:
680  return CollCaseReversed<SHAPE_LINE_CHAIN, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
681 
682  case SH_NULL:
683  return false;
684 
685  default:
686  break;
687  }
688  break;
689 
690  case SH_SEGMENT:
691  switch( aB->Type() )
692  {
693  case SH_RECT:
694  return CollCase<SHAPE_RECT, SHAPE_SEGMENT>( aB, aA, aClearance, aActual, aLocation, aMTV );
695 
696  case SH_CIRCLE:
697  return CollCaseReversed<SHAPE_SEGMENT, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aLocation, aMTV );
698 
699  case SH_LINE_CHAIN:
700  return CollCase<SHAPE_LINE_CHAIN, SHAPE_SEGMENT>( aB, aA, aClearance, aActual, aLocation, aMTV );
701 
702  case SH_SEGMENT:
703  return CollCase<SHAPE_SEGMENT, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
704 
705  case SH_SIMPLE:
707  return CollCase<SHAPE_LINE_CHAIN_BASE, SHAPE_SEGMENT>( aB, aA, aClearance, aActual, aLocation, aMTV );
708 
709  case SH_ARC:
710  return CollCaseReversed<SHAPE_SEGMENT, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
711 
712  case SH_NULL:
713  return false;
714 
715  default:
716  break;
717  }
718  break;
719 
720  case SH_SIMPLE:
722  switch( aB->Type() )
723  {
724  case SH_RECT:
725  return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN_BASE>( aB, aA, aClearance, aActual, aLocation, aMTV );
726 
727  case SH_CIRCLE:
728  return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN_BASE>( aB, aA, aClearance, aActual, aLocation, aMTV );
729 
730  case SH_LINE_CHAIN:
731  return CollCase<SHAPE_LINE_CHAIN, SHAPE_LINE_CHAIN_BASE>( aB, aA, aClearance, aActual, aLocation, aMTV );
732 
733  case SH_SEGMENT:
734  return CollCase<SHAPE_LINE_CHAIN_BASE, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
735 
736  case SH_SIMPLE:
738  return CollCase<SHAPE_LINE_CHAIN_BASE, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
739 
740  case SH_ARC:
741  return CollCaseReversed<SHAPE_LINE_CHAIN_BASE, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
742 
743  case SH_NULL:
744  return false;
745 
746  default:
747  break;
748  }
749  break;
750 
751  case SH_ARC:
752  switch( aB->Type() )
753  {
754  case SH_RECT:
755  return CollCase<SHAPE_ARC, SHAPE_RECT>( aA, aB, aClearance, aActual, aLocation, aMTV );
756 
757  case SH_CIRCLE:
758  return CollCase<SHAPE_ARC, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aLocation, aMTV );
759 
760  case SH_LINE_CHAIN:
761  return CollCase<SHAPE_ARC, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aLocation, aMTV );
762 
763  case SH_SEGMENT:
764  return CollCase<SHAPE_ARC, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
765 
766  case SH_SIMPLE:
768  return CollCase<SHAPE_ARC, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
769 
770  case SH_ARC:
771  return CollCase<SHAPE_ARC, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
772 
773  case SH_NULL:
774  return false;
775 
776  default:
777  break;
778  }
779  break;
780 
781  default:
782  break;
783  }
784 
785  wxFAIL_MSG( wxString::Format( "Unsupported collision: %s with %s",
786  SHAPE_TYPE_asString( aA->Type() ),
787  SHAPE_TYPE_asString( aB->Type() ) ) );
788 
789  return false;
790 }
791 
792 static bool collideShapes( const SHAPE* aA, const SHAPE* aB, int aClearance, int* aActual,
793  VECTOR2I* aLocation, VECTOR2I* aMTV )
794 {
795  int currentActual = std::numeric_limits<int>::max();
796  VECTOR2I currentLocation;
797  VECTOR2I currentMTV(0, 0);
798  bool colliding = false;
799 
800  auto canExit =
801  [&]()
802  {
803  if( !colliding )
804  return false;
805 
806  if( aActual && currentActual > 0 )
807  return false;
808 
809  if( aMTV )
810  return false;
811 
812  return true;
813  };
814 
815  auto collideCompoundSubshapes =
816  [&]( const SHAPE* elemA, const SHAPE* elemB, int clearance ) -> bool
817  {
818  int actual = 0;
819  VECTOR2I location;
820  VECTOR2I mtv;
821 
822  if( collideSingleShapes( elemA, elemB, clearance,
823  aActual || aLocation ? &actual : nullptr,
824  aLocation ? &location : nullptr,
825  aMTV ? &mtv : nullptr ) )
826  {
827  if( actual < currentActual )
828  {
829  currentActual = actual;
830  currentLocation = location;
831  }
832 
833  if( aMTV && mtv.SquaredEuclideanNorm() > currentMTV.SquaredEuclideanNorm() )
834  {
835  currentMTV = mtv;
836  }
837 
838  return true;
839  }
840 
841  return false;
842  };
843 
844  if( aA->Type() == SH_COMPOUND && aB->Type() == SH_COMPOUND )
845  {
846  const SHAPE_COMPOUND* cmpA = static_cast<const SHAPE_COMPOUND*>( aA );
847  const SHAPE_COMPOUND* cmpB = static_cast<const SHAPE_COMPOUND*>( aB );
848 
849  for( const SHAPE* elemA : cmpA->Shapes() )
850  {
851  for( const SHAPE* elemB : cmpB->Shapes() )
852  {
853  if( collideCompoundSubshapes( elemA, elemB, aClearance ) )
854  {
855  colliding = true;
856 
857  if( canExit() )
858  break;
859  }
860  }
861 
862  if( canExit() )
863  break;
864  }
865  }
866  else if( aA->Type() == SH_COMPOUND )
867  {
868  const SHAPE_COMPOUND* cmpA = static_cast<const SHAPE_COMPOUND*>( aA );
869 
870  for( const SHAPE* elemA : cmpA->Shapes() )
871  {
872  if( collideCompoundSubshapes( elemA, aB, aClearance ) )
873  {
874  colliding = true;
875 
876  if( canExit() )
877  break;
878  }
879  }
880  }
881  else if( aB->Type() == SH_COMPOUND )
882  {
883  const SHAPE_COMPOUND* cmpB = static_cast<const SHAPE_COMPOUND*>( aB );
884 
885  for( const SHAPE* elemB : cmpB->Shapes() )
886  {
887  if( collideCompoundSubshapes( aA, elemB, aClearance ) )
888  {
889  colliding = true;
890 
891  if( canExit() )
892  break;
893  }
894  }
895  }
896  else
897  {
898  return collideSingleShapes( aA, aB, aClearance, aActual, aLocation, aMTV );
899  }
900 
901  if( colliding )
902  {
903  if( aLocation )
904  *aLocation = currentLocation;
905 
906  if( aActual )
907  *aActual = currentActual;
908 
909  if( aMTV )
910  *aMTV = currentMTV;
911  }
912 
913  return colliding;
914 }
915 
916 
917 bool SHAPE::Collide( const SHAPE* aShape, int aClearance, VECTOR2I* aMTV ) const
918 {
919  return collideShapes( this, aShape, aClearance, nullptr, nullptr, aMTV );
920 }
921 
922 
923 bool SHAPE::Collide( const SHAPE* aShape, int aClearance, int* aActual, VECTOR2I* aLocation ) const
924 {
925  return collideShapes( this, aShape, aClearance, aActual, aLocation, nullptr );
926 }
927 
928 
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:148
VECTOR2_TRAITS< int >::extended_type extended_type
Definition: vector2d.h:76
compound shape, consisting of multiple simple shapes
Definition: shape.h:49
bool Collide(const SHAPE *aShape, int aClearance, VECTOR2I *aMTV) const override
Check if the boundary of shape (this) lies closer to the shape aShape than aClearance,...
Definition: shape_rect.h:98
void SetCenter(const VECTOR2I &aCenter)
Definition: shape_circle.h:102
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.cpp:285
bool CollCase(const SHAPE *aA, const SHAPE *aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
const SHAPE_LINE_CHAIN Outline() const
Definition: shape_rect.h:170
int GetRadius() const
Definition: shape_circle.h:107
virtual bool IsClosed() const =0
Define a general 2D-vector/point.
Definition: vector2d.h:61
virtual size_t GetPointCount() const =0
extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
Definition: vector2d.h:300
const VECTOR2I GetCenter() const
Definition: shape_circle.h:112
virtual VECTOR2I Centre() const
Compute a center-of-mass of the shape.
Definition: shape.h:216
virtual size_t GetSegmentCount() const =0
static bool collideShapes(const SHAPE *aA, const SHAPE *aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
static SEG::ecoord Square(int a)
Definition: seg.h:122
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const
Check if the boundary of shape (this) lies closer to the point aP than aClearance,...
Definition: shape.h:165
const SEG & GetSeg() const
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if point aP lies closer to us than aClearance.
const VECTOR2I GetSize() const
Definition: shape_rect.h:124
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:79
bool Collide(const SEG &aSeg, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if the boundary of shape (this) lies closer to the segment aSeg than aClearance,...
Definition: shape_circle.h:76
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=0.005 *PCB_IU_PER_MM) const
Constructs a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:417
const VECTOR2I & GetPosition() const
Definition: shape_rect.h:116
VECTOR2I::extended_type ecoord
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const
Check if point aP lies inside a polygon (any type) defined by the line chain.
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
Definition: seg.cpp:227
static wxString SHAPE_TYPE_asString(SHAPE_TYPE a)
Definition: shape.h:55
circular arc
Definition: shape.h:50
An abstract shape on 2D plane.
Definition: shape.h:116
static VECTOR2I pushoutForce(const SHAPE_CIRCLE &aA, const SEG &aB, int aClearance)
static bool Collide(const SHAPE_CIRCLE &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
circle
Definition: shape.h:46
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
Definition: ptree.cpp:200
Definition: seg.h:40
virtual const SEG GetSegment(int aIndex) const =0
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:404
int GetWidth() const
Definition: shape_arc.h:112
a single triangle belonging to a POLY_SET triangulation
Definition: shape.h:52
const std::vector< SHAPE * > & Shapes() const
SHAPE_LINE_CHAIN.
empty shape (no shape...),
Definition: shape.h:51
line chain (polyline)
Definition: shape.h:45
axis-aligned rectangle
Definition: shape.h:43
virtual const VECTOR2I GetPoint(int aIndex) const =0
bool CollCaseReversed(const SHAPE *aA, const SHAPE *aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
static bool collideSingleShapes(const SHAPE *aA, const SHAPE *aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
int GetWidth() const
bool Collide(const SHAPE *aShape, int aClearance, VECTOR2I *aMTV) const override
Check if the boundary of shape (this) lies closer to the shape aShape than aClearance,...
Definition: shape_segment.h:67
simple polygon
Definition: shape.h:47
SHAPE_TYPE Type() const
Return the type of the shape.
Definition: shape.h:94
line segment
Definition: shape.h:44