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