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