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