KiCad PCB EDA Suite
Loading...
Searching...
No Matches
drc_creepage_utils.cpp
Go to the documentation of this file.
1/*
2 * Copyright The KiCad Developers.
3 * Copyright (C) 2024 Fabien Corona f.corona<at>laposte.net
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License
7 * as published by the Free Software Foundation; either version 2
8 * of the License, or (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, you may find one here:
17 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
18 * or you may search the http://www.gnu.org website for the version 2 license,
19 * or you may write to the Free Software Foundation, Inc.,
20 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
21 */
22
25#include <thread_pool.h>
26
27
28extern bool segmentIntersectsArc( const VECTOR2I& p1, const VECTOR2I& p2, const VECTOR2I& center,
29 double radius, EDA_ANGLE startAngle, EDA_ANGLE endAngle,
30 std::vector<VECTOR2I>* aIntersectPoints );
31
32
33//Check if line segments 'p1q1' and 'p2q2' intersect, excluding endpoint overlap
34
36 std::vector<VECTOR2I>* aIntersectPoints )
37{
38 if( p1 == p2 || p1 == q2 || q1 == p2 || q1 == q2 )
39 return false;
40
41 SEG segment1( p1, q1 );
42 SEG segment2( p2, q2 );
43
44 std::vector<VECTOR2I> intersectionPoints;
45
46
47 INTERSECTABLE_GEOM geom1 = segment1;
48 INTERSECTABLE_GEOM geom2 = segment2;
49
50 INTERSECTION_VISITOR visitor( geom2, intersectionPoints );
51
52 std::visit( visitor, geom1 );
53
54 if( aIntersectPoints )
55 {
56 for( VECTOR2I& point : intersectionPoints )
57 aIntersectPoints->push_back( point );
58 }
59
60
61 return intersectionPoints.size() > 0;
62}
63
64
65bool compareShapes( const CREEP_SHAPE* a, const CREEP_SHAPE* b )
66{
67 if( !a )
68 return true;
69 if( !b )
70 return false;
71
72 if( a->GetType() != b->GetType() )
73 {
74 return a->GetType() < b->GetType();
75 }
76
77 if( a->GetType() == CREEP_SHAPE::TYPE::UNDEFINED )
78 return true;
79
80 auto posA = a->GetPos();
81 auto posB = b->GetPos();
82
83 if( posA != posB )
84 {
85 return posA < posB;
86 }
87 if( a->GetType() == CREEP_SHAPE::TYPE::CIRCLE )
88 {
89 return a->GetRadius() < b->GetRadius();
90 }
91 return false;
92}
93
94bool areEquivalent( const CREEP_SHAPE* a, const CREEP_SHAPE* b )
95{
96 if( !a && !b )
97 {
98 return true;
99 }
100 if( ( !a && b ) || ( a && !b ) )
101 {
102 return false;
103 }
104 if( a->GetType() != b->GetType() )
105 {
106 return false;
107 }
108 if( a->GetType() == CREEP_SHAPE::TYPE::POINT )
109 {
110 return a->GetPos() == b->GetPos();
111 }
112 if( a->GetType() == CREEP_SHAPE::TYPE::CIRCLE )
113 {
114 return a->GetPos() == b->GetPos() && ( a->GetRadius() == b->GetRadius() );
115 }
116 return false;
117}
118
119
120std::vector<PATH_CONNECTION> BE_SHAPE_POINT::Paths( const BE_SHAPE_POINT& aS2, double aMaxWeight,
121 double aMaxSquaredWeight ) const
122{
123 std::vector<PATH_CONNECTION> result;
124
125 double weight = ( this->GetPos() - aS2.GetPos() ).SquaredEuclideanNorm();
126
127 if( weight > aMaxSquaredWeight )
128 return result;
129
131 pc.a1 = this->GetPos();
132 pc.a2 = aS2.GetPos();
133 pc.weight = sqrt( weight );
134
135 result.push_back( pc );
136 return result;
137}
138
139std::vector<PATH_CONNECTION> BE_SHAPE_POINT::Paths( const BE_SHAPE_CIRCLE& aS2, double aMaxWeight,
140 double aMaxSquaredWeight ) const
141{
142 std::vector<PATH_CONNECTION> result;
143 int radius = aS2.GetRadius();
144 VECTOR2I pointPos = this->GetPos();
145 VECTOR2I circleCenter = aS2.GetPos();
146
147 if( radius <= 0 )
148 {
149 return result;
150 }
151
152 double pointToCenterDistanceSquared = ( pointPos - circleCenter ).SquaredEuclideanNorm();
153 double weightSquared = pointToCenterDistanceSquared - (float) radius * (float) radius;
154
155 if( weightSquared > aMaxSquaredWeight )
156 return result;
157
158
159 VECTOR2D direction1 = VECTOR2D( pointPos.x - circleCenter.x, pointPos.y - circleCenter.y );
160 direction1 = direction1.Resize( 1 );
161
162 VECTOR2D direction2 = direction1.Perpendicular();
163
164 double radiusSquared = double( radius ) * double( radius );
165
166 double distance = sqrt( pointToCenterDistanceSquared );
167 double value1 = radiusSquared / distance;
168 double value2 = sqrt( radiusSquared - value1 * value1 );
169
170 VECTOR2D resultPoint;
171
173 pc.a1 = pointPos;
174 pc.weight = sqrt( weightSquared );
175
176 resultPoint = direction1 * value1 + direction2 * value2 + circleCenter;
177 pc.a2.x = int( resultPoint.x );
178 pc.a2.y = int( resultPoint.y );
179 result.push_back( pc );
180
181 resultPoint = direction1 * value1 - direction2 * value2 + circleCenter;
182 pc.a2.x = int( resultPoint.x );
183 pc.a2.y = int( resultPoint.y );
184 result.push_back( pc );
185
186 return result;
187}
188
189std::pair<bool, bool>
191{
192 std::pair<bool, bool> result;
193 double R = m_radius;
194
195 VECTOR2I newPoint = aPoint.GetPos() - m_pos;
196
197 if( newPoint.SquaredEuclideanNorm() <= R * R )
198 {
199 // If the point is inside the arc
200 result.first = false;
201 result.second = false;
202 return result;
203 }
204
205 EDA_ANGLE testAngle = AngleBetweenStartAndEnd( aPoint.GetPos() );
206
207 double startAngle = m_startAngle.AsRadians();
208 double endAngle = m_endAngle.AsRadians();
209 double pointAngle = testAngle.AsRadians();
210
211 bool greaterThan180 = ( m_endAngle - m_startAngle ) > EDA_ANGLE( 180 );
212 bool connectToEndPoint;
213
214 connectToEndPoint = ( cos( startAngle ) * newPoint.x + sin( startAngle ) * newPoint.y >= R );
215
216 if( greaterThan180 )
217 connectToEndPoint &= ( cos( endAngle ) * newPoint.x + sin( endAngle ) * newPoint.y <= R );
218
219 connectToEndPoint |= ( cos( endAngle ) * newPoint.x + sin( endAngle ) * newPoint.y <= R )
220 && ( pointAngle >= endAngle || pointAngle <= startAngle );
221
222
223 result.first = !connectToEndPoint;
224
225 connectToEndPoint = ( cos( endAngle ) * newPoint.x + sin( endAngle ) * newPoint.y >= R );
226
227 if( greaterThan180 )
228 connectToEndPoint &=
229 ( cos( startAngle ) * newPoint.x + sin( startAngle ) * newPoint.y <= R );
230
231 connectToEndPoint |= ( cos( startAngle ) * newPoint.x + sin( startAngle ) * newPoint.y <= R )
232 && ( pointAngle >= endAngle || pointAngle <= startAngle );
233
234
235 result.second = !connectToEndPoint;
236 return result;
237}
238
239std::vector<PATH_CONNECTION> BE_SHAPE_POINT::Paths( const BE_SHAPE_ARC& aS2, double aMaxWeight,
240 double aMaxSquaredWeight ) const
241{
242 std::vector<PATH_CONNECTION> result;
243 VECTOR2I center = aS2.GetPos();
244 double radius = aS2.GetRadius();
245
246 // First path tries to connect to start point
247 // Second path tries to connect to end point
248 std::pair<bool, bool> behavesLikeCircle;
249 behavesLikeCircle = aS2.IsThereATangentPassingThroughPoint( *this );
250
251 if( behavesLikeCircle.first && behavesLikeCircle.second )
252 {
254 return this->Paths( csc, aMaxWeight, aMaxSquaredWeight );
255 }
256
257 if( behavesLikeCircle.first )
258 {
260 std::vector<PATH_CONNECTION> paths = this->Paths( csc, aMaxWeight, aMaxSquaredWeight );
261
262 if( paths.size() > 1 ) // Point to circle creates either 0 or 2 connections
263 result.push_back( paths[1] );
264 }
265 else
266 {
267 BE_SHAPE_POINT csp1( aS2.GetStartPoint() );
268
269 for( const PATH_CONNECTION& pc : this->Paths( csp1, aMaxWeight, aMaxSquaredWeight ) )
270 result.push_back( pc );
271 }
272 if( behavesLikeCircle.second )
273 {
275 std::vector<PATH_CONNECTION> paths = this->Paths( csc, aMaxWeight, aMaxSquaredWeight );
276
277 if( paths.size() > 1 ) // Point to circle creates either 0 or 2 connections
278 {
279 result.push_back( paths[0] );
280 }
281 }
282 else
283 {
284 BE_SHAPE_POINT csp1( aS2.GetEndPoint() );
285
286 for( const PATH_CONNECTION& pc : this->Paths( csp1, aMaxWeight, aMaxSquaredWeight ) )
287 result.push_back( pc );
288 }
289 return result;
290}
291
292std::vector<PATH_CONNECTION> BE_SHAPE_CIRCLE::Paths( const BE_SHAPE_ARC& aS2, double aMaxWeight,
293 double aMaxSquaredWeight ) const
294{
295 std::vector<PATH_CONNECTION> result;
296 VECTOR2I circleCenter = this->GetPos();
297 double circleRadius = this->GetRadius();
298 VECTOR2I arcCenter = aS2.GetPos();
299 double arcRadius = aS2.GetRadius();
300 EDA_ANGLE arcStartAngle = aS2.GetStartAngle();
301 EDA_ANGLE arcEndAngle = aS2.GetEndAngle();
302
303 double centerDistance = ( circleCenter - arcCenter ).EuclideanNorm();
304
305 if( centerDistance + arcRadius < circleRadius )
306 {
307 // The arc is inside the circle
308 return result;
309 }
310
311 BE_SHAPE_POINT csp1( aS2.GetStartPoint() );
312 BE_SHAPE_POINT csp2( aS2.GetEndPoint() );
313 BE_SHAPE_CIRCLE csc( arcCenter, arcRadius );
314
315
316 for( const PATH_CONNECTION& pc : this->Paths( csc, aMaxWeight, aMaxSquaredWeight ) )
317 {
318 EDA_ANGLE pointAngle = aS2.AngleBetweenStartAndEnd( pc.a2 - arcCenter );
319
320 if( pointAngle <= aS2.GetEndAngle() )
321 result.push_back( pc );
322 }
323
324 if( result.size() == 4 )
325 {
326 // It behaved as a circle
327 return result;
328 }
329
330 for( const BE_SHAPE_POINT& csp : { csp1, csp2 } )
331 {
332 for( PATH_CONNECTION pc : this->Paths( csp, aMaxWeight, aMaxSquaredWeight ) )
333 {
334 if( !segmentIntersectsArc( pc.a1, pc.a2, arcCenter, arcRadius, arcStartAngle,
335 arcEndAngle, nullptr ) )
336 {
337 result.push_back( pc );
338 }
339 }
340 }
341
342
343 return result;
344}
345
346
347std::vector<PATH_CONNECTION> BE_SHAPE_ARC::Paths( const BE_SHAPE_ARC& aS2, double aMaxWeight,
348 double aMaxSquaredWeight ) const
349{
350 std::vector<PATH_CONNECTION> result;
351 VECTOR2I circleCenter = this->GetPos();
352 double circleRadius = this->GetRadius();
353 VECTOR2I arcCenter = aS2.GetPos();
354 double arcRadius = aS2.GetRadius();
355
356 double centerDistance = ( circleCenter - arcCenter ).EuclideanNorm();
357
358 if( centerDistance + arcRadius < circleRadius )
359 {
360 // The arc is inside the circle
361 return result;
362 }
363
364 BE_SHAPE_POINT csp1( aS2.GetStartPoint() );
365 BE_SHAPE_POINT csp2( aS2.GetEndPoint() );
366 BE_SHAPE_CIRCLE csc( arcCenter, arcRadius );
367
368
369 for( const PATH_CONNECTION& pc : this->Paths( BE_SHAPE_CIRCLE( aS2.GetPos(), aS2.GetRadius() ),
370 aMaxWeight, aMaxSquaredWeight ) )
371 {
372 EDA_ANGLE pointAngle = aS2.AngleBetweenStartAndEnd( pc.a2 - arcCenter );
373
374 if( pointAngle <= aS2.GetEndAngle() )
375 result.push_back( pc );
376 }
377
378 for( const PATH_CONNECTION& pc : BE_SHAPE_CIRCLE( this->GetPos(), this->GetRadius() )
379 .Paths( aS2, aMaxWeight, aMaxSquaredWeight ) )
380 {
381 EDA_ANGLE pointAngle = this->AngleBetweenStartAndEnd( pc.a2 - arcCenter );
382
383 if( pointAngle <= this->GetEndAngle() )
384 result.push_back( pc );
385 }
386
387 return result;
388}
389
390
391std::vector<PATH_CONNECTION> BE_SHAPE_CIRCLE::Paths( const BE_SHAPE_CIRCLE& aS2, double aMaxWeight,
392 double aMaxSquaredWeight ) const
393{
394 std::vector<PATH_CONNECTION> result;
395
396 VECTOR2I p1 = this->GetPos();
397 VECTOR2I p2 = aS2.GetPos();
398
399 VECTOR2D distSquared( double( ( p2 - p1 ).x ), double( ( p2 - p1 ).y ) );
400 double weightSquared = distSquared.SquaredEuclideanNorm();
401
402 double R1 = this->GetRadius();
403 double R2 = aS2.GetRadius();
404
405 double Rdiff = abs( R1 - R2 );
406 double Rsum = R1 + R2;
407
408 // "Straight" paths
409 double weightSquared1 = weightSquared - Rdiff * Rdiff;
410 // "Crossed" paths
411 double weightSquared2 = weightSquared - Rsum * Rsum;
412
413 if( weightSquared1 <= aMaxSquaredWeight )
414 {
415 VECTOR2D direction1 = VECTOR2D( p2.x - p1.x, p2.y - p1.y );
416 direction1 = direction1.Resize( 1 );
417 VECTOR2D direction2 = direction1.Perpendicular();
418
419 double D = sqrt( weightSquared );
420 double ratio1 = ( R1 - R2 ) / D;
421 double ratio2 = sqrt( 1 - ratio1 * ratio1 );
422
423
425 pc.weight = sqrt( weightSquared1 );
426
427 pc.a1 = p1 + direction1 * R1 * ratio1 + direction2 * R1 * ratio2;
428 pc.a2 = p2 + direction1 * R2 * ratio1 + direction2 * R2 * ratio2;
429
430 result.push_back( pc );
431
432 pc.a1 = p1 + direction1 * R1 * ratio1 - direction2 * R1 * ratio2;
433 pc.a2 = p2 + direction1 * R2 * ratio1 - direction2 * R2 * ratio2;
434
435 result.push_back( pc );
436 }
437 if( weightSquared2 <= aMaxSquaredWeight )
438 {
439 VECTOR2D direction1 = VECTOR2D( p2.x - p1.x, p2.y - p1.y );
440 direction1 = direction1.Resize( 1 );
441 VECTOR2D direction2 = direction1.Perpendicular();
442
443 double D = sqrt( weightSquared );
444 double ratio1 = ( R1 + R2 ) / D;
445 double ratio2 = sqrt( 1 - ratio1 * ratio1 );
446
447
449 pc.weight = sqrt( weightSquared2 );
450
451 pc.a1 = p1 + direction1 * R1 * ratio1 + direction2 * R1 * ratio2;
452 pc.a2 = p2 - direction1 * R2 * ratio1 - direction2 * R2 * ratio2;
453
454 result.push_back( pc );
455
456 pc.a1 = p1 + direction1 * R1 * ratio1 - direction2 * R1 * ratio2;
457 pc.a2 = p2 - direction1 * R2 * ratio1 + direction2 * R2 * ratio2;
458
459 result.push_back( pc );
460 }
461
462 return result;
463}
464
465
466void CREEPAGE_GRAPH::TransformCreepShapesToNodes( std::vector<CREEP_SHAPE*>& aShapes )
467{
468 for( CREEP_SHAPE* p1 : aShapes )
469 {
470 if( !p1 )
471 continue;
472
473 switch( p1->GetType() )
474 {
475 case CREEP_SHAPE::TYPE::POINT: AddNode( GRAPH_NODE::TYPE::POINT, p1, p1->GetPos() ); break;
476 case CREEP_SHAPE::TYPE::CIRCLE: AddNode( GRAPH_NODE::TYPE::CIRCLE, p1, p1->GetPos() ); break;
477 case CREEP_SHAPE::TYPE::ARC: AddNode( GRAPH_NODE::TYPE::ARC, p1, p1->GetPos() ); break;
478 default: break;
479 }
480 }
481}
482
484{
485 // Sort the vector
486 sort( m_shapeCollection.begin(), m_shapeCollection.end(), compareShapes );
487 std::vector<CREEP_SHAPE*> newVector;
488
489 size_t i = 0;
490
491 for( i = 0; i < m_shapeCollection.size() - 1; i++ )
492 {
493 if( m_shapeCollection[i] == nullptr )
494 continue;
495
497 {
498 delete m_shapeCollection[i];
499 m_shapeCollection[i] = nullptr;
500 }
501 else
502 {
503 newVector.push_back( m_shapeCollection[i] );
504 }
505 }
506
507 if( m_shapeCollection[i] )
508 newVector.push_back( m_shapeCollection[i] );
509
510 std::swap( m_shapeCollection, newVector );
511}
512
514{
515 for( BOARD_ITEM* drawing : m_boardEdge )
516 {
517 PCB_SHAPE* d = dynamic_cast<PCB_SHAPE*>( drawing );
518
519 if( !d )
520 continue;
521
522 switch( d->GetShape() )
523 {
524 case SHAPE_T::SEGMENT:
525 {
526 BE_SHAPE_POINT* a = new BE_SHAPE_POINT( d->GetStart() );
527 m_shapeCollection.push_back( a );
528 a = new BE_SHAPE_POINT( d->GetEnd() );
529 m_shapeCollection.push_back( a );
530 break;
531 }
532 case SHAPE_T::RECTANGLE:
533 {
534 BE_SHAPE_POINT* a = new BE_SHAPE_POINT( d->GetStart() );
535 m_shapeCollection.push_back( a );
536 a = new BE_SHAPE_POINT( d->GetEnd() );
537 m_shapeCollection.push_back( a );
538 a = new BE_SHAPE_POINT( VECTOR2I( d->GetEnd().x, d->GetStart().y ) );
539 m_shapeCollection.push_back( a );
540 a = new BE_SHAPE_POINT( VECTOR2I( d->GetStart().x, d->GetEnd().y ) );
541 m_shapeCollection.push_back( a );
542 break;
543 }
544 case SHAPE_T::POLY:
545 {
546 std::vector<VECTOR2I> points;
547 d->DupPolyPointsList( points );
548
549 for( auto p : points )
550 {
551 BE_SHAPE_POINT* a = new BE_SHAPE_POINT( p );
552 m_shapeCollection.push_back( a );
553 }
554 break;
555 }
556 case SHAPE_T::CIRCLE:
557 {
558 BE_SHAPE_CIRCLE* a = new BE_SHAPE_CIRCLE( d->GetCenter(), d->GetRadius() );
559 a->SetParent( d );
560 m_shapeCollection.push_back( a );
561 break;
562 }
563
564 case SHAPE_T::ARC:
565 {
566 // If the arc is not locally convex, only use the endpoints
567 double tolerance = 10;
568 VECTOR2D center( double( d->GetCenter().x ), double( d->GetCenter().y ) );
569 VECTOR2D mid( double( d->GetArcMid().x ), double( d->GetArcMid().y ) );
570 VECTOR2D dir( mid - center );
571 dir = dir / d->GetRadius() * ( d->GetRadius() - tolerance );
572
573 EDA_ANGLE alpha, beta;
574 d->CalcArcAngles( alpha, beta );
575 BE_SHAPE_ARC* a = new BE_SHAPE_ARC( d->GetCenter(), d->GetRadius(), alpha, beta,
576 d->GetStart(), d->GetEnd() );
577 a->SetParent( d );
578
579 m_shapeCollection.push_back( a );
580 break;
581 }
582 default: break;
583 }
584 }
585}
586
587
588std::vector<PCB_SHAPE> GRAPH_CONNECTION::GetShapes()
589{
590 std::vector<PCB_SHAPE> shapes = std::vector<PCB_SHAPE>();
591 int lineWidth = 0;
592
593 if( !m_path.m_show )
594 return shapes;
595
596 if( !n1 || !n2 )
597 return shapes;
598
599 if( n1->m_type == GRAPH_NODE::TYPE::VIRTUAL || n2->m_type == GRAPH_NODE::TYPE::VIRTUAL )
600 {
601 return shapes;
602 }
603
604 if( !m_forceStraightLine && n1->m_parent && ( n1->m_parent == n2->m_parent )
605 && ( n1->m_parent->GetType() == CREEP_SHAPE::TYPE::CIRCLE ) )
606 {
607 VECTOR2I center = n1->m_parent->GetPos();
608 VECTOR2I R1 = n1->m_pos - center;
609 VECTOR2I R2 = n2->m_pos - center;
610 PCB_SHAPE s( nullptr, SHAPE_T::ARC );
611
612 if( R1.Cross( R2 ) > 0 )
613 {
614 s.SetStart( n1->m_pos );
615 s.SetEnd( n2->m_pos );
616 }
617 else
618 {
619 s.SetStart( n2->m_pos );
620 s.SetEnd( n1->m_pos );
621 }
622 s.SetCenter( center );
623
624
625 s.SetWidth( lineWidth );
626 s.SetLayer( Eco1_User );
627
628 shapes.push_back( s );
629 return shapes;
630 }
631
632 else if( !m_forceStraightLine && n1->m_parent && ( n1->m_parent == n2->m_parent )
633 && n1->m_parent->GetType() == CREEP_SHAPE::TYPE::ARC )
634 {
635 BE_SHAPE_ARC* arc = dynamic_cast<BE_SHAPE_ARC*>( n1->m_parent );
636
637 if( !arc )
638 {
639 PCB_SHAPE s;
640 s.SetStart( m_path.a1 );
641 s.SetEnd( m_path.a2 );
642
643 s.SetWidth( lineWidth );
644
645 s.SetLayer( Eco1_User );
646
647 shapes.push_back( s );
648 return shapes;
649 }
650
651 VECTOR2I center = arc->GetPos();
652 VECTOR2I R1 = n1->m_pos - center;
653 VECTOR2I R2 = n2->m_pos - center;
654 PCB_SHAPE s( nullptr, SHAPE_T::ARC );
655
656
657 if( R1.Cross( R2 ) > 0 )
658 {
659 s.SetStart( n1->m_pos );
660 s.SetEnd( n2->m_pos );
661 }
662 else
663 {
664 s.SetStart( n2->m_pos );
665 s.SetEnd( n1->m_pos );
666 }
667
668 s.SetCenter( center );
669
670 //Check that we are on the correct side of the arc.
671 VECTOR2I mid = s.GetArcMid();
672 EDA_ANGLE midAngle = arc->AngleBetweenStartAndEnd( mid );
673
674 if( midAngle > arc->GetEndAngle() )
675 {
676 VECTOR2I tmp;
677 tmp = s.GetStart();
678 s.SetStart( s.GetEnd() );
679 s.SetEnd( tmp );
680 s.SetCenter( center );
681 }
682
683 s.SetWidth( lineWidth );
684 s.SetLayer( Eco1_User );
685
686 shapes.push_back( s );
687 return shapes;
688 }
689
690 PCB_SHAPE s;
691 s.SetStart( m_path.a1 );
692 s.SetEnd( m_path.a2 );
693 s.SetWidth( lineWidth );
694
695 shapes.push_back( s );
696
697 return shapes;
698}
699
700void CREEP_SHAPE::ConnectChildren( std::shared_ptr<GRAPH_NODE>& a1, std::shared_ptr<GRAPH_NODE>&,
701 CREEPAGE_GRAPH& aG ) const
702{
703}
704
705
706void BE_SHAPE_POINT::ConnectChildren( std::shared_ptr<GRAPH_NODE>& a1, std::shared_ptr<GRAPH_NODE>&,
707 CREEPAGE_GRAPH& aG ) const
708{
709}
710
711void BE_SHAPE_CIRCLE::ShortenChildDueToGV( std::shared_ptr<GRAPH_NODE>& a1,
712 std::shared_ptr<GRAPH_NODE>& a2, CREEPAGE_GRAPH& aG,
713 double aNormalWeight ) const
714{
715 EDA_ANGLE angle1 = EDA_ANGLE( a1->m_pos - m_pos );
716 EDA_ANGLE angle2 = EDA_ANGLE( a2->m_pos - m_pos );
717
718 while( angle1 < ANGLE_0 )
719 angle1 += ANGLE_360;
720 while( angle2 < ANGLE_0 )
721 angle2 += ANGLE_360;
722 while( angle1 > ANGLE_360 )
723 angle1 -= ANGLE_360;
724 while( angle2 > ANGLE_360 )
725 angle2 -= ANGLE_360;
726
727
728 EDA_ANGLE maxAngle = angle1 > angle2 ? angle1 : angle2;
729 EDA_ANGLE skipAngle =
730 EDA_ANGLE( asin( float( aG.m_minGrooveWidth ) / ( 2 * m_radius ) ), RADIANS_T );
731 skipAngle += skipAngle; // Cannot multiply EDA_ANGLE by scalar, but this really is angle *2
732 EDA_ANGLE pointAngle = maxAngle - skipAngle;
733
734 VECTOR2I skipPoint = m_pos;
735 skipPoint.x += m_radius * cos( pointAngle.AsRadians() );
736 skipPoint.y += m_radius * sin( pointAngle.AsRadians() );
737
738
739 std::shared_ptr<GRAPH_NODE> gnt = aG.AddNode( GRAPH_NODE::POINT, a1->m_parent, skipPoint );
740
742
743 pc.a1 = maxAngle == angle2 ? a1->m_pos : a2->m_pos;
744 pc.a2 = skipPoint;
745 pc.weight = aNormalWeight - aG.m_minGrooveWidth;
746 aG.AddConnection( maxAngle == angle2 ? a1 : a2, gnt, pc );
747
748 pc.a1 = skipPoint;
749 pc.a2 = maxAngle == angle2 ? a2->m_pos : a1->m_pos;
750 pc.weight = aG.m_minGrooveWidth;
751
752 std::shared_ptr<GRAPH_CONNECTION> gc = aG.AddConnection( gnt, maxAngle == angle2 ? a2 : a1, pc );
753
754 if( gc )
755 gc->m_forceStraightLine = true;
756}
757
758void BE_SHAPE_CIRCLE::ConnectChildren( std::shared_ptr<GRAPH_NODE>& a1,
759 std::shared_ptr<GRAPH_NODE>& a2, CREEPAGE_GRAPH& aG ) const
760{
761 if( !a1 || !a2 )
762 return;
763
764 if( m_radius == 0 )
765 return;
766
767 VECTOR2D distI( a1->m_pos - a2->m_pos );
768 VECTOR2D distD( double( distI.x ), double( distI.y ) );
769
770 double weight = m_radius * 2 * asin( distD.EuclideanNorm() / ( 2.0 * m_radius ) );
771
772 if( ( weight > aG.GetTarget() ) )
773 return;
774
775 if( aG.m_minGrooveWidth <= 0 )
776 {
778 pc.a1 = a1->m_pos;
779 pc.a2 = a2->m_pos;
780 pc.weight = std::max( weight, 0.0 );
781
782 aG.AddConnection( a1, a2, pc );
783 return;
784 }
785
786 if( weight > aG.m_minGrooveWidth )
787 ShortenChildDueToGV( a1, a2, aG, weight );
788 // Else well.. this paths will be "shorted" by another one
789}
790
791
792void BE_SHAPE_ARC::ConnectChildren( std::shared_ptr<GRAPH_NODE>& a1, std::shared_ptr<GRAPH_NODE>& a2,
793 CREEPAGE_GRAPH& aG ) const
794{
795 if( !a1 || !a2 )
796 return;
797
798 EDA_ANGLE angle1 = AngleBetweenStartAndEnd( a1->m_pos );
799 EDA_ANGLE angle2 = AngleBetweenStartAndEnd( a2->m_pos );
800
801 double weight = abs( m_radius * ( angle2 - angle1 ).AsRadians() );
802
803 if( true || aG.m_minGrooveWidth <= 0 )
804 {
805 if( ( weight > aG.GetTarget() ) )
806 return;
807
809 pc.a1 = a1->m_pos;
810 pc.a2 = a2->m_pos;
811 pc.weight = weight;
812
813 aG.AddConnection( a1, a2, pc );
814 return;
815 }
816
817 if( weight > aG.m_minGrooveWidth )
818 ShortenChildDueToGV( a1, a2, aG, weight );
819}
820
821void CREEPAGE_GRAPH::SetTarget( double aTarget )
822{
823 m_creepageTarget = aTarget;
824 m_creepageTargetSquared = aTarget * aTarget;
825}
826
827bool segmentIntersectsArc( const VECTOR2I& p1, const VECTOR2I& p2, const VECTOR2I& center,
828 double radius, EDA_ANGLE startAngle, EDA_ANGLE endAngle,
829 std::vector<VECTOR2I>* aIntersectPoints )
830{
831 SEG segment( p1, p2 );
832
833 VECTOR2I startPoint( radius * cos( startAngle.AsRadians() ),
834 radius * sin( startAngle.AsRadians() ) );
835 startPoint += center;
836 SHAPE_ARC arc( center, startPoint, endAngle - startAngle );
837
838 std::vector<VECTOR2I> intersectionPoints;
839 INTERSECTABLE_GEOM geom1 = segment;
840 INTERSECTABLE_GEOM geom2 = arc;
841
842 INTERSECTION_VISITOR visitor( geom2, intersectionPoints );
843 std::visit( visitor, geom1 );
844
845 if( aIntersectPoints )
846 {
847 for( VECTOR2I& point : intersectionPoints )
848 aIntersectPoints->push_back( point );
849 }
850
851 return intersectionPoints.size() > 0;
852}
853
854std::vector<PATH_CONNECTION> CU_SHAPE_SEGMENT::Paths( const BE_SHAPE_POINT& aS2, double aMaxWeight,
855 double aMaxSquaredWeight ) const
856{
857 std::vector<PATH_CONNECTION> result;
858 VECTOR2I start = this->GetStart();
859 VECTOR2I end = this->GetEnd();
860 double halfWidth = this->GetWidth() / 2;
861 EDA_ANGLE trackAngle( end - start );
862 VECTOR2I pointPos = aS2.GetPos();
863
864 double length = ( start - end ).EuclideanNorm();
865 double projectedPos = cos( trackAngle.AsRadians() ) * ( pointPos.x - start.x )
866 + sin( trackAngle.AsRadians() ) * ( pointPos.y - start.y );
867
868 VECTOR2I newPoint;
869
870 if( projectedPos <= 0 )
871 {
872 newPoint = start + ( pointPos - start ).Resize( halfWidth );
873 }
874 else if( projectedPos >= length )
875 {
876 newPoint = end + ( pointPos - end ).Resize( halfWidth );
877 }
878 else
879 {
880 double posOnSegment = ( start - pointPos ).SquaredEuclideanNorm()
881 - ( end - pointPos ).SquaredEuclideanNorm();
882 posOnSegment = posOnSegment / ( 2 * length ) + length / 2;
883
884 newPoint = start + ( end - start ).Resize( posOnSegment );
885 newPoint += ( pointPos - newPoint ).Resize( halfWidth );
886 }
887
888 double weightSquared = ( pointPos - newPoint ).SquaredEuclideanNorm();
889
890 if( weightSquared > aMaxSquaredWeight )
891 return result;
892
894 pc.a1 = newPoint;
895 pc.a2 = pointPos;
896 pc.weight = sqrt( weightSquared );
897
898 result.push_back( pc );
899 return result;
900}
901
902
903std::vector<PATH_CONNECTION> CU_SHAPE_SEGMENT::Paths( const BE_SHAPE_CIRCLE& aS2, double aMaxWeight,
904 double aMaxSquaredWeight ) const
905{
906 std::vector<PATH_CONNECTION> result;
907 VECTOR2I start = this->GetStart();
908 VECTOR2I end = this->GetEnd();
909 double halfWidth = this->GetWidth() / 2;
910
911 double circleRadius = aS2.GetRadius();
912 VECTOR2I circleCenter = aS2.GetPos();
913 double length = ( start - end ).EuclideanNorm();
914 EDA_ANGLE trackAngle( end - start );
915
916 double weightSquared = std::numeric_limits<double>::infinity();
917 VECTOR2I PointOnTrack, PointOnCircle;
918
919 // There are two possible paths
920 // First the one on the side of the start of the track.
921 double projectedPos1 = cos( trackAngle.AsRadians() ) * ( circleCenter.x - start.x )
922 + sin( trackAngle.AsRadians() ) * ( circleCenter.y - start.y );
923 double projectedPos2 = projectedPos1 + circleRadius;
924 projectedPos1 = projectedPos1 - circleRadius;
925
926 double trackSide = ( end - start ).Cross( circleCenter - start ) > 0 ? 1 : -1;
927
928 if( ( projectedPos1 < 0 && projectedPos2 < 0 ) )
929 {
930 CU_SHAPE_CIRCLE csc( start, halfWidth );
931 for( PATH_CONNECTION pc : csc.Paths( aS2, aMaxWeight, aMaxSquaredWeight ) )
932 {
933 result.push_back( pc );
934 }
935 }
936 else if( ( projectedPos1 > length && projectedPos2 > length ) )
937 {
938 CU_SHAPE_CIRCLE csc( end, halfWidth );
939
940 for( const PATH_CONNECTION& pc : csc.Paths( aS2, aMaxWeight, aMaxSquaredWeight ) )
941 result.push_back( pc );
942 }
943
944 else if( ( projectedPos1 >= 0 ) && ( projectedPos1 <= length ) && ( projectedPos2 >= 0 )
945 && ( projectedPos2 <= length ) )
946 {
947 // Both point connects to the segment part of the track
948 PointOnTrack = start;
949 PointOnTrack += ( end - start ).Resize( projectedPos1 );
950 PointOnTrack += ( end - start ).Perpendicular().Resize( halfWidth ) * trackSide;
951 PointOnCircle = circleCenter - ( end - start ).Resize( circleRadius );
952 weightSquared = ( PointOnCircle - PointOnTrack ).SquaredEuclideanNorm();
953
954 if( weightSquared < aMaxSquaredWeight )
955 {
957 pc.a1 = PointOnTrack;
958 pc.a2 = PointOnCircle;
959 pc.weight = sqrt( weightSquared );
960
961 result.push_back( pc );
962
963 PointOnTrack = start;
964 PointOnTrack += ( end - start ).Resize( projectedPos2 );
965 PointOnTrack += ( end - start ).Perpendicular().Resize( halfWidth ) * trackSide;
966 PointOnCircle = circleCenter + ( end - start ).Resize( circleRadius );
967
968
969 pc.a1 = PointOnTrack;
970 pc.a2 = PointOnCircle;
971
972 result.push_back( pc );
973 }
974 }
975 else if( ( ( projectedPos1 >= 0 ) && ( projectedPos1 <= length ) )
976 && ( ( projectedPos2 > length ) || projectedPos2 < 0 ) )
977 {
978 CU_SHAPE_CIRCLE csc( end, halfWidth );
979 std::vector<PATH_CONNECTION> pcs = csc.Paths( aS2, aMaxWeight, aMaxSquaredWeight );
980
981 if( pcs.size() < 2 )
982 return result;
983
984 result.push_back( pcs.at( trackSide == 1 ? 1 : 0 ) );
985
986
987 PointOnTrack = start;
988 PointOnTrack += ( end - start ).Resize( projectedPos1 );
989 PointOnTrack += ( end - start ).Perpendicular().Resize( halfWidth ) * trackSide;
990 PointOnCircle = circleCenter - ( end - start ).Resize( circleRadius );
991 weightSquared = ( PointOnCircle - PointOnTrack ).SquaredEuclideanNorm();
992
993 if( weightSquared < aMaxSquaredWeight )
994 {
996 pc.a1 = PointOnTrack;
997 pc.a2 = PointOnCircle;
998 pc.weight = sqrt( weightSquared );
999
1000 result.push_back( pc );
1001 }
1002 }
1003 else if( ( ( projectedPos2 >= 0 ) && ( projectedPos2 <= length ) )
1004 && ( ( projectedPos1 > length ) || projectedPos1 < 0 ) )
1005 {
1006 CU_SHAPE_CIRCLE csc( start, halfWidth );
1007 std::vector<PATH_CONNECTION> pcs = csc.Paths( aS2, aMaxWeight, aMaxSquaredWeight );
1008
1009 if( pcs.size() < 2 )
1010 return result;
1011
1012 result.push_back( pcs.at( trackSide == 1 ? 0 : 1 ) );
1013
1014 PointOnTrack = start;
1015 PointOnTrack += ( end - start ).Resize( projectedPos2 );
1016 PointOnTrack += ( end - start ).Perpendicular().Resize( halfWidth ) * trackSide;
1017 PointOnCircle = circleCenter + ( end - start ).Resize( circleRadius );
1018 weightSquared = ( PointOnCircle - PointOnTrack ).SquaredEuclideanNorm();
1019
1020 if( weightSquared < aMaxSquaredWeight )
1021 {
1022 PATH_CONNECTION pc;
1023 pc.a1 = PointOnTrack;
1024 pc.a2 = PointOnCircle;
1025 pc.weight = sqrt( weightSquared );
1026
1027 result.push_back( pc );
1028 }
1029 }
1030
1031 return result;
1032}
1033
1034
1035std::vector<PATH_CONNECTION> CU_SHAPE_SEGMENT::Paths( const BE_SHAPE_ARC& aS2, double aMaxWeight,
1036 double aMaxSquaredWeight ) const
1037{
1038 std::vector<PATH_CONNECTION> result;
1039
1040 BE_SHAPE_CIRCLE bsc( aS2.GetPos(), aS2.GetRadius() );
1041
1042 for( const PATH_CONNECTION& pc : this->Paths( bsc, aMaxWeight, aMaxSquaredWeight ) )
1043 {
1044 EDA_ANGLE testAngle = aS2.AngleBetweenStartAndEnd( pc.a2 );
1045
1046 if( testAngle < aS2.GetEndAngle() )
1047 result.push_back( pc );
1048 }
1049
1050 if( result.size() < 2 )
1051 {
1052 BE_SHAPE_POINT bsp1( aS2.GetStartPoint() );
1053 BE_SHAPE_POINT bsp2( aS2.GetEndPoint() );
1054
1055 VECTOR2I beArcPos = aS2.GetPos();
1056 int beArcRadius = aS2.GetRadius();
1057 EDA_ANGLE beArcStartAngle = aS2.GetStartAngle();
1058 EDA_ANGLE beArcEndAngle = aS2.GetEndAngle();
1059
1060 for( const PATH_CONNECTION& pc : this->Paths( bsp1, aMaxWeight, aMaxSquaredWeight ) )
1061 {
1062 if( !segmentIntersectsArc( pc.a1, pc.a2, beArcPos, beArcRadius, beArcStartAngle,
1063 beArcEndAngle, nullptr ) )
1064 {
1065 result.push_back( pc );
1066 }
1067 }
1068
1069 for( const PATH_CONNECTION& pc : this->Paths( bsp2, aMaxWeight, aMaxSquaredWeight ) )
1070 {
1071 if( !segmentIntersectsArc( pc.a1, pc.a2, beArcPos, beArcRadius, beArcStartAngle,
1072 beArcEndAngle, nullptr ) )
1073 {
1074 result.push_back( pc );
1075 }
1076 }
1077 }
1078
1079 return result;
1080}
1081
1082
1083std::vector<PATH_CONNECTION> CU_SHAPE_CIRCLE::Paths( const BE_SHAPE_ARC& aS2, double aMaxWeight,
1084 double aMaxSquaredWeight ) const
1085{
1086 std::vector<PATH_CONNECTION> result;
1087 VECTOR2I beArcPos = aS2.GetPos();
1088 int beArcRadius = aS2.GetRadius();
1089 EDA_ANGLE beArcStartAngle = aS2.GetStartAngle();
1090 EDA_ANGLE beArcEndAngle = aS2.GetEndAngle();
1091
1092 BE_SHAPE_CIRCLE bsc( beArcPos, beArcRadius );
1093
1094 for( const PATH_CONNECTION& pc : this->Paths( bsc, aMaxWeight, aMaxSquaredWeight ) )
1095 {
1096 EDA_ANGLE testAngle = aS2.AngleBetweenStartAndEnd( pc.a2 );
1097
1098 if( testAngle < aS2.GetEndAngle() )
1099 result.push_back( pc );
1100 }
1101
1102 if( result.size() < 2 )
1103 {
1104 BE_SHAPE_POINT bsp1( aS2.GetStartPoint() );
1105 BE_SHAPE_POINT bsp2( aS2.GetEndPoint() );
1106
1107 for( const PATH_CONNECTION& pc : this->Paths( bsp1, aMaxWeight, aMaxSquaredWeight ) )
1108 {
1109 if( !segmentIntersectsArc( pc.a1, pc.a2, beArcPos, beArcRadius, beArcStartAngle,
1110 beArcEndAngle, nullptr ) )
1111 {
1112 result.push_back( pc );
1113 }
1114 }
1115
1116 for( const PATH_CONNECTION& pc : this->Paths( bsp2, aMaxWeight, aMaxSquaredWeight ) )
1117 {
1118 if( !segmentIntersectsArc( pc.a1, pc.a2, beArcPos, beArcRadius, beArcStartAngle,
1119 beArcEndAngle, nullptr ) )
1120 {
1121 result.push_back( pc );
1122 }
1123 }
1124 }
1125 return result;
1126}
1127
1128std::vector<PATH_CONNECTION> CU_SHAPE_ARC::Paths( const BE_SHAPE_CIRCLE& aS2, double aMaxWeight,
1129 double aMaxSquaredWeight ) const
1130{
1131 std::vector<PATH_CONNECTION> result;
1132
1133 CU_SHAPE_CIRCLE csc( this->GetPos(), this->GetRadius() + this->GetWidth() / 2 );
1134
1135 for( const PATH_CONNECTION& pc : this->Paths( csc, aMaxWeight, aMaxSquaredWeight ) )
1136 {
1137 EDA_ANGLE testAngle = this->AngleBetweenStartAndEnd( pc.a2 );
1138
1139 if( testAngle < this->GetEndAngle() )
1140 result.push_back( pc );
1141 }
1142
1143 if( result.size() < 2 )
1144 {
1145 CU_SHAPE_CIRCLE csc1( this->GetStartPoint(), this->GetWidth() / 2 );
1146 CU_SHAPE_CIRCLE csc2( this->GetEndPoint(), this->GetWidth() / 2 );
1147
1148 for( const PATH_CONNECTION& pc : this->Paths( csc1, aMaxWeight, aMaxSquaredWeight ) )
1149 result.push_back( pc );
1150
1151 for( const PATH_CONNECTION& pc : this->Paths( csc2, aMaxWeight, aMaxSquaredWeight ) )
1152 result.push_back( pc );
1153 }
1154
1155 return result;
1156}
1157
1158
1159std::vector<PATH_CONNECTION> CU_SHAPE_ARC::Paths( const BE_SHAPE_ARC& aS2, double aMaxWeight,
1160 double aMaxSquaredWeight ) const
1161{
1162 std::vector<PATH_CONNECTION> result;
1163 VECTOR2I beArcPos = aS2.GetPos();
1164 int beArcRadius = aS2.GetRadius();
1165 EDA_ANGLE beArcStartAngle = aS2.GetStartAngle();
1166 EDA_ANGLE beArcEndAngle = aS2.GetEndAngle();
1167
1168 BE_SHAPE_CIRCLE bsc( aS2.GetPos(), aS2.GetRadius() );
1169
1170 for( const PATH_CONNECTION& pc : this->Paths( bsc, aMaxWeight, aMaxSquaredWeight ) )
1171 {
1172 EDA_ANGLE testAngle = aS2.AngleBetweenStartAndEnd( pc.a2 );
1173
1174 if( testAngle < aS2.GetEndAngle() )
1175 result.push_back( pc );
1176 }
1177
1178 if( result.size() < 2 )
1179 {
1180 BE_SHAPE_POINT bsp1( aS2.GetStartPoint() );
1181 BE_SHAPE_POINT bsp2( aS2.GetEndPoint() );
1182
1183 for( const PATH_CONNECTION& pc : this->Paths( bsp1, aMaxWeight, aMaxSquaredWeight ) )
1184 {
1185 if( !segmentIntersectsArc( pc.a1, pc.a2, beArcPos, beArcRadius, beArcStartAngle,
1186 beArcEndAngle, nullptr ) )
1187 {
1188 result.push_back( pc );
1189 }
1190 }
1191
1192 for( const PATH_CONNECTION& pc : this->Paths( bsp2, aMaxWeight, aMaxSquaredWeight ) )
1193 {
1194 if( !segmentIntersectsArc( pc.a1, pc.a2, beArcPos, beArcRadius, beArcStartAngle,
1195 beArcEndAngle, nullptr ) )
1196 {
1197 result.push_back( pc );
1198 }
1199 }
1200 }
1201
1202 return result;
1203}
1204
1205
1206std::vector<PATH_CONNECTION> CU_SHAPE_CIRCLE::Paths( const BE_SHAPE_POINT& aS2, double aMaxWeight,
1207 double aMaxSquaredWeight ) const
1208{
1209 std::vector<PATH_CONNECTION> result;
1210
1211 double R = this->GetRadius();
1212 VECTOR2I center = this->GetPos();
1213 VECTOR2I point = aS2.GetPos();
1214 double weight = ( center - point ).EuclideanNorm() - R;
1215
1216 if( weight > aMaxWeight )
1217 return result;
1218
1219 PATH_CONNECTION pc;
1220 pc.weight = std::max( weight, 0.0 );
1221 pc.a2 = point;
1222 pc.a1 = center + ( point - center ).Resize( R );
1223
1224 result.push_back( pc );
1225 return result;
1226}
1227
1228
1229std::vector<PATH_CONNECTION> CU_SHAPE_CIRCLE::Paths( const CU_SHAPE_CIRCLE& aS2, double aMaxWeight,
1230 double aMaxSquaredWeight ) const
1231{
1232 std::vector<PATH_CONNECTION> result;
1233
1234 double R1 = this->GetRadius();
1235 double R2 = aS2.GetRadius();
1236 VECTOR2I C1 = this->GetPos();
1237 VECTOR2I C2 = aS2.GetPos();
1238
1239 if( ( C1 - C2 ).SquaredEuclideanNorm() < ( R1 - R2 ) * ( R1 - R2 ) )
1240 {
1241 // One of the circles is inside the other
1242 return result;
1243 }
1244
1245 double weight = ( C1 - C2 ).EuclideanNorm() - R1 - R2;
1246
1247 if( weight > aMaxWeight || weight < 0 )
1248 return result;
1249
1250 PATH_CONNECTION pc;
1251 pc.weight = std::max( weight, 0.0 );
1252 pc.a1 = ( C2 - C1 ).Resize( R1 ) + C1;
1253 pc.a2 = ( C1 - C2 ).Resize( R2 ) + C2;
1254 result.push_back( pc );
1255 return result;
1256}
1257
1258
1259std::vector<PATH_CONNECTION> CU_SHAPE_SEGMENT::Paths( const CU_SHAPE_CIRCLE& aS2, double aMaxWeight,
1260 double aMaxSquaredWeight ) const
1261{
1262 std::vector<PATH_CONNECTION> result;
1263
1264 VECTOR2I s_start = this->GetStart();
1265 VECTOR2I s_end = this->GetEnd();
1266 double halfWidth = this->GetWidth() / 2;
1267
1268 EDA_ANGLE trackAngle( s_end - s_start );
1269 VECTOR2I pointPos = aS2.GetPos();
1270
1271 double length = ( s_start - s_end ).EuclideanNorm();
1272 double projectedPos = cos( trackAngle.AsRadians() ) * ( pointPos.x - s_start.x )
1273 + sin( trackAngle.AsRadians() ) * ( pointPos.y - s_start.y );
1274
1275 if( ( projectedPos <= 0 ) || ( s_start == s_end ) )
1276 {
1277 CU_SHAPE_CIRCLE csc( s_start, halfWidth );
1278 return csc.Paths( aS2, aMaxWeight, aMaxSquaredWeight );
1279 }
1280
1281 if( projectedPos >= length )
1282 {
1283 CU_SHAPE_CIRCLE csc( s_end, halfWidth );
1284 return csc.Paths( aS2, aMaxWeight, aMaxSquaredWeight );
1285 }
1286
1287 double radius = aS2.GetRadius();
1288 double trackSide = ( s_end - s_start ).Cross( pointPos - s_start ) > 0 ? 1 : -1;
1289
1290 PATH_CONNECTION pc;
1291 pc.a1 = s_start + ( s_end - s_start ).Resize( projectedPos )
1292 + ( s_end - s_start ).Perpendicular().Resize( halfWidth ) * trackSide;
1293 pc.a2 = ( pc.a1 - pointPos ).Resize( radius ) + pointPos;
1294 pc.weight = ( pc.a2 - pc.a1 ).SquaredEuclideanNorm();
1295
1296 if( pc.weight <= aMaxSquaredWeight )
1297 {
1298 pc.weight = sqrt( pc.weight );
1299 result.push_back( pc );
1300 }
1301
1302 return result;
1303}
1304
1305
1306std::vector<PATH_CONNECTION> CU_SHAPE_CIRCLE::Paths( const CU_SHAPE_ARC& aS2, double aMaxWeight,
1307 double aMaxSquaredWeight ) const
1308{
1309 std::vector<PATH_CONNECTION> result;
1310
1311 VECTOR2I circlePos = this->GetPos();
1312 VECTOR2I arcPos = aS2.GetPos();
1313
1314 double circleRadius = this->GetRadius();
1315 double arcRadius = aS2.GetRadius();
1316
1317 VECTOR2I startPoint = aS2.GetStartPoint();
1318 VECTOR2I endPoint = aS2.GetEndPoint();
1319
1320 CU_SHAPE_CIRCLE csc( arcPos, arcRadius + aS2.GetWidth() / 2 );
1321
1322 if( ( circlePos - arcPos ).EuclideanNorm() > arcRadius + circleRadius )
1323 {
1324 const std::vector<PATH_CONNECTION>& pcs = this->Paths( csc, aMaxWeight, aMaxSquaredWeight );
1325
1326 if( pcs.size() == 1 )
1327 {
1328 EDA_ANGLE testAngle = aS2.AngleBetweenStartAndEnd( pcs[0].a2 );
1329
1330 if( testAngle < aS2.GetEndAngle() )
1331 {
1332 result.push_back( pcs[0] );
1333 return result;
1334 }
1335 }
1336 }
1337
1338 CU_SHAPE_CIRCLE csc1( startPoint, aS2.GetWidth() / 2 );
1339 CU_SHAPE_CIRCLE csc2( endPoint, aS2.GetWidth() / 2 );
1340
1341 PATH_CONNECTION* bestPath = nullptr;
1342
1343
1344 std::vector<PATH_CONNECTION> pcs1 = this->Paths( csc1, aMaxWeight, aMaxSquaredWeight );
1345 std::vector<PATH_CONNECTION> pcs2 = this->Paths( csc2, aMaxWeight, aMaxSquaredWeight );
1346
1347 for( PATH_CONNECTION& pc : pcs1 )
1348 {
1349 if( !bestPath || ( ( bestPath->weight > pc.weight ) && ( pc.weight > 0 ) ) )
1350 bestPath = &pc;
1351 }
1352
1353 for( PATH_CONNECTION& pc : pcs2 )
1354 {
1355 if( !bestPath || ( ( bestPath->weight > pc.weight ) && ( pc.weight > 0 ) ) )
1356 bestPath = &pc;
1357 }
1358
1359 // If the circle center is insde the arc ring
1360
1361 PATH_CONNECTION pc3;
1362
1363 if( ( circlePos - arcPos ).SquaredEuclideanNorm() < arcRadius * arcRadius )
1364 {
1365 if( circlePos != arcPos ) // The best path is already found otherwise
1366 {
1367 EDA_ANGLE testAngle = aS2.AngleBetweenStartAndEnd( circlePos );
1368
1369 if( testAngle < aS2.GetEndAngle() )
1370 {
1371 pc3.weight = std::max( arcRadius - ( circlePos - arcPos ).EuclideanNorm() - circleRadius, 0.0 );
1372 pc3.a1 = circlePos + ( circlePos - arcPos ).Resize( circleRadius );
1373 pc3.a2 = arcPos + ( circlePos - arcPos ).Resize( arcRadius - aS2.GetWidth() / 2 );
1374
1375 if( !bestPath || ( ( bestPath->weight > pc3.weight ) && ( pc3.weight > 0 ) ) )
1376 bestPath = &pc3;
1377 }
1378 }
1379 }
1380
1381 if( bestPath && bestPath->weight > 0 )
1382 {
1383 result.push_back( *bestPath );
1384 }
1385
1386 return result;
1387}
1388
1389
1390std::vector<PATH_CONNECTION> CU_SHAPE_SEGMENT::Paths( const CU_SHAPE_ARC& aS2, double aMaxWeight,
1391 double aMaxSquaredWeight ) const
1392{
1393 std::vector<PATH_CONNECTION> result;
1394
1395 VECTOR2I s_start = this->GetStart();
1396 VECTOR2I s_end = this->GetEnd();
1397 double halfWidth1 = this->GetWidth() / 2;
1398
1399 VECTOR2I arcPos = aS2.GetPos();
1400 double arcRadius = aS2.GetRadius();
1401 double halfWidth2 = aS2.GetWidth() / 2;
1402
1403
1404 CU_SHAPE_CIRCLE csc( arcPos, arcRadius + halfWidth2 );
1405
1406 std::vector<PATH_CONNECTION> pcs;
1407 pcs = this->Paths( csc, aMaxWeight, aMaxSquaredWeight );
1408
1409 if( pcs.size() < 1 )
1410 return result;
1411
1412 VECTOR2I circlePoint;
1413 EDA_ANGLE testAngle;
1414
1415 if( pcs.size() > 0 )
1416 {
1417 circlePoint = pcs[0].a1;
1418 testAngle = ( aS2.AngleBetweenStartAndEnd( pcs[0].a1 ) );
1419 }
1420
1421 if( testAngle < aS2.GetEndAngle() && pcs.size() > 0 )
1422 {
1423 result.push_back( pcs[0] );
1424 return result;
1425 }
1426
1427 CU_SHAPE_CIRCLE csc1( aS2.GetStartPoint(), halfWidth2 );
1428 CU_SHAPE_CIRCLE csc2( aS2.GetEndPoint(), halfWidth2 );
1429 PATH_CONNECTION* bestPath = nullptr;
1430
1431 for( PATH_CONNECTION& pc : this->Paths( csc1, aMaxWeight, aMaxSquaredWeight ) )
1432 {
1433 if( !bestPath || ( bestPath->weight > pc.weight ) )
1434 bestPath = &pc;
1435 }
1436
1437 for( PATH_CONNECTION& pc : this->Paths( csc2, aMaxWeight, aMaxSquaredWeight ) )
1438 {
1439 if( !bestPath || ( bestPath->weight > pc.weight ) )
1440 bestPath = &pc;
1441 }
1442
1443 CU_SHAPE_CIRCLE csc3( s_start, halfWidth1 );
1444 CU_SHAPE_CIRCLE csc4( s_end, halfWidth1 );
1445
1446 for( PATH_CONNECTION& pc : csc3.Paths( aS2, aMaxWeight, aMaxSquaredWeight ) )
1447 {
1448 if( !bestPath || ( bestPath->weight > pc.weight ) )
1449 bestPath = &pc;
1450 }
1451
1452
1453 for( PATH_CONNECTION& pc : csc4.Paths( aS2, aMaxWeight, aMaxSquaredWeight ) )
1454 {
1455 if( !bestPath || ( bestPath->weight > pc.weight ) )
1456 bestPath = &pc;
1457 }
1458
1459 if( bestPath )
1460 result.push_back( *bestPath );
1461
1462 return result;
1463}
1464
1465// Function to compute the projection of point P onto the line segment AB
1467{
1468 if( A == B )
1469 return A;
1470 if( A == P )
1471 return A;
1472
1473 VECTOR2I AB = B - A;
1474 VECTOR2I AP = P - A;
1475
1476 double t = float( AB.Dot( AP ) ) / float( AB.SquaredEuclideanNorm() );
1477
1478 // Clamp t to the range [0, 1] to restrict the projection to the segment
1479 t = std::max( 0.0, std::min( 1.0, t ) );
1480
1481 return A + ( AB * t );
1482}
1483
1484
1485std::vector<PATH_CONNECTION> CU_SHAPE_SEGMENT::Paths( const CU_SHAPE_SEGMENT& aS2,
1486 double aMaxWeight,
1487 double aMaxSquaredWeight ) const
1488{
1489 std::vector<PATH_CONNECTION> result;
1490
1491 VECTOR2I A( this->GetStart() );
1492 VECTOR2I B( this->GetEnd() );
1493 double halfWidth1 = this->GetWidth() / 2;
1494
1495
1496 VECTOR2I C( aS2.GetStart() );
1497 VECTOR2I D( aS2.GetEnd() );
1498 double halfWidth2 = aS2.GetWidth() / 2;
1499
1504
1505 // Calculate all possible squared distances between the segments
1506 double dist1 = ( P1 - C ).SquaredEuclideanNorm();
1507 double dist2 = ( P2 - D ).SquaredEuclideanNorm();
1508 double dist3 = ( P3 - A ).SquaredEuclideanNorm();
1509 double dist4 = ( P4 - B ).SquaredEuclideanNorm();
1510
1511 // Find the minimum squared distance and update closest points
1512 double min_dist = dist1;
1513 VECTOR2I closest1 = P1;
1514 VECTOR2I closest2 = C;
1515
1516 if( dist2 < min_dist )
1517 {
1518 min_dist = dist2;
1519 closest1 = P2;
1520 closest2 = D;
1521 }
1522
1523 if( dist3 < min_dist )
1524 {
1525 min_dist = dist3;
1526 closest1 = A;
1527 closest2 = P3;
1528 }
1529
1530 if( dist4 < min_dist )
1531 {
1532 min_dist = dist4;
1533 closest1 = B;
1534 closest2 = P4;
1535 }
1536
1537
1538 PATH_CONNECTION pc;
1539 pc.a1 = closest1 + ( closest2 - closest1 ).Resize( halfWidth1 );
1540 pc.a2 = closest2 + ( closest1 - closest2 ).Resize( halfWidth2 );
1541 pc.weight = std::max( sqrt( min_dist ) - halfWidth1 - halfWidth2, 0.0 );
1542
1543 if( pc.weight <= aMaxWeight )
1544 result.push_back( pc );
1545
1546 return result;
1547}
1548
1549
1550std::vector<PATH_CONNECTION> CU_SHAPE_CIRCLE::Paths( const BE_SHAPE_CIRCLE& aS2, double aMaxWeight,
1551 double aMaxSquaredWeight ) const
1552{
1553 std::vector<PATH_CONNECTION> result;
1554
1555 double R1 = this->GetRadius();
1556 double R2 = aS2.GetRadius();
1557 VECTOR2I center1 = this->GetPos();
1558 VECTOR2I center2 = aS2.GetPos();
1559 double dist = ( center1 - center2 ).EuclideanNorm();
1560
1561 if( dist > aMaxWeight || dist == 0 )
1562 return result;
1563
1564 double weight = sqrt( dist * dist - R2 * R2 ) - R1;
1565 double theta = asin( R2 / dist );
1566 double psi = acos( R2 / dist );
1567
1568 if( weight > aMaxWeight )
1569 return result;
1570
1571 PATH_CONNECTION pc;
1572 pc.weight = std::max( weight, 0.0 );
1573
1574 double circleAngle = EDA_ANGLE( center2 - center1 ).AsRadians();
1575
1576 VECTOR2I pStart;
1577 VECTOR2I pEnd;
1578
1579 pStart = VECTOR2I( R1 * cos( theta + circleAngle ), R1 * sin( theta + circleAngle ) );
1580 pStart += center1;
1581 pEnd = VECTOR2I( -R2 * cos( psi - circleAngle ), R2 * sin( psi - circleAngle ) );
1582 pEnd += center2;
1583
1584 pc.a1 = pStart;
1585 pc.a2 = pEnd;
1586 result.push_back( pc );
1587
1588 pStart = VECTOR2I( R1 * cos( -theta + circleAngle ), R1 * sin( -theta + circleAngle ) );
1589 pStart += center1;
1590 pEnd = VECTOR2I( -R2 * cos( -psi - circleAngle ), R2 * sin( -psi - circleAngle ) );
1591 pEnd += center2;
1592
1593 pc.a1 = pStart;
1594 pc.a2 = pEnd;
1595
1596 result.push_back( pc );
1597 return result;
1598}
1599
1600
1601std::vector<PATH_CONNECTION> CU_SHAPE_ARC::Paths( const BE_SHAPE_POINT& aS2, double aMaxWeight,
1602 double aMaxSquaredWeight ) const
1603{
1604 std::vector<PATH_CONNECTION> result;
1605 VECTOR2I point = aS2.GetPos();
1606 VECTOR2I arcCenter = this->GetPos();
1607
1608 double radius = this->GetRadius();
1609 double width = this->GetWidth();
1610
1611 EDA_ANGLE angle( point - arcCenter );
1612
1613 while( angle < this->GetStartAngle() )
1614 angle += ANGLE_360;
1615 while( angle > this->GetEndAngle() + ANGLE_360 )
1616 angle -= ANGLE_360;
1617
1618 if( angle < this->GetEndAngle() )
1619 {
1620 if( ( point - arcCenter ).SquaredEuclideanNorm() > radius * radius )
1621 {
1622 CU_SHAPE_CIRCLE circle( arcCenter, radius + width / 2 );
1623 return circle.Paths( aS2, aMaxWeight, aMaxSquaredWeight );
1624 }
1625 else
1626 {
1627 PATH_CONNECTION pc;
1628 pc.weight = std::max( ( radius - width / 2 ) - ( point - arcCenter ).EuclideanNorm(), 0.0 );
1629 pc.a1 = ( point - arcCenter ).Resize( radius - width / 2 ) + arcCenter;
1630 pc.a2 = point;
1631
1632 if( pc.weight > 0 && pc.weight < aMaxWeight )
1633 result.push_back( pc );
1634
1635 return result;
1636 }
1637 }
1638 else
1639 {
1640 VECTOR2I nearestPoint;
1641
1642 if( ( point - this->GetStartPoint() ).SquaredEuclideanNorm()
1643 > ( point - this->GetEndPoint() ).SquaredEuclideanNorm() )
1644 {
1645 nearestPoint = this->GetEndPoint();
1646 }
1647 else
1648 {
1649 nearestPoint = this->GetStartPoint();
1650 }
1651
1652 CU_SHAPE_CIRCLE circle( nearestPoint, width / 2 );
1653 return circle.Paths( aS2, aMaxWeight, aMaxSquaredWeight );
1654 }
1655
1656 return result;
1657}
1658
1659
1660std::vector<PATH_CONNECTION> CU_SHAPE_ARC::Paths( const CU_SHAPE_ARC& aS2, double aMaxWeight,
1661 double aMaxSquaredWeight ) const
1662{
1663 std::vector<PATH_CONNECTION> result;
1664
1665 double R1 = this->GetRadius();
1666 double R2 = aS2.GetRadius();
1667
1668 VECTOR2I C1 = this->GetPos();
1669 VECTOR2I C2 = aS2.GetPos();
1670
1671 PATH_CONNECTION bestPath;
1672 bestPath.weight = std::numeric_limits<double>::infinity();
1673 CU_SHAPE_CIRCLE csc1( C1, R1 + this->GetWidth() / 2 );
1674 CU_SHAPE_CIRCLE csc2( C2, R2 + aS2.GetWidth() / 2 );
1675
1676 CU_SHAPE_CIRCLE csc3( this->GetStartPoint(), this->GetWidth() / 2 );
1677 CU_SHAPE_CIRCLE csc4( this->GetEndPoint(), this->GetWidth() / 2 );
1678 CU_SHAPE_CIRCLE csc5( aS2.GetStartPoint(), aS2.GetWidth() / 2 );
1679 CU_SHAPE_CIRCLE csc6( aS2.GetEndPoint(), aS2.GetWidth() / 2 );
1680
1681 for( const std::vector<PATH_CONNECTION>& pcs : { csc1.Paths( csc2, aMaxWeight, aMaxSquaredWeight ),
1682 this->Paths( csc2, aMaxWeight, aMaxSquaredWeight ),
1683 csc1.Paths( aS2, aMaxWeight, aMaxSquaredWeight ) } )
1684 {
1685 for( const PATH_CONNECTION& pc : pcs )
1686 {
1687 EDA_ANGLE testAngle1 = this->AngleBetweenStartAndEnd( pc.a1 );
1688 EDA_ANGLE testAngle2 = aS2.AngleBetweenStartAndEnd( pc.a2 );
1689
1690 if( testAngle1 < this->GetEndAngle() && testAngle2 < aS2.GetEndAngle() && bestPath.weight > pc.weight )
1691 bestPath = pc;
1692 }
1693 }
1694
1695 for( const std::vector<PATH_CONNECTION>& pcs : { this->Paths( csc5, aMaxWeight, aMaxSquaredWeight ),
1696 this->Paths( csc6, aMaxWeight, aMaxSquaredWeight ),
1697 csc3.Paths( aS2, aMaxWeight, aMaxSquaredWeight ),
1698 csc4.Paths( aS2, aMaxWeight, aMaxSquaredWeight ) } )
1699 {
1700 for( const PATH_CONNECTION& pc : pcs )
1701 {
1702 if( bestPath.weight > pc.weight )
1703 bestPath = pc;
1704 }
1705 }
1706
1707 if( bestPath.weight != std::numeric_limits<double>::infinity() )
1708 result.push_back( bestPath );
1709
1710 return result;
1711}
1712
1713
1714bool segmentIntersectsCircle( const VECTOR2I& p1, const VECTOR2I& p2, const VECTOR2I& center, double radius,
1715 std::vector<VECTOR2I>* aIntersectPoints )
1716{
1717 SEG segment( p1, p2 );
1719
1720 std::vector<VECTOR2I> intersectionPoints;
1721 INTERSECTABLE_GEOM geom1 = segment;
1722 INTERSECTABLE_GEOM geom2 = circle;
1723
1724 INTERSECTION_VISITOR visitor( geom2, intersectionPoints );
1725 std::visit( visitor, geom1 );
1726
1727 if( aIntersectPoints )
1728 {
1729 for( VECTOR2I& point : intersectionPoints )
1730 aIntersectPoints->push_back( point );
1731 }
1732
1733 return intersectionPoints.size() > 0;
1734}
1735
1736bool SegmentIntersectsBoard( const VECTOR2I& aP1, const VECTOR2I& aP2,
1737 const std::vector<BOARD_ITEM*>& aBe,
1738 const std::vector<const BOARD_ITEM*>& aDontTestAgainst,
1739 int aMinGrooveWidth )
1740{
1741 std::vector<VECTOR2I> intersectionPoints;
1742 bool TestGrooveWidth = aMinGrooveWidth > 0;
1743
1744 for( BOARD_ITEM* be : aBe )
1745 {
1746 if( count( aDontTestAgainst.begin(), aDontTestAgainst.end(), be ) > 0 )
1747 continue;
1748
1749 PCB_SHAPE* d = static_cast<PCB_SHAPE*>( be );
1750 if( !d )
1751 continue;
1752
1753 switch( d->GetShape() )
1754 {
1755 case SHAPE_T::SEGMENT:
1756 {
1757 bool intersects = segments_intersect( aP1, aP2, d->GetStart(), d->GetEnd(),
1758 &intersectionPoints );
1759
1760 if( intersects && !TestGrooveWidth )
1761 return false;
1762
1763 break;
1764 }
1765
1766 case SHAPE_T::RECTANGLE:
1767 {
1768 VECTOR2I c1 = d->GetStart();
1769 VECTOR2I c2( d->GetStart().x, d->GetEnd().y );
1770 VECTOR2I c3 = d->GetEnd();
1771 VECTOR2I c4( d->GetEnd().x, d->GetStart().y );
1772
1773 bool intersects = false;
1774 intersects |= segments_intersect( aP1, aP2, c1, c2, &intersectionPoints );
1775 intersects |= segments_intersect( aP1, aP2, c2, c3, &intersectionPoints );
1776 intersects |= segments_intersect( aP1, aP2, c3, c4, &intersectionPoints );
1777 intersects |= segments_intersect( aP1, aP2, c4, c1, &intersectionPoints );
1778
1779 if( intersects && !TestGrooveWidth )
1780 return false;
1781
1782 break;
1783 }
1784
1785 case SHAPE_T::POLY:
1786 {
1787 std::vector<VECTOR2I> points;
1788 d->DupPolyPointsList( points );
1789
1790 if( points.size() < 2 )
1791 break;
1792
1793 VECTOR2I prevPoint = points.back();
1794
1795 bool intersects = false;
1796
1797 for( const VECTOR2I& p : points )
1798 {
1799 intersects |= segments_intersect( aP1, aP2, prevPoint, p, &intersectionPoints );
1800 prevPoint = p;
1801 }
1802
1803 if( intersects && !TestGrooveWidth )
1804 return false;
1805
1806 break;
1807 }
1808
1809 case SHAPE_T::CIRCLE:
1810 {
1811 VECTOR2I center = d->GetCenter();
1812 double radius = d->GetRadius();
1813
1814 bool intersects = segmentIntersectsCircle( aP1, aP2, center, radius, &intersectionPoints );
1815
1816 if( intersects && !TestGrooveWidth )
1817 return false;
1818
1819 break;
1820 }
1821
1822 case SHAPE_T::ARC:
1823 {
1824 VECTOR2I center = d->GetCenter();
1825 double radius = d->GetRadius();
1826
1827 EDA_ANGLE A, B;
1828 d->CalcArcAngles( A, B );
1829
1830 bool intersects = segmentIntersectsArc( aP1, aP2, center, radius, A, B, &intersectionPoints );
1831
1832 if( intersects && !TestGrooveWidth )
1833 return false;
1834
1835 break;
1836 }
1837
1838
1839 default: break;
1840 }
1841 }
1842
1843 if( intersectionPoints.size() <= 0 )
1844 return true;
1845
1846 if( intersectionPoints.size() % 2 != 0 )
1847 return false; // Should not happen if the start and end are both on the board
1848
1849 int minx = intersectionPoints[0].x;
1850 int maxx = intersectionPoints[0].x;
1851 int miny = intersectionPoints[0].y;
1852 int maxy = intersectionPoints[0].y;
1853
1854 for( const VECTOR2I& v : intersectionPoints )
1855 {
1856 minx = v.x < minx ? v.x : minx;
1857 maxx = v.x > maxx ? v.x : maxx;
1858 miny = v.x < miny ? v.x : miny;
1859 maxy = v.x > maxy ? v.x : maxy;
1860 }
1861
1862 if( abs( maxx - minx ) > abs( maxy - miny ) )
1863 {
1864 std::sort( intersectionPoints.begin(), intersectionPoints.end(),
1865 []( const VECTOR2I& a, const VECTOR2I& b )
1866 {
1867 return a.x > b.x;
1868 } );
1869 }
1870 else
1871 {
1872 std::sort( intersectionPoints.begin(), intersectionPoints.end(),
1873 []( const VECTOR2I& a, const VECTOR2I& b )
1874 {
1875 return a.y > b.y;
1876 } );
1877 }
1878
1879 int GVSquared = aMinGrooveWidth * aMinGrooveWidth;
1880
1881 for( size_t i = 0; i < intersectionPoints.size(); i += 2 )
1882 {
1883 if( intersectionPoints[i].SquaredDistance( intersectionPoints[i + 1] ) > GVSquared )
1884 return false;
1885 }
1886
1887 return true;
1888}
1889
1890
1891std::vector<PATH_CONNECTION> GetPaths( CREEP_SHAPE* aS1, CREEP_SHAPE* aS2, double aMaxWeight )
1892{
1893 double maxWeight = aMaxWeight;
1894 double maxWeightSquared = maxWeight * maxWeight;
1895 std::vector<PATH_CONNECTION> result;
1896
1897 CU_SHAPE_SEGMENT* cusegment1 = dynamic_cast<CU_SHAPE_SEGMENT*>( aS1 );
1898 CU_SHAPE_SEGMENT* cusegment2 = dynamic_cast<CU_SHAPE_SEGMENT*>( aS2 );
1899 CU_SHAPE_CIRCLE* cucircle1 = dynamic_cast<CU_SHAPE_CIRCLE*>( aS1 );
1900 CU_SHAPE_CIRCLE* cucircle2 = dynamic_cast<CU_SHAPE_CIRCLE*>( aS2 );
1901 CU_SHAPE_ARC* cuarc1 = dynamic_cast<CU_SHAPE_ARC*>( aS1 );
1902 CU_SHAPE_ARC* cuarc2 = dynamic_cast<CU_SHAPE_ARC*>( aS2 );
1903
1904
1905 BE_SHAPE_POINT* bepoint1 = dynamic_cast<BE_SHAPE_POINT*>( aS1 );
1906 BE_SHAPE_POINT* bepoint2 = dynamic_cast<BE_SHAPE_POINT*>( aS2 );
1907 BE_SHAPE_CIRCLE* becircle1 = dynamic_cast<BE_SHAPE_CIRCLE*>( aS1 );
1908 BE_SHAPE_CIRCLE* becircle2 = dynamic_cast<BE_SHAPE_CIRCLE*>( aS2 );
1909 BE_SHAPE_ARC* bearc1 = dynamic_cast<BE_SHAPE_ARC*>( aS1 );
1910 BE_SHAPE_ARC* bearc2 = dynamic_cast<BE_SHAPE_ARC*>( aS2 );
1911
1912 // Cu to Cu
1913
1914 if( cuarc1 && cuarc2 )
1915 return cuarc1->Paths( *cuarc2, maxWeight, maxWeightSquared );
1916 if( cuarc1 && cucircle2 )
1917 return cuarc1->Paths( *cucircle2, maxWeight, maxWeightSquared );
1918 if( cuarc1 && cusegment2 )
1919 return cuarc1->Paths( *cusegment2, maxWeight, maxWeightSquared );
1920 if( cucircle1 && cuarc2 )
1921 return cucircle1->Paths( *cuarc2, maxWeight, maxWeightSquared );
1922 if( cucircle1 && cucircle2 )
1923 return cucircle1->Paths( *cucircle2, maxWeight, maxWeightSquared );
1924 if( cucircle1 && cusegment2 )
1925 return cucircle1->Paths( *cusegment2, maxWeight, maxWeightSquared );
1926 if( cusegment1 && cuarc2 )
1927 return cusegment1->Paths( *cuarc2, maxWeight, maxWeightSquared );
1928 if( cusegment1 && cucircle2 )
1929 return cusegment1->Paths( *cucircle2, maxWeight, maxWeightSquared );
1930 if( cusegment1 && cusegment2 )
1931 return cusegment1->Paths( *cusegment2, maxWeight, maxWeightSquared );
1932
1933
1934 // Cu to Be
1935
1936 if( cuarc1 && bearc2 )
1937 return cuarc1->Paths( *bearc2, maxWeight, maxWeightSquared );
1938 if( cuarc1 && becircle2 )
1939 return cuarc1->Paths( *becircle2, maxWeight, maxWeightSquared );
1940 if( cuarc1 && bepoint2 )
1941 return cuarc1->Paths( *bepoint2, maxWeight, maxWeightSquared );
1942 if( cucircle1 && bearc2 )
1943 return cucircle1->Paths( *bearc2, maxWeight, maxWeightSquared );
1944 if( cucircle1 && becircle2 )
1945 return cucircle1->Paths( *becircle2, maxWeight, maxWeightSquared );
1946 if( cucircle1 && bepoint2 )
1947 return cucircle1->Paths( *bepoint2, maxWeight, maxWeightSquared );
1948 if( cusegment1 && bearc2 )
1949 return cusegment1->Paths( *bearc2, maxWeight, maxWeightSquared );
1950 if( cusegment1 && becircle2 )
1951 return cusegment1->Paths( *becircle2, maxWeight, maxWeightSquared );
1952 if( cusegment1 && bepoint2 )
1953 return cusegment1->Paths( *bepoint2, maxWeight, maxWeightSquared );
1954
1955 // Reversed
1956
1957
1958 if( cuarc2 && bearc1 )
1959 return bearc1->Paths( *bearc2, maxWeight, maxWeightSquared );
1960 if( cuarc2 && becircle1 )
1961 return becircle1->Paths( *bearc2, maxWeight, maxWeightSquared );
1962 if( cuarc2 && bepoint1 )
1963 return bepoint1->Paths( *bearc2, maxWeight, maxWeightSquared );
1964 if( cucircle2 && bearc1 )
1965 return bearc1->Paths( *cucircle2, maxWeight, maxWeightSquared );
1966 if( cucircle2 && becircle1 )
1967 return becircle1->Paths( *cucircle2, maxWeight, maxWeightSquared );
1968 if( cucircle2 && bepoint1 )
1969 return bepoint1->Paths( *cucircle2, maxWeight, maxWeightSquared );
1970 if( cusegment2 && bearc1 )
1971 return bearc1->Paths( *cusegment2, maxWeight, maxWeightSquared );
1972 if( cusegment2 && becircle1 )
1973 return becircle1->Paths( *cusegment2, maxWeight, maxWeightSquared );
1974 if( cusegment2 && bepoint1 )
1975 return bepoint1->Paths( *cusegment2, maxWeight, maxWeightSquared );
1976
1977
1978 // Be to Be
1979
1980 if( bearc1 && bearc2 )
1981 return bearc1->Paths( *bearc2, maxWeight, maxWeightSquared );
1982 if( bearc1 && becircle2 )
1983 return bearc1->Paths( *becircle2, maxWeight, maxWeightSquared );
1984 if( bearc1 && bepoint2 )
1985 return bearc1->Paths( *bepoint2, maxWeight, maxWeightSquared );
1986 if( becircle1 && bearc2 )
1987 return becircle1->Paths( *bearc2, maxWeight, maxWeightSquared );
1988 if( becircle1 && becircle2 )
1989 return becircle1->Paths( *becircle2, maxWeight, maxWeightSquared );
1990 if( becircle1 && bepoint2 )
1991 return becircle1->Paths( *bepoint2, maxWeight, maxWeightSquared );
1992 if( bepoint1 && bearc2 )
1993 return bepoint1->Paths( *bearc2, maxWeight, maxWeightSquared );
1994 if( bepoint1 && becircle2 )
1995 return bepoint1->Paths( *becircle2, maxWeight, maxWeightSquared );
1996 if( bepoint1 && bepoint2 )
1997 return bepoint1->Paths( *bepoint2, maxWeight, maxWeightSquared );
1998
1999 return result;
2000}
2001
2002double CREEPAGE_GRAPH::Solve( std::shared_ptr<GRAPH_NODE>& aFrom, std::shared_ptr<GRAPH_NODE>& aTo,
2003 std::vector<std::shared_ptr<GRAPH_CONNECTION>>& aResult ) // Change to vector of pointers
2004{
2005 if( !aFrom || !aTo )
2006 return 0;
2007
2008 if( aFrom == aTo )
2009 return 0;
2010
2011 // Dijkstra's algorithm for shortest path
2012 std::unordered_map<GRAPH_NODE*, double> distances;
2013 std::unordered_map<GRAPH_NODE*, GRAPH_NODE*> previous;
2014
2015 auto cmp = [&distances]( GRAPH_NODE* left, GRAPH_NODE* right )
2016 {
2017 double distLeft = distances[left];
2018 double distRight = distances[right];
2019
2020 if( distLeft == distRight )
2021 return left > right; // Compare addresses to avoid ties.
2022 return distLeft > distRight;
2023 };
2024 std::priority_queue<GRAPH_NODE*, std::vector<GRAPH_NODE*>, decltype( cmp )> pq( cmp );
2025
2026 // Initialize distances to infinity for all nodes except the starting node
2027 for( const std::shared_ptr<GRAPH_NODE>& node : m_nodes )
2028 {
2029 if( node != nullptr )
2030 distances[node.get()] = std::numeric_limits<double>::infinity(); // Set to infinity
2031 }
2032
2033 distances[aFrom.get()] = 0.0;
2034 distances[aTo.get()] = std::numeric_limits<double>::infinity();
2035 pq.push( aFrom.get() );
2036
2037 // Dijkstra's main loop
2038 while( !pq.empty() )
2039 {
2040 GRAPH_NODE* current = pq.top();
2041 pq.pop();
2042
2043 if( current == aTo.get() )
2044 {
2045 break; // Shortest path found
2046 }
2047
2048 // Traverse neighbors
2049 for( const std::shared_ptr<GRAPH_CONNECTION>& connection : current->m_node_conns )
2050 {
2051 GRAPH_NODE* neighbor = ( connection->n1 ).get() == current ? ( connection->n2 ).get()
2052 : ( connection->n1 ).get();
2053
2054 if( !neighbor )
2055 continue;
2056
2057 // Ignore connections with negative weights as Dijkstra doesn't support them.
2058 if( connection->m_path.weight < 0.0 )
2059 {
2060 wxLogTrace( "CREEPAGE", "Negative weight connection found. Ignoring connection." );
2061 continue;
2062 }
2063
2064
2065 double alt = distances[current] + connection->m_path.weight; // Calculate alternative path cost
2066
2067 if( alt < distances[neighbor] )
2068 {
2069 distances[neighbor] = alt;
2070 previous[neighbor] = current;
2071 pq.push( neighbor );
2072 }
2073 }
2074 }
2075
2076 double pathWeight = distances[aTo.get()];
2077
2078 // If aTo is unreachable, return infinity
2079 if( pathWeight == std::numeric_limits<double>::infinity() )
2080 return std::numeric_limits<double>::infinity();
2081
2082 // Trace back the path from aTo to aFrom
2083 GRAPH_NODE* step = aTo.get();
2084
2085 while( step != aFrom.get() )
2086 {
2087 GRAPH_NODE* prevNode = previous[step];
2088
2089 for( const std::shared_ptr<GRAPH_CONNECTION>& node_conn : step->m_node_conns )
2090 {
2091 if( ( ( node_conn->n1 ).get() == prevNode && ( node_conn->n2 ).get() == step )
2092 || ( ( node_conn->n1 ).get() == step && ( node_conn->n2 ).get() == prevNode ) )
2093 {
2094 aResult.push_back( node_conn );
2095 break;
2096 }
2097 }
2098 step = prevNode;
2099 }
2100
2101 return pathWeight;
2102}
2103
2104void CREEPAGE_GRAPH::Addshape( const SHAPE& aShape, std::shared_ptr<GRAPH_NODE>& aConnectTo,
2105 BOARD_ITEM* aParent )
2106{
2107 CREEP_SHAPE* newshape = nullptr;
2108
2109 if( !aConnectTo )
2110 return;
2111
2112 switch( aShape.Type() )
2113 {
2114 case SH_SEGMENT:
2115 {
2116 const SHAPE_SEGMENT& segment = dynamic_cast<const SHAPE_SEGMENT&>( aShape );
2117 CU_SHAPE_SEGMENT* cuseg = new CU_SHAPE_SEGMENT( segment.GetSeg().A, segment.GetSeg().B,
2118 segment.GetWidth() );
2119 newshape = dynamic_cast<CREEP_SHAPE*>( cuseg );
2120 break;
2121 }
2122 case SH_CIRCLE:
2123 {
2124 const SHAPE_CIRCLE& circle = dynamic_cast<const SHAPE_CIRCLE&>( aShape );
2126 newshape = dynamic_cast<CREEP_SHAPE*>( cucircle );
2127 break;
2128 }
2129 case SH_ARC:
2130 {
2131 const SHAPE_ARC& arc = dynamic_cast<const SHAPE_ARC&>( aShape );
2132 EDA_ANGLE alpha, beta;
2133 VECTOR2I start, end;
2134
2135 EDA_SHAPE edaArc( SHAPE_T::ARC, 0, FILL_T::NO_FILL );
2136
2137 if( arc.IsClockwise() )
2138 {
2139 edaArc.SetArcGeometry( arc.GetP0(), arc.GetArcMid(), arc.GetP1() );
2140 start = arc.GetP0();
2141 end = arc.GetP1();
2142 }
2143 else
2144 {
2145 edaArc.SetArcGeometry( arc.GetP1(), arc.GetArcMid(), arc.GetP0() );
2146 start = arc.GetP1();
2147 end = arc.GetP0();
2148 }
2149
2150 edaArc.CalcArcAngles( alpha, beta );
2151
2152 CU_SHAPE_ARC* cuarc = new CU_SHAPE_ARC( edaArc.getCenter(), edaArc.GetRadius(), alpha, beta,
2153 arc.GetP0(), arc.GetP1() );
2154 cuarc->SetWidth( arc.GetWidth() );
2155 newshape = dynamic_cast<CREEP_SHAPE*>( cuarc );
2156 break;
2157 }
2158 case SH_COMPOUND:
2159 {
2160 int nbShapes = static_cast<const SHAPE_COMPOUND*>( &aShape )->Shapes().size();
2161 for( const SHAPE* subshape : ( static_cast<const SHAPE_COMPOUND*>( &aShape )->Shapes() ) )
2162 {
2163 if( subshape )
2164 {
2165 // We don't want to add shape for the inner rectangle of rounded rectangles
2166 if( !( ( subshape->Type() == SH_RECT ) && ( nbShapes == 5 ) ) )
2167 Addshape( *subshape, aConnectTo, aParent );
2168 }
2169 }
2170 break;
2171 }
2172 case SH_POLY_SET:
2173 {
2174 const SHAPE_POLY_SET& polySet = dynamic_cast<const SHAPE_POLY_SET&>( aShape );
2175
2176 for( auto it = polySet.CIterateSegmentsWithHoles(); it; it++ )
2177 {
2178 const SEG object = *it;
2179 SHAPE_SEGMENT segment( object.A, object.B );
2180 Addshape( segment, aConnectTo, aParent );
2181 }
2182 break;
2183 }
2184 case SH_LINE_CHAIN:
2185 {
2186 const SHAPE_LINE_CHAIN& lineChain = dynamic_cast<const SHAPE_LINE_CHAIN&>( aShape );
2187
2188 VECTOR2I prevPoint = lineChain.CLastPoint();
2189
2190 for( const VECTOR2I& point : lineChain.CPoints() )
2191 {
2192 SHAPE_SEGMENT segment( point, prevPoint );
2193 prevPoint = point;
2194 Addshape( segment, aConnectTo, aParent );
2195 }
2196
2197 break;
2198 }
2199 case SH_RECT:
2200 {
2201 const SHAPE_RECT& rect = dynamic_cast<const SHAPE_RECT&>( aShape );
2202
2203 VECTOR2I point0 = rect.GetPosition();
2204 VECTOR2I point1 = rect.GetPosition() + VECTOR2I( rect.GetSize().x, 0 );
2205 VECTOR2I point2 = rect.GetPosition() + rect.GetSize();
2206 VECTOR2I point3 = rect.GetPosition() + VECTOR2I( 0, rect.GetSize().y );
2207
2208 Addshape( SHAPE_SEGMENT( point0, point1 ), aConnectTo, aParent );
2209 Addshape( SHAPE_SEGMENT( point1, point2 ), aConnectTo, aParent );
2210 Addshape( SHAPE_SEGMENT( point2, point3 ), aConnectTo, aParent );
2211 Addshape( SHAPE_SEGMENT( point3, point0 ), aConnectTo, aParent );
2212 break;
2213 }
2214 default: break;
2215 }
2216
2217 if( !newshape )
2218 return;
2219
2220 std::shared_ptr<GRAPH_NODE> gnShape = nullptr;
2221
2222 newshape->SetParent( aParent );
2223
2224 switch( aShape.Type() )
2225 {
2226 case SH_SEGMENT: gnShape = AddNode( GRAPH_NODE::SEGMENT, newshape, newshape->GetPos() ); break;
2227 case SH_CIRCLE: gnShape = AddNode( GRAPH_NODE::CIRCLE, newshape, newshape->GetPos() ); break;
2228 case SH_ARC: gnShape = AddNode( GRAPH_NODE::ARC, newshape, newshape->GetPos() ); break;
2229 default: break;
2230 }
2231
2232 if( gnShape )
2233 {
2234 m_shapeCollection.push_back( newshape );
2235 gnShape->m_net = aConnectTo->m_net;
2236 std::shared_ptr<GRAPH_CONNECTION> gc = AddConnection( gnShape, aConnectTo );
2237
2238 if( gc )
2239 gc->m_path.m_show = false;
2240 }
2241 else
2242 {
2243 delete newshape;
2244 newshape = nullptr;
2245 }
2246}
2247
2248void CREEPAGE_GRAPH::GeneratePaths( double aMaxWeight, PCB_LAYER_ID aLayer )
2249{
2250 std::vector<std::shared_ptr<GRAPH_NODE>> nodes;
2251 std::mutex nodes_lock;
2253
2254 std::copy_if( m_nodes.begin(), m_nodes.end(), std::back_inserter( nodes ),
2255 [&]( const std::shared_ptr<GRAPH_NODE>& gn )
2256 {
2257 return !!gn && gn->m_parent && gn->m_connectDirectly
2258 && ( gn->m_type != GRAPH_NODE::TYPE::VIRTUAL );
2259 } );
2260
2261 std::sort( nodes.begin(), nodes.end(),
2262 []( const std::shared_ptr<GRAPH_NODE>& gn1, const std::shared_ptr<GRAPH_NODE>& gn2 )
2263 {
2264 return ( gn1->m_parent < gn2->m_parent ) || ( gn1->m_parent == gn2->m_parent
2265 && gn1->m_net < gn2->m_net );
2266 } );
2267
2268 // Build parent -> net -> nodes mapping for efficient filtering
2269 std::unordered_map<const BOARD_ITEM*, std::unordered_map<int, std::vector<std::shared_ptr<GRAPH_NODE>>>> parent_net_groups;
2270 std::vector<const BOARD_ITEM*> parent_keys;
2271
2272 for( const auto& gn : nodes )
2273 {
2274 const BOARD_ITEM* parent = gn->m_parent->GetParent();
2275
2276 if( parent_net_groups[parent].empty() )
2277 parent_keys.push_back( parent );
2278
2279 parent_net_groups[parent][gn->m_net].push_back( gn );
2280 }
2281
2282 // Generate work items: compare nodes between different parents only
2283 struct WorkItem {
2284 std::shared_ptr<GRAPH_NODE> node1, node2;
2285 };
2286 std::vector<WorkItem> work_items;
2287
2288 for( size_t i = 0; i < parent_keys.size(); ++i )
2289 {
2290 for( size_t j = i + 1; j < parent_keys.size(); ++j )
2291 {
2292 const auto& group1_nets = parent_net_groups[parent_keys[i]];
2293 const auto& group2_nets = parent_net_groups[parent_keys[j]];
2294
2295 for( const auto& [net1, nodes1] : group1_nets )
2296 {
2297 for( const auto& [net2, nodes2] : group2_nets )
2298 {
2299 // Skip if same net and both nets have only conductive nodes
2300 if( net1 == net2 )
2301 {
2302 bool all_conductive_1 = std::all_of( nodes1.begin(), nodes1.end(),
2303 []( const auto& n ) { return n->m_parent->IsConductive(); } );
2304 bool all_conductive_2 = std::all_of( nodes2.begin(), nodes2.end(),
2305 []( const auto& n ) { return n->m_parent->IsConductive(); } );
2306
2307 if( all_conductive_1 && all_conductive_2 )
2308 continue;
2309 }
2310
2311 // Add all node pairs from these net groups
2312 for( const auto& gn1 : nodes1 )
2313 for( const auto& gn2 : nodes2 )
2314 work_items.push_back( { gn1, gn2 } );
2315 }
2316 }
2317 }
2318 }
2319
2320 auto processWorkItems = [&]( size_t start_idx, size_t end_idx ) -> bool
2321 {
2322 for( size_t idx = start_idx; idx < end_idx; ++idx )
2323 {
2324 auto [gn1, gn2] = work_items[idx];
2325
2326 for( PATH_CONNECTION pc : GetPaths( gn1->m_parent, gn2->m_parent, aMaxWeight ) )
2327 {
2328 std::vector<const BOARD_ITEM*> IgnoreForTest = {
2329 gn1->m_parent->GetParent(), gn2->m_parent->GetParent()
2330 };
2331
2332 if( !pc.isValid( m_board, aLayer, m_boardEdge, IgnoreForTest, m_boardOutline,
2333 { false, true }, m_minGrooveWidth ) )
2334 continue;
2335
2336 std::shared_ptr<GRAPH_NODE> connect1 = gn1, connect2 = gn2;
2337 std::lock_guard<std::mutex> lock( nodes_lock );
2338
2339 // Handle non-point node1
2340 if( gn1->m_parent->GetType() != CREEP_SHAPE::TYPE::POINT )
2341 {
2342 auto gnt1 = AddNode( GRAPH_NODE::POINT, gn1->m_parent, pc.a1 );
2343 gnt1->m_connectDirectly = false;
2344 connect1 = gnt1;
2345
2346 if( gn1->m_parent->IsConductive() )
2347 {
2348 if( auto gc = AddConnection( gn1, gnt1 ) )
2349 gc->m_path.m_show = false;
2350 }
2351 }
2352
2353 // Handle non-point node2
2354 if( gn2->m_parent->GetType() != CREEP_SHAPE::TYPE::POINT )
2355 {
2356 auto gnt2 = AddNode( GRAPH_NODE::POINT, gn2->m_parent, pc.a2 );
2357 gnt2->m_connectDirectly = false;
2358 connect2 = gnt2;
2359
2360 if( gn2->m_parent->IsConductive() )
2361 {
2362 if( auto gc = AddConnection( gn2, gnt2 ) )
2363 gc->m_path.m_show = false;
2364 }
2365 }
2366
2367 AddConnection( connect1, connect2, pc );
2368 }
2369 }
2370 return true;
2371 };
2372
2373 // If the number of tasks is high enough, this indicates that the calling process
2374 // has already parallelized the work, so we can process all items in one go.
2375 if( tp.get_tasks_total() >= tp.get_thread_count() - 4 )
2376 {
2377 processWorkItems( 0, work_items.size() );
2378 }
2379 else
2380 {
2381 auto ret = tp.parallelize_loop( work_items.size(), processWorkItems );
2382
2383 for( size_t ii = 0; ii < ret.size(); ii++ )
2384 {
2385 std::future<bool>& r = ret[ii];
2386
2387 if( !r.valid() )
2388 continue;
2389
2390 while( r.wait_for( std::chrono::milliseconds( 100 ) ) != std::future_status::ready ){}
2391 }
2392 }
2393}
2394
2395
2396void CREEPAGE_GRAPH::Trim( double aWeightLimit )
2397{
2398 std::vector<std::shared_ptr<GRAPH_CONNECTION>> toRemove;
2399
2400 // Collect connections to remove
2401 for( std::shared_ptr<GRAPH_CONNECTION>& gc : m_connections )
2402 {
2403 if( gc && ( gc->m_path.weight > aWeightLimit ) )
2404 toRemove.push_back( gc );
2405 }
2406
2407 // Remove collected connections
2408 for( const std::shared_ptr<GRAPH_CONNECTION>& gc : toRemove )
2409 RemoveConnection( gc );
2410}
2411
2412void CREEPAGE_GRAPH::RemoveConnection( const std::shared_ptr<GRAPH_CONNECTION>& aGc, bool aDelete )
2413{
2414 if( !aGc )
2415 return;
2416
2417 for( std::shared_ptr<GRAPH_NODE> gn : { aGc->n1, aGc->n2 } )
2418 {
2419 if( gn )
2420 {
2421 gn->m_node_conns.erase( aGc );
2422
2423 if( gn->m_node_conns.empty() && aDelete )
2424 {
2425 auto it = std::find_if( m_nodes.begin(), m_nodes.end(),
2426 [&gn]( const std::shared_ptr<GRAPH_NODE>& node )
2427 {
2428 return node.get() == gn.get();
2429 } );
2430
2431 if( it != m_nodes.end() )
2432 m_nodes.erase( it );
2433
2434 m_nodeset.erase( gn );
2435 }
2436 }
2437 }
2438
2439 if( aDelete )
2440 {
2441 // Remove the connection from the graph's connections
2442 m_connections.erase( std::remove( m_connections.begin(), m_connections.end(), aGc ),
2443 m_connections.end() );
2444 }
2445}
2446
2447
2448std::shared_ptr<GRAPH_NODE> CREEPAGE_GRAPH::AddNode( GRAPH_NODE::TYPE aType, CREEP_SHAPE* parent,
2449 const VECTOR2I& pos )
2450{
2451 std::shared_ptr<GRAPH_NODE> gn = FindNode( aType, parent, pos );
2452
2453 if( gn )
2454 return gn;
2455
2456 gn = std::make_shared<GRAPH_NODE>( aType, parent, pos );
2457 m_nodes.push_back( gn );
2458 m_nodeset.insert( gn );
2459 return gn;
2460}
2461
2462std::shared_ptr<GRAPH_NODE> CREEPAGE_GRAPH::AddNodeVirtual()
2463{
2464 //Virtual nodes are always unique, do not try to find them
2465 std::shared_ptr<GRAPH_NODE> gn = std::make_shared<GRAPH_NODE>( GRAPH_NODE::TYPE::VIRTUAL, nullptr );
2466 m_nodes.push_back( gn );
2467 m_nodeset.insert( gn );
2468 return gn;
2469}
2470
2471
2472std::shared_ptr<GRAPH_CONNECTION> CREEPAGE_GRAPH::AddConnection( std::shared_ptr<GRAPH_NODE>& aN1,
2473 std::shared_ptr<GRAPH_NODE>& aN2,
2474 const PATH_CONNECTION& aPc )
2475{
2476 if( !aN1 || !aN2 )
2477 return nullptr;
2478
2479 wxASSERT_MSG( ( aN1 != aN2 ), "Creepage: a connection connects a node to itself" );
2480
2481 std::shared_ptr<GRAPH_CONNECTION> gc = std::make_shared<GRAPH_CONNECTION>( aN1, aN2, aPc );
2482 m_connections.push_back( gc );
2483 aN1->m_node_conns.insert( gc );
2484 aN2->m_node_conns.insert( gc );
2485
2486 return gc;
2487}
2488
2489std::shared_ptr<GRAPH_CONNECTION> CREEPAGE_GRAPH::AddConnection( std::shared_ptr<GRAPH_NODE>& aN1,
2490 std::shared_ptr<GRAPH_NODE>& aN2 )
2491{
2492 if( !aN1 || !aN2 )
2493 return nullptr;
2494
2495 PATH_CONNECTION pc;
2496 pc.a1 = aN1->m_pos;
2497 pc.a2 = aN2->m_pos;
2498 pc.weight = 0;
2499
2500 return AddConnection( aN1, aN2, pc );
2501}
2502
2503std::shared_ptr<GRAPH_NODE> CREEPAGE_GRAPH::FindNode( GRAPH_NODE::TYPE aType, CREEP_SHAPE* aParent,
2504 const VECTOR2I& aPos )
2505{
2506 auto it = m_nodeset.find( std::make_shared<GRAPH_NODE>( aType, aParent, aPos ) );
2507
2508 if( it != m_nodeset.end() )
2509 return *it;
2510
2511 return nullptr;
2512}
2513
2514
2515std::shared_ptr<GRAPH_NODE> CREEPAGE_GRAPH::AddNetElements( int aNetCode, PCB_LAYER_ID aLayer,
2516 int aMaxCreepage )
2517{
2518 std::shared_ptr<GRAPH_NODE> virtualNode = AddNodeVirtual();
2519 virtualNode->m_net = aNetCode;
2520
2521 for( FOOTPRINT* footprint : m_board.Footprints() )
2522 {
2523 for( PAD* pad : footprint->Pads() )
2524 {
2525 if( pad->GetNetCode() != aNetCode )
2526 continue;
2527
2528 std::shared_ptr<SHAPE> padShape = pad->GetEffectiveShape( aLayer );
2529
2530 if( padShape )
2531 {
2532 Addshape( *padShape, virtualNode, pad );
2533 }
2534 }
2535 }
2536
2537 for( PCB_TRACK* track : m_board.Tracks() )
2538 {
2539 if( !track )
2540 continue;
2541
2542 if( track->GetNetCode() != aNetCode )
2543 continue;
2544
2545 if( !track->IsOnLayer( aLayer ) )
2546 continue;
2547
2548 if( track->GetEffectiveShape() == nullptr )
2549 continue;
2550
2551 Addshape( *( track->GetEffectiveShape() ), virtualNode, track );
2552 }
2553
2554
2555 for( ZONE* zone : m_board.Zones() )
2556 {
2557 if( !zone )
2558 continue;
2559
2560 if( zone->GetNetCode() != aNetCode )
2561 continue;
2562
2563 if( zone->GetEffectiveShape( aLayer ) == nullptr )
2564 continue;
2565
2566 Addshape( *( zone->GetEffectiveShape( aLayer ) ), virtualNode, zone );
2567 }
2568
2569 const DRAWINGS drawings = m_board.Drawings();
2570
2571 for( BOARD_ITEM* drawing : drawings )
2572 {
2573 if( !drawing )
2574 continue;
2575
2576 if( !drawing->IsConnected() )
2577 continue;
2578
2579 BOARD_CONNECTED_ITEM* bci = dynamic_cast<BOARD_CONNECTED_ITEM*>( drawing );
2580
2581 if( !bci )
2582 continue;
2583
2584 if( bci->GetNetCode() != aNetCode )
2585 continue;
2586
2587 if( bci->IsOnLayer( aLayer ) )
2588 {
2589 Addshape( *( bci->GetEffectiveShape() ), virtualNode, bci );
2590 }
2591 }
2592
2593
2594 return virtualNode;
2595}
Creepage: a board edge arc.
std::pair< bool, bool > IsThereATangentPassingThroughPoint(const BE_SHAPE_POINT aPoint) const
EDA_ANGLE GetStartAngle() const override
int GetRadius() const override
EDA_ANGLE m_endAngle
VECTOR2I GetStartPoint() const override
EDA_ANGLE m_startAngle
std::vector< PATH_CONNECTION > Paths(const BE_SHAPE_POINT &aS2, double aMaxWeight, double aMaxSquaredWeight) const override
void ConnectChildren(std::shared_ptr< GRAPH_NODE > &a1, std::shared_ptr< GRAPH_NODE > &a2, CREEPAGE_GRAPH &aG) const override
EDA_ANGLE GetEndAngle() const override
VECTOR2I GetEndPoint() const override
EDA_ANGLE AngleBetweenStartAndEnd(const VECTOR2I aPoint) const
Creepage: a board edge circle.
int GetRadius() const override
void ShortenChildDueToGV(std::shared_ptr< GRAPH_NODE > &a1, std::shared_ptr< GRAPH_NODE > &a2, CREEPAGE_GRAPH &aG, double aNormalWeight) const
std::vector< PATH_CONNECTION > Paths(const BE_SHAPE_POINT &aS2, double aMaxWeight, double aMaxSquaredWeight) const override
void ConnectChildren(std::shared_ptr< GRAPH_NODE > &a1, std::shared_ptr< GRAPH_NODE > &a2, CREEPAGE_GRAPH &aG) const override
Creepage: a board edge point.
void ConnectChildren(std::shared_ptr< GRAPH_NODE > &a1, std::shared_ptr< GRAPH_NODE > &a2, CREEPAGE_GRAPH &aG) const override
std::vector< PATH_CONNECTION > Paths(const BE_SHAPE_POINT &aS2, double aMaxWeight, double aMaxSquaredWeight) const override
A base class derived from BOARD_ITEM for items that can be connected and have a net,...
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition: board_item.h:79
virtual bool IsOnLayer(PCB_LAYER_ID aLayer) const
Test to see if this object is on the given layer.
Definition: board_item.h:314
virtual std::shared_ptr< SHAPE > GetEffectiveShape(PCB_LAYER_ID aLayer=UNDEFINED_LAYER, FLASHING aFlash=FLASHING::DEFAULT) const
Some pad shapes can be complex (rounded/chamfered rectangle), even without considering custom shapes.
Definition: board_item.cpp:326
const ZONES & Zones() const
Definition: board.h:362
const FOOTPRINTS & Footprints() const
Definition: board.h:358
const TRACKS & Tracks() const
Definition: board.h:356
const DRAWINGS & Drawings() const
Definition: board.h:360
Represent basic circle geometry with utility geometry functions.
Definition: circle.h:33
std::shared_ptr< GRAPH_NODE > AddNode(GRAPH_NODE::TYPE aType, CREEP_SHAPE *aParent=nullptr, const VECTOR2I &aPos=VECTOR2I())
std::shared_ptr< GRAPH_CONNECTION > AddConnection(std::shared_ptr< GRAPH_NODE > &aN1, std::shared_ptr< GRAPH_NODE > &aN2, const PATH_CONNECTION &aPc)
void SetTarget(double aTarget)
double Solve(std::shared_ptr< GRAPH_NODE > &aFrom, std::shared_ptr< GRAPH_NODE > &aTo, std::vector< std::shared_ptr< GRAPH_CONNECTION > > &aResult)
void Addshape(const SHAPE &aShape, std::shared_ptr< GRAPH_NODE > &aConnectTo, BOARD_ITEM *aParent=nullptr)
std::vector< CREEP_SHAPE * > m_shapeCollection
std::shared_ptr< GRAPH_NODE > AddNodeVirtual()
void TransformCreepShapesToNodes(std::vector< CREEP_SHAPE * > &aShapes)
void Trim(double aWeightLimit)
SHAPE_POLY_SET * m_boardOutline
std::vector< BOARD_ITEM * > m_boardEdge
double m_creepageTargetSquared
std::unordered_set< std::shared_ptr< GRAPH_NODE >, GraphNodeHash, GraphNodeEqual > m_nodeset
void GeneratePaths(double aMaxWeight, PCB_LAYER_ID aLayer)
std::vector< std::shared_ptr< GRAPH_NODE > > m_nodes
std::vector< std::shared_ptr< GRAPH_CONNECTION > > m_connections
std::shared_ptr< GRAPH_NODE > AddNetElements(int aNetCode, PCB_LAYER_ID aLayer, int aMaxCreepage)
void RemoveConnection(const std::shared_ptr< GRAPH_CONNECTION > &, bool aDelete=false)
std::shared_ptr< GRAPH_NODE > FindNode(GRAPH_NODE::TYPE aType, CREEP_SHAPE *aParent, const VECTOR2I &aPos)
A class used to represent the shapes for creepage calculation.
VECTOR2I GetPos() const
CREEP_SHAPE::TYPE GetType() const
void SetParent(BOARD_ITEM *aParent)
virtual int GetRadius() const
virtual void ConnectChildren(std::shared_ptr< GRAPH_NODE > &a1, std::shared_ptr< GRAPH_NODE > &a2, CREEPAGE_GRAPH &aG) const
Creepage: a conductive arc.
VECTOR2I GetStartPoint() const override
void SetWidth(double aW)
EDA_ANGLE AngleBetweenStartAndEnd(const VECTOR2I aPoint) const
VECTOR2I GetEndPoint() const override
EDA_ANGLE GetStartAngle() const override
double GetWidth() const
int GetRadius() const override
EDA_ANGLE GetEndAngle() const override
std::vector< PATH_CONNECTION > Paths(const BE_SHAPE_POINT &aS2, double aMaxWeight, double aMaxSquaredWeight) const override
Creepage: a conductive circle.
int GetRadius() const override
VECTOR2I GetPos() const
std::vector< PATH_CONNECTION > Paths(const BE_SHAPE_POINT &aS2, double aMaxWeight, double aMaxSquaredWeight) const override
Creepage: a conductive segment.
std::vector< PATH_CONNECTION > Paths(const BE_SHAPE_POINT &aS2, double aMaxWeight, double aMaxSquaredWeight) const override
VECTOR2I GetStart() const
double GetWidth() const
VECTOR2I GetEnd() const
double AsRadians() const
Definition: eda_angle.h:120
EDA_ITEM * GetParent() const
Definition: eda_item.h:112
EDA_ITEM * m_parent
Owner.
Definition: eda_item.h:528
void SetCenter(const VECTOR2I &aCenter)
Definition: eda_shape.cpp:956
VECTOR2I getCenter() const
Definition: eda_shape.cpp:930
void CalcArcAngles(EDA_ANGLE &aStartAngle, EDA_ANGLE &aEndAngle) const
Calc arc start and end angles such that aStartAngle < aEndAngle.
Definition: eda_shape.cpp:989
int GetRadius() const
Definition: eda_shape.cpp:1005
SHAPE_T GetShape() const
Definition: eda_shape.h:168
const VECTOR2I & GetEnd() const
Return the ending point of the graphic.
Definition: eda_shape.h:215
void SetStart(const VECTOR2I &aStart)
Definition: eda_shape.h:177
void DupPolyPointsList(std::vector< VECTOR2I > &aBuffer) const
Duplicate the list of corners in a std::vector<VECTOR2I>.
Definition: eda_shape.cpp:1884
const VECTOR2I & GetStart() const
Return the starting point of the graphic.
Definition: eda_shape.h:173
void SetEnd(const VECTOR2I &aEnd)
Definition: eda_shape.h:219
void SetArcGeometry(const VECTOR2I &aStart, const VECTOR2I &aMid, const VECTOR2I &aEnd)
Set the three controlling points for an arc.
Definition: eda_shape.cpp:1041
void SetWidth(int aWidth)
Definition: eda_shape.cpp:2375
VECTOR2I GetArcMid() const
Definition: eda_shape.cpp:975
std::vector< PCB_SHAPE > GetShapes()
std::shared_ptr< GRAPH_NODE > n2
PATH_CONNECTION m_path
std::shared_ptr< GRAPH_NODE > n1
std::set< std::shared_ptr< GRAPH_CONNECTION > > m_node_conns
Definition: pad.h:54
VECTOR2I GetCenter() const override
This defaults to the center of the bounding box if not overridden.
Definition: pcb_shape.h:81
void SetLayer(PCB_LAYER_ID aLayer) override
Set the layer this item is on.
Definition: pcb_shape.cpp:176
Definition: seg.h:42
VECTOR2I A
Definition: seg.h:49
VECTOR2I B
Definition: seg.h:50
const VECTOR2I & GetArcMid() const
Definition: shape_arc.h:118
bool IsClockwise() const
Definition: shape_arc.h:318
int GetWidth() const
Definition: shape_arc.h:210
const VECTOR2I & GetP1() const
Definition: shape_arc.h:117
const VECTOR2I & GetP0() const
Definition: shape_arc.h:116
SHAPE_TYPE Type() const
Return the type of the shape.
Definition: shape.h:98
int GetRadius() const
Definition: shape_circle.h:118
const VECTOR2I GetCenter() const
Definition: shape_circle.h:123
const std::vector< SHAPE * > & Shapes() const
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
const VECTOR2I & CLastPoint() const
Return the last point in the line chain.
const std::vector< VECTOR2I > & CPoints() const
Represent a set of closed polygons.
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles() const
Return an iterator object, for the aOutline-th outline in the set (with holes).
const VECTOR2I & GetPosition() const
Definition: shape_rect.h:160
const VECTOR2I GetSize() const
Definition: shape_rect.h:168
const SEG & GetSeg() const
int GetWidth() const
An abstract shape on 2D plane.
Definition: shape.h:126
constexpr extended_type Cross(const VECTOR2< T > &aVector) const
Compute cross product of self with aVector.
Definition: vector2d.h:546
constexpr extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
Definition: vector2d.h:307
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition: vector2d.h:283
constexpr VECTOR2< T > Perpendicular() const
Compute the perpendicular vector.
Definition: vector2d.h:314
constexpr extended_type Dot(const VECTOR2< T > &aVector) const
Compute dot product of self with aVector.
Definition: vector2d.h:554
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:385
Handle a list of polygons defining a copper zone.
Definition: zone.h:74
static bool empty(const wxTextEntryBase *aCtrl)
VECTOR2I closestPointOnSegment(const VECTOR2I &A, const VECTOR2I &B, const VECTOR2I &P)
bool SegmentIntersectsBoard(const VECTOR2I &aP1, const VECTOR2I &aP2, const std::vector< BOARD_ITEM * > &aBe, const std::vector< const BOARD_ITEM * > &aDontTestAgainst, int aMinGrooveWidth)
bool segmentIntersectsArc(const VECTOR2I &p1, const VECTOR2I &p2, const VECTOR2I &center, double radius, EDA_ANGLE startAngle, EDA_ANGLE endAngle, std::vector< VECTOR2I > *aIntersectPoints)
std::vector< PATH_CONNECTION > GetPaths(CREEP_SHAPE *aS1, CREEP_SHAPE *aS2, double aMaxWeight)
bool compareShapes(const CREEP_SHAPE *a, const CREEP_SHAPE *b)
bool segments_intersect(VECTOR2I p1, VECTOR2I q1, VECTOR2I p2, VECTOR2I q2, std::vector< VECTOR2I > *aIntersectPoints)
bool areEquivalent(const CREEP_SHAPE *a, const CREEP_SHAPE *b)
bool segmentIntersectsCircle(const VECTOR2I &p1, const VECTOR2I &p2, const VECTOR2I &center, double radius, std::vector< VECTOR2I > *aIntersectPoints)
static constexpr EDA_ANGLE ANGLE_0
Definition: eda_angle.h:411
@ RADIANS_T
Definition: eda_angle.h:32
static constexpr EDA_ANGLE ANGLE_360
Definition: eda_angle.h:417
@ RECTANGLE
Use RECTANGLE instead of RECT to avoid collision in a Windows header.
std::variant< LINE, HALF_LINE, SEG, CIRCLE, SHAPE_ARC, BOX2I > INTERSECTABLE_GEOM
A variant type that can hold any of the supported geometry types for intersection calculations.
Definition: intersection.h:43
PCB_LAYER_ID
A quick note on layer IDs:
Definition: layer_ids.h:60
@ Eco1_User
Definition: layer_ids.h:109
#define D(x)
Definition: ptree.cpp:41
static float distance(const SFVEC2UI &a, const SFVEC2UI &b)
@ SH_POLY_SET
set of polygons (with holes, etc.)
Definition: shape.h:52
@ SH_RECT
axis-aligned rectangle
Definition: shape.h:47
@ SH_CIRCLE
circle
Definition: shape.h:50
@ SH_SEGMENT
line segment
Definition: shape.h:48
@ SH_ARC
circular arc
Definition: shape.h:54
@ SH_LINE_CHAIN
line chain (polyline)
Definition: shape.h:49
@ SH_COMPOUND
compound shape, consisting of multiple simple shapes
Definition: shape.h:53
A visitor that visits INTERSECTABLE_GEOM variant objects with another (which is held as state: m_othe...
Definition: intersection.h:53
VECTOR2I center
int radius
VECTOR2I end
SHAPE_CIRCLE circle(c.m_circle_center, c.m_circle_radius)
thread_pool & GetKiCadThreadPool()
Get a reference to the current thread pool.
Definition: thread_pool.cpp:30
static thread_pool * tp
Definition: thread_pool.cpp:28
BS::thread_pool thread_pool
Definition: thread_pool.h:31
VECTOR2< int32_t > VECTOR2I
Definition: vector2d.h:695
VECTOR2< double > VECTOR2D
Definition: vector2d.h:694