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