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