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