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