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, see <https://www.gnu.org/licenses/>.
17 */
18
19#include <optional>
20
22
25#include <pcb_track.h>
26#include <thread_pool.h>
27
28
29void BuildCreepageBoardEdges( BOARD& aBoard, std::vector<BOARD_ITEM*>& aVector,
30 std::vector<std::unique_ptr<PCB_SHAPE>>& aOwned,
31 const std::set<const BOARD_ITEM*>* aExclude )
32{
33 const int errorMax = aBoard.GetDesignSettings().m_MaxError;
34
35 auto excluded =
36 [&]( const BOARD_ITEM* aItem ) -> bool
37 {
38 if( !aExclude || !aItem )
39 return false;
40
41 if( aExclude->count( aItem ) )
42 return true;
43
44 const BOARD_ITEM* parent = dynamic_cast<const BOARD_ITEM*>( aItem->GetParent() );
45
46 return parent && aExclude->count( parent );
47 };
48
49 // The creepage graph only handles SEGMENT/ARC/CIRCLE/RECTANGLE/POLY, so Bezier curves must be
50 // flattened to segments or they are silently ignored and creepage paths pass through them
51 auto addEdgeDrawing =
52 [&]( BOARD_ITEM* aDrawing )
53 {
54 if( !aDrawing || !aDrawing->IsOnLayer( Edge_Cuts ) )
55 return;
56
57 if( excluded( aDrawing ) )
58 return;
59
60 // Downstream code static_casts every item in m_boardEdge to PCB_SHAPE, so non-shape items
61 // (text, dimensions, ...) on Edge.Cuts must not enter the graph
62 PCB_SHAPE* shape = dynamic_cast<PCB_SHAPE*>( aDrawing );
63
64 if( !shape )
65 return;
66
67 if( shape->GetShape() != SHAPE_T::BEZIER )
68 {
69 aVector.push_back( shape );
70 return;
71 }
72
73 shape->RebuildBezierToSegmentsPointsList( errorMax );
74 const std::vector<VECTOR2I>& pts = shape->GetBezierPoints();
75
76 for( size_t i = 1; i < pts.size(); ++i )
77 {
78 if( pts[i - 1] == pts[i] )
79 continue;
80
81 auto seg = std::make_unique<PCB_SHAPE>( nullptr, SHAPE_T::SEGMENT );
82 seg->SetStart( pts[i - 1] );
83 seg->SetEnd( pts[i] );
84 aVector.push_back( seg.get() );
85 aOwned.push_back( std::move( seg ) );
86 }
87 };
88
89 for( BOARD_ITEM* drawing : aBoard.Drawings() )
90 addEdgeDrawing( drawing );
91
92 for( FOOTPRINT* fp : aBoard.Footprints() )
93 {
94 if( !fp )
95 continue;
96
97 for( BOARD_ITEM* drawing : fp->GraphicalItems() )
98 addEdgeDrawing( drawing );
99 }
100
101 for( const PAD* p : aBoard.GetPads() )
102 {
103 if( !p || p->GetAttribute() != PAD_ATTRIB::NPTH )
104 continue;
105
106 if( excluded( p ) )
107 continue;
108
109 // TODO: handle backdrilling and post-machining
110
111 std::shared_ptr<SHAPE_SEGMENT> hole = p->GetEffectiveHoleShape();
112
113 if( !hole )
114 continue;
115
116 VECTOR2I ptA = hole->GetSeg().A;
117 VECTOR2I ptB = hole->GetSeg().B;
118 int radius = hole->GetWidth() / 2;
119
120 if( ptA == ptB )
121 {
122 auto s = std::make_unique<PCB_SHAPE>( nullptr, SHAPE_T::CIRCLE );
123 s->SetRadius( radius );
124 s->SetPosition( ptA );
125 aVector.push_back( s.get() );
126 aOwned.push_back( std::move( s ) );
127 }
128 else
129 {
130 // Oblong slot outline as two straight sides and two semicircular end caps
131 VECTOR2I axis = ptB - ptA;
132 VECTOR2I perp = axis.Perpendicular().Resize( radius );
133
134 auto seg1 = std::make_unique<PCB_SHAPE>( nullptr, SHAPE_T::SEGMENT );
135 seg1->SetStart( ptA + perp );
136 seg1->SetEnd( ptB + perp );
137 aVector.push_back( seg1.get() );
138 aOwned.push_back( std::move( seg1 ) );
139
140 auto seg2 = std::make_unique<PCB_SHAPE>( nullptr, SHAPE_T::SEGMENT );
141 seg2->SetStart( ptA - perp );
142 seg2->SetEnd( ptB - perp );
143 aVector.push_back( seg2.get() );
144 aOwned.push_back( std::move( seg2 ) );
145
146 VECTOR2I midA = ptA - axis.Resize( radius );
147 auto arcA = std::make_unique<PCB_SHAPE>( nullptr, SHAPE_T::ARC );
148 arcA->SetArcGeometry( ptA + perp, midA, ptA - perp );
149 aVector.push_back( arcA.get() );
150 aOwned.push_back( std::move( arcA ) );
151
152 VECTOR2I midB = ptB + axis.Resize( radius );
153 auto arcB = std::make_unique<PCB_SHAPE>( nullptr, SHAPE_T::ARC );
154 arcB->SetArcGeometry( ptB - perp, midB, ptB + perp );
155 aVector.push_back( arcB.get() );
156 aOwned.push_back( std::move( arcB ) );
157 }
158 }
159}
160
161
162bool segmentIntersectsArc( const VECTOR2I& p1, const VECTOR2I& p2, const VECTOR2I& center,
163 double radius, EDA_ANGLE startAngle, EDA_ANGLE endAngle,
164 std::vector<VECTOR2I>* aIntersectionPoints = nullptr )
165{
166 SEG segment( p1, p2 );
167 VECTOR2I startPoint( radius * cos( startAngle.AsRadians() ), radius * sin( startAngle.AsRadians() ) );
168 SHAPE_ARC arc( center, startPoint + center, endAngle - startAngle );
169
170 INTERSECTABLE_GEOM geom1 = segment;
171 INTERSECTABLE_GEOM geom2 = arc;
172
173 std::vector<VECTOR2I> rawPoints;
174 INTERSECTION_VISITOR visitor( geom2, rawPoints );
175 std::visit( visitor, geom1 );
176
177 // A path is allowed to end on the arc, so an intersection at either endpoint is a touch,
178 // not a crossing. Only interior crossings count. Tolerance absorbs solver rounding.
179 std::vector<VECTOR2I> filtered;
180
181 const VECTOR2I::extended_type tolerance = 50;
182 const VECTOR2I::extended_type toleranceSq = tolerance * tolerance;
183
184 auto coincident =
185 [&]( const VECTOR2I& a, const VECTOR2I& b )
186 {
187 return ( a - b ).SquaredEuclideanNorm() <= toleranceSq;
188 };
189
190 for( const VECTOR2I& ip : rawPoints )
191 {
192 if( !coincident( ip, p1 ) && !coincident( ip, p2 ) )
193 filtered.push_back( ip );
194 }
195
196 if( aIntersectionPoints )
197 {
198 for( const VECTOR2I& ip : filtered )
199 aIntersectionPoints->push_back( ip );
200 }
201
202 return !filtered.empty();
203}
204
205
206//Check if line segments 'p1q1' and 'p2q2' intersect, excluding endpoint overlap
207
208bool segments_intersect( const VECTOR2I& p1, const VECTOR2I& q1, const VECTOR2I& p2, const VECTOR2I& q2,
209 std::vector<VECTOR2I>& aIntersectionPoints )
210{
211 if( p1 == p2 || p1 == q2 || q1 == p2 || q1 == q2 )
212 return false;
213
214 SEG segment1( p1, q1 );
215 SEG segment2( p2, q2 );
216
217 INTERSECTABLE_GEOM geom1 = segment1;
218 INTERSECTABLE_GEOM geom2 = segment2;
219
220 size_t startCount = aIntersectionPoints.size();
221
222 INTERSECTION_VISITOR visitor( geom2, aIntersectionPoints );
223 std::visit( visitor, geom1 );
224
225 return aIntersectionPoints.size() > startCount;
226}
227
228
229bool compareShapes( const CREEP_SHAPE* a, const CREEP_SHAPE* b )
230{
231 if( !a )
232 return true;
233
234 if( !b )
235 return false;
236
237 if( a->GetType() != b->GetType() )
238 return a->GetType() < b->GetType();
239
240 if( a->GetType() == CREEP_SHAPE::TYPE::UNDEFINED )
241 return true;
242
243 if( a->GetPos() != b->GetPos() )
244 return a->GetPos() < b->GetPos();
245
246 if( a->GetType() == CREEP_SHAPE::TYPE::CIRCLE )
247 return a->GetRadius() < b->GetRadius();
248
249 return false;
250}
251
252
253bool areEquivalent( const CREEP_SHAPE* a, const CREEP_SHAPE* b )
254{
255 if( !a && !b )
256 return true;
257
258 if( !a || !b )
259 return false;
260
261 if( a->GetType() != b->GetType() )
262 return false;
263
264 if( a->GetType() == CREEP_SHAPE::TYPE::POINT_TYPE )
265 return a->GetPos() == b->GetPos();
266
267 if( a->GetType() == CREEP_SHAPE::TYPE::CIRCLE )
268 return a->GetPos() == b->GetPos() && ( a->GetRadius() == b->GetRadius() );
269
270 return false;
271}
272
273
274std::vector<PATH_CONNECTION> BE_SHAPE_POINT::Paths( const BE_SHAPE_POINT& aS2, double aMaxWeight,
275 double aMaxSquaredWeight ) const
276{
277 std::vector<PATH_CONNECTION> result;
278
279 double weight = ( this->GetPos() - aS2.GetPos() ).SquaredEuclideanNorm();
280
281 if( weight > aMaxSquaredWeight )
282 return result;
283
285 pc.a1 = this->GetPos();
286 pc.a2 = aS2.GetPos();
287 pc.weight = sqrt( weight );
288
289 result.push_back( pc );
290 return result;
291}
292
293
294std::vector<PATH_CONNECTION> BE_SHAPE_POINT::Paths( const BE_SHAPE_CIRCLE& aS2, double aMaxWeight,
295 double aMaxSquaredWeight ) const
296{
297 std::vector<PATH_CONNECTION> result;
298 int radius = aS2.GetRadius();
299 VECTOR2I pointPos = this->GetPos();
300 VECTOR2I circleCenter = aS2.GetPos();
301
302 if( radius <= 0 )
303 return result;
304
305 double pointToCenterDistanceSquared = ( pointPos - circleCenter ).SquaredEuclideanNorm();
306 double weightSquared = pointToCenterDistanceSquared - (float) radius * (float) radius;
307
308 if( weightSquared > aMaxSquaredWeight )
309 return result;
310
311 VECTOR2D direction1 = VECTOR2D( pointPos.x - circleCenter.x, pointPos.y - circleCenter.y );
312 direction1 = direction1.Resize( 1 );
313
314 VECTOR2D direction2 = direction1.Perpendicular();
315
316 double radiusSquared = double( radius ) * double( radius );
317
318 double distance = sqrt( pointToCenterDistanceSquared );
319 double value1 = radiusSquared / distance;
320 double value2 = sqrt( radiusSquared - value1 * value1 );
321
322 VECTOR2D resultPoint;
323
325 pc.a1 = pointPos;
326 pc.weight = sqrt( weightSquared );
327
328 resultPoint = direction1 * value1 + direction2 * value2 + circleCenter;
329 pc.a2.x = int( resultPoint.x );
330 pc.a2.y = int( resultPoint.y );
331 result.push_back( pc );
332
333 resultPoint = direction1 * value1 - direction2 * value2 + circleCenter;
334 pc.a2.x = int( resultPoint.x );
335 pc.a2.y = int( resultPoint.y );
336 result.push_back( pc );
337
338 return result;
339}
340
341
342std::pair<bool, bool> BE_SHAPE_ARC::IsThereATangentPassingThroughPoint( const BE_SHAPE_POINT aPoint ) const
343{
344 std::pair<bool, bool> result;
345 double R = m_radius;
346
347 VECTOR2I newPoint = aPoint.GetPos() - m_pos;
348
349 if( newPoint.SquaredEuclideanNorm() <= R * R )
350 {
351 // If the point is inside the arc
352 result.first = false;
353 result.second = false;
354 return result;
355 }
356
357 EDA_ANGLE testAngle = AngleBetweenStartAndEnd( aPoint.GetPos() );
358
359 double startAngle = m_startAngle.AsRadians();
360 double endAngle = m_endAngle.AsRadians();
361 double pointAngle = testAngle.AsRadians();
362
363 bool greaterThan180 = ( m_endAngle - m_startAngle ) > EDA_ANGLE( 180 );
364 bool connectToEndPoint;
365
366 connectToEndPoint = ( cos( startAngle ) * newPoint.x + sin( startAngle ) * newPoint.y >= R );
367
368 if( greaterThan180 )
369 connectToEndPoint &= ( cos( endAngle ) * newPoint.x + sin( endAngle ) * newPoint.y <= R );
370
371 connectToEndPoint |= ( cos( endAngle ) * newPoint.x + sin( endAngle ) * newPoint.y <= R )
372 && ( pointAngle >= endAngle || pointAngle <= startAngle );
373
374 result.first = !connectToEndPoint;
375
376 connectToEndPoint = ( cos( endAngle ) * newPoint.x + sin( endAngle ) * newPoint.y >= R );
377
378 if( greaterThan180 )
379 connectToEndPoint &= ( cos( startAngle ) * newPoint.x + sin( startAngle ) * newPoint.y <= R );
380
381 connectToEndPoint |= ( cos( startAngle ) * newPoint.x + sin( startAngle ) * newPoint.y <= R )
382 && ( pointAngle >= endAngle || pointAngle <= startAngle );
383
384 result.second = !connectToEndPoint;
385 return result;
386}
387
388
389std::vector<PATH_CONNECTION> BE_SHAPE_POINT::Paths( const BE_SHAPE_ARC& aS2, double aMaxWeight,
390 double aMaxSquaredWeight ) const
391{
392 std::vector<PATH_CONNECTION> result;
393 VECTOR2I center = aS2.GetPos();
394 double radius = aS2.GetRadius();
395
396 // First path tries to connect to start point
397 // Second path tries to connect to end point
398 std::pair<bool, bool> behavesLikeCircle;
399 behavesLikeCircle = aS2.IsThereATangentPassingThroughPoint( *this );
400
401 if( behavesLikeCircle.first && behavesLikeCircle.second )
402 {
404 return this->Paths( csc, aMaxWeight, aMaxSquaredWeight );
405 }
406
407 if( behavesLikeCircle.first )
408 {
410 std::vector<PATH_CONNECTION> paths = this->Paths( csc, aMaxWeight, aMaxSquaredWeight );
411
412 if( paths.size() > 1 ) // Point to circle creates either 0 or 2 connections
413 result.push_back( paths[1] );
414 }
415 else
416 {
417 BE_SHAPE_POINT csp1( aS2.GetStartPoint() );
418
419 for( const PATH_CONNECTION& pc : this->Paths( csp1, aMaxWeight, aMaxSquaredWeight ) )
420 result.push_back( pc );
421 }
422
423 if( behavesLikeCircle.second )
424 {
426 std::vector<PATH_CONNECTION> paths = this->Paths( csc, aMaxWeight, aMaxSquaredWeight );
427
428 if( paths.size() > 1 ) // Point to circle creates either 0 or 2 connections
429 result.push_back( paths[0] );
430 }
431 else
432 {
433 BE_SHAPE_POINT csp1( aS2.GetEndPoint() );
434
435 for( const PATH_CONNECTION& pc : this->Paths( csp1, aMaxWeight, aMaxSquaredWeight ) )
436 result.push_back( pc );
437 }
438
439 return result;
440}
441
442std::vector<PATH_CONNECTION> BE_SHAPE_CIRCLE::Paths( const BE_SHAPE_ARC& aS2, double aMaxWeight,
443 double aMaxSquaredWeight ) const
444{
445 std::vector<PATH_CONNECTION> result;
446 VECTOR2I circleCenter = this->GetPos();
447 double circleRadius = this->GetRadius();
448 VECTOR2I arcCenter = aS2.GetPos();
449 double arcRadius = aS2.GetRadius();
450 EDA_ANGLE arcStartAngle = aS2.GetStartAngle();
451 EDA_ANGLE arcEndAngle = aS2.GetEndAngle();
452
453 double centerDistance = ( circleCenter - arcCenter ).EuclideanNorm();
454
455 if( centerDistance + arcRadius < circleRadius )
456 {
457 // The arc is inside the circle
458 return result;
459 }
460
461 BE_SHAPE_POINT csp1( aS2.GetStartPoint() );
462 BE_SHAPE_POINT csp2( aS2.GetEndPoint() );
463 BE_SHAPE_CIRCLE csc( arcCenter, arcRadius );
464
465 for( const PATH_CONNECTION& pc : this->Paths( csc, aMaxWeight, aMaxSquaredWeight ) )
466 {
467 EDA_ANGLE pointAngle = aS2.AngleBetweenStartAndEnd( pc.a2 );
468
469 if( pointAngle <= aS2.GetEndAngle() )
470 result.push_back( pc );
471 }
472
473 if( result.size() == 4 )
474 {
475 // It behaved as a circle
476 return result;
477 }
478
479 for( const BE_SHAPE_POINT& csp : { csp1, csp2 } )
480 {
481 for( const PATH_CONNECTION& pc : this->Paths( csp, aMaxWeight, aMaxSquaredWeight ) )
482 {
483 if( !segmentIntersectsArc( pc.a1, pc.a2, arcCenter, arcRadius, arcStartAngle, arcEndAngle ) )
484 result.push_back( pc );
485 }
486 }
487
488 return result;
489}
490
491
492std::vector<PATH_CONNECTION> BE_SHAPE_ARC::Paths( const BE_SHAPE_ARC& aS2, double aMaxWeight,
493 double aMaxSquaredWeight ) const
494{
495 std::vector<PATH_CONNECTION> result;
496 VECTOR2I circleCenter = this->GetPos();
497 double circleRadius = this->GetRadius();
498 VECTOR2I arcCenter = aS2.GetPos();
499 double arcRadius = aS2.GetRadius();
500
501 double centerDistance = ( circleCenter - arcCenter ).EuclideanNorm();
502
503 if( centerDistance + arcRadius < circleRadius )
504 {
505 // The arc is inside the circle
506 return result;
507 }
508
509 BE_SHAPE_POINT csp1( aS2.GetStartPoint() );
510 BE_SHAPE_POINT csp2( aS2.GetEndPoint() );
511 BE_SHAPE_CIRCLE csc( arcCenter, arcRadius );
512
513
514 for( const PATH_CONNECTION& pc : this->Paths( BE_SHAPE_CIRCLE( aS2.GetPos(), aS2.GetRadius() ),
515 aMaxWeight, aMaxSquaredWeight ) )
516 {
517 EDA_ANGLE pointAngle = aS2.AngleBetweenStartAndEnd( pc.a2 );
518
519 if( pointAngle <= aS2.GetEndAngle() )
520 result.push_back( pc );
521 }
522
523 for( const PATH_CONNECTION& pc : BE_SHAPE_CIRCLE( this->GetPos(), this->GetRadius() )
524 .Paths( aS2, aMaxWeight, aMaxSquaredWeight ) )
525 {
526 EDA_ANGLE pointAngle = this->AngleBetweenStartAndEnd( pc.a1 );
527
528 if( pointAngle <= this->GetEndAngle() )
529 result.push_back( pc );
530 }
531
532 return result;
533}
534
535
536std::vector<PATH_CONNECTION> BE_SHAPE_CIRCLE::Paths( const BE_SHAPE_CIRCLE& aS2, double aMaxWeight,
537 double aMaxSquaredWeight ) const
538{
539 std::vector<PATH_CONNECTION> result;
540
541 VECTOR2I p1 = this->GetPos();
542 VECTOR2I p2 = aS2.GetPos();
543
544 VECTOR2D distSquared( double( ( p2 - p1 ).x ), double( ( p2 - p1 ).y ) );
545 double weightSquared = distSquared.SquaredEuclideanNorm();
546
547 double R1 = this->GetRadius();
548 double R2 = aS2.GetRadius();
549
550 double Rdiff = abs( R1 - R2 );
551 double Rsum = R1 + R2;
552
553 // "Straight" paths
554 double weightSquared1 = weightSquared - Rdiff * Rdiff;
555 // "Crossed" paths
556 double weightSquared2 = weightSquared - Rsum * Rsum;
557
558 if( weightSquared1 <= aMaxSquaredWeight )
559 {
560 VECTOR2D direction1 = VECTOR2D( p2.x - p1.x, p2.y - p1.y );
561 direction1 = direction1.Resize( 1 );
562 VECTOR2D direction2 = direction1.Perpendicular();
563
564 double D = sqrt( weightSquared );
565 double ratio1 = ( R1 - R2 ) / D;
566 double ratio2 = sqrt( 1 - ratio1 * ratio1 );
567
568
570 pc.weight = sqrt( weightSquared1 );
571
572 pc.a1 = p1 + direction1 * R1 * ratio1 + direction2 * R1 * ratio2;
573 pc.a2 = p2 + direction1 * R2 * ratio1 + direction2 * R2 * ratio2;
574
575 result.push_back( pc );
576
577 pc.a1 = p1 + direction1 * R1 * ratio1 - direction2 * R1 * ratio2;
578 pc.a2 = p2 + direction1 * R2 * ratio1 - direction2 * R2 * ratio2;
579
580 result.push_back( pc );
581 }
582 if( weightSquared2 <= aMaxSquaredWeight )
583 {
584 VECTOR2D direction1 = VECTOR2D( p2.x - p1.x, p2.y - p1.y );
585 direction1 = direction1.Resize( 1 );
586 VECTOR2D direction2 = direction1.Perpendicular();
587
588 double D = sqrt( weightSquared );
589 double ratio1 = ( R1 + R2 ) / D;
590 double ratio2 = sqrt( 1 - ratio1 * ratio1 );
591
592
594 pc.weight = sqrt( weightSquared2 );
595
596 pc.a1 = p1 + direction1 * R1 * ratio1 + direction2 * R1 * ratio2;
597 pc.a2 = p2 - direction1 * R2 * ratio1 - direction2 * R2 * ratio2;
598
599 result.push_back( pc );
600
601 pc.a1 = p1 + direction1 * R1 * ratio1 - direction2 * R1 * ratio2;
602 pc.a2 = p2 - direction1 * R2 * ratio1 + direction2 * R2 * ratio2;
603
604 result.push_back( pc );
605 }
606
607 return result;
608}
609
610
611void CREEPAGE_GRAPH::TransformCreepShapesToNodes( const std::vector<std::unique_ptr<CREEP_SHAPE>>& aShapes )
612{
613 for( const std::unique_ptr<CREEP_SHAPE>& shape : aShapes )
614 {
615 CREEP_SHAPE* p1 = shape.get();
616
617 if( !p1 )
618 continue;
619
620 switch( p1->GetType() )
621 {
622 case CREEP_SHAPE::TYPE::POINT_TYPE: AddNode( GRAPH_NODE::TYPE::POINT, p1, p1->GetPos() ); break;
623 case CREEP_SHAPE::TYPE::CIRCLE: AddNode( GRAPH_NODE::TYPE::CIRCLE, p1, p1->GetPos() ); break;
624 case CREEP_SHAPE::TYPE::ARC: AddNode( GRAPH_NODE::TYPE::ARC, p1, p1->GetPos() ); break;
625 default: break;
626 }
627 }
628}
629
631{
632 std::sort( m_shapeCollection.begin(), m_shapeCollection.end(),
633 []( const auto& a, const auto& b ) { return compareShapes( a.get(), b.get() ); } );
634 size_t kept = 0;
635
636 for( size_t i = 0; i < m_shapeCollection.size(); ++i )
637 {
638 if( !m_shapeCollection[i] )
639 continue;
640
641 // Keep the last equivalent shape: its parent metadata may differ from earlier shapes.
642 if( i + 1 < m_shapeCollection.size()
643 && areEquivalent( m_shapeCollection[i].get(), m_shapeCollection[i + 1].get() ) )
644 continue;
645
646 if( kept != i )
647 m_shapeCollection[kept] = std::move( m_shapeCollection[i] );
648
649 ++kept;
650 }
651
652 m_shapeCollection.resize( kept );
653}
654
656{
657 // Flag overlapping cutouts so the arc void check below only runs when needed.
658 std::vector<BOX2I> cutouts;
659
660 for( BOARD_ITEM* be : m_boardEdge )
661 {
662 PCB_SHAPE* s = static_cast<PCB_SHAPE*>( be );
663
664 if( s
666 || s->GetShape() == SHAPE_T::POLY ) )
667 {
668 cutouts.push_back( s->GetBoundingBox() );
669 }
670 }
671
672 for( size_t i = 0; i < cutouts.size() && !m_hasOverlappingCutouts; ++i )
673 {
674 for( size_t j = i + 1; j < cutouts.size(); ++j )
675 {
676 if( cutouts[i].Intersects( cutouts[j] ) && !cutouts[i].Contains( cutouts[j] )
677 && !cutouts[j].Contains( cutouts[i] ) )
678 {
680 break;
681 }
682 }
683 }
684
685 for( BOARD_ITEM* drawing : m_boardEdge )
686 {
687 PCB_SHAPE* d = dynamic_cast<PCB_SHAPE*>( drawing );
688
689 if( !d )
690 continue;
691
692 switch( d->GetShape() )
693 {
694 case SHAPE_T::SEGMENT:
695 {
696 auto a = std::make_unique<BE_SHAPE_POINT>( d->GetStart() );
697 a->SetParent( d );
698 m_shapeCollection.push_back( std::move( a ) );
699 a = std::make_unique<BE_SHAPE_POINT>( d->GetEnd() );
700 a->SetParent( d );
701 m_shapeCollection.push_back( std::move( a ) );
702 break;
703 }
704
706 {
707 int r = d->GetCornerRadius();
708
709 if( r > 0 )
710 {
711 // Rounded rectangle: decompose into arcs.
712 // Normalize coordinates so x1 < x2 and y1 < y2.
713 int x1 = std::min( d->GetStart().x, d->GetEnd().x );
714 int y1 = std::min( d->GetStart().y, d->GetEnd().y );
715 int x2 = std::max( d->GetStart().x, d->GetEnd().x );
716 int y2 = std::max( d->GetStart().y, d->GetEnd().y );
717
718 int w = x2 - x1;
719 int h = y2 - y1;
720
721 auto addArc = [&]( const VECTOR2I& center, const VECTOR2I& startPt,
722 const VECTOR2I& endPt )
723 {
724 EDA_ANGLE startAngle( VECTOR2D( startPt - center ) );
725 EDA_ANGLE endAngle( VECTOR2D( endPt - center ) );
726
727 while( endAngle < startAngle )
728 endAngle += ANGLE_360;
729
730 auto arc = std::make_unique<BE_SHAPE_ARC>( center, r, startAngle, endAngle,
731 startPt, endPt );
732 arc->SetParent( d );
733 m_shapeCollection.push_back( std::move( arc ) );
734 };
735
736 if( h == 2 * r )
737 {
738 // Horizontal stadium: left and right semicircles. The endpoint order
739 // makes addArc sweep the outer half of each circle so the caps bulge
740 // away from the slot.
741 addArc( { x1 + r, y1 + r }, { x1 + r, y2 }, { x1 + r, y1 } );
742 addArc( { x2 - r, y1 + r }, { x2 - r, y1 }, { x2 - r, y2 } );
743 }
744 else if( w == 2 * r )
745 {
746 // Vertical stadium: top and bottom semicircles
747 addArc( { x1 + r, y1 + r }, { x1, y1 + r }, { x2, y1 + r } );
748 addArc( { x1 + r, y2 - r }, { x2, y2 - r }, { x1, y2 - r } );
749 }
750 else
751 {
752 // General rounded rectangle: four quarter-circle arcs
753 addArc( { x1 + r, y1 + r }, { x1, y1 + r }, { x1 + r, y1 } );
754 addArc( { x2 - r, y1 + r }, { x2 - r, y1 }, { x2, y1 + r } );
755 addArc( { x2 - r, y2 - r }, { x2, y2 - r }, { x2 - r, y2 } );
756 addArc( { x1 + r, y2 - r }, { x1 + r, y2 }, { x1, y2 - r } );
757 }
758 }
759 else
760 {
761 auto a = std::make_unique<BE_SHAPE_POINT>( d->GetStart() );
762 a->SetParent( d );
763 m_shapeCollection.push_back( std::move( a ) );
764 a = std::make_unique<BE_SHAPE_POINT>( d->GetEnd() );
765 a->SetParent( d );
766 m_shapeCollection.push_back( std::move( a ) );
767 a = std::make_unique<BE_SHAPE_POINT>( VECTOR2I( d->GetEnd().x, d->GetStart().y ) );
768 a->SetParent( d );
769 m_shapeCollection.push_back( std::move( a ) );
770 a = std::make_unique<BE_SHAPE_POINT>( VECTOR2I( d->GetStart().x, d->GetEnd().y ) );
771 a->SetParent( d );
772 m_shapeCollection.push_back( std::move( a ) );
773 }
774
775 break;
776 }
777
778 case SHAPE_T::POLY:
779 for( const VECTOR2I& p : d->GetPolyPoints() )
780 {
781 auto a = std::make_unique<BE_SHAPE_POINT>( p );
782 a->SetParent( d );
783 m_shapeCollection.push_back( std::move( a ) );
784 }
785
786 break;
787
788 case SHAPE_T::CIRCLE:
789 {
790 auto a = std::make_unique<BE_SHAPE_CIRCLE>( d->GetCenter(), d->GetRadius() );
791 a->SetParent( d );
792 m_shapeCollection.push_back( std::move( a ) );
793 break;
794 }
795
796 case SHAPE_T::ARC:
797 {
798 // If the arc is not locally convex, only use the endpoints
799 double tolerance = 10;
800 VECTOR2D center( double( d->GetCenter().x ), double( d->GetCenter().y ) );
801 VECTOR2D mid( double( d->GetArcMid().x ), double( d->GetArcMid().y ) );
802 VECTOR2D dir( mid - center );
803 dir = dir / d->GetRadius() * ( d->GetRadius() - tolerance );
804
805 EDA_ANGLE alpha, beta;
806 d->CalcArcAngles( alpha, beta );
807 auto a = std::make_unique<BE_SHAPE_ARC>( d->GetCenter(), d->GetRadius(), alpha, beta,
808 d->GetStart(), d->GetEnd() );
809 a->SetParent( d );
810
811 m_shapeCollection.push_back( std::move( a ) );
812 break;
813 }
814
815 default:
816 break;
817 }
818 }
819}
820
821
822void GRAPH_CONNECTION::GetShapes( std::vector<PCB_SHAPE>& aShapes )
823{
824 if( !m_path.m_show )
825 return;
826
827 if( !n1 || !n2 )
828 return;
829
830 if( n1->m_type == GRAPH_NODE::TYPE::VIRTUAL || n2->m_type == GRAPH_NODE::TYPE::VIRTUAL )
831 return;
832
833 if( !m_forceStraightLine && n1->m_parent
834 && n1->m_parent == n2->m_parent
835 && n1->m_parent->GetType() == CREEP_SHAPE::TYPE::CIRCLE )
836 {
837 VECTOR2I center = n1->m_parent->GetPos();
838 VECTOR2I R1 = n1->m_pos - center;
839 VECTOR2I R2 = n2->m_pos - center;
840 PCB_SHAPE s( nullptr, SHAPE_T::ARC );
841
842 if( R1.Cross( R2 ) > 0 )
843 {
844 s.SetStart( n1->m_pos );
845 s.SetEnd( n2->m_pos );
846 }
847 else
848 {
849 s.SetStart( n2->m_pos );
850 s.SetEnd( n1->m_pos );
851 }
852
853 s.SetCenter( center );
854 aShapes.push_back( s );
855 return;
856 }
857
858 if( !m_forceStraightLine && n1->m_parent
859 && n1->m_parent == n2->m_parent
860 && n1->m_parent->GetType() == CREEP_SHAPE::TYPE::ARC )
861 {
862 if( BE_SHAPE_ARC* arc = dynamic_cast<BE_SHAPE_ARC*>( n1->m_parent ) )
863 {
864 VECTOR2I center = arc->GetPos();
865 VECTOR2I R1 = n1->m_pos - center;
866 VECTOR2I R2 = n2->m_pos - center;
867 PCB_SHAPE s( nullptr, SHAPE_T::ARC );
868
869 if( R1.Cross( R2 ) > 0 )
870 {
871 s.SetStart( n1->m_pos );
872 s.SetEnd( n2->m_pos );
873 }
874 else
875 {
876 s.SetStart( n2->m_pos );
877 s.SetEnd( n1->m_pos );
878 }
879
880 s.SetCenter( center );
881
882 //Check that we are on the correct side of the arc.
883 VECTOR2I mid = s.GetArcMid();
884 EDA_ANGLE midAngle = arc->AngleBetweenStartAndEnd( mid );
885
886 if( midAngle > arc->GetEndAngle() )
887 {
888 VECTOR2I tmp;
889 tmp = s.GetStart();
890 s.SetStart( s.GetEnd() );
891 s.SetEnd( tmp );
892 s.SetCenter( center );
893 }
894
895 aShapes.push_back( s );
896 return;
897 }
898 }
899
900 PCB_SHAPE s( nullptr, SHAPE_T::SEGMENT );
901 s.SetStart( m_path.a1 );
902 s.SetEnd( m_path.a2 );
903 aShapes.push_back( s );
904}
905
906
907void CREEP_SHAPE::ConnectChildren( std::shared_ptr<GRAPH_NODE>& a1, std::shared_ptr<GRAPH_NODE>&,
908 CREEPAGE_GRAPH& aG ) const
909{
910}
911
912
913void BE_SHAPE_POINT::ConnectChildren( std::shared_ptr<GRAPH_NODE>& a1, std::shared_ptr<GRAPH_NODE>&,
914 CREEPAGE_GRAPH& aG ) const
915{
916}
917
918
919void BE_SHAPE_CIRCLE::ShortenChildDueToGV( std::shared_ptr<GRAPH_NODE>& a1, std::shared_ptr<GRAPH_NODE>& a2,
920 CREEPAGE_GRAPH& aG, double aNormalWeight ) const
921{
922 EDA_ANGLE angle1 = EDA_ANGLE( a1->m_pos - m_pos );
923 EDA_ANGLE angle2 = EDA_ANGLE( a2->m_pos - m_pos );
924
925 while( angle1 < ANGLE_0 )
926 angle1 += ANGLE_360;
927 while( angle2 < ANGLE_0 )
928 angle2 += ANGLE_360;
929 while( angle1 > ANGLE_360 )
930 angle1 -= ANGLE_360;
931 while( angle2 > ANGLE_360 )
932 angle2 -= ANGLE_360;
933
934 EDA_ANGLE maxAngle = angle1 > angle2 ? angle1 : angle2;
935 EDA_ANGLE skipAngle =
936 EDA_ANGLE( asin( float( aG.m_minGrooveWidth ) / ( 2 * m_radius ) ), RADIANS_T );
937 skipAngle += skipAngle; // Cannot multiply EDA_ANGLE by scalar, but this really is angle *2
938 EDA_ANGLE pointAngle = maxAngle - skipAngle;
939
940 VECTOR2I skipPoint = m_pos;
941 skipPoint.x += m_radius * cos( pointAngle.AsRadians() );
942 skipPoint.y += m_radius * sin( pointAngle.AsRadians() );
943
944 std::shared_ptr<GRAPH_NODE> gnt = aG.AddNode( GRAPH_NODE::POINT, a1->m_parent, skipPoint );
945
947
948 pc.a1 = maxAngle == angle2 ? a1->m_pos : a2->m_pos;
949 pc.a2 = skipPoint;
950 pc.weight = aNormalWeight - aG.m_minGrooveWidth;
951 aG.AddConnection( maxAngle == angle2 ? a1 : a2, gnt, pc );
952
953 pc.a1 = skipPoint;
954 pc.a2 = maxAngle == angle2 ? a2->m_pos : a1->m_pos;
955 pc.weight = aG.m_minGrooveWidth;
956
957 std::shared_ptr<GRAPH_CONNECTION> gc = aG.AddConnection( gnt, maxAngle == angle2 ? a2 : a1, pc );
958
959 if( gc )
960 gc->m_forceStraightLine = true;
961}
962
963
964void BE_SHAPE_CIRCLE::ConnectChildren( std::shared_ptr<GRAPH_NODE>& a1, std::shared_ptr<GRAPH_NODE>& a2,
965 CREEPAGE_GRAPH& aG ) const
966{
967 if( !a1 || !a2 )
968 return;
969
970 if( m_radius == 0 )
971 return;
972
973 // When cutouts overlap, part of this wall runs inside the merged void and is not
974 // a real edge to hug. Check the shorter arc, the one the solver measures and draws.
976 {
977 int tol = aG.m_board.GetDesignSettings().m_MaxError + 1000;
978 double a1r = EDA_ANGLE( a1->m_pos - m_pos ).AsRadians();
979 double a2r = EDA_ANGLE( a2->m_pos - m_pos ).AsRadians();
980 double delta = a2r - a1r;
981
982 while( delta > M_PI )
983 delta -= 2 * M_PI;
984 while( delta < -M_PI )
985 delta += 2 * M_PI;
986
987 for( int i = 0; i <= 8; ++i )
988 {
989 double a = a1r + delta * i / 8.0;
990 VECTOR2I p( m_pos.x + m_radius * cos( a ), m_pos.y + m_radius * sin( a ) );
991
992 if( !aG.m_boardOutline->Contains( p, -1, tol ) && !aG.m_boardOutline->PointOnEdge( p, tol ) )
993 return;
994 }
995 }
996
997 VECTOR2D distI( a1->m_pos - a2->m_pos );
998 VECTOR2D distD( double( distI.x ), double( distI.y ) );
999
1000 double weight = m_radius * 2 * asin( distD.EuclideanNorm() / ( 2.0 * m_radius ) );
1001
1002 if( weight > aG.GetTarget() )
1003 return;
1004
1005 if( aG.m_minGrooveWidth <= 0 )
1006 {
1007 PATH_CONNECTION pc;
1008 pc.a1 = a1->m_pos;
1009 pc.a2 = a2->m_pos;
1010 pc.weight = std::max( weight, 0.0 );
1011
1012 aG.AddConnection( a1, a2, pc );
1013 return;
1014 }
1015
1016 if( weight > aG.m_minGrooveWidth )
1017 ShortenChildDueToGV( a1, a2, aG, weight );
1018 // Else well.. this paths will be "shorted" by another one
1019}
1020
1021
1022void BE_SHAPE_ARC::ConnectChildren( std::shared_ptr<GRAPH_NODE>& a1, std::shared_ptr<GRAPH_NODE>& a2,
1023 CREEPAGE_GRAPH& aG ) const
1024{
1025 if( !a1 || !a2 )
1026 return;
1027
1028 EDA_ANGLE angle1 = AngleBetweenStartAndEnd( a1->m_pos );
1029 EDA_ANGLE angle2 = AngleBetweenStartAndEnd( a2->m_pos );
1030
1031 // Skip an arc that dips into an overlapping cutout, it is not a real edge to hug.
1032 // Sample the whole sub-arc, the tolerance clears the outline arc-to-segment error.
1034 {
1035 int tol = aG.m_board.GetDesignSettings().m_MaxError + 1000;
1036 double a1r = angle1.AsRadians();
1037 double a2r = angle2.AsRadians();
1038
1039 for( int i = 0; i <= 8; ++i )
1040 {
1041 double a = a1r + ( a2r - a1r ) * i / 8.0;
1042 VECTOR2I p( m_pos.x + m_radius * cos( a ), m_pos.y + m_radius * sin( a ) );
1043
1044 if( !aG.m_boardOutline->Contains( p, -1, tol ) && !aG.m_boardOutline->PointOnEdge( p, tol ) )
1045 return;
1046 }
1047 }
1048
1049 double weight = abs( m_radius * ( angle2 - angle1 ).AsRadians() );
1050
1051 if( aG.m_minGrooveWidth <= 0 )
1052 {
1053 if( ( weight > aG.GetTarget() ) )
1054 return;
1055
1056 PATH_CONNECTION pc;
1057 pc.a1 = a1->m_pos;
1058 pc.a2 = a2->m_pos;
1059 pc.weight = weight;
1060
1061 aG.AddConnection( a1, a2, pc );
1062 return;
1063 }
1064
1065 if( weight > aG.m_minGrooveWidth )
1066 ShortenChildDueToGV( a1, a2, aG, weight );
1067}
1068
1069
1070void CREEPAGE_GRAPH::SetTarget( double aTarget )
1071{
1072 m_creepageTarget = aTarget;
1073 m_creepageTargetSquared = aTarget * aTarget;
1074}
1075
1076
1077std::vector<PATH_CONNECTION> CU_SHAPE_SEGMENT::Paths( const BE_SHAPE_POINT& aS2, double aMaxWeight,
1078 double aMaxSquaredWeight ) const
1079{
1080 std::vector<PATH_CONNECTION> result;
1081 VECTOR2I start = this->GetStart();
1082 VECTOR2I end = this->GetEnd();
1083 double halfWidth = this->GetWidth() / 2;
1084 EDA_ANGLE trackAngle( end - start );
1085 VECTOR2I pointPos = aS2.GetPos();
1086
1087 double length = ( start - end ).EuclideanNorm();
1088 double projectedPos = cos( trackAngle.AsRadians() ) * ( pointPos.x - start.x )
1089 + sin( trackAngle.AsRadians() ) * ( pointPos.y - start.y );
1090
1091 VECTOR2I newPoint;
1092
1093 if( projectedPos <= 0 )
1094 {
1095 newPoint = start + ( pointPos - start ).Resize( halfWidth );
1096 }
1097 else if( projectedPos >= length )
1098 {
1099 newPoint = end + ( pointPos - end ).Resize( halfWidth );
1100 }
1101 else
1102 {
1103 double posOnSegment = ( start - pointPos ).SquaredEuclideanNorm()
1104 - ( end - pointPos ).SquaredEuclideanNorm();
1105 posOnSegment = posOnSegment / ( 2 * length ) + length / 2;
1106
1107 newPoint = start + ( end - start ).Resize( posOnSegment );
1108 newPoint += ( pointPos - newPoint ).Resize( halfWidth );
1109 }
1110
1111 double weightSquared = ( pointPos - newPoint ).SquaredEuclideanNorm();
1112
1113 if( weightSquared > aMaxSquaredWeight )
1114 return result;
1115
1116 PATH_CONNECTION pc;
1117 pc.a1 = newPoint;
1118 pc.a2 = pointPos;
1119 pc.weight = sqrt( weightSquared );
1120
1121 result.push_back( pc );
1122 return result;
1123}
1124
1125
1126std::vector<PATH_CONNECTION> CU_SHAPE_SEGMENT::Paths( const BE_SHAPE_CIRCLE& aS2, double aMaxWeight,
1127 double aMaxSquaredWeight ) const
1128{
1129 std::vector<PATH_CONNECTION> result;
1130 VECTOR2I start = this->GetStart();
1131 VECTOR2I end = this->GetEnd();
1132 double halfWidth = this->GetWidth() / 2;
1133
1134 double circleRadius = aS2.GetRadius();
1135 VECTOR2I circleCenter = aS2.GetPos();
1136 double length = ( start - end ).EuclideanNorm();
1137 EDA_ANGLE trackAngle( end - start );
1138
1139 double weightSquared = std::numeric_limits<double>::infinity();
1140 VECTOR2I PointOnTrack, PointOnCircle;
1141
1142 // There are two possible paths
1143 // First the one on the side of the start of the track.
1144 double projectedPos1 = cos( trackAngle.AsRadians() ) * ( circleCenter.x - start.x )
1145 + sin( trackAngle.AsRadians() ) * ( circleCenter.y - start.y );
1146 double projectedPos2 = projectedPos1 + circleRadius;
1147 projectedPos1 = projectedPos1 - circleRadius;
1148
1149 double trackSide = ( end - start ).Cross( circleCenter - start ) > 0 ? 1 : -1;
1150
1151 if( ( projectedPos1 < 0 && projectedPos2 < 0 ) )
1152 {
1153 CU_SHAPE_CIRCLE csc( start, halfWidth );
1154 for( PATH_CONNECTION pc : csc.Paths( aS2, aMaxWeight, aMaxSquaredWeight ) )
1155 {
1156 result.push_back( pc );
1157 }
1158 }
1159 else if( ( projectedPos1 > length && projectedPos2 > length ) )
1160 {
1161 CU_SHAPE_CIRCLE csc( end, halfWidth );
1162
1163 for( const PATH_CONNECTION& pc : csc.Paths( aS2, aMaxWeight, aMaxSquaredWeight ) )
1164 result.push_back( pc );
1165 }
1166
1167 else if( ( projectedPos1 >= 0 ) && ( projectedPos1 <= length ) && ( projectedPos2 >= 0 )
1168 && ( projectedPos2 <= length ) )
1169 {
1170 // Both point connects to the segment part of the track
1171 PointOnTrack = start;
1172 PointOnTrack += ( end - start ).Resize( projectedPos1 );
1173 PointOnTrack += ( end - start ).Perpendicular().Resize( halfWidth ) * trackSide;
1174 PointOnCircle = circleCenter - ( end - start ).Resize( circleRadius );
1175 weightSquared = ( PointOnCircle - PointOnTrack ).SquaredEuclideanNorm();
1176
1177 if( weightSquared < aMaxSquaredWeight )
1178 {
1179 PATH_CONNECTION pc;
1180 pc.a1 = PointOnTrack;
1181 pc.a2 = PointOnCircle;
1182 pc.weight = sqrt( weightSquared );
1183
1184 result.push_back( pc );
1185
1186 PointOnTrack = start;
1187 PointOnTrack += ( end - start ).Resize( projectedPos2 );
1188 PointOnTrack += ( end - start ).Perpendicular().Resize( halfWidth ) * trackSide;
1189 PointOnCircle = circleCenter + ( end - start ).Resize( circleRadius );
1190
1191
1192 pc.a1 = PointOnTrack;
1193 pc.a2 = PointOnCircle;
1194
1195 result.push_back( pc );
1196 }
1197 }
1198 else if( ( ( projectedPos1 >= 0 ) && ( projectedPos1 <= length ) )
1199 && ( ( projectedPos2 > length ) || projectedPos2 < 0 ) )
1200 {
1201 CU_SHAPE_CIRCLE csc( end, halfWidth );
1202 std::vector<PATH_CONNECTION> pcs = csc.Paths( aS2, aMaxWeight, aMaxSquaredWeight );
1203
1204 if( pcs.size() < 2 )
1205 return result;
1206
1207 result.push_back( pcs.at( trackSide == 1 ? 1 : 0 ) );
1208
1209
1210 PointOnTrack = start;
1211 PointOnTrack += ( end - start ).Resize( projectedPos1 );
1212 PointOnTrack += ( end - start ).Perpendicular().Resize( halfWidth ) * trackSide;
1213 PointOnCircle = circleCenter - ( end - start ).Resize( circleRadius );
1214 weightSquared = ( PointOnCircle - PointOnTrack ).SquaredEuclideanNorm();
1215
1216 if( weightSquared < aMaxSquaredWeight )
1217 {
1218 PATH_CONNECTION pc;
1219 pc.a1 = PointOnTrack;
1220 pc.a2 = PointOnCircle;
1221 pc.weight = sqrt( weightSquared );
1222
1223 result.push_back( pc );
1224 }
1225 }
1226 else if( ( ( projectedPos2 >= 0 ) && ( projectedPos2 <= length ) )
1227 && ( ( projectedPos1 > length ) || projectedPos1 < 0 ) )
1228 {
1229 CU_SHAPE_CIRCLE csc( start, halfWidth );
1230 std::vector<PATH_CONNECTION> pcs = csc.Paths( aS2, aMaxWeight, aMaxSquaredWeight );
1231
1232 if( pcs.size() < 2 )
1233 return result;
1234
1235 result.push_back( pcs.at( trackSide == 1 ? 0 : 1 ) );
1236
1237 PointOnTrack = start;
1238 PointOnTrack += ( end - start ).Resize( projectedPos2 );
1239 PointOnTrack += ( end - start ).Perpendicular().Resize( halfWidth ) * trackSide;
1240 PointOnCircle = circleCenter + ( end - start ).Resize( circleRadius );
1241 weightSquared = ( PointOnCircle - PointOnTrack ).SquaredEuclideanNorm();
1242
1243 if( weightSquared < aMaxSquaredWeight )
1244 {
1245 PATH_CONNECTION pc;
1246 pc.a1 = PointOnTrack;
1247 pc.a2 = PointOnCircle;
1248 pc.weight = sqrt( weightSquared );
1249
1250 result.push_back( pc );
1251 }
1252 }
1253 else if( projectedPos1 < 0 && projectedPos2 > length )
1254 {
1255 // The circle projects past both ends of the track, so neither tangent lands on the
1256 // track flank and each end cap carries one side of the path
1257 CU_SHAPE_CIRCLE cscStart( start, halfWidth );
1258 std::vector<PATH_CONNECTION> startPcs = cscStart.Paths( aS2, aMaxWeight, aMaxSquaredWeight );
1259
1260 if( startPcs.size() >= 2 )
1261 result.push_back( startPcs.at( trackSide == 1 ? 0 : 1 ) );
1262
1263 CU_SHAPE_CIRCLE cscEnd( end, halfWidth );
1264 std::vector<PATH_CONNECTION> endPcs = cscEnd.Paths( aS2, aMaxWeight, aMaxSquaredWeight );
1265
1266 if( endPcs.size() >= 2 )
1267 result.push_back( endPcs.at( trackSide == 1 ? 1 : 0 ) );
1268 }
1269
1270 return result;
1271}
1272
1273
1274std::vector<PATH_CONNECTION> CU_SHAPE_SEGMENT::Paths( const BE_SHAPE_ARC& aS2, double aMaxWeight,
1275 double aMaxSquaredWeight ) const
1276{
1277 std::vector<PATH_CONNECTION> result;
1278
1279 BE_SHAPE_CIRCLE bsc( aS2.GetPos(), aS2.GetRadius() );
1280
1281 for( const PATH_CONNECTION& pc : this->Paths( bsc, aMaxWeight, aMaxSquaredWeight ) )
1282 {
1283 EDA_ANGLE testAngle = aS2.AngleBetweenStartAndEnd( pc.a2 );
1284
1285 if( testAngle < aS2.GetEndAngle() )
1286 result.push_back( pc );
1287 }
1288
1289 if( result.size() < 2 )
1290 {
1291 BE_SHAPE_POINT bsp1( aS2.GetStartPoint() );
1292 BE_SHAPE_POINT bsp2( aS2.GetEndPoint() );
1293
1294 VECTOR2I beArcPos = aS2.GetPos();
1295 int beArcRadius = aS2.GetRadius();
1296 EDA_ANGLE beArcStartAngle = aS2.GetStartAngle();
1297 EDA_ANGLE beArcEndAngle = aS2.GetEndAngle();
1298
1299 for( const PATH_CONNECTION& pc : this->Paths( bsp1, aMaxWeight, aMaxSquaredWeight ) )
1300 {
1301 if( !segmentIntersectsArc( pc.a1, pc.a2, beArcPos, beArcRadius, beArcStartAngle, beArcEndAngle ) )
1302 result.push_back( pc );
1303 }
1304
1305 for( const PATH_CONNECTION& pc : this->Paths( bsp2, aMaxWeight, aMaxSquaredWeight ) )
1306 {
1307 if( !segmentIntersectsArc( pc.a1, pc.a2, beArcPos, beArcRadius, beArcStartAngle, beArcEndAngle ) )
1308 result.push_back( pc );
1309 }
1310 }
1311
1312 return result;
1313}
1314
1315
1316std::vector<PATH_CONNECTION> CU_SHAPE_CIRCLE::Paths( const BE_SHAPE_ARC& aS2, double aMaxWeight,
1317 double aMaxSquaredWeight ) const
1318{
1319 std::vector<PATH_CONNECTION> result;
1320 VECTOR2I beArcPos = aS2.GetPos();
1321 int beArcRadius = aS2.GetRadius();
1322 EDA_ANGLE beArcStartAngle = aS2.GetStartAngle();
1323 EDA_ANGLE beArcEndAngle = aS2.GetEndAngle();
1324
1325 BE_SHAPE_CIRCLE bsc( beArcPos, beArcRadius );
1326
1327 for( const PATH_CONNECTION& pc : this->Paths( bsc, aMaxWeight, aMaxSquaredWeight ) )
1328 {
1329 EDA_ANGLE testAngle = aS2.AngleBetweenStartAndEnd( pc.a2 );
1330
1331 if( testAngle < aS2.GetEndAngle() )
1332 result.push_back( pc );
1333 }
1334
1335 if( result.size() < 2 )
1336 {
1337 BE_SHAPE_POINT bsp1( aS2.GetStartPoint() );
1338 BE_SHAPE_POINT bsp2( aS2.GetEndPoint() );
1339
1340 for( const PATH_CONNECTION& pc : this->Paths( bsp1, aMaxWeight, aMaxSquaredWeight ) )
1341 {
1342 if( !segmentIntersectsArc( pc.a1, pc.a2, beArcPos, beArcRadius, beArcStartAngle, beArcEndAngle ) )
1343 result.push_back( pc );
1344 }
1345
1346 for( const PATH_CONNECTION& pc : this->Paths( bsp2, aMaxWeight, aMaxSquaredWeight ) )
1347 {
1348 if( !segmentIntersectsArc( pc.a1, pc.a2, beArcPos, beArcRadius, beArcStartAngle, beArcEndAngle ) )
1349 result.push_back( pc );
1350 }
1351
1352 }
1353 return result;
1354}
1355
1356
1357std::vector<PATH_CONNECTION> CU_SHAPE_ARC::Paths( const BE_SHAPE_CIRCLE& aS2, double aMaxWeight,
1358 double aMaxSquaredWeight ) const
1359{
1360 std::vector<PATH_CONNECTION> result;
1361
1362 CU_SHAPE_CIRCLE csc( this->GetPos(), this->GetRadius() + this->GetWidth() / 2 );
1363
1364 for( const PATH_CONNECTION& pc : this->Paths( csc, aMaxWeight, aMaxSquaredWeight ) )
1365 {
1366 EDA_ANGLE testAngle = this->AngleBetweenStartAndEnd( pc.a2 );
1367
1368 if( testAngle < this->GetEndAngle() )
1369 result.push_back( pc );
1370 }
1371
1372 if( result.size() < 2 )
1373 {
1374 CU_SHAPE_CIRCLE csc1( this->GetStartPoint(), this->GetWidth() / 2 );
1375 CU_SHAPE_CIRCLE csc2( this->GetEndPoint(), this->GetWidth() / 2 );
1376
1377 for( const PATH_CONNECTION& pc : this->Paths( csc1, aMaxWeight, aMaxSquaredWeight ) )
1378 result.push_back( pc );
1379
1380 for( const PATH_CONNECTION& pc : this->Paths( csc2, aMaxWeight, aMaxSquaredWeight ) )
1381 result.push_back( pc );
1382 }
1383
1384 return result;
1385}
1386
1387
1388std::vector<PATH_CONNECTION> CU_SHAPE_ARC::Paths( const BE_SHAPE_ARC& aS2, double aMaxWeight,
1389 double aMaxSquaredWeight ) const
1390{
1391 std::vector<PATH_CONNECTION> result;
1392 VECTOR2I beArcPos = aS2.GetPos();
1393 int beArcRadius = aS2.GetRadius();
1394 EDA_ANGLE beArcStartAngle = aS2.GetStartAngle();
1395 EDA_ANGLE beArcEndAngle = aS2.GetEndAngle();
1396
1397 BE_SHAPE_CIRCLE bsc( aS2.GetPos(), aS2.GetRadius() );
1398
1399 for( const PATH_CONNECTION& pc : this->Paths( bsc, aMaxWeight, aMaxSquaredWeight ) )
1400 {
1401 EDA_ANGLE testAngle = aS2.AngleBetweenStartAndEnd( pc.a2 );
1402
1403 if( testAngle < aS2.GetEndAngle() )
1404 result.push_back( pc );
1405 }
1406
1407 if( result.size() < 2 )
1408 {
1409 BE_SHAPE_POINT bsp1( aS2.GetStartPoint() );
1410 BE_SHAPE_POINT bsp2( aS2.GetEndPoint() );
1411
1412 for( const PATH_CONNECTION& pc : this->Paths( bsp1, aMaxWeight, aMaxSquaredWeight ) )
1413 {
1414 if( !segmentIntersectsArc( pc.a1, pc.a2, beArcPos, beArcRadius, beArcStartAngle, beArcEndAngle ) )
1415 result.push_back( pc );
1416 }
1417
1418 for( const PATH_CONNECTION& pc : this->Paths( bsp2, aMaxWeight, aMaxSquaredWeight ) )
1419 {
1420 if( !segmentIntersectsArc( pc.a1, pc.a2, beArcPos, beArcRadius, beArcStartAngle, beArcEndAngle ) )
1421 result.push_back( pc );
1422 }
1423 }
1424
1425 return result;
1426}
1427
1428
1429std::vector<PATH_CONNECTION> CU_SHAPE_CIRCLE::Paths( const BE_SHAPE_POINT& aS2, double aMaxWeight,
1430 double aMaxSquaredWeight ) const
1431{
1432 std::vector<PATH_CONNECTION> result;
1433
1434 double R = this->GetRadius();
1435 VECTOR2I center = this->GetPos();
1436 VECTOR2I point = aS2.GetPos();
1437 double weight = ( center - point ).EuclideanNorm() - R;
1438
1439 if( weight > aMaxWeight )
1440 return result;
1441
1442 PATH_CONNECTION pc;
1443 pc.weight = std::max( weight, 0.0 );
1444 pc.a2 = point;
1445 pc.a1 = center + ( point - center ).Resize( R );
1446
1447 result.push_back( pc );
1448 return result;
1449}
1450
1451
1452std::vector<PATH_CONNECTION> CU_SHAPE_CIRCLE::Paths( const CU_SHAPE_CIRCLE& aS2, double aMaxWeight,
1453 double aMaxSquaredWeight ) const
1454{
1455 std::vector<PATH_CONNECTION> result;
1456
1457 double R1 = this->GetRadius();
1458 double R2 = aS2.GetRadius();
1459 VECTOR2I C1 = this->GetPos();
1460 VECTOR2I C2 = aS2.GetPos();
1461
1462 if( ( C1 - C2 ).SquaredEuclideanNorm() < ( R1 - R2 ) * ( R1 - R2 ) )
1463 {
1464 // One of the circles is inside the other
1465 return result;
1466 }
1467
1468 double weight = ( C1 - C2 ).EuclideanNorm() - R1 - R2;
1469
1470 if( weight > aMaxWeight || weight < 0 )
1471 return result;
1472
1473 PATH_CONNECTION pc;
1474 pc.weight = std::max( weight, 0.0 );
1475 pc.a1 = ( C2 - C1 ).Resize( R1 ) + C1;
1476 pc.a2 = ( C1 - C2 ).Resize( R2 ) + C2;
1477 result.push_back( pc );
1478 return result;
1479}
1480
1481
1482std::vector<PATH_CONNECTION> CU_SHAPE_SEGMENT::Paths( const CU_SHAPE_CIRCLE& aS2, double aMaxWeight,
1483 double aMaxSquaredWeight ) const
1484{
1485 std::vector<PATH_CONNECTION> result;
1486
1487 VECTOR2I s_start = this->GetStart();
1488 VECTOR2I s_end = this->GetEnd();
1489 double halfWidth = this->GetWidth() / 2;
1490
1491 EDA_ANGLE trackAngle( s_end - s_start );
1492 VECTOR2I pointPos = aS2.GetPos();
1493
1494 double length = ( s_start - s_end ).EuclideanNorm();
1495 double projectedPos = cos( trackAngle.AsRadians() ) * ( pointPos.x - s_start.x )
1496 + sin( trackAngle.AsRadians() ) * ( pointPos.y - s_start.y );
1497
1498 if( ( projectedPos <= 0 ) || ( s_start == s_end ) )
1499 {
1500 CU_SHAPE_CIRCLE csc( s_start, halfWidth );
1501 return csc.Paths( aS2, aMaxWeight, aMaxSquaredWeight );
1502 }
1503
1504 if( projectedPos >= length )
1505 {
1506 CU_SHAPE_CIRCLE csc( s_end, halfWidth );
1507 return csc.Paths( aS2, aMaxWeight, aMaxSquaredWeight );
1508 }
1509
1510 double radius = aS2.GetRadius();
1511 double trackSide = ( s_end - s_start ).Cross( pointPos - s_start ) > 0 ? 1 : -1;
1512
1513 PATH_CONNECTION pc;
1514 pc.a1 = s_start + ( s_end - s_start ).Resize( projectedPos )
1515 + ( s_end - s_start ).Perpendicular().Resize( halfWidth ) * trackSide;
1516 pc.a2 = ( pc.a1 - pointPos ).Resize( radius ) + pointPos;
1517 pc.weight = ( pc.a2 - pc.a1 ).SquaredEuclideanNorm();
1518
1519 if( pc.weight <= aMaxSquaredWeight )
1520 {
1521 pc.weight = sqrt( pc.weight );
1522 result.push_back( pc );
1523 }
1524
1525 return result;
1526}
1527
1528
1529std::vector<PATH_CONNECTION> CU_SHAPE_CIRCLE::Paths( const CU_SHAPE_ARC& aS2, double aMaxWeight,
1530 double aMaxSquaredWeight ) const
1531{
1532 std::vector<PATH_CONNECTION> result;
1533
1534 VECTOR2I circlePos = this->GetPos();
1535 VECTOR2I arcPos = aS2.GetPos();
1536
1537 double circleRadius = this->GetRadius();
1538 double arcRadius = aS2.GetRadius();
1539
1540 VECTOR2I startPoint = aS2.GetStartPoint();
1541 VECTOR2I endPoint = aS2.GetEndPoint();
1542
1543 CU_SHAPE_CIRCLE csc( arcPos, arcRadius + aS2.GetWidth() / 2 );
1544
1545 if( ( circlePos - arcPos ).EuclideanNorm() > arcRadius + circleRadius )
1546 {
1547 const std::vector<PATH_CONNECTION>& pcs = this->Paths( csc, aMaxWeight, aMaxSquaredWeight );
1548
1549 if( pcs.size() == 1 )
1550 {
1551 EDA_ANGLE testAngle = aS2.AngleBetweenStartAndEnd( pcs[0].a2 );
1552
1553 if( testAngle < aS2.GetEndAngle() )
1554 {
1555 result.push_back( pcs[0] );
1556 return result;
1557 }
1558 }
1559 }
1560
1561 CU_SHAPE_CIRCLE csc1( startPoint, aS2.GetWidth() / 2 );
1562 CU_SHAPE_CIRCLE csc2( endPoint, aS2.GetWidth() / 2 );
1563
1564 PATH_CONNECTION* bestPath = nullptr;
1565
1566
1567 std::vector<PATH_CONNECTION> pcs1 = this->Paths( csc1, aMaxWeight, aMaxSquaredWeight );
1568 std::vector<PATH_CONNECTION> pcs2 = this->Paths( csc2, aMaxWeight, aMaxSquaredWeight );
1569
1570 for( PATH_CONNECTION& pc : pcs1 )
1571 {
1572 if( !bestPath || ( ( bestPath->weight > pc.weight ) && ( pc.weight > 0 ) ) )
1573 bestPath = &pc;
1574 }
1575
1576 for( PATH_CONNECTION& pc : pcs2 )
1577 {
1578 if( !bestPath || ( ( bestPath->weight > pc.weight ) && ( pc.weight > 0 ) ) )
1579 bestPath = &pc;
1580 }
1581
1582 // If the circle center is insde the arc ring
1583
1584 PATH_CONNECTION pc3;
1585
1586 if( ( circlePos - arcPos ).SquaredEuclideanNorm() < arcRadius * arcRadius )
1587 {
1588 if( circlePos != arcPos ) // The best path is already found otherwise
1589 {
1590 EDA_ANGLE testAngle = aS2.AngleBetweenStartAndEnd( circlePos );
1591
1592 if( testAngle < aS2.GetEndAngle() )
1593 {
1594 pc3.weight = std::max( arcRadius - ( circlePos - arcPos ).EuclideanNorm() - circleRadius, 0.0 );
1595 pc3.a1 = circlePos + ( circlePos - arcPos ).Resize( circleRadius );
1596 pc3.a2 = arcPos + ( circlePos - arcPos ).Resize( arcRadius - aS2.GetWidth() / 2 );
1597
1598 if( !bestPath || ( ( bestPath->weight > pc3.weight ) && ( pc3.weight > 0 ) ) )
1599 bestPath = &pc3;
1600 }
1601 }
1602 }
1603
1604 if( bestPath && bestPath->weight > 0 )
1605 {
1606 result.push_back( *bestPath );
1607 }
1608
1609 return result;
1610}
1611
1612
1613std::vector<PATH_CONNECTION> CU_SHAPE_SEGMENT::Paths( const CU_SHAPE_ARC& aS2, double aMaxWeight,
1614 double aMaxSquaredWeight ) const
1615{
1616 std::vector<PATH_CONNECTION> result;
1617
1618 VECTOR2I s_start = this->GetStart();
1619 VECTOR2I s_end = this->GetEnd();
1620 double halfWidth1 = this->GetWidth() / 2;
1621
1622 VECTOR2I arcPos = aS2.GetPos();
1623 double arcRadius = aS2.GetRadius();
1624 double halfWidth2 = aS2.GetWidth() / 2;
1625
1626
1627 CU_SHAPE_CIRCLE csc( arcPos, arcRadius + halfWidth2 );
1628
1629 std::vector<PATH_CONNECTION> pcs;
1630 pcs = this->Paths( csc, aMaxWeight, aMaxSquaredWeight );
1631
1632 if( pcs.size() < 1 )
1633 return result;
1634
1635 VECTOR2I circlePoint;
1636 EDA_ANGLE testAngle;
1637
1638 if( pcs.size() > 0 )
1639 {
1640 circlePoint = pcs[0].a1;
1641 testAngle = ( aS2.AngleBetweenStartAndEnd( pcs[0].a1 ) );
1642 }
1643
1644 if( testAngle < aS2.GetEndAngle() && pcs.size() > 0 )
1645 {
1646 result.push_back( pcs[0] );
1647 return result;
1648 }
1649
1650 CU_SHAPE_CIRCLE csc1( aS2.GetStartPoint(), halfWidth2 );
1651 CU_SHAPE_CIRCLE csc2( aS2.GetEndPoint(), halfWidth2 );
1652 std::optional<PATH_CONNECTION> bestPath;
1653
1654 for( PATH_CONNECTION& pc : this->Paths( csc1, aMaxWeight, aMaxSquaredWeight ) )
1655 {
1656 if( !bestPath || ( bestPath->weight > pc.weight ) )
1657 bestPath = pc;
1658 }
1659
1660 for( PATH_CONNECTION& pc : this->Paths( csc2, aMaxWeight, aMaxSquaredWeight ) )
1661 {
1662 if( !bestPath || ( bestPath->weight > pc.weight ) )
1663 bestPath = pc;
1664 }
1665
1666 CU_SHAPE_CIRCLE csc3( s_start, halfWidth1 );
1667 CU_SHAPE_CIRCLE csc4( s_end, halfWidth1 );
1668
1669 for( PATH_CONNECTION& pc : csc3.Paths( aS2, aMaxWeight, aMaxSquaredWeight ) )
1670 {
1671 if( !bestPath || ( bestPath->weight > pc.weight ) )
1672 bestPath = pc;
1673 }
1674
1675
1676 for( PATH_CONNECTION& pc : csc4.Paths( aS2, aMaxWeight, aMaxSquaredWeight ) )
1677 {
1678 if( !bestPath || ( bestPath->weight > pc.weight ) )
1679 bestPath = pc;
1680 }
1681
1682 if( bestPath )
1683 result.push_back( *bestPath );
1684
1685 return result;
1686}
1687
1688// Function to compute the projection of point P onto the line segment AB
1690{
1691 if( A == B )
1692 return A;
1693 if( A == P )
1694 return A;
1695
1696 VECTOR2I AB = B - A;
1697 VECTOR2I AP = P - A;
1698
1699 double t = float( AB.Dot( AP ) ) / float( AB.SquaredEuclideanNorm() );
1700
1701 // Clamp t to the range [0, 1] to restrict the projection to the segment
1702 t = std::max( 0.0, std::min( 1.0, t ) );
1703
1704 return A + ( AB * t );
1705}
1706
1707
1708std::vector<PATH_CONNECTION> CU_SHAPE_SEGMENT::Paths( const CU_SHAPE_SEGMENT& aS2,
1709 double aMaxWeight,
1710 double aMaxSquaredWeight ) const
1711{
1712 std::vector<PATH_CONNECTION> result;
1713
1714 VECTOR2I A( this->GetStart() );
1715 VECTOR2I B( this->GetEnd() );
1716 double halfWidth1 = this->GetWidth() / 2;
1717
1718
1719 VECTOR2I C( aS2.GetStart() );
1720 VECTOR2I D( aS2.GetEnd() );
1721 double halfWidth2 = aS2.GetWidth() / 2;
1722
1723 VECTOR2I P1 = closestPointOnSegment( A, B, C );
1724 VECTOR2I P2 = closestPointOnSegment( A, B, D );
1725 VECTOR2I P3 = closestPointOnSegment( C, D, A );
1727
1728 // Calculate all possible squared distances between the segments
1729 double dist1 = ( P1 - C ).SquaredEuclideanNorm();
1730 double dist2 = ( P2 - D ).SquaredEuclideanNorm();
1731 double dist3 = ( P3 - A ).SquaredEuclideanNorm();
1732 double dist4 = ( P4 - B ).SquaredEuclideanNorm();
1733
1734 // Find the minimum squared distance and update closest points
1735 double min_dist = dist1;
1736 VECTOR2I closest1 = P1;
1737 VECTOR2I closest2 = C;
1738
1739 if( dist2 < min_dist )
1740 {
1741 min_dist = dist2;
1742 closest1 = P2;
1743 closest2 = D;
1744 }
1745
1746 if( dist3 < min_dist )
1747 {
1748 min_dist = dist3;
1749 closest1 = A;
1750 closest2 = P3;
1751 }
1752
1753 if( dist4 < min_dist )
1754 {
1755 min_dist = dist4;
1756 closest1 = B;
1757 closest2 = P4;
1758 }
1759
1760
1761 PATH_CONNECTION pc;
1762 pc.a1 = closest1 + ( closest2 - closest1 ).Resize( halfWidth1 );
1763 pc.a2 = closest2 + ( closest1 - closest2 ).Resize( halfWidth2 );
1764 pc.weight = std::max( sqrt( min_dist ) - halfWidth1 - halfWidth2, 0.0 );
1765
1766 if( pc.weight <= aMaxWeight )
1767 result.push_back( pc );
1768
1769 return result;
1770}
1771
1772
1773std::vector<PATH_CONNECTION> CU_SHAPE_CIRCLE::Paths( const BE_SHAPE_CIRCLE& aS2, double aMaxWeight,
1774 double aMaxSquaredWeight ) const
1775{
1776 std::vector<PATH_CONNECTION> result;
1777
1778 double R1 = this->GetRadius();
1779 double R2 = aS2.GetRadius();
1780 VECTOR2I center1 = this->GetPos();
1781 VECTOR2I center2 = aS2.GetPos();
1782 double dist = ( center1 - center2 ).EuclideanNorm();
1783
1784 // Prune on the tangent sqrt(dist^2 - R2^2) - R1, which is much shorter than the centre
1785 // distance beside a large hole
1786 double reach = aMaxWeight + R1;
1787
1788 if( dist == 0 || dist * dist > reach * reach + R2 * R2 )
1789 return result;
1790
1791 double circleAngle = EDA_ANGLE( center2 - center1 ).AsRadians();
1792
1793 if( dist <= R2 )
1794 {
1795 // Copper circle center is inside the board-edge circle so external tangent lines
1796 // don't exist. The nearest gap is the radial distance between circle boundaries.
1797 double weight = std::max( R2 - dist - R1, 0.0 );
1798
1799 if( weight > aMaxWeight )
1800 return result;
1801
1802 double radialAngle = circleAngle + M_PI;
1803 double cx = cos( radialAngle );
1804 double cy = sin( radialAngle );
1805 VECTOR2I pEnd = center2 + VECTOR2I( R2 * cx, R2 * cy );
1806 VECTOR2I pStart = center1 + VECTOR2I( R1 * cx, R1 * cy );
1807
1808 PATH_CONNECTION pc;
1809 pc.a1 = pStart;
1810 pc.a2 = pEnd;
1811 pc.weight = weight;
1812
1813 // Callers expect two entries (one per tangent side) and select by index.
1814 result.push_back( pc );
1815 result.push_back( pc );
1816
1817 return result;
1818 }
1819
1820 double weight = sqrt( dist * dist - R2 * R2 ) - R1;
1821 double theta = asin( R2 / dist );
1822 double psi = acos( R2 / dist );
1823
1824 if( weight > aMaxWeight )
1825 return result;
1826
1827 PATH_CONNECTION pc;
1828 pc.weight = std::max( weight, 0.0 );
1829
1830 VECTOR2I pStart;
1831 VECTOR2I pEnd;
1832
1833 pStart = VECTOR2I( R1 * cos( theta + circleAngle ), R1 * sin( theta + circleAngle ) );
1834 pStart += center1;
1835 pEnd = VECTOR2I( -R2 * cos( psi - circleAngle ), R2 * sin( psi - circleAngle ) );
1836 pEnd += center2;
1837
1838 pc.a1 = pStart;
1839 pc.a2 = pEnd;
1840 result.push_back( pc );
1841
1842 pStart = VECTOR2I( R1 * cos( -theta + circleAngle ), R1 * sin( -theta + circleAngle ) );
1843 pStart += center1;
1844 pEnd = VECTOR2I( -R2 * cos( -psi - circleAngle ), R2 * sin( -psi - circleAngle ) );
1845 pEnd += center2;
1846
1847 pc.a1 = pStart;
1848 pc.a2 = pEnd;
1849
1850 result.push_back( pc );
1851 return result;
1852}
1853
1854
1855std::vector<PATH_CONNECTION> CU_SHAPE_ARC::Paths( const BE_SHAPE_POINT& aS2, double aMaxWeight,
1856 double aMaxSquaredWeight ) const
1857{
1858 std::vector<PATH_CONNECTION> result;
1859 VECTOR2I point = aS2.GetPos();
1860 VECTOR2I arcCenter = this->GetPos();
1861
1862 double radius = this->GetRadius();
1863 double width = this->GetWidth();
1864
1865 EDA_ANGLE angle( point - arcCenter );
1866
1867 while( angle < this->GetStartAngle() )
1868 angle += ANGLE_360;
1869 while( angle > this->GetEndAngle() + ANGLE_360 )
1870 angle -= ANGLE_360;
1871
1872 if( angle < this->GetEndAngle() )
1873 {
1874 if( ( point - arcCenter ).SquaredEuclideanNorm() > radius * radius )
1875 {
1876 CU_SHAPE_CIRCLE circle( arcCenter, radius + width / 2 );
1877 return circle.Paths( aS2, aMaxWeight, aMaxSquaredWeight );
1878 }
1879 else
1880 {
1881 PATH_CONNECTION pc;
1882 pc.weight = std::max( ( radius - width / 2 ) - ( point - arcCenter ).EuclideanNorm(), 0.0 );
1883 pc.a1 = ( point - arcCenter ).Resize( radius - width / 2 ) + arcCenter;
1884 pc.a2 = point;
1885
1886 if( pc.weight > 0 && pc.weight < aMaxWeight )
1887 result.push_back( pc );
1888
1889 return result;
1890 }
1891 }
1892 else
1893 {
1894 VECTOR2I nearestPoint;
1895
1896 if( ( point - this->GetStartPoint() ).SquaredEuclideanNorm()
1897 > ( point - this->GetEndPoint() ).SquaredEuclideanNorm() )
1898 {
1899 nearestPoint = this->GetEndPoint();
1900 }
1901 else
1902 {
1903 nearestPoint = this->GetStartPoint();
1904 }
1905
1906 CU_SHAPE_CIRCLE circle( nearestPoint, width / 2 );
1907 return circle.Paths( aS2, aMaxWeight, aMaxSquaredWeight );
1908 }
1909}
1910
1911
1912std::vector<PATH_CONNECTION> CU_SHAPE_ARC::Paths( const CU_SHAPE_ARC& aS2, double aMaxWeight,
1913 double aMaxSquaredWeight ) const
1914{
1915 std::vector<PATH_CONNECTION> result;
1916
1917 double R1 = this->GetRadius();
1918 double R2 = aS2.GetRadius();
1919
1920 VECTOR2I C1 = this->GetPos();
1921 VECTOR2I C2 = aS2.GetPos();
1922
1923 PATH_CONNECTION bestPath;
1924 bestPath.weight = std::numeric_limits<double>::infinity();
1925 CU_SHAPE_CIRCLE csc1( C1, R1 + this->GetWidth() / 2 );
1926 CU_SHAPE_CIRCLE csc2( C2, R2 + aS2.GetWidth() / 2 );
1927
1928 CU_SHAPE_CIRCLE csc3( this->GetStartPoint(), this->GetWidth() / 2 );
1929 CU_SHAPE_CIRCLE csc4( this->GetEndPoint(), this->GetWidth() / 2 );
1930 CU_SHAPE_CIRCLE csc5( aS2.GetStartPoint(), aS2.GetWidth() / 2 );
1931 CU_SHAPE_CIRCLE csc6( aS2.GetEndPoint(), aS2.GetWidth() / 2 );
1932
1933 for( const std::vector<PATH_CONNECTION>& pcs : { csc1.Paths( csc2, aMaxWeight, aMaxSquaredWeight ),
1934 this->Paths( csc2, aMaxWeight, aMaxSquaredWeight ),
1935 csc1.Paths( aS2, aMaxWeight, aMaxSquaredWeight ) } )
1936 {
1937 for( const PATH_CONNECTION& pc : pcs )
1938 {
1939 EDA_ANGLE testAngle1 = this->AngleBetweenStartAndEnd( pc.a1 );
1940 EDA_ANGLE testAngle2 = aS2.AngleBetweenStartAndEnd( pc.a2 );
1941
1942 if( testAngle1 < this->GetEndAngle() && testAngle2 < aS2.GetEndAngle() && bestPath.weight > pc.weight )
1943 bestPath = pc;
1944 }
1945 }
1946
1947 for( const std::vector<PATH_CONNECTION>& pcs : { this->Paths( csc5, aMaxWeight, aMaxSquaredWeight ),
1948 this->Paths( csc6, aMaxWeight, aMaxSquaredWeight ),
1949 csc3.Paths( aS2, aMaxWeight, aMaxSquaredWeight ),
1950 csc4.Paths( aS2, aMaxWeight, aMaxSquaredWeight ) } )
1951 {
1952 for( const PATH_CONNECTION& pc : pcs )
1953 {
1954 if( bestPath.weight > pc.weight )
1955 bestPath = pc;
1956 }
1957 }
1958
1959 if( bestPath.weight != std::numeric_limits<double>::infinity() )
1960 result.push_back( bestPath );
1961
1962 return result;
1963}
1964
1965
1966bool segmentIntersectsCircle( const VECTOR2I& p1, const VECTOR2I& p2, const VECTOR2I& center, double radius,
1967 std::vector<VECTOR2I>* aIntersectPoints )
1968{
1969 SEG segment( p1, p2 );
1971
1972 std::vector<VECTOR2I> intersectionPoints;
1973 INTERSECTABLE_GEOM geom1 = segment;
1974 INTERSECTABLE_GEOM geom2 = circle;
1975
1976 INTERSECTION_VISITOR visitor( geom2, intersectionPoints );
1977 std::visit( visitor, geom1 );
1978
1979 // A path is allowed to end on the circle, so an intersection at either endpoint is a
1980 // touch, not a crossing. Only interior crossings count.
1981 const VECTOR2I::extended_type toleranceSq = 50 * 50;
1982
1983 auto coincident = [&]( const VECTOR2I& a, const VECTOR2I& b )
1984 {
1985 return ( a - b ).SquaredEuclideanNorm() <= toleranceSq;
1986 };
1987
1988 std::vector<VECTOR2I> filtered;
1989
1990 for( const VECTOR2I& ip : intersectionPoints )
1991 {
1992 if( !coincident( ip, p1 ) && !coincident( ip, p2 ) )
1993 filtered.push_back( ip );
1994 }
1995
1996 if( aIntersectPoints )
1997 {
1998 for( VECTOR2I& point : filtered )
1999 aIntersectPoints->push_back( point );
2000 }
2001
2002 return filtered.size() > 0;
2003}
2004
2005bool SegmentIntersectsBoard( const VECTOR2I& aP1, const VECTOR2I& aP2,
2006 const std::vector<BOARD_ITEM*>& aBe,
2007 const std::vector<const BOARD_ITEM*>& aDontTestAgainst,
2008 int aMinGrooveWidth )
2009{
2010 std::vector<VECTOR2I> intersectionPoints;
2011 bool TestGrooveWidth = aMinGrooveWidth > 0;
2012
2013 for( BOARD_ITEM* be : aBe )
2014 {
2015 if( count( aDontTestAgainst.begin(), aDontTestAgainst.end(), be ) > 0 )
2016 continue;
2017
2018 PCB_SHAPE* d = static_cast<PCB_SHAPE*>( be );
2019 if( !d )
2020 continue;
2021
2022 switch( d->GetShape() )
2023 {
2024 case SHAPE_T::SEGMENT:
2025 {
2026 bool intersects = segments_intersect( aP1, aP2, d->GetStart(), d->GetEnd(), intersectionPoints );
2027
2028 if( intersects && !TestGrooveWidth )
2029 return false;
2030
2031 break;
2032 }
2033
2034 case SHAPE_T::RECTANGLE:
2035 {
2036 int r = d->GetCornerRadius();
2037
2038 if( r > 0 )
2039 {
2040 // Rounded rectangle: four shortened straight sides + four quarter-circle arcs.
2041 int x1 = std::min( d->GetStart().x, d->GetEnd().x );
2042 int y1 = std::min( d->GetStart().y, d->GetEnd().y );
2043 int x2 = std::max( d->GetStart().x, d->GetEnd().x );
2044 int y2 = std::max( d->GetStart().y, d->GetEnd().y );
2045
2046 // Straight sides (between arc endpoints). Skip zero-length
2047 // sides that occur when one dimension equals 2*r (stadium).
2048 int w = x2 - x1;
2049 int h = y2 - y1;
2050 bool intersects = false;
2051
2052 if( w > 2 * r )
2053 {
2054 intersects |= segments_intersect( aP1, aP2, { x1 + r, y1 }, { x2 - r, y1 },
2055 intersectionPoints );
2056 intersects |= segments_intersect( aP1, aP2, { x2 - r, y2 }, { x1 + r, y2 },
2057 intersectionPoints );
2058 }
2059
2060 if( h > 2 * r )
2061 {
2062 intersects |= segments_intersect( aP1, aP2, { x2, y1 + r }, { x2, y2 - r },
2063 intersectionPoints );
2064 intersects |= segments_intersect( aP1, aP2, { x1, y2 - r }, { x1, y1 + r },
2065 intersectionPoints );
2066 }
2067
2068 if( intersects && !TestGrooveWidth )
2069 return false;
2070
2071 // Corner arcs, matching the decomposition in TransformEdgeToCreepShapes.
2072 // Stadium shapes get semicircles instead of four quarter-arcs to
2073 // avoid duplicate centers that cause division by zero in Paths().
2074 struct CornerArcRange
2075 {
2077 EDA_ANGLE startAngle;
2078 EDA_ANGLE endAngle;
2079 };
2080
2081 std::vector<CornerArcRange> arcs;
2082
2083 if( h == 2 * r )
2084 {
2085 // Horizontal stadium: left and right semicircles. Each cap spans
2086 // the outer half of its circle so the modeled boundary matches the
2087 // decomposition in TransformEdgeToCreepShapes.
2088 arcs.push_back( { { x1 + r, y1 + r },
2089 EDA_ANGLE( 90.0, DEGREES_T ),
2090 EDA_ANGLE( 270.0, DEGREES_T ) } );
2091 arcs.push_back( { { x2 - r, y1 + r },
2092 EDA_ANGLE( -90.0, DEGREES_T ),
2093 EDA_ANGLE( 90.0, DEGREES_T ) } );
2094 }
2095 else if( w == 2 * r )
2096 {
2097 // Vertical stadium: top and bottom semicircles
2098 arcs.push_back( { { x1 + r, y1 + r },
2099 EDA_ANGLE( -180.0, DEGREES_T ),
2100 EDA_ANGLE( 0.0, DEGREES_T ) } );
2101 arcs.push_back( { { x1 + r, y2 - r },
2102 EDA_ANGLE( 0.0, DEGREES_T ),
2103 EDA_ANGLE( 180.0, DEGREES_T ) } );
2104 }
2105 else
2106 {
2107 arcs = {
2108 { { x1 + r, y1 + r }, EDA_ANGLE( -180.0, DEGREES_T ),
2109 EDA_ANGLE( -90.0, DEGREES_T ) },
2110 { { x2 - r, y1 + r }, EDA_ANGLE( -90.0, DEGREES_T ),
2111 EDA_ANGLE( 0.0, DEGREES_T ) },
2112 { { x2 - r, y2 - r }, EDA_ANGLE( 0.0, DEGREES_T ),
2113 EDA_ANGLE( 90.0, DEGREES_T ) },
2114 { { x1 + r, y2 - r }, EDA_ANGLE( 90.0, DEGREES_T ),
2115 EDA_ANGLE( 180.0, DEGREES_T ) },
2116 };
2117 }
2118
2119 for( const CornerArcRange& ca : arcs )
2120 {
2121 bool arcIntersects = segmentIntersectsArc( aP1, aP2, ca.center, r,
2122 ca.startAngle, ca.endAngle,
2123 &intersectionPoints );
2124
2125 if( arcIntersects && !TestGrooveWidth )
2126 return false;
2127 }
2128 }
2129 else
2130 {
2131 VECTOR2I c1 = d->GetStart();
2132 VECTOR2I c2( d->GetStart().x, d->GetEnd().y );
2133 VECTOR2I c3 = d->GetEnd();
2134 VECTOR2I c4( d->GetEnd().x, d->GetStart().y );
2135
2136 bool intersects = false;
2137 intersects |= segments_intersect( aP1, aP2, c1, c2, intersectionPoints );
2138 intersects |= segments_intersect( aP1, aP2, c2, c3, intersectionPoints );
2139 intersects |= segments_intersect( aP1, aP2, c3, c4, intersectionPoints );
2140 intersects |= segments_intersect( aP1, aP2, c4, c1, intersectionPoints );
2141
2142 if( intersects && !TestGrooveWidth )
2143 return false;
2144 }
2145
2146 break;
2147 }
2148
2149 case SHAPE_T::POLY:
2150 {
2151 std::vector<VECTOR2I> points = d->GetPolyPoints();
2152
2153 if( points.size() < 2 )
2154 break;
2155
2156 VECTOR2I prevPoint = points.back();
2157
2158 bool intersects = false;
2159
2160 for( const VECTOR2I& p : points )
2161 {
2162 intersects |= segments_intersect( aP1, aP2, prevPoint, p, intersectionPoints );
2163 prevPoint = p;
2164 }
2165
2166 if( intersects && !TestGrooveWidth )
2167 return false;
2168
2169 break;
2170 }
2171
2172 case SHAPE_T::CIRCLE:
2173 {
2174 VECTOR2I center = d->GetCenter();
2175 double radius = d->GetRadius();
2176
2177 bool intersects = segmentIntersectsCircle( aP1, aP2, center, radius, &intersectionPoints );
2178
2179 if( intersects && !TestGrooveWidth )
2180 return false;
2181
2182 break;
2183 }
2184
2185 case SHAPE_T::ARC:
2186 {
2187 VECTOR2I center = d->GetCenter();
2188 double radius = d->GetRadius();
2189
2190 EDA_ANGLE A, B;
2191 d->CalcArcAngles( A, B );
2192
2193 bool intersects = segmentIntersectsArc( aP1, aP2, center, radius, A, B, &intersectionPoints );
2194
2195 if( intersects && !TestGrooveWidth )
2196 return false;
2197
2198 break;
2199 }
2200
2201 default:
2202 break;
2203 }
2204 }
2205
2206 if( intersectionPoints.size() <= 0 )
2207 return true;
2208
2209 if( intersectionPoints.size() % 2 != 0 )
2210 return false; // Should not happen if the start and end are both on the board
2211
2212 int minx = intersectionPoints[0].x;
2213 int maxx = intersectionPoints[0].x;
2214 int miny = intersectionPoints[0].y;
2215 int maxy = intersectionPoints[0].y;
2216
2217 for( const VECTOR2I& v : intersectionPoints )
2218 {
2219 minx = std::min( v.x, minx );
2220 maxx = std::max( v.x, maxx );
2221 miny = std::min( v.y, miny );
2222 maxy = std::max( v.y, maxy );
2223 }
2224
2225 if( abs( maxx - minx ) > abs( maxy - miny ) )
2226 {
2227 std::sort( intersectionPoints.begin(), intersectionPoints.end(),
2228 []( const VECTOR2I& a, const VECTOR2I& b )
2229 {
2230 return a.x > b.x;
2231 } );
2232 }
2233 else
2234 {
2235 std::sort( intersectionPoints.begin(), intersectionPoints.end(),
2236 []( const VECTOR2I& a, const VECTOR2I& b )
2237 {
2238 return a.y > b.y;
2239 } );
2240 }
2241
2242 int GVSquared = aMinGrooveWidth * aMinGrooveWidth;
2243
2244 for( size_t i = 0; i < intersectionPoints.size(); i += 2 )
2245 {
2246 if( intersectionPoints[i].SquaredDistance( intersectionPoints[i + 1] ) > GVSquared )
2247 return false;
2248 }
2249
2250 return true;
2251}
2252
2253
2254std::vector<PATH_CONNECTION> GetPaths( CREEP_SHAPE* aS1, CREEP_SHAPE* aS2, double aMaxWeight )
2255{
2256 double maxWeight = aMaxWeight;
2257 double maxWeightSquared = maxWeight * maxWeight;
2258 std::vector<PATH_CONNECTION> result;
2259
2260 CU_SHAPE_SEGMENT* cusegment1 = dynamic_cast<CU_SHAPE_SEGMENT*>( aS1 );
2261 CU_SHAPE_SEGMENT* cusegment2 = dynamic_cast<CU_SHAPE_SEGMENT*>( aS2 );
2262 CU_SHAPE_CIRCLE* cucircle1 = dynamic_cast<CU_SHAPE_CIRCLE*>( aS1 );
2263 CU_SHAPE_CIRCLE* cucircle2 = dynamic_cast<CU_SHAPE_CIRCLE*>( aS2 );
2264 CU_SHAPE_ARC* cuarc1 = dynamic_cast<CU_SHAPE_ARC*>( aS1 );
2265 CU_SHAPE_ARC* cuarc2 = dynamic_cast<CU_SHAPE_ARC*>( aS2 );
2266
2267
2268 BE_SHAPE_POINT* bepoint1 = dynamic_cast<BE_SHAPE_POINT*>( aS1 );
2269 BE_SHAPE_POINT* bepoint2 = dynamic_cast<BE_SHAPE_POINT*>( aS2 );
2270 BE_SHAPE_CIRCLE* becircle1 = dynamic_cast<BE_SHAPE_CIRCLE*>( aS1 );
2271 BE_SHAPE_CIRCLE* becircle2 = dynamic_cast<BE_SHAPE_CIRCLE*>( aS2 );
2272 BE_SHAPE_ARC* bearc1 = dynamic_cast<BE_SHAPE_ARC*>( aS1 );
2273 BE_SHAPE_ARC* bearc2 = dynamic_cast<BE_SHAPE_ARC*>( aS2 );
2274
2275 // Cu to Cu
2276
2277 if( cuarc1 && cuarc2 )
2278 return cuarc1->Paths( *cuarc2, maxWeight, maxWeightSquared );
2279 if( cuarc1 && cucircle2 )
2280 return cuarc1->Paths( *cucircle2, maxWeight, maxWeightSquared );
2281 if( cuarc1 && cusegment2 )
2282 return cuarc1->Paths( *cusegment2, maxWeight, maxWeightSquared );
2283 if( cucircle1 && cuarc2 )
2284 return cucircle1->Paths( *cuarc2, maxWeight, maxWeightSquared );
2285 if( cucircle1 && cucircle2 )
2286 return cucircle1->Paths( *cucircle2, maxWeight, maxWeightSquared );
2287 if( cucircle1 && cusegment2 )
2288 return cucircle1->Paths( *cusegment2, maxWeight, maxWeightSquared );
2289 if( cusegment1 && cuarc2 )
2290 return cusegment1->Paths( *cuarc2, maxWeight, maxWeightSquared );
2291 if( cusegment1 && cucircle2 )
2292 return cusegment1->Paths( *cucircle2, maxWeight, maxWeightSquared );
2293 if( cusegment1 && cusegment2 )
2294 return cusegment1->Paths( *cusegment2, maxWeight, maxWeightSquared );
2295
2296
2297 // Cu to Be
2298
2299 if( cuarc1 && bearc2 )
2300 return cuarc1->Paths( *bearc2, maxWeight, maxWeightSquared );
2301 if( cuarc1 && becircle2 )
2302 return cuarc1->Paths( *becircle2, maxWeight, maxWeightSquared );
2303 if( cuarc1 && bepoint2 )
2304 return cuarc1->Paths( *bepoint2, maxWeight, maxWeightSquared );
2305 if( cucircle1 && bearc2 )
2306 return cucircle1->Paths( *bearc2, maxWeight, maxWeightSquared );
2307 if( cucircle1 && becircle2 )
2308 return cucircle1->Paths( *becircle2, maxWeight, maxWeightSquared );
2309 if( cucircle1 && bepoint2 )
2310 return cucircle1->Paths( *bepoint2, maxWeight, maxWeightSquared );
2311 if( cusegment1 && bearc2 )
2312 return cusegment1->Paths( *bearc2, maxWeight, maxWeightSquared );
2313 if( cusegment1 && becircle2 )
2314 return cusegment1->Paths( *becircle2, maxWeight, maxWeightSquared );
2315 if( cusegment1 && bepoint2 )
2316 return cusegment1->Paths( *bepoint2, maxWeight, maxWeightSquared );
2317
2318 // Reversed
2319
2320 if( cuarc2 && bearc1 )
2321 return bearc1->Paths( *cuarc2, maxWeight, maxWeightSquared );
2322 if( cuarc2 && becircle1 )
2323 return becircle1->Paths( *cuarc2, maxWeight, maxWeightSquared );
2324 if( cuarc2 && bepoint1 )
2325 return bepoint1->Paths( *cuarc2, maxWeight, maxWeightSquared );
2326 if( cucircle2 && bearc1 )
2327 return bearc1->Paths( *cucircle2, maxWeight, maxWeightSquared );
2328 if( cucircle2 && becircle1 )
2329 return becircle1->Paths( *cucircle2, maxWeight, maxWeightSquared );
2330 if( cucircle2 && bepoint1 )
2331 return bepoint1->Paths( *cucircle2, maxWeight, maxWeightSquared );
2332 if( cusegment2 && bearc1 )
2333 return bearc1->Paths( *cusegment2, maxWeight, maxWeightSquared );
2334 if( cusegment2 && becircle1 )
2335 return becircle1->Paths( *cusegment2, maxWeight, maxWeightSquared );
2336 if( cusegment2 && bepoint1 )
2337 return bepoint1->Paths( *cusegment2, maxWeight, maxWeightSquared );
2338
2339
2340 // Be to Be
2341
2342 if( bearc1 && bearc2 )
2343 return bearc1->Paths( *bearc2, maxWeight, maxWeightSquared );
2344 if( bearc1 && becircle2 )
2345 return bearc1->Paths( *becircle2, maxWeight, maxWeightSquared );
2346 if( bearc1 && bepoint2 )
2347 return bearc1->Paths( *bepoint2, maxWeight, maxWeightSquared );
2348 if( becircle1 && bearc2 )
2349 return becircle1->Paths( *bearc2, maxWeight, maxWeightSquared );
2350 if( becircle1 && becircle2 )
2351 return becircle1->Paths( *becircle2, maxWeight, maxWeightSquared );
2352 if( becircle1 && bepoint2 )
2353 return becircle1->Paths( *bepoint2, maxWeight, maxWeightSquared );
2354 if( bepoint1 && bearc2 )
2355 return bepoint1->Paths( *bearc2, maxWeight, maxWeightSquared );
2356 if( bepoint1 && becircle2 )
2357 return bepoint1->Paths( *becircle2, maxWeight, maxWeightSquared );
2358 if( bepoint1 && bepoint2 )
2359 return bepoint1->Paths( *bepoint2, maxWeight, maxWeightSquared );
2360
2361 return result;
2362}
2363
2364double CREEPAGE_GRAPH::Solve( std::shared_ptr<GRAPH_NODE>& aFrom, std::shared_ptr<GRAPH_NODE>& aTo,
2365 std::vector<std::shared_ptr<GRAPH_CONNECTION>>& aResult ) // Change to vector of pointers
2366{
2367 if( !aFrom || !aTo )
2368 return 0;
2369
2370 if( aFrom == aTo )
2371 return 0;
2372
2373 // Dijkstra's algorithm for shortest path
2374 std::unordered_map<GRAPH_NODE*, double> distances;
2375 std::unordered_map<GRAPH_NODE*, GRAPH_NODE*> previous;
2376
2377 // Each heap entry carries the tentative distance captured at push time. A comparator that read
2378 // the live distances map instead would let a decrease-key reinsertion silently corrupt the heap
2379 // ordering, so aTo could be popped on a non-shortest path and the early break would return it.
2380 using QUEUE_ITEM = std::pair<double, GRAPH_NODE*>;
2381
2382 auto cmp = []( const QUEUE_ITEM& aLeft, const QUEUE_ITEM& aRight )
2383 {
2384 if( aLeft.first == aRight.first )
2385 return aLeft.second > aRight.second; // Compare addresses to avoid ties.
2386 return aLeft.first > aRight.first;
2387 };
2388 std::priority_queue<QUEUE_ITEM, std::vector<QUEUE_ITEM>, decltype( cmp )> pq( cmp );
2389
2390 // Initialize distances to infinity for all nodes except the starting node
2391 for( const std::shared_ptr<GRAPH_NODE>& node : m_nodes )
2392 {
2393 if( node != nullptr )
2394 distances[node.get()] = std::numeric_limits<double>::infinity(); // Set to infinity
2395 }
2396
2397 distances[aFrom.get()] = 0.0;
2398 distances[aTo.get()] = std::numeric_limits<double>::infinity();
2399 pq.push( { 0.0, aFrom.get() } );
2400
2401 // Dijkstra's main loop
2402 while( !pq.empty() )
2403 {
2404 auto [dist, current] = pq.top();
2405 pq.pop();
2406
2407 // A stale entry left behind by a decrease-key reinsertion; its shorter copy was already
2408 // processed
2409 if( dist > distances[current] )
2410 continue;
2411
2412 if( current == aTo.get() )
2413 {
2414 break; // Shortest path found
2415 }
2416
2417 // Traverse neighbors
2418 for( const std::shared_ptr<GRAPH_CONNECTION>& connection : current->m_node_conns )
2419 {
2420 GRAPH_NODE* neighbor = ( connection->n1 ).get() == current ? ( connection->n2 ).get()
2421 : ( connection->n1 ).get();
2422
2423 if( !neighbor )
2424 continue;
2425
2426 // Ignore connections with negative weights as Dijkstra doesn't support them.
2427 if( connection->m_path.weight < 0.0 )
2428 {
2429 wxLogTrace( "CREEPAGE", "Negative weight connection found. Ignoring connection." );
2430 continue;
2431 }
2432
2433 double alt = distances[current] + connection->m_path.weight; // Calculate alternative path cost
2434
2435 if( alt < distances[neighbor] )
2436 {
2437 distances[neighbor] = alt;
2438 previous[neighbor] = current;
2439 pq.push( { alt, neighbor } );
2440 }
2441 }
2442 }
2443
2444 double pathWeight = distances[aTo.get()];
2445
2446 // If aTo is unreachable, return infinity
2447 if( pathWeight == std::numeric_limits<double>::infinity() )
2448 return std::numeric_limits<double>::infinity();
2449
2450 // Trace back the path from aTo to aFrom
2451 GRAPH_NODE* step = aTo.get();
2452
2453 while( step != aFrom.get() )
2454 {
2455 GRAPH_NODE* prevNode = previous[step];
2456
2457 for( const std::shared_ptr<GRAPH_CONNECTION>& node_conn : step->m_node_conns )
2458 {
2459 if( ( ( node_conn->n1 ).get() == prevNode && ( node_conn->n2 ).get() == step )
2460 || ( ( node_conn->n1 ).get() == step && ( node_conn->n2 ).get() == prevNode ) )
2461 {
2462 aResult.push_back( node_conn );
2463 break;
2464 }
2465 }
2466 step = prevNode;
2467 }
2468
2469 return pathWeight;
2470}
2471
2472void CREEPAGE_GRAPH::Addshape( const SHAPE& aShape, std::shared_ptr<GRAPH_NODE>& aConnectTo,
2473 BOARD_ITEM* aParent )
2474{
2475 std::unique_ptr<CREEP_SHAPE> newshape;
2476
2477 if( !aConnectTo )
2478 return;
2479
2480 switch( aShape.Type() )
2481 {
2482 case SH_SEGMENT:
2483 {
2484 const SHAPE_SEGMENT& segment = dynamic_cast<const SHAPE_SEGMENT&>( aShape );
2485 newshape = std::make_unique<CU_SHAPE_SEGMENT>( segment.GetSeg().A, segment.GetSeg().B,
2486 segment.GetWidth() );
2487 break;
2488 }
2489
2490 case SH_CIRCLE:
2491 {
2492 const SHAPE_CIRCLE& circle = dynamic_cast<const SHAPE_CIRCLE&>( aShape );
2493 newshape = std::make_unique<CU_SHAPE_CIRCLE>( circle.GetCenter(), circle.GetRadius() );
2494 break;
2495 }
2496
2497 case SH_ARC:
2498 {
2499 const SHAPE_ARC& arc = dynamic_cast<const SHAPE_ARC&>( aShape );
2500 EDA_ANGLE alpha, beta;
2501
2502 EDA_SHAPE edaArc( arc );
2503
2504 edaArc.CalcArcAngles( alpha, beta );
2505
2506 auto cuArc = std::make_unique<CU_SHAPE_ARC>( edaArc.getCenter(), edaArc.GetRadius(), alpha, beta,
2507 arc.GetP0(), arc.GetP1() );
2508 cuArc->SetWidth( arc.GetWidth() );
2509 newshape = std::move( cuArc );
2510 break;
2511 }
2512
2513 case SH_COMPOUND:
2514 {
2515 int nbShapes = (int) static_cast<const SHAPE_COMPOUND*>( &aShape )->Shapes().size();
2516
2517 for( const SHAPE* subshape : ( static_cast<const SHAPE_COMPOUND*>( &aShape )->Shapes() ) )
2518 {
2519 if( subshape )
2520 {
2521 // We don't want to add shape for the inner rectangle of rounded rectangles
2522 if( !( ( subshape->Type() == SH_RECT ) && ( nbShapes == 5 ) ) )
2523 Addshape( *subshape, aConnectTo, aParent );
2524 }
2525 }
2526 break;
2527 }
2528
2529 case SH_POLY_SET:
2530 {
2531 const SHAPE_POLY_SET& polySet = dynamic_cast<const SHAPE_POLY_SET&>( aShape );
2532
2533 for( auto it = polySet.CIterateSegmentsWithHoles(); it; it++ )
2534 {
2535 const SEG object = *it;
2536 SHAPE_SEGMENT segment( object.A, object.B );
2537 Addshape( segment, aConnectTo, aParent );
2538 }
2539 break;
2540 }
2541
2542 case SH_LINE_CHAIN:
2543 {
2544 const SHAPE_LINE_CHAIN& lineChain = dynamic_cast<const SHAPE_LINE_CHAIN&>( aShape );
2545
2546 VECTOR2I prevPoint = lineChain.CLastPoint();
2547
2548 for( const VECTOR2I& point : lineChain.CPoints() )
2549 {
2550 SHAPE_SEGMENT segment( point, prevPoint );
2551 prevPoint = point;
2552 Addshape( segment, aConnectTo, aParent );
2553 }
2554
2555 break;
2556 }
2557
2558 case SH_SIMPLE:
2559 {
2560 // SHAPE_SIMPLE is the arbitrary-polygon form used for rectangular, trapezoidal and
2561 // chamfered pads when they are not axis-aligned (orthogonal rotations collapse to
2562 // SH_RECT instead). Decompose its closed outline into segments so the copper edge
2563 // is added to the graph, otherwise the pad contributes no creepage anchor and the
2564 // path snaps to the pad hole instead of the copper (issue #24543).
2565 const SHAPE_SIMPLE& simple = dynamic_cast<const SHAPE_SIMPLE&>( aShape );
2566 const SHAPE_LINE_CHAIN& vertices = simple.Vertices();
2567
2568 if( vertices.PointCount() < 3 )
2569 break;
2570
2571 VECTOR2I prevPoint = vertices.CLastPoint();
2572
2573 for( const VECTOR2I& point : vertices.CPoints() )
2574 {
2575 if( point != prevPoint )
2576 Addshape( SHAPE_SEGMENT( prevPoint, point ), aConnectTo, aParent );
2577
2578 prevPoint = point;
2579 }
2580
2581 break;
2582 }
2583
2584 case SH_RECT:
2585 {
2586 const SHAPE_RECT& rect = dynamic_cast<const SHAPE_RECT&>( aShape );
2587
2588 VECTOR2I point0 = rect.GetPosition();
2589 VECTOR2I point1 = rect.GetPosition() + VECTOR2I( rect.GetSize().x, 0 );
2590 VECTOR2I point2 = rect.GetPosition() + rect.GetSize();
2591 VECTOR2I point3 = rect.GetPosition() + VECTOR2I( 0, rect.GetSize().y );
2592
2593 Addshape( SHAPE_SEGMENT( point0, point1 ), aConnectTo, aParent );
2594 Addshape( SHAPE_SEGMENT( point1, point2 ), aConnectTo, aParent );
2595 Addshape( SHAPE_SEGMENT( point2, point3 ), aConnectTo, aParent );
2596 Addshape( SHAPE_SEGMENT( point3, point0 ), aConnectTo, aParent );
2597 break;
2598 }
2599
2600 default:
2601 break;
2602 }
2603
2604 if( !newshape )
2605 return;
2606
2607 std::shared_ptr<GRAPH_NODE> gnShape = nullptr;
2608
2609 newshape->SetParent( aParent );
2610
2611 switch( aShape.Type() )
2612 {
2613 case SH_SEGMENT: gnShape = AddNode( GRAPH_NODE::SEGMENT, newshape.get(), newshape->GetPos() ); break;
2614 case SH_CIRCLE: gnShape = AddNode( GRAPH_NODE::CIRCLE, newshape.get(), newshape->GetPos() ); break;
2615 case SH_ARC: gnShape = AddNode( GRAPH_NODE::ARC, newshape.get(), newshape->GetPos() ); break;
2616 default: break;
2617 }
2618
2619 if( gnShape )
2620 {
2621 m_shapeCollection.push_back( std::move( newshape ) );
2622 gnShape->m_net = aConnectTo->m_net;
2623 std::shared_ptr<GRAPH_CONNECTION> gc = AddConnection( gnShape, aConnectTo );
2624
2625 if( gc )
2626 gc->m_path.m_show = false;
2627 }
2628}
2629
2630void CREEPAGE_GRAPH::GeneratePaths( double aMaxWeight, PCB_LAYER_ID aLayer,
2631 const std::set<int>* aRelevantNets )
2632{
2633 auto irrelevantPair = [&]( const std::shared_ptr<GRAPH_NODE>& gn1,
2634 const std::shared_ptr<GRAPH_NODE>& gn2 ) -> bool
2635 {
2636 return aRelevantNets && gn1->m_parent && gn2->m_parent && gn1->m_parent->IsConductive()
2637 && gn2->m_parent->IsConductive() && !aRelevantNets->count( gn1->m_net )
2638 && !aRelevantNets->count( gn2->m_net );
2639 };
2640
2641 std::vector<std::shared_ptr<GRAPH_NODE>> nodes;
2642 std::mutex nodes_lock;
2644
2645 std::vector<CREEPAGE_TRACK_ENTRY*> trackEntries;
2646 TRACK_RTREE::Builder trackBuilder;
2647
2648 if( aLayer != Edge_Cuts )
2649 {
2650 for( PCB_TRACK* track : m_board.Tracks() )
2651 {
2652 if( track && track->Type() == KICAD_T::PCB_TRACE_T && track->IsOnLayer( aLayer ) )
2653 {
2654 std::shared_ptr<SHAPE> sh = track->GetEffectiveShape();
2655
2656 if( sh && sh->Type() == SHAPE_TYPE::SH_SEGMENT )
2657 {
2659 entry->segment = SEG( track->GetStart(), track->GetEnd() );
2660 entry->layer = aLayer;
2661 entry->halfWidth = track->GetWidth() / 2;
2662 entry->track = track;
2663
2664 BOX2I bbox = track->GetBoundingBox();
2665 int minCoords[2] = { bbox.GetX(), bbox.GetY() };
2666 int maxCoords[2] = { bbox.GetRight(), bbox.GetBottom() };
2667 trackBuilder.Add( minCoords, maxCoords, entry );
2668 trackEntries.push_back( entry );
2669 }
2670 }
2671 }
2672 }
2673
2674 TRACK_RTREE trackIndex = trackBuilder.Build();
2675
2676 std::copy_if( m_nodes.begin(), m_nodes.end(), std::back_inserter( nodes ),
2677 [&]( const std::shared_ptr<GRAPH_NODE>& gn )
2678 {
2679 return gn && gn->m_parent && gn->m_connectDirectly && ( gn->m_type != GRAPH_NODE::TYPE::VIRTUAL );
2680 } );
2681
2682 std::sort( nodes.begin(), nodes.end(),
2683 []( const std::shared_ptr<GRAPH_NODE>& gn1, const std::shared_ptr<GRAPH_NODE>& gn2 )
2684 {
2685 return gn1->m_parent < gn2->m_parent
2686 || ( gn1->m_parent == gn2->m_parent && gn1->m_net < gn2->m_net );
2687 } );
2688
2689 // Build parent -> net -> nodes mapping for efficient filtering
2690 // Also cache bounding boxes for early spatial filtering
2691 std::unordered_map<const BOARD_ITEM*, std::unordered_map<int, std::vector<std::shared_ptr<GRAPH_NODE>>>> parent_net_groups;
2692 std::unordered_map<const BOARD_ITEM*, BOX2I> parent_bboxes;
2693 std::vector<const BOARD_ITEM*> parent_keys;
2694
2695 for( const auto& gn : nodes )
2696 {
2697 const BOARD_ITEM* parent = gn->m_parent->GetParent();
2698
2699 if( parent_net_groups[parent].empty() )
2700 {
2701 parent_keys.push_back( parent );
2702 if( parent )
2703 parent_bboxes[parent] = parent->GetBoundingBox();
2704 }
2705
2706 parent_net_groups[parent][gn->m_net].push_back( gn );
2707 }
2708
2709 // Generate work items using parent-level spatial indexing
2710 std::vector<std::pair<std::shared_ptr<GRAPH_NODE>, std::shared_ptr<GRAPH_NODE>>> work_items;
2711
2712 // Use RTree for spatial indexing of parent bounding boxes
2713 // Expand each bbox by maxWeight to find potentially overlapping parents
2714
2715 int64_t maxDist = static_cast<int64_t>( aMaxWeight );
2716
2717 struct ParentEntry
2718 {
2719 const BOARD_ITEM* parent;
2720 BOX2I bbox;
2721 };
2722
2723 std::vector<ParentEntry> parentEntries;
2724
2725 for( const auto* parent : parent_keys )
2726 {
2727 if( parent )
2728 {
2729 ParentEntry entry;
2730 entry.parent = parent;
2731 entry.bbox = parent_bboxes[parent];
2732 parentEntries.push_back( entry );
2733 }
2734 }
2735
2737
2738 for( ParentEntry& entry : parentEntries )
2739 {
2740 int minCoords[2] = { entry.bbox.GetLeft(), entry.bbox.GetTop() };
2741 int maxCoords[2] = { entry.bbox.GetRight(), entry.bbox.GetBottom() };
2742 parentBuilder.Add( minCoords, maxCoords, &entry );
2743 }
2744
2745 auto parentIndex = parentBuilder.Build();
2746
2747 // Parallelize parent pair search using thread pool
2748 std::mutex work_items_lock;
2749
2750 auto searchParent = [&]( size_t i ) -> bool
2751 {
2752 const ParentEntry& entry1 = parentEntries[i];
2753 const BOARD_ITEM* parent1 = entry1.parent;
2754 BOX2I bbox1 = entry1.bbox;
2755
2756 std::vector<std::pair<std::shared_ptr<GRAPH_NODE>, std::shared_ptr<GRAPH_NODE>>> localWorkItems;
2757
2758 // Search for parents within maxDist of bbox1
2759 int searchMin[2] = { bbox1.GetLeft() - (int) maxDist, bbox1.GetTop() - (int) maxDist };
2760 int searchMax[2] = { bbox1.GetRight() + (int) maxDist, bbox1.GetBottom() + (int) maxDist };
2761
2762 auto parentVisitor = [&]( ParentEntry* entry2 ) -> bool
2763 {
2764 const BOARD_ITEM* parent2 = entry2->parent;
2765
2766 // Only process if parent1 < parent2 to avoid duplicates
2767 if( parent1 >= parent2 )
2768 return true;
2769
2770 // Precise bbox distance check
2771 BOX2I bbox2 = entry2->bbox;
2772
2773 int64_t bboxDistX = 0;
2774
2775 if( bbox2.GetLeft() > bbox1.GetRight() )
2776 bboxDistX = bbox2.GetLeft() - bbox1.GetRight();
2777 else if( bbox1.GetLeft() > bbox2.GetRight() )
2778 bboxDistX = bbox1.GetLeft() - bbox2.GetRight();
2779
2780 int64_t bboxDistY = 0;
2781
2782 if( bbox2.GetTop() > bbox1.GetBottom() )
2783 bboxDistY = bbox2.GetTop() - bbox1.GetBottom();
2784 else if( bbox1.GetTop() > bbox2.GetBottom() )
2785 bboxDistY = bbox1.GetTop() - bbox2.GetBottom();
2786
2787 int64_t bboxDistSq = bboxDistX * bboxDistX + bboxDistY * bboxDistY;
2788
2789 if( bboxDistSq > maxDist * maxDist )
2790 return true;
2791
2792 // Get nodes for both parents (thread-safe reads from const map)
2793 auto it1 = parent_net_groups.find( parent1 );
2794 auto it2 = parent_net_groups.find( parent2 );
2795
2796 if( it1 == parent_net_groups.end() || it2 == parent_net_groups.end() )
2797 return true;
2798
2799 for( const auto& [net1, nodes1] : it1->second )
2800 {
2801 for( const auto& [net2, nodes2] : it2->second )
2802 {
2803 // Skip same net if both are conductive
2804 if( net1 == net2 && !nodes1.empty() && !nodes2.empty() )
2805 {
2806 if( nodes1[0]->m_parent->IsConductive()
2807 && nodes2[0]->m_parent->IsConductive() )
2808 continue;
2809 }
2810
2811 for( const auto& gn1 : nodes1 )
2812 {
2813 for( const auto& gn2 : nodes2 )
2814 {
2815 VECTOR2I pos1 = gn1->m_parent->GetPos();
2816 VECTOR2I pos2 = gn2->m_parent->GetPos();
2817 int r1 = gn1->m_parent->GetRadius();
2818 int r2 = gn2->m_parent->GetRadius();
2819
2820 int64_t centerDistSq = ( pos1 - pos2 ).SquaredEuclideanNorm();
2821 double threshold = aMaxWeight + r1 + r2;
2822 double thresholdSq = threshold * threshold;
2823
2824 if( (double) centerDistSq > thresholdSq )
2825 continue;
2826
2827 if( irrelevantPair( gn1, gn2 ) )
2828 continue;
2829
2830 localWorkItems.push_back( { gn1, gn2 } );
2831 }
2832 }
2833 }
2834 }
2835
2836 return true;
2837 };
2838
2839 parentIndex.Search( searchMin, searchMax, parentVisitor );
2840
2841 // Merge local results into global
2842 if( !localWorkItems.empty() )
2843 {
2844 std::lock_guard<std::mutex> lock( work_items_lock );
2845 work_items.insert( work_items.end(), localWorkItems.begin(), localWorkItems.end() );
2846 }
2847
2848 return true;
2849 };
2850
2851 // Use thread pool if there are enough parents
2852 if( parentEntries.size() > 100 && tp.get_tasks_total() < tp.get_thread_count() - 4 )
2853 {
2854 auto ret = tp.submit_loop( 0, parentEntries.size(), searchParent );
2855
2856 for( auto& r : ret )
2857 {
2858 if( r.valid() )
2859 r.wait();
2860 }
2861 }
2862 else
2863 {
2864 for( size_t i = 0; i < parentEntries.size(); ++i )
2865 searchParent( i );
2866 }
2867
2868 // Generate work items for same-parent node pairs. The cross-parent search above
2869 // skips pairs where parent1 == parent2, but creepage paths between different edge
2870 // segments of the same slot (which share a footprint grandparent) are needed for
2871 // the path to navigate around the slot geometry. Also handles null-parent nodes
2872 // (e.g. NPTH pad shapes) which were excluded from the RTree search entirely.
2873 for( const auto& [parent, net_groups] : parent_net_groups )
2874 {
2875 std::vector<std::shared_ptr<GRAPH_NODE>> sameParentNodes;
2876
2877 for( const auto& [net, nodeList] : net_groups )
2878 sameParentNodes.insert( sameParentNodes.end(), nodeList.begin(), nodeList.end() );
2879
2880 for( size_t i = 0; i < sameParentNodes.size(); i++ )
2881 {
2882 for( size_t j = i + 1; j < sameParentNodes.size(); j++ )
2883 {
2884 auto& gn1 = sameParentNodes[i];
2885 auto& gn2 = sameParentNodes[j];
2886
2887 // ConnectChildren already handles nodes on the same CREEP_SHAPE
2888 if( gn1->m_parent == gn2->m_parent )
2889 continue;
2890
2891 // Skip same-net conductive pairs
2892 if( gn1->m_parent->IsConductive() && gn2->m_parent->IsConductive()
2893 && gn1->m_net == gn2->m_net )
2894 {
2895 continue;
2896 }
2897
2898 VECTOR2I pos1 = gn1->m_parent->GetPos();
2899 VECTOR2I pos2 = gn2->m_parent->GetPos();
2900 int r1 = gn1->m_parent->GetRadius();
2901 int r2 = gn2->m_parent->GetRadius();
2902
2903 int64_t centerDistSq = ( pos1 - pos2 ).SquaredEuclideanNorm();
2904 double threshold = aMaxWeight + r1 + r2;
2905 double thresholdSq = threshold * threshold;
2906
2907 if( (double) centerDistSq > thresholdSq )
2908 continue;
2909
2910 if( irrelevantPair( gn1, gn2 ) )
2911 continue;
2912
2913 work_items.push_back( { gn1, gn2 } );
2914 }
2915 }
2916 }
2917
2918 auto processWorkItems =
2919 [&]( size_t idx ) -> bool
2920 {
2921 auto& [gn1, gn2] = work_items[idx];
2922
2923 // Distance filtering already done during work item creation
2924 CREEP_SHAPE* shape1 = gn1->m_parent;
2925 CREEP_SHAPE* shape2 = gn2->m_parent;
2926
2927 for( const PATH_CONNECTION& pc : GetPaths( shape1, shape2, aMaxWeight ) )
2928 {
2929 std::vector<const BOARD_ITEM*> IgnoreForTest;
2930
2931 // Don't ignore the whole parent board item for arc/circle ends. The
2932 // tangent touch is already handled by the endpoint exclusion in
2933 // segmentIntersectsArc/Circle (issue #24286). A rounded slot is a single
2934 // PCB_SHAPE, so ignoring the parent would exempt every other edge of the
2935 // same slot and let a path cut across it.
2936
2937 // Ignore each CU shape's own parent for the endpoint-inside-track
2938 // test so we don't reject paths that touch the track's own edge.
2939 if( shape1->IsConductive() )
2940 IgnoreForTest.push_back( shape1->GetParent() );
2941
2942 if( shape2->IsConductive() )
2943 IgnoreForTest.push_back( shape2->GetParent() );
2944
2945 bool valid = pc.isValid( m_board, aLayer, m_boardEdge, IgnoreForTest, m_boardOutline,
2946 { false, true }, m_minGrooveWidth, &trackIndex );
2947
2948 if( !valid )
2949 {
2950 continue;
2951 }
2952
2953 std::shared_ptr<GRAPH_NODE> connect1 = gn1, connect2 = gn2;
2954 std::lock_guard<std::mutex> lock( nodes_lock );
2955
2956 // Handle non-point node1
2957 if( gn1->m_parent->GetType() != CREEP_SHAPE::TYPE::POINT_TYPE )
2958 {
2959 auto gnt1 = AddNode( GRAPH_NODE::POINT, gn1->m_parent, pc.a1 );
2960 gnt1->m_connectDirectly = false;
2961 connect1 = gnt1;
2962
2963 if( gn1->m_parent->IsConductive() )
2964 {
2965 if( std::shared_ptr<GRAPH_CONNECTION> gc = AddConnection( gn1, gnt1 ) )
2966 gc->m_path.m_show = false;
2967 }
2968 }
2969
2970 // Handle non-point node2
2971 if( gn2->m_parent->GetType() != CREEP_SHAPE::TYPE::POINT_TYPE )
2972 {
2973 auto gnt2 = AddNode( GRAPH_NODE::POINT, gn2->m_parent, pc.a2 );
2974 gnt2->m_connectDirectly = false;
2975 connect2 = gnt2;
2976
2977 if( gn2->m_parent->IsConductive() )
2978 {
2979 if( std::shared_ptr<GRAPH_CONNECTION> gc = AddConnection( gn2, gnt2 ) )
2980 gc->m_path.m_show = false;
2981 }
2982 }
2983
2984 AddConnection( connect1, connect2, pc );
2985 }
2986
2987 return true;
2988 };
2989
2990 // If the number of tasks is high enough, this indicates that the calling process
2991 // has already parallelized the work, so we can process all items in one go.
2992 if( tp.get_tasks_total() >= tp.get_thread_count() - 4 )
2993 {
2994 for( size_t ii = 0; ii < work_items.size(); ii++ )
2995 processWorkItems( ii );
2996 }
2997 else
2998 {
2999 auto ret = tp.submit_loop( 0, work_items.size(), processWorkItems );
3000
3001 for( size_t ii = 0; ii < ret.size(); ii++ )
3002 {
3003 auto& r = ret[ii];
3004
3005 if( !r.valid() )
3006 continue;
3007
3008 while( r.wait_for( std::chrono::milliseconds( 100 ) ) != std::future_status::ready ){}
3009 }
3010 }
3011
3012 // Clean up track entries
3013 for( CREEPAGE_TRACK_ENTRY* entry : trackEntries )
3014 delete entry;
3015}
3016
3017
3018void CREEPAGE_GRAPH::detachConnection( const std::shared_ptr<GRAPH_CONNECTION>& aGc )
3019{
3020 if( !aGc )
3021 return;
3022
3023 for( const std::shared_ptr<GRAPH_NODE>& gn : { aGc->n1, aGc->n2 } )
3024 {
3025 if( gn )
3026 gn->m_node_conns.erase( aGc );
3027 }
3028}
3029
3030
3031void CREEPAGE_GRAPH::TruncateToPrefix( size_t aNodeCount, size_t aConnectionCount )
3032{
3033 size_t vectorSize = m_connections.size();
3034
3035 // Detach each connection from its endpoints' lists; the bulk resize drops them in one shot
3036 for( size_t i = aConnectionCount; i < vectorSize; i++ )
3038
3039 m_connections.resize( aConnectionCount, nullptr );
3040 m_nodes.resize( aNodeCount, nullptr );
3041
3042 // Without this, stale per-solve nodes corrupt subsequent FindNode/AddNode lookups
3043 m_nodeset.clear();
3044
3045 for( size_t i = 0; i < aNodeCount; ++i )
3046 {
3047 if( m_nodes[i] )
3048 m_nodeset.insert( m_nodes[i] );
3049 }
3050}
3051
3052
3053std::shared_ptr<GRAPH_NODE> CREEPAGE_GRAPH::AddNode( GRAPH_NODE::TYPE aType, CREEP_SHAPE* parent,
3054 const VECTOR2I& pos )
3055{
3056 std::shared_ptr<GRAPH_NODE> gn = FindNode( aType, parent, pos );
3057
3058 if( gn )
3059 return gn;
3060
3061 gn = std::make_shared<GRAPH_NODE>( aType, parent, pos );
3062 m_nodes.push_back( gn );
3063 m_nodeset.insert( gn );
3064 return gn;
3065}
3066
3067
3068std::shared_ptr<GRAPH_NODE> CREEPAGE_GRAPH::AddNodeVirtual()
3069{
3070 //Virtual nodes are always unique, do not try to find them
3071 std::shared_ptr<GRAPH_NODE> gn = std::make_shared<GRAPH_NODE>( GRAPH_NODE::TYPE::VIRTUAL, nullptr );
3072 m_nodes.push_back( gn );
3073 m_nodeset.insert( gn );
3074 return gn;
3075}
3076
3077
3078std::shared_ptr<GRAPH_CONNECTION> CREEPAGE_GRAPH::AddConnection( std::shared_ptr<GRAPH_NODE>& aN1,
3079 std::shared_ptr<GRAPH_NODE>& aN2,
3080 const PATH_CONNECTION& aPc )
3081{
3082 if( !aN1 || !aN2 )
3083 return nullptr;
3084
3085 wxASSERT_MSG( ( aN1 != aN2 ), "Creepage: a connection connects a node to itself" );
3086
3087 std::shared_ptr<GRAPH_CONNECTION> gc = std::make_shared<GRAPH_CONNECTION>( aN1, aN2, aPc );
3088 m_connections.push_back( gc );
3089 aN1->m_node_conns.insert( gc );
3090 aN2->m_node_conns.insert( gc );
3091
3092 return gc;
3093}
3094
3095
3096std::shared_ptr<GRAPH_CONNECTION> CREEPAGE_GRAPH::AddConnection( std::shared_ptr<GRAPH_NODE>& aN1,
3097 std::shared_ptr<GRAPH_NODE>& aN2 )
3098{
3099 if( !aN1 || !aN2 )
3100 return nullptr;
3101
3102 PATH_CONNECTION pc;
3103 pc.a1 = aN1->m_pos;
3104 pc.a2 = aN2->m_pos;
3105 pc.weight = 0;
3106
3107 return AddConnection( aN1, aN2, pc );
3108}
3109
3110
3111std::shared_ptr<GRAPH_NODE> CREEPAGE_GRAPH::FindNode( GRAPH_NODE::TYPE aType, CREEP_SHAPE* aParent,
3112 const VECTOR2I& aPos )
3113{
3114 auto it = m_nodeset.find( std::make_shared<GRAPH_NODE>( aType, aParent, aPos ) );
3115
3116 if( it != m_nodeset.end() )
3117 return *it;
3118
3119 return nullptr;
3120}
3121
3122
3123std::shared_ptr<GRAPH_NODE> CREEPAGE_GRAPH::AddNetElements( int aNetCode, PCB_LAYER_ID aLayer,
3124 int aMaxCreepage )
3125{
3126 std::shared_ptr<GRAPH_NODE> virtualNode = AddNodeVirtual();
3127 virtualNode->m_net = aNetCode;
3128
3129 for( FOOTPRINT* footprint : m_board.Footprints() )
3130 {
3131 for( PAD* pad : footprint->Pads() )
3132 {
3133 if( pad->GetNetCode() != aNetCode || !pad->IsOnLayer( aLayer ) )
3134 continue;
3135
3136 if( pad->HasCopperRemoved( aLayer ) )
3137 continue;
3138
3139 if( std::shared_ptr<SHAPE> padShape = pad->GetEffectiveShape( aLayer ) )
3140 Addshape( *padShape, virtualNode, pad );
3141 }
3142 }
3143
3144 for( PCB_TRACK* track : m_board.Tracks() )
3145 {
3146 if( track->GetNetCode() != aNetCode || !track->IsOnLayer( aLayer ) )
3147 continue;
3148
3149 if( track->Type() == PCB_VIA_T && static_cast<const PCB_VIA*>( track )->HasCopperRemoved( aLayer ) )
3150 continue;
3151
3152 if( std::shared_ptr<SHAPE> shape = track->GetEffectiveShape() )
3153 Addshape( *shape, virtualNode, track );
3154 }
3155
3156
3157 for( ZONE* zone : m_board.Zones() )
3158 {
3159 if( zone->GetIsRuleArea() )
3160 continue;
3161
3162 if( zone->GetNetCode() != aNetCode || !zone->IsOnLayer( aLayer ) )
3163 continue;
3164
3165 if( std::shared_ptr<SHAPE> shape = zone->GetEffectiveShape( aLayer ) )
3166 Addshape( *shape, virtualNode, zone );
3167 }
3168
3169 const DRAWINGS drawings = m_board.Drawings();
3170
3171 for( BOARD_ITEM* drawing : drawings )
3172 {
3173 if( drawing->IsConnected() )
3174 {
3175 BOARD_CONNECTED_ITEM* bci = static_cast<BOARD_CONNECTED_ITEM*>( drawing );
3176
3177 if( bci->GetNetCode() != aNetCode || !bci->IsOnLayer( aLayer ) )
3178 continue;
3179
3180 if( std::shared_ptr<SHAPE> shape = bci->GetEffectiveShape() )
3181 Addshape( *shape, virtualNode, bci );
3182 }
3183 }
3184
3185
3186 return virtualNode;
3187}
BOX2< VECTOR2I > BOX2I
Definition box2.h:917
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
BE_SHAPE_ARC(VECTOR2I aPos, int aRadius, EDA_ANGLE aStartAngle, EDA_ANGLE aEndAngle, VECTOR2D aStartPoint, VECTOR2D aEndPoint)
VECTOR2I GetStartPoint() const override
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
BE_SHAPE_CIRCLE(VECTOR2I aPos=VECTOR2I(0, 0), int aRadius=0)
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.
BE_SHAPE_POINT(VECTOR2I aPos)
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:99
virtual bool IsOnLayer(PCB_LAYER_ID aLayer) const
Test to see if this object is on the given layer.
Definition board_item.h:432
virtual std::shared_ptr< SHAPE > GetEffectiveShape(PCB_LAYER_ID aLayer=UNDEFINED_LAYER, FLASHING aFlash=FLASHING::DEFAULT, DRC_CONSTRAINT_T aUsage=NULL_CONSTRAINT) const
Some pad shapes can be complex (rounded/chamfered rectangle), even without considering custom shapes.
Information pertinent to a Pcbnew printed circuit board.
Definition board.h:411
const std::vector< PAD * > GetPads() const
Return a reference to a list of all the pads.
Definition board.cpp:3771
const FOOTPRINTS & Footprints() const
Definition board.h:465
BOARD_DESIGN_SETTINGS & GetDesignSettings()
Definition board.cpp:1318
const DRAWINGS & Drawings() const
Definition board.h:467
constexpr coord_type GetY() const
Definition box2.h:211
constexpr coord_type GetX() const
Definition box2.h:210
constexpr coord_type GetLeft() const
Definition box2.h:231
constexpr coord_type GetRight() const
Definition box2.h:220
constexpr coord_type GetTop() const
Definition box2.h:232
constexpr coord_type GetBottom() const
Definition box2.h:225
Represent basic circle geometry with utility geometry functions.
Definition circle.h:33
A graph with nodes and connections for creepage calculation.
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)
void GeneratePaths(double aMaxWeight, PCB_LAYER_ID aLayer, const std::set< int > *aRelevantNets=nullptr)
Generate creepage paths between graph nodes.
std::shared_ptr< GRAPH_NODE > AddNodeVirtual()
SHAPE_POLY_SET * m_boardOutline
void TransformCreepShapesToNodes(const std::vector< std::unique_ptr< CREEP_SHAPE > > &aShapes)
void TruncateToPrefix(size_t aNodeCount, size_t aConnectionCount)
Remove every node and connection added after the given prefix sizes, then rebuild the node lookup set...
std::vector< BOARD_ITEM * > m_boardEdge
std::vector< std::unique_ptr< CREEP_SHAPE > > m_shapeCollection
std::unordered_set< std::shared_ptr< GRAPH_NODE >, GraphNodeHash, GraphNodeEqual > m_nodeset
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)
std::shared_ptr< GRAPH_NODE > FindNode(GRAPH_NODE::TYPE aType, CREEP_SHAPE *aParent, const VECTOR2I &aPos)
void detachConnection(const std::shared_ptr< GRAPH_CONNECTION > &aGc)
A class used to represent the shapes for creepage calculation.
VECTOR2I GetPos() const
CREEP_SHAPE::TYPE GetType() const
virtual int GetRadius() const
const BOARD_ITEM * GetParent() 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
EDA_ANGLE AngleBetweenStartAndEnd(const VECTOR2I aPoint) const
VECTOR2I GetEndPoint() const override
EDA_ANGLE GetStartAngle() const override
double GetWidth() const
CU_SHAPE_ARC(VECTOR2I aPos, double aRadius, EDA_ANGLE aStartAngle, EDA_ANGLE aEndAngle, VECTOR2D aStartPoint, VECTOR2D aEndPoint)
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
CU_SHAPE_CIRCLE(VECTOR2I aPos, double aRadius=0)
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
CU_SHAPE_SEGMENT(VECTOR2I aStart, VECTOR2I aEnd, double aWidth=0)
double AsRadians() const
Definition eda_angle.h:119
virtual const BOX2I GetBoundingBox() const
Return the orthogonal bounding box of this object for display purposes.
Definition eda_item.cpp:280
VECTOR2I getCenter() const
std::vector< VECTOR2I > GetPolyPoints() const
Duplicate the polygon outlines into a flat list of VECTOR2I points.
void CalcArcAngles(EDA_ANGLE &aStartAngle, EDA_ANGLE &aEndAngle) const
Calc arc start and end angles such that aStartAngle < aEndAngle.
int GetRadius() const
SHAPE_T GetShape() const
Definition eda_shape.h:178
void RebuildBezierToSegmentsPointsList(int aMaxError)
Rebuild the m_bezierPoints vertex list that approximate the Bezier curve by a list of segments.
const VECTOR2I & GetEnd() const
Return the ending point of the graphic.
Definition eda_shape.h:334
const VECTOR2I & GetStart() const
Return the starting point of the graphic.
Definition eda_shape.h:284
const std::vector< VECTOR2I > & GetBezierPoints() const
Definition eda_shape.h:506
int GetCornerRadius() const
VECTOR2I GetArcMid() const
std::shared_ptr< GRAPH_NODE > n2
PATH_CONNECTION m_path
void GetShapes(std::vector< PCB_SHAPE > &aShapes)
std::shared_ptr< GRAPH_NODE > n1
std::set< std::shared_ptr< GRAPH_CONNECTION > > m_node_conns
Builder for constructing a PACKED_RTREE from a set of items.
void Add(const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS], const DATATYPE &aData)
Definition pad.h:61
const BOX2I GetBoundingBox() const override
Return the orthogonal bounding box of this object for display purposes.
void SetCenter(const VECTOR2I &aCenter) override
VECTOR2I GetCenter() const override
This defaults to the center of the bounding box if not overridden.
Definition pcb_shape.h:80
void SetEnd(const VECTOR2I &aEnd) override
void SetStart(const VECTOR2I &aStart) override
bool HasCopperRemoved(PCB_LAYER_ID aLayer) const
Check whether backdrilling or post-machining left no copper at all on a layer.
Definition seg.h:38
VECTOR2I A
Definition seg.h:45
VECTOR2I B
Definition seg.h:46
int GetWidth() const override
Definition shape_arc.h:215
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:96
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...
int PointCount() const
Return the number of points (vertices) in this line chain.
const VECTOR2I & CLastPoint() const
Return the last point in the line chain.
const std::vector< VECTOR2I > & CPoints() const
Represent a set of closed polygons.
bool PointOnEdge(const VECTOR2I &aP, int aAccuracy=0) const
Check if point aP lies on an edge or vertex of some of the outlines or holes.
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles() const
Return an iterator object, for the aOutline-th outline in the set (with holes).
bool Contains(const VECTOR2I &aP, int aSubpolyIndex=-1, int aAccuracy=0, bool aUseBBoxCaches=false) const
Return true if a given subpolygon contains the point aP.
const SEG & GetSeg() const
int GetWidth() const override
Represent a simple polygon consisting of a zero-thickness closed chain of connected line segments.
const SHAPE_LINE_CHAIN & Vertices() const
Return the list of vertices defining this simple polygon.
An abstract shape on 2D plane.
Definition shape.h:124
constexpr extended_type Cross(const VECTOR2< T > &aVector) const
Compute cross product of self with aVector.
Definition vector2d.h:559
constexpr extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
Definition vector2d.h:312
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition vector2d.h:281
VECTOR2_TRAITS< int32_t >::extended_type extended_type
Definition vector2d.h:69
constexpr VECTOR2< T > Perpendicular() const
Compute the perpendicular vector.
Definition vector2d.h:335
constexpr extended_type Dot(const VECTOR2< T > &aVector) const
Compute dot product of self with aVector.
Definition vector2d.h:567
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition vector2d.h:406
Handle a list of polygons defining a copper zone.
Definition zone.h:70
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)
std::vector< PATH_CONNECTION > GetPaths(CREEP_SHAPE *aS1, CREEP_SHAPE *aS2, double aMaxWeight)
bool segmentIntersectsArc(const VECTOR2I &p1, const VECTOR2I &p2, const VECTOR2I &center, double radius, EDA_ANGLE startAngle, EDA_ANGLE endAngle, std::vector< VECTOR2I > *aIntersectionPoints=nullptr)
bool compareShapes(const CREEP_SHAPE *a, const CREEP_SHAPE *b)
bool segments_intersect(const VECTOR2I &p1, const VECTOR2I &q1, const VECTOR2I &p2, const VECTOR2I &q2, std::vector< VECTOR2I > &aIntersectionPoints)
void BuildCreepageBoardEdges(BOARD &aBoard, std::vector< BOARD_ITEM * > &aVector, std::vector< std::unique_ptr< PCB_SHAPE > > &aOwned, const std::set< const BOARD_ITEM * > *aExclude)
Collect the board-edge items used by the creepage graph.
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)
KIRTREE::PACKED_RTREE< CREEPAGE_TRACK_ENTRY *, int, 2 > TRACK_RTREE
static constexpr EDA_ANGLE ANGLE_0
Definition eda_angle.h:472
@ RADIANS_T
Definition eda_angle.h:31
@ DEGREES_T
Definition eda_angle.h:30
static constexpr EDA_ANGLE ANGLE_360
Definition eda_angle.h:478
@ SEGMENT
Definition eda_shape.h:57
@ RECTANGLE
Use RECTANGLE instead of RECT to avoid collision in a Windows header.
Definition eda_shape.h:58
std::variant< LINE, HALF_LINE, SEG, CIRCLE, SHAPE_ARC, SHAPE_ELLIPSE, BOX2I > INTERSECTABLE_GEOM
A variant type that can hold any of the supported geometry types for intersection calculations.
PCB_LAYER_ID
A quick note on layer IDs:
Definition layer_ids.h:56
@ Edge_Cuts
Definition layer_ids.h:108
@ NPTH
like PAD_PTH, but not plated mechanical use only, no connection allowed
Definition padstack.h:104
std::deque< BOARD_ITEM * > DRAWINGS
#define D(x)
Definition ptree.cpp:37
static float distance(const SFVEC2UI &a, const SFVEC2UI &b)
@ SH_POLY_SET
set of polygons (with holes, etc.)
Definition shape.h:48
@ SH_RECT
axis-aligned rectangle
Definition shape.h:43
@ SH_CIRCLE
circle
Definition shape.h:46
@ SH_SIMPLE
simple polygon
Definition shape.h:47
@ SH_SEGMENT
line segment
Definition shape.h:44
@ SH_ARC
circular arc
Definition shape.h:50
@ SH_LINE_CHAIN
line chain (polyline)
Definition shape.h:45
@ SH_COMPOUND
compound shape, consisting of multiple simple shapes
Definition shape.h:49
int halfWidth
const PCB_TRACK * track
SEG segment
PCB_LAYER_ID layer
A visitor that visits INTERSECTABLE_GEOM variant objects with another (which is held as state: m_othe...
VECTOR2I center
int radius
VECTOR2I end
SHAPE_CIRCLE circle(c.m_circle_center, c.m_circle_radius)
wxString result
Test unit parsing edge cases and error handling.
int delta
#define M_PI
thread_pool & GetKiCadThreadPool()
Get a reference to the current thread pool.
static thread_pool * tp
BS::priority_thread_pool thread_pool
Definition thread_pool.h:27
@ PCB_VIA_T
class PCB_VIA, a via (like a track segment on a copper layer)
Definition typeinfo.h:89
@ PCB_TRACE_T
class PCB_TRACK, a track segment (segment on a copper layer)
Definition typeinfo.h:88
VECTOR2< int32_t > VECTOR2I
Definition vector2d.h:708
VECTOR2< double > VECTOR2D
Definition vector2d.h:707
static PIECE rect(double aLeft, double aTop, double aRight, double aBottom, bool aMixed=false)