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