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