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-2022 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#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>
34#include <geometry/shape_rect.h>
37#include <math/vector2d.h>
38
40
41
42static 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
69static 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
147static 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
174static 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
271static 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
289static 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( wxT( "MTV not implemented for %s : %s collisions" ),
293 aA.TypeName(),
294 aB.TypeName() ) );
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( aB.Type() == SH_LINE_CHAIN )
312 {
313 const SHAPE_LINE_CHAIN* aB_line_chain = static_cast<const SHAPE_LINE_CHAIN*>( &aB );
314
315 // ignore arcs - we will collide these separately
316 if( aB_line_chain->IsArcSegment( i ) )
317 continue;
318 }
319
320 if( aA.Collide( aB.GetSegment( i ), aClearance,
321 aActual || aLocation ? &collision_dist : nullptr,
322 aLocation ? &pn : nullptr ) )
323 {
324 if( collision_dist < closest_dist )
325 {
326 nearest = pn;
327 closest_dist = collision_dist;
328 }
329
330 if( closest_dist == 0 )
331 break;
332
333 // If we're not looking for aActual then any collision will do
334 if( !aActual )
335 break;
336 }
337 }
338
339 if( aB.Type() == SH_LINE_CHAIN )
340 {
341 const SHAPE_LINE_CHAIN* aB_line_chain = static_cast<const SHAPE_LINE_CHAIN*>( &aB );
342
343 for( size_t i = 0; i < aB_line_chain->ArcCount(); i++ )
344 {
345 const SHAPE_ARC& arc = aB_line_chain->Arc( i );
346
347 // The arcs in the chain should have zero width
348 wxASSERT_MSG( arc.GetWidth() == 0, wxT( "Invalid arc width - should be zero" ) );
349
350 if( arc.Collide( &aA, aClearance, aActual, aLocation ) )
351 return true;
352 }
353 }
354 }
355
356 if( closest_dist == 0 || closest_dist < aClearance )
357 {
358 if( aLocation )
359 *aLocation = nearest;
360
361 if( aActual )
362 *aActual = closest_dist;
363
364 return true;
365 }
366
367 return false;
368}
369
370
371static inline bool Collide( const SHAPE_RECT& aA, const SHAPE_LINE_CHAIN_BASE& aB, int aClearance,
372 int* aActual, VECTOR2I* aLocation, VECTOR2I* aMTV )
373{
374 wxASSERT_MSG( !aMTV, wxString::Format( wxT( "MTV not implemented for %s : %s collisions" ),
375 aA.TypeName(),
376 aB.TypeName() ) );
377
378 int closest_dist = INT_MAX;
379 VECTOR2I nearest;
380
381 if( aB.IsClosed() && aB.PointInside( aA.Centre() ) )
382 {
383 nearest = aA.Centre();
384 closest_dist = 0;
385 }
386 else
387 {
388 for( size_t s = 0; s < aB.GetSegmentCount(); s++ )
389 {
390 int collision_dist = 0;
391 VECTOR2I pn;
392
393 if( aA.Collide( aB.GetSegment( s ), aClearance,
394 aActual || aLocation ? &collision_dist : nullptr,
395 aLocation ? &pn : nullptr ) )
396 {
397 if( collision_dist < closest_dist )
398 {
399 nearest = pn;
400 closest_dist = collision_dist;
401 }
402
403 if( closest_dist == 0 )
404 break;
405
406 // If we're not looking for aActual then any collision will do
407 if( !aActual )
408 break;
409 }
410 }
411 }
412
413 if( closest_dist == 0 || closest_dist < aClearance )
414 {
415 if( aLocation )
416 *aLocation = nearest;
417
418 if( aActual )
419 *aActual = closest_dist;
420
421 return true;
422 }
423
424 return false;
425}
426
427
428static inline bool Collide( const SHAPE_RECT& aA, const SHAPE_SEGMENT& aB, int aClearance,
429 int* aActual, VECTOR2I* aLocation, VECTOR2I* aMTV )
430{
431 wxASSERT_MSG( !aMTV, wxString::Format( wxT( "MTV not implemented for %s : %s collisions" ),
432 aA.TypeName(),
433 aB.TypeName() ) );
434
435 bool rv = aA.Collide( aB.GetSeg(), aClearance + aB.GetWidth() / 2, aActual, aLocation );
436
437 if( aActual )
438 *aActual = std::max( 0, *aActual - aB.GetWidth() / 2 );
439
440 return rv;
441}
442
443
444static inline bool Collide( const SHAPE_SEGMENT& aA, const SHAPE_SEGMENT& aB, int aClearance,
445 int* aActual, VECTOR2I* aLocation, VECTOR2I* aMTV )
446{
447 wxASSERT_MSG( !aMTV, wxString::Format( wxT( "MTV not implemented for %s : %s collisions" ),
448 aA.TypeName(),
449 aB.TypeName() ) );
450
451 bool rv = aA.Collide( aB.GetSeg(), aClearance + aB.GetWidth() / 2, aActual, aLocation );
452
453 if( aActual )
454 *aActual = std::max( 0, *aActual - aB.GetWidth() / 2 );
455
456 return rv;
457}
458
459
460static inline bool Collide( const SHAPE_LINE_CHAIN_BASE& aA, const SHAPE_SEGMENT& aB,
461 int aClearance, int* aActual, VECTOR2I* aLocation, VECTOR2I* aMTV )
462{
463 wxASSERT_MSG( !aMTV, wxString::Format( wxT( "MTV not implemented for %s : %s collisions" ),
464 aA.TypeName(),
465 aB.TypeName() ) );
466
467 bool rv = aA.Collide( aB.GetSeg(), aClearance + aB.GetWidth() / 2, aActual, aLocation );
468
469 if( aActual )
470 *aActual = std::max( 0, *aActual - aB.GetWidth() / 2 );
471
472 return rv;
473}
474
475
476static inline bool Collide( const SHAPE_RECT& aA, const SHAPE_RECT& aB, int aClearance,
477 int* aActual, VECTOR2I* aLocation, VECTOR2I* aMTV )
478{
479 if( aClearance || aActual || aLocation || aMTV )
480 {
481 return Collide( aA.Outline(), aB.Outline(), aClearance, aActual, aLocation, aMTV );
482 }
483 else
484 {
485 BOX2I bboxa = aA.BBox();
486 BOX2I bboxb = aB.BBox();
487
488 return bboxa.Intersects( bboxb );
489 }
490}
491
492
493static inline bool Collide( const SHAPE_ARC& aA, const SHAPE_RECT& aB, int aClearance,
494 int* aActual, VECTOR2I* aLocation, VECTOR2I* aMTV )
495{
496 wxASSERT_MSG( !aMTV, wxString::Format( wxT( "MTV not implemented for %s : %s collisions" ),
497 aA.TypeName(),
498 aB.TypeName() ) );
499
500 const SHAPE_LINE_CHAIN lc( aA );
501
502 bool rv = Collide( lc, aB.Outline(), aClearance + aA.GetWidth() / 2, aActual, aLocation, aMTV );
503
504 if( rv && aActual )
505 *aActual = std::max( 0, *aActual - aA.GetWidth() / 2 );
506
507 return rv;
508}
509
510
511static inline bool Collide( const SHAPE_ARC& aA, const SHAPE_CIRCLE& aB, int aClearance,
512 int* aActual, VECTOR2I* aLocation, VECTOR2I* aMTV )
513{
514 const SHAPE_LINE_CHAIN lc( aA );
515
516 bool rv = Collide( aB, lc, aClearance + aA.GetWidth() / 2, aActual, aLocation, aMTV );
517
518 if( rv && aActual )
519 *aActual = std::max( 0, *aActual - aA.GetWidth() / 2 );
520
521 return rv;
522}
523
524
525static inline bool Collide( const SHAPE_ARC& aA, const SHAPE_LINE_CHAIN& aB, int aClearance,
526 int* aActual, VECTOR2I* aLocation, VECTOR2I* aMTV )
527{
528 wxASSERT_MSG( !aMTV, wxString::Format( wxT( "MTV not implemented for %s : %s collisions" ),
529 aA.TypeName(),
530 aB.TypeName() ) );
531
532 int closest_dist = INT_MAX;
533 VECTOR2I nearest;
534
535 if( aB.IsClosed() && aB.PointInside( aA.GetP0() ) )
536 {
537 closest_dist = 0;
538 nearest = aA.GetP0();
539 }
540 else
541 {
542 for( size_t i = 0; i < aB.GetSegmentCount(); i++ )
543 {
544 int collision_dist = 0;
545 VECTOR2I pn;
546
547 // ignore arcs - we will collide these separately
548 if( aB.IsArcSegment( i ) )
549 continue;
550
551 if( aA.Collide( aB.GetSegment( i ), aClearance,
552 aActual || aLocation ? &collision_dist : nullptr,
553 aLocation ? &pn : nullptr ) )
554 {
555 if( collision_dist < closest_dist )
556 {
557 nearest = pn;
558 closest_dist = collision_dist;
559 }
560
561 if( closest_dist == 0 )
562 break;
563
564 // If we're not looking for aActual then any collision will do
565 if( !aActual )
566 break;
567 }
568 }
569
570 for( size_t i = 0; i < aB.ArcCount(); i++ )
571 {
572 const SHAPE_ARC& arc = aB.Arc( i );
573
574 // The arcs in the chain should have zero width
575 wxASSERT_MSG( arc.GetWidth() == 0, wxT( "Invalid arc width - should be zero" ) );
576
577 if( arc.Collide( &aA, aClearance, aActual, aLocation ) )
578 return true;
579 }
580 }
581
582 if( closest_dist == 0 || closest_dist < aClearance )
583 {
584 if( aLocation )
585 *aLocation = nearest;
586
587 if( aActual )
588 *aActual = closest_dist;
589
590 return true;
591 }
592
593 return false;
594}
595
596
597static inline bool Collide( const SHAPE_ARC& aA, const SHAPE_SEGMENT& aB, int aClearance,
598 int* aActual, VECTOR2I* aLocation, VECTOR2I* aMTV )
599{
600 wxASSERT_MSG( !aMTV, wxString::Format( wxT( "MTV not implemented for %s : %s collisions" ),
601 aA.TypeName(),
602 aB.TypeName() ) );
603
604 const SHAPE_LINE_CHAIN lc( aA );
605
606 bool rv = Collide( lc, aB, aClearance + aA.GetWidth() / 2, aActual, aLocation, aMTV );
607
608 if( rv && aActual )
609 *aActual = std::max( 0, *aActual - aA.GetWidth() / 2 );
610
611 return rv;
612}
613
614
615static inline bool Collide( const SHAPE_ARC& aA, const SHAPE_LINE_CHAIN_BASE& aB, int aClearance,
616 int* aActual, VECTOR2I* aLocation, VECTOR2I* aMTV )
617{
618 wxASSERT_MSG( !aMTV, wxString::Format( wxT( "MTV not implemented for %s : %s collisions" ),
619 aA.TypeName(),
620 aB.TypeName() ) );
621
622 int closest_dist = INT_MAX;
623 VECTOR2I nearest;
624
625 if( aB.IsClosed() && aB.PointInside( aA.GetP0() ) )
626 {
627 closest_dist = 0;
628 nearest = aA.GetP0();
629 }
630 else
631 {
632 for( size_t i = 0; i < aB.GetSegmentCount(); i++ )
633 {
634 int collision_dist = 0;
635 VECTOR2I pn;
636
637 if( aA.Collide( aB.GetSegment( i ), aClearance,
638 aActual || aLocation ? &collision_dist : nullptr,
639 aLocation ? &pn : nullptr ) )
640 {
641 if( collision_dist < closest_dist )
642 {
643 nearest = pn;
644 closest_dist = collision_dist;
645 }
646
647 if( closest_dist == 0 )
648 break;
649
650 // If we're not looking for aActual then any collision will do
651 if( !aActual )
652 break;
653 }
654 }
655 }
656
657 if( closest_dist == 0 || closest_dist < aClearance )
658 {
659 if( aLocation )
660 *aLocation = nearest;
661
662 if( aActual )
663 *aActual = closest_dist;
664
665 return true;
666 }
667
668 return false;
669}
670
671
672static inline bool Collide( const SHAPE_ARC& aA, const SHAPE_ARC& aB, int aClearance,
673 int* aActual, VECTOR2I* aLocation, VECTOR2I* aMTV )
674{
675 wxASSERT_MSG( !aMTV, wxString::Format( wxT( "MTV not implemented for %s : %s collisions" ),
676 aA.TypeName(),
677 aB.TypeName() ) );
678
679 SEG mediatrix( aA.GetCenter(), aB.GetCenter() );
680
681 std::vector<VECTOR2I> ips;
682
683 // Basic case - arcs intersect
684 if( aA.Intersect( aB, &ips ) > 0 )
685 {
686 if( aActual )
687 *aActual = 0;
688
689 if( aLocation )
690 *aLocation = ips[0]; // Pick the first intersection point
691
692 return true;
693 }
694
695 // Arcs don't intersect, build a list of points to check
696 std::vector<VECTOR2I> ptsA;
697 std::vector<VECTOR2I> ptsB;
698
699 bool cocentered = ( mediatrix.A == mediatrix.B );
700
701 // 1: Interior points of both arcs, which are on the line segment between the two centres
702 if( !cocentered )
703 {
704 aA.IntersectLine( mediatrix, &ptsA );
705 aB.IntersectLine( mediatrix, &ptsB );
706 }
707
708 // 2: Check arc end points
709 ptsA.push_back( aA.GetP0() );
710 ptsA.push_back( aA.GetP1() );
711 ptsB.push_back( aB.GetP0() );
712 ptsB.push_back( aB.GetP1() );
713
714 // 3: Endpoint of one and "projected" point on the other, which is on the
715 // line segment through that endpoint and the centre of the other arc
716 aA.IntersectLine( SEG( aB.GetP0(), aA.GetCenter() ), &ptsA );
717 aA.IntersectLine( SEG( aB.GetP1(), aA.GetCenter() ), &ptsA );
718
719 aB.IntersectLine( SEG( aA.GetP0(), aB.GetCenter() ), &ptsB );
720 aB.IntersectLine( SEG( aA.GetP1(), aB.GetCenter() ), &ptsB );
721
722 double minDist = std::numeric_limits<double>::max();
723 SEG minDistSeg;
724 bool rv = false;
725
726 int widths = ( aA.GetWidth() / 2 ) + ( aB.GetWidth() / 2 );
727
728 // @todo performance could be improved by only checking certain points (e.g only check end
729 // points against other end points or their corresponding "projected" points)
730 for( const VECTOR2I& ptA : ptsA )
731 {
732 for( const VECTOR2I& ptB : ptsB )
733 {
734 SEG candidateMinDist( ptA, ptB );
735 int dist = candidateMinDist.Length() - widths;
736
737 if( dist < aClearance )
738 {
739 if( !rv || dist < minDist )
740 {
741 minDist = dist;
742 minDistSeg = candidateMinDist;
743 }
744
745 rv = true;
746 }
747 }
748 }
749
750 if( rv && aActual )
751 *aActual = std::max( 0, minDistSeg.Length() - widths );
752
753 if( rv && aLocation )
754 *aLocation = minDistSeg.Center();
755
756 return rv;
757}
758
759
760template<class T_a, class T_b>
761inline bool CollCase( const SHAPE* aA, const SHAPE* aB, int aClearance, int* aActual,
762 VECTOR2I* aLocation, VECTOR2I* aMTV )
763
764{
765 return Collide( *static_cast<const T_a*>( aA ), *static_cast<const T_b*>( aB ),
766 aClearance, aActual, aLocation, aMTV);
767}
768
769
770template<class T_a, class T_b>
771inline bool CollCaseReversed ( const SHAPE* aA, const SHAPE* aB, int aClearance, int* aActual,
772 VECTOR2I* aLocation, VECTOR2I* aMTV )
773{
774 bool rv = Collide( *static_cast<const T_b*>( aB ), *static_cast<const T_a*>( aA ),
775 aClearance, aActual, aLocation, aMTV);
776
777 if( rv && aMTV)
778 *aMTV = - *aMTV;
779
780 return rv;
781}
782
783
784static bool collideSingleShapes( const SHAPE* aA, const SHAPE* aB, int aClearance, int* aActual,
785 VECTOR2I* aLocation, VECTOR2I* aMTV )
786{
787 switch( aA->Type() )
788 {
789 case SH_NULL:
790 return false;
791
792 case SH_RECT:
793 switch( aB->Type() )
794 {
795 case SH_RECT:
796 return CollCase<SHAPE_RECT, SHAPE_RECT>( aA, aB, aClearance, aActual, aLocation, aMTV );
797
798 case SH_CIRCLE:
799 return CollCase<SHAPE_RECT, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aLocation, aMTV );
800
801 case SH_LINE_CHAIN:
802 return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aLocation, aMTV );
803
804 case SH_SEGMENT:
805 return CollCase<SHAPE_RECT, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
806
807 case SH_SIMPLE:
809 return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
810
811 case SH_ARC:
812 return CollCaseReversed<SHAPE_RECT, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
813
814 case SH_NULL:
815 return false;
816
817 default:
818 break;
819 }
820 break;
821
822 case SH_CIRCLE:
823 switch( aB->Type() )
824 {
825 case SH_RECT:
826 return CollCaseReversed<SHAPE_CIRCLE, SHAPE_RECT>( aA, aB, aClearance, aActual, aLocation, aMTV );
827
828 case SH_CIRCLE:
829 return CollCase<SHAPE_CIRCLE, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aLocation, aMTV );
830
831 case SH_LINE_CHAIN:
832 return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aLocation, aMTV );
833
834 case SH_SEGMENT:
835 return CollCase<SHAPE_CIRCLE, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
836
837 case SH_SIMPLE:
839 return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
840
841 case SH_ARC:
842 return CollCaseReversed<SHAPE_CIRCLE, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
843
844 case SH_NULL:
845 return false;
846
847 default:
848 break;
849 }
850 break;
851
852 case SH_LINE_CHAIN:
853 switch( aB->Type() )
854 {
855 case SH_RECT:
856 return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN>( aB, aA, aClearance, aActual, aLocation, aMTV );
857
858 case SH_CIRCLE:
859 return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN>( aB, aA, aClearance, aActual, aLocation, aMTV );
860
861 case SH_LINE_CHAIN:
862 return CollCase<SHAPE_LINE_CHAIN, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aLocation, aMTV );
863
864 case SH_SEGMENT:
865 return CollCase<SHAPE_LINE_CHAIN, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
866
867 case SH_SIMPLE:
869 return CollCase<SHAPE_LINE_CHAIN, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
870
871 case SH_ARC:
872 return CollCaseReversed<SHAPE_LINE_CHAIN, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
873
874 case SH_NULL:
875 return false;
876
877 default:
878 break;
879 }
880 break;
881
882 case SH_SEGMENT:
883 switch( aB->Type() )
884 {
885 case SH_RECT:
886 return CollCase<SHAPE_RECT, SHAPE_SEGMENT>( aB, aA, aClearance, aActual, aLocation, aMTV );
887
888 case SH_CIRCLE:
889 return CollCaseReversed<SHAPE_SEGMENT, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aLocation, aMTV );
890
891 case SH_LINE_CHAIN:
892 return CollCase<SHAPE_LINE_CHAIN, SHAPE_SEGMENT>( aB, aA, aClearance, aActual, aLocation, aMTV );
893
894 case SH_SEGMENT:
895 return CollCase<SHAPE_SEGMENT, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
896
897 case SH_SIMPLE:
899 return CollCase<SHAPE_LINE_CHAIN_BASE, SHAPE_SEGMENT>( aB, aA, aClearance, aActual, aLocation, aMTV );
900
901 case SH_ARC:
902 return CollCaseReversed<SHAPE_SEGMENT, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
903
904 case SH_NULL:
905 return false;
906
907 default:
908 break;
909 }
910 break;
911
912 case SH_SIMPLE:
914 switch( aB->Type() )
915 {
916 case SH_RECT:
917 return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN_BASE>( aB, aA, aClearance, aActual, aLocation, aMTV );
918
919 case SH_CIRCLE:
920 return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN_BASE>( aB, aA, aClearance, aActual, aLocation, aMTV );
921
922 case SH_LINE_CHAIN:
923 return CollCase<SHAPE_LINE_CHAIN, SHAPE_LINE_CHAIN_BASE>( aB, aA, aClearance, aActual, aLocation, aMTV );
924
925 case SH_SEGMENT:
926 return CollCase<SHAPE_LINE_CHAIN_BASE, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
927
928 case SH_SIMPLE:
930 return CollCase<SHAPE_LINE_CHAIN_BASE, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
931
932 case SH_ARC:
933 return CollCaseReversed<SHAPE_LINE_CHAIN_BASE, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
934
935 case SH_NULL:
936 return false;
937
938 default:
939 break;
940 }
941 break;
942
943 case SH_ARC:
944 switch( aB->Type() )
945 {
946 case SH_RECT:
947 return CollCase<SHAPE_ARC, SHAPE_RECT>( aA, aB, aClearance, aActual, aLocation, aMTV );
948
949 case SH_CIRCLE:
950 return CollCase<SHAPE_ARC, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aLocation, aMTV );
951
952 case SH_LINE_CHAIN:
953 return CollCase<SHAPE_ARC, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aLocation, aMTV );
954
955 case SH_SEGMENT:
956 return CollCase<SHAPE_ARC, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
957
958 case SH_SIMPLE:
960 return CollCase<SHAPE_ARC, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
961
962 case SH_ARC:
963 return CollCase<SHAPE_ARC, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
964
965 case SH_NULL:
966 return false;
967
968 default:
969 break;
970 }
971 break;
972
973 default:
974 break;
975 }
976
977 wxFAIL_MSG( wxString::Format( wxT( "Unsupported collision: %s with %s" ),
978 SHAPE_TYPE_asString( aA->Type() ),
979 SHAPE_TYPE_asString( aB->Type() ) ) );
980
981 return false;
982}
983
984static bool collideShapes( const SHAPE* aA, const SHAPE* aB, int aClearance, int* aActual,
985 VECTOR2I* aLocation, VECTOR2I* aMTV )
986{
987 int currentActual = std::numeric_limits<int>::max();
988 VECTOR2I currentLocation;
989 VECTOR2I currentMTV(0, 0);
990 bool colliding = false;
991
992 auto canExit =
993 [&]()
994 {
995 if( !colliding )
996 return false;
997
998 if( aActual && currentActual > 0 )
999 return false;
1000
1001 if( aMTV )
1002 return false;
1003
1004 return true;
1005 };
1006
1007 auto collideCompoundSubshapes =
1008 [&]( const SHAPE* elemA, const SHAPE* elemB, int clearance ) -> bool
1009 {
1010 int actual = 0;
1011 VECTOR2I location;
1012 VECTOR2I mtv;
1013
1014 if( collideSingleShapes( elemA, elemB, clearance,
1015 aActual || aLocation ? &actual : nullptr,
1016 aLocation ? &location : nullptr,
1017 aMTV ? &mtv : nullptr ) )
1018 {
1019 if( actual < currentActual )
1020 {
1021 currentActual = actual;
1022 currentLocation = location;
1023 }
1024
1025 if( aMTV && mtv.SquaredEuclideanNorm() > currentMTV.SquaredEuclideanNorm() )
1026 {
1027 currentMTV = mtv;
1028 }
1029
1030 return true;
1031 }
1032
1033 return false;
1034 };
1035
1036 if( aA->Type() == SH_COMPOUND && aB->Type() == SH_COMPOUND )
1037 {
1038 const SHAPE_COMPOUND* cmpA = static_cast<const SHAPE_COMPOUND*>( aA );
1039 const SHAPE_COMPOUND* cmpB = static_cast<const SHAPE_COMPOUND*>( aB );
1040
1041 for( const SHAPE* elemA : cmpA->Shapes() )
1042 {
1043 for( const SHAPE* elemB : cmpB->Shapes() )
1044 {
1045 if( collideCompoundSubshapes( elemA, elemB, aClearance ) )
1046 {
1047 colliding = true;
1048
1049 if( canExit() )
1050 break;
1051 }
1052 }
1053
1054 if( canExit() )
1055 break;
1056 }
1057 }
1058 else if( aA->Type() == SH_COMPOUND )
1059 {
1060 const SHAPE_COMPOUND* cmpA = static_cast<const SHAPE_COMPOUND*>( aA );
1061
1062 for( const SHAPE* elemA : cmpA->Shapes() )
1063 {
1064 if( collideCompoundSubshapes( elemA, aB, aClearance ) )
1065 {
1066 colliding = true;
1067
1068 if( canExit() )
1069 break;
1070 }
1071 }
1072 }
1073 else if( aB->Type() == SH_COMPOUND )
1074 {
1075 const SHAPE_COMPOUND* cmpB = static_cast<const SHAPE_COMPOUND*>( aB );
1076
1077 for( const SHAPE* elemB : cmpB->Shapes() )
1078 {
1079 if( collideCompoundSubshapes( aA, elemB, aClearance ) )
1080 {
1081 colliding = true;
1082
1083 if( canExit() )
1084 break;
1085 }
1086 }
1087 }
1088 else
1089 {
1090 return collideSingleShapes( aA, aB, aClearance, aActual, aLocation, aMTV );
1091 }
1092
1093 if( colliding )
1094 {
1095 if( aLocation )
1096 *aLocation = currentLocation;
1097
1098 if( aActual )
1099 *aActual = currentActual;
1100
1101 if( aMTV )
1102 *aMTV = currentMTV;
1103 }
1104
1105 return colliding;
1106}
1107
1108
1109bool SHAPE::Collide( const SHAPE* aShape, int aClearance, VECTOR2I* aMTV ) const
1110{
1111 return collideShapes( this, aShape, aClearance, nullptr, nullptr, aMTV );
1112}
1113
1114
1115bool SHAPE::Collide( const SHAPE* aShape, int aClearance, int* aActual, VECTOR2I* aLocation ) const
1116{
1117 return collideShapes( this, aShape, aClearance, aActual, aLocation, nullptr );
1118}
1119
1120
bool Intersects(const BOX2< Vec > &aRect) const
Definition: box2.h:269
Definition: seg.h:42
VECTOR2I A
Definition: seg.h:49
VECTOR2I B
Definition: seg.h:50
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
Definition: seg.cpp:269
int Length() const
Return the length (this).
Definition: seg.h:326
static SEG::ecoord Square(int a)
Definition: seg.h:123
VECTOR2I Center() const
Definition: seg.h:362
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.cpp:329
int GetWidth() const
Definition: shape_arc.h:157
const VECTOR2I & GetP1() const
Definition: shape_arc.h:113
int IntersectLine(const SEG &aSeg, std::vector< VECTOR2I > *aIpsBuffer) const
Find intersection points between this arc and aSeg, treating aSeg as an infinite line.
Definition: shape_arc.cpp:273
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_arc.cpp:241
int Intersect(const SHAPE_ARC &aArc, std::vector< VECTOR2I > *aIpsBuffer) const
Find intersection points between this arc and aArc.
Definition: shape_arc.cpp:294
VECTOR2I GetCenter() const
Definition: shape_arc.cpp:433
const VECTOR2I & GetP0() const
Definition: shape_arc.h:112
wxString TypeName() const
Definition: shape.h:101
SHAPE_TYPE Type() const
Return the type of the shape.
Definition: shape.h:96
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:77
int GetRadius() const
Definition: shape_circle.h:108
const VECTOR2I GetCenter() const
Definition: shape_circle.h:113
void SetCenter(const VECTOR2I &aCenter)
Definition: shape_circle.h:103
const std::vector< SHAPE * > & Shapes() const
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.
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.
virtual size_t GetPointCount() const =0
virtual size_t GetSegmentCount() const =0
virtual const VECTOR2I GetPoint(int aIndex) const =0
virtual bool IsClosed() const =0
virtual const SEG GetSegment(int aIndex) const =0
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
const SHAPE_ARC & Arc(size_t aArc) const
bool IsClosed() const override
virtual const SEG GetSegment(int aIndex) const override
virtual size_t GetSegmentCount() const override
size_t ArcCount() const
bool IsArcSegment(size_t aSegment) 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_rect.h:109
const SHAPE_LINE_CHAIN Outline() const
Definition: shape_rect.h:179
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
Definition: shape_rect.h:92
const VECTOR2I & GetPosition() const
Definition: shape_rect.h:127
const VECTOR2I GetSize() const
Definition: shape_rect.h:135
const SEG & GetSeg() const
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:69
An abstract shape on 2D plane.
Definition: shape.h:124
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:179
virtual VECTOR2I Centre() const
Compute a center-of-mass of the shape.
Definition: shape.h:230
extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
Definition: vector2d.h:272
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:75
VECTOR2_TRAITS< int >::extended_type extended_type
Definition: vector2d.h:72
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition: eda_angle.h:418
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
@ SH_RECT
axis-aligned rectangle
Definition: shape.h:45
@ SH_CIRCLE
circle
Definition: shape.h:48
@ SH_SIMPLE
simple polygon
Definition: shape.h:49
@ SH_NULL
empty shape (no shape...),
Definition: shape.h:53
@ SH_SEGMENT
line segment
Definition: shape.h:46
@ SH_ARC
circular arc
Definition: shape.h:52
@ SH_POLY_SET_TRIANGLE
a single triangle belonging to a POLY_SET triangulation
Definition: shape.h:54
@ SH_LINE_CHAIN
line chain (polyline)
Definition: shape.h:47
@ SH_COMPOUND
compound shape, consisting of multiple simple shapes
Definition: shape.h:51
static wxString SHAPE_TYPE_asString(SHAPE_TYPE a)
Definition: shape.h:57
static bool collideSingleShapes(const SHAPE *aA, const SHAPE *aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
static bool Collide(const SHAPE_CIRCLE &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
bool CollCaseReversed(const SHAPE *aA, const SHAPE *aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
static VECTOR2I pushoutForce(const SHAPE_CIRCLE &aA, const SEG &aB, int aClearance)
bool CollCase(const SHAPE *aA, const SHAPE *aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
static bool collideShapes(const SHAPE *aA, const SHAPE *aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
VECTOR2I::extended_type ecoord
constexpr int delta
double EuclideanNorm(const VECTOR2I &vector)
Definition: trigo.h:129
VECTOR2< int > VECTOR2I
Definition: vector2d.h:590