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