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