30 std::vector<std::unique_ptr<PCB_SHAPE>>& aOwned,
31 const std::set<const BOARD_ITEM*>* aExclude )
38 if( !aExclude || !aItem )
41 if( aExclude->count( aItem ) )
46 return parent && aExclude->count( parent );
54 if( !aDrawing || !aDrawing->IsOnLayer(
Edge_Cuts ) )
57 if( excluded( aDrawing ) )
69 aVector.push_back( shape );
76 for(
size_t i = 1; i < pts.size(); ++i )
78 if( pts[i - 1] == pts[i] )
82 seg->SetStart( pts[i - 1] );
83 seg->SetEnd( pts[i] );
84 aVector.push_back( seg.get() );
85 aOwned.push_back( std::move( seg ) );
90 addEdgeDrawing( drawing );
97 for(
BOARD_ITEM* drawing : fp->GraphicalItems() )
98 addEdgeDrawing( drawing );
111 std::shared_ptr<SHAPE_SEGMENT> hole = p->GetEffectiveHoleShape();
118 int radius = hole->GetWidth() / 2;
124 s->SetPosition( ptA );
125 aVector.push_back( s.get() );
126 aOwned.push_back( std::move( s ) );
135 seg1->SetStart( ptA + perp );
136 seg1->SetEnd( ptB + perp );
137 aVector.push_back( seg1.get() );
138 aOwned.push_back( std::move( seg1 ) );
141 seg2->SetStart( ptA - perp );
142 seg2->SetEnd( ptB - perp );
143 aVector.push_back( seg2.get() );
144 aOwned.push_back( std::move( seg2 ) );
147 auto arcA = std::make_unique<PCB_SHAPE>(
nullptr,
SHAPE_T::ARC );
148 arcA->SetArcGeometry( ptA + perp, midA, ptA - perp );
149 aVector.push_back( arcA.get() );
150 aOwned.push_back( std::move( arcA ) );
153 auto arcB = std::make_unique<PCB_SHAPE>(
nullptr,
SHAPE_T::ARC );
154 arcB->SetArcGeometry( ptB - perp, midB, ptB + perp );
155 aVector.push_back( arcB.get() );
156 aOwned.push_back( std::move( arcB ) );
164 std::vector<VECTOR2I>* aIntersectionPoints =
nullptr )
166 SEG segment( p1, p2 );
173 std::vector<VECTOR2I> rawPoints;
175 std::visit( visitor, geom1 );
179 std::vector<VECTOR2I> filtered;
187 return ( a - b ).SquaredEuclideanNorm() <= toleranceSq;
190 for(
const VECTOR2I& ip : rawPoints )
192 if( !coincident( ip, p1 ) && !coincident( ip, p2 ) )
193 filtered.push_back( ip );
196 if( aIntersectionPoints )
198 for(
const VECTOR2I& ip : filtered )
199 aIntersectionPoints->push_back( ip );
202 return !filtered.empty();
209 std::vector<VECTOR2I>& aIntersectionPoints )
211 if( p1 == p2 || p1 == q2 || q1 == p2 || q1 == q2 )
214 SEG segment1( p1, q1 );
215 SEG segment2( p2, q2 );
220 size_t startCount = aIntersectionPoints.size();
223 std::visit( visitor, geom1 );
225 return aIntersectionPoints.size() > startCount;
240 if( a->
GetType() == CREEP_SHAPE::TYPE::UNDEFINED )
246 if( a->
GetType() == CREEP_SHAPE::TYPE::CIRCLE )
264 if( a->
GetType() == CREEP_SHAPE::TYPE::POINT_TYPE )
267 if( a->
GetType() == CREEP_SHAPE::TYPE::CIRCLE )
275 double aMaxSquaredWeight )
const
277 std::vector<PATH_CONNECTION>
result;
279 double weight = ( this->
GetPos() - aS2.
GetPos() ).SquaredEuclideanNorm();
281 if( weight > aMaxSquaredWeight )
287 pc.
weight = sqrt( weight );
295 double aMaxSquaredWeight )
const
297 std::vector<PATH_CONNECTION>
result;
305 double pointToCenterDistanceSquared = ( pointPos - circleCenter ).SquaredEuclideanNorm();
306 double weightSquared = pointToCenterDistanceSquared - (float)
radius * (
float)
radius;
308 if( weightSquared > aMaxSquaredWeight )
312 direction1 = direction1.
Resize( 1 );
316 double radiusSquared = double(
radius ) * double(
radius );
318 double distance = sqrt( pointToCenterDistanceSquared );
319 double value1 = radiusSquared /
distance;
320 double value2 = sqrt( radiusSquared - value1 * value1 );
326 pc.
weight = sqrt( weightSquared );
328 resultPoint = direction1 * value1 + direction2 * value2 + circleCenter;
329 pc.
a2.
x = int( resultPoint.
x );
330 pc.
a2.
y = int( resultPoint.
y );
333 resultPoint = direction1 * value1 - direction2 * value2 + circleCenter;
334 pc.
a2.
x = int( resultPoint.
x );
335 pc.
a2.
y = int( resultPoint.
y );
344 std::pair<bool, bool>
result;
361 double pointAngle = testAngle.
AsRadians();
364 bool connectToEndPoint;
366 connectToEndPoint = ( cos( startAngle ) * newPoint.
x + sin( startAngle ) * newPoint.
y >= R );
369 connectToEndPoint &= ( cos( endAngle ) * newPoint.
x + sin( endAngle ) * newPoint.
y <= R );
371 connectToEndPoint |= ( cos( endAngle ) * newPoint.
x + sin( endAngle ) * newPoint.
y <= R )
372 && ( pointAngle >= endAngle || pointAngle <= startAngle );
374 result.first = !connectToEndPoint;
376 connectToEndPoint = ( cos( endAngle ) * newPoint.
x + sin( endAngle ) * newPoint.
y >= R );
379 connectToEndPoint &= ( cos( startAngle ) * newPoint.
x + sin( startAngle ) * newPoint.
y <= R );
381 connectToEndPoint |= ( cos( startAngle ) * newPoint.
x + sin( startAngle ) * newPoint.
y <= R )
382 && ( pointAngle >= endAngle || pointAngle <= startAngle );
384 result.second = !connectToEndPoint;
390 double aMaxSquaredWeight )
const
392 std::vector<PATH_CONNECTION>
result;
398 std::pair<bool, bool> behavesLikeCircle;
401 if( behavesLikeCircle.first && behavesLikeCircle.second )
404 return this->
Paths( csc, aMaxWeight, aMaxSquaredWeight );
407 if( behavesLikeCircle.first )
410 std::vector<PATH_CONNECTION> paths = this->
Paths( csc, aMaxWeight, aMaxSquaredWeight );
412 if( paths.size() > 1 )
413 result.push_back( paths[1] );
423 if( behavesLikeCircle.second )
426 std::vector<PATH_CONNECTION> paths = this->
Paths( csc, aMaxWeight, aMaxSquaredWeight );
428 if( paths.size() > 1 )
429 result.push_back( paths[0] );
443 double aMaxSquaredWeight )
const
445 std::vector<PATH_CONNECTION>
result;
453 double centerDistance = ( circleCenter - arcCenter ).EuclideanNorm();
455 if( centerDistance + arcRadius < circleRadius )
493 double aMaxSquaredWeight )
const
495 std::vector<PATH_CONNECTION>
result;
501 double centerDistance = ( circleCenter - arcCenter ).EuclideanNorm();
503 if( centerDistance + arcRadius < circleRadius )
515 aMaxWeight, aMaxSquaredWeight ) )
524 .
Paths( aS2, aMaxWeight, aMaxSquaredWeight ) )
537 double aMaxSquaredWeight )
const
539 std::vector<PATH_CONNECTION>
result;
544 VECTOR2D distSquared(
double( ( p2 - p1 ).x ),
double( ( p2 - p1 ).y ) );
550 double Rdiff = abs( R1 - R2 );
551 double Rsum = R1 + R2;
554 double weightSquared1 = weightSquared - Rdiff * Rdiff;
556 double weightSquared2 = weightSquared - Rsum * Rsum;
558 if( weightSquared1 <= aMaxSquaredWeight )
561 direction1 = direction1.
Resize( 1 );
564 double D = sqrt( weightSquared );
565 double ratio1 = ( R1 - R2 ) /
D;
566 double ratio2 = sqrt( 1 - ratio1 * ratio1 );
570 pc.
weight = sqrt( weightSquared1 );
572 pc.
a1 = p1 + direction1 * R1 * ratio1 + direction2 * R1 * ratio2;
573 pc.
a2 = p2 + direction1 * R2 * ratio1 + direction2 * R2 * ratio2;
577 pc.
a1 = p1 + direction1 * R1 * ratio1 - direction2 * R1 * ratio2;
578 pc.
a2 = p2 + direction1 * R2 * ratio1 - direction2 * R2 * ratio2;
582 if( weightSquared2 <= aMaxSquaredWeight )
585 direction1 = direction1.
Resize( 1 );
588 double D = sqrt( weightSquared );
589 double ratio1 = ( R1 + R2 ) /
D;
590 double ratio2 = sqrt( 1 - ratio1 * ratio1 );
594 pc.
weight = sqrt( weightSquared2 );
596 pc.
a1 = p1 + direction1 * R1 * ratio1 + direction2 * R1 * ratio2;
597 pc.
a2 = p2 - direction1 * R2 * ratio1 - direction2 * R2 * ratio2;
601 pc.
a1 = p1 + direction1 * R1 * ratio1 - direction2 * R1 * ratio2;
602 pc.
a2 = p2 - direction1 * R2 * ratio1 + direction2 * R2 * ratio2;
613 for(
const std::unique_ptr<CREEP_SHAPE>& shape : aShapes )
622 case CREEP_SHAPE::TYPE::POINT_TYPE:
AddNode( GRAPH_NODE::TYPE::POINT, p1, p1->
GetPos() );
break;
623 case CREEP_SHAPE::TYPE::CIRCLE:
AddNode( GRAPH_NODE::TYPE::CIRCLE, p1, p1->
GetPos() );
break;
624 case CREEP_SHAPE::TYPE::ARC:
AddNode( GRAPH_NODE::TYPE::ARC, p1, p1->
GetPos() );
break;
633 [](
const auto& a,
const auto& b ) { return compareShapes( a.get(), b.get() ); } );
658 std::vector<BOX2I> cutouts;
674 for(
size_t j = i + 1; j < cutouts.size(); ++j )
676 if( cutouts[i].Intersects( cutouts[j] ) && !cutouts[i].Contains( cutouts[j] )
677 && !cutouts[j].Contains( cutouts[i] ) )
696 auto a = std::make_unique<BE_SHAPE_POINT>( d->
GetStart() );
699 a = std::make_unique<BE_SHAPE_POINT>( d->
GetEnd() );
727 while( endAngle < startAngle )
730 auto arc = std::make_unique<BE_SHAPE_ARC>(
center, r, startAngle, endAngle,
741 addArc( { x1 + r, y1 + r }, { x1 + r, y2 }, { x1 + r, y1 } );
742 addArc( { x2 - r, y1 + r }, { x2 - r, y1 }, { x2 - r, y2 } );
744 else if( w == 2 * r )
747 addArc( { x1 + r, y1 + r }, { x1, y1 + r }, { x2, y1 + r } );
748 addArc( { x1 + r, y2 - r }, { x2, y2 - r }, { x1, y2 - r } );
753 addArc( { x1 + r, y1 + r }, { x1, y1 + r }, { x1 + r, y1 } );
754 addArc( { x2 - r, y1 + r }, { x2 - r, y1 }, { x2, y1 + r } );
755 addArc( { x2 - r, y2 - r }, { x2, y2 - r }, { x2 - r, y2 } );
756 addArc( { x1 + r, y2 - r }, { x1 + r, y2 }, { x1, y2 - r } );
761 auto a = std::make_unique<BE_SHAPE_POINT>( d->
GetStart() );
764 a = std::make_unique<BE_SHAPE_POINT>( d->
GetEnd() );
781 auto a = std::make_unique<BE_SHAPE_POINT>( p );
799 double tolerance = 10;
830 if(
n1->m_type == GRAPH_NODE::TYPE::VIRTUAL ||
n2->m_type == GRAPH_NODE::TYPE::VIRTUAL )
834 &&
n1->m_parent ==
n2->m_parent
835 &&
n1->m_parent->GetType() == CREEP_SHAPE::TYPE::CIRCLE )
842 if( R1.
Cross( R2 ) > 0 )
854 aShapes.push_back( s );
859 &&
n1->m_parent ==
n2->m_parent
860 &&
n1->m_parent->GetType() == CREEP_SHAPE::TYPE::ARC )
869 if( R1.
Cross( R2 ) > 0 )
884 EDA_ANGLE midAngle = arc->AngleBetweenStartAndEnd( mid );
886 if( midAngle > arc->GetEndAngle() )
895 aShapes.push_back( s );
903 aShapes.push_back( s );
934 EDA_ANGLE maxAngle = angle1 > angle2 ? angle1 : angle2;
937 skipAngle += skipAngle;
938 EDA_ANGLE pointAngle = maxAngle - skipAngle;
948 pc.
a1 = maxAngle == angle2 ? a1->m_pos : a2->m_pos;
954 pc.
a2 = maxAngle == angle2 ? a2->m_pos : a1->m_pos;
957 std::shared_ptr<GRAPH_CONNECTION> gc = aG.
AddConnection( gnt, maxAngle == angle2 ? a2 : a1, pc );
960 gc->m_forceStraightLine =
true;
980 double delta = a2r - a1r;
987 for(
int i = 0; i <= 8; ++i )
989 double a = a1r +
delta * i / 8.0;
997 VECTOR2D distI( a1->m_pos - a2->m_pos );
998 VECTOR2D distD(
double( distI.
x ),
double( distI.
y ) );
1010 pc.
weight = std::max( weight, 0.0 );
1039 for(
int i = 0; i <= 8; ++i )
1041 double a = a1r + ( a2r - a1r ) * i / 8.0;
1049 double weight = abs(
m_radius * ( angle2 - angle1 ).AsRadians() );
1078 double aMaxSquaredWeight )
const
1080 std::vector<PATH_CONNECTION>
result;
1083 double halfWidth = this->
GetWidth() / 2;
1087 double length = ( start -
end ).EuclideanNorm();
1088 double projectedPos = cos( trackAngle.
AsRadians() ) * ( pointPos.
x - start.
x )
1089 + sin( trackAngle.
AsRadians() ) * ( pointPos.
y - start.
y );
1093 if( projectedPos <= 0 )
1095 newPoint = start + ( pointPos - start ).Resize( halfWidth );
1097 else if( projectedPos >= length )
1099 newPoint =
end + ( pointPos -
end ).Resize( halfWidth );
1103 double posOnSegment = ( start - pointPos ).SquaredEuclideanNorm()
1104 - (
end - pointPos ).SquaredEuclideanNorm();
1105 posOnSegment = posOnSegment / ( 2 * length ) + length / 2;
1107 newPoint = start + (
end - start ).Resize( posOnSegment );
1108 newPoint += ( pointPos - newPoint ).Resize( halfWidth );
1111 double weightSquared = ( pointPos - newPoint ).SquaredEuclideanNorm();
1113 if( weightSquared > aMaxSquaredWeight )
1119 pc.
weight = sqrt( weightSquared );
1127 double aMaxSquaredWeight )
const
1129 std::vector<PATH_CONNECTION>
result;
1132 double halfWidth = this->
GetWidth() / 2;
1136 double length = ( start -
end ).EuclideanNorm();
1139 double weightSquared = std::numeric_limits<double>::infinity();
1140 VECTOR2I PointOnTrack, PointOnCircle;
1144 double projectedPos1 = cos( trackAngle.
AsRadians() ) * ( circleCenter.
x - start.
x )
1145 + sin( trackAngle.
AsRadians() ) * ( circleCenter.
y - start.
y );
1146 double projectedPos2 = projectedPos1 + circleRadius;
1147 projectedPos1 = projectedPos1 - circleRadius;
1149 double trackSide = (
end - start ).Cross( circleCenter - start ) > 0 ? 1 : -1;
1151 if( ( projectedPos1 < 0 && projectedPos2 < 0 ) )
1159 else if( ( projectedPos1 > length && projectedPos2 > length ) )
1167 else if( ( projectedPos1 >= 0 ) && ( projectedPos1 <= length ) && ( projectedPos2 >= 0 )
1168 && ( projectedPos2 <= length ) )
1171 PointOnTrack = start;
1172 PointOnTrack += (
end - start ).Resize( projectedPos1 );
1173 PointOnTrack += (
end - start ).Perpendicular().
Resize( halfWidth ) * trackSide;
1174 PointOnCircle = circleCenter - (
end - start ).Resize( circleRadius );
1175 weightSquared = ( PointOnCircle - PointOnTrack ).SquaredEuclideanNorm();
1177 if( weightSquared < aMaxSquaredWeight )
1180 pc.
a1 = PointOnTrack;
1181 pc.
a2 = PointOnCircle;
1182 pc.
weight = sqrt( weightSquared );
1186 PointOnTrack = start;
1187 PointOnTrack += (
end - start ).Resize( projectedPos2 );
1188 PointOnTrack += (
end - start ).Perpendicular().
Resize( halfWidth ) * trackSide;
1189 PointOnCircle = circleCenter + (
end - start ).Resize( circleRadius );
1192 pc.
a1 = PointOnTrack;
1193 pc.
a2 = PointOnCircle;
1198 else if( ( ( projectedPos1 >= 0 ) && ( projectedPos1 <= length ) )
1199 && ( ( projectedPos2 > length ) || projectedPos2 < 0 ) )
1202 std::vector<PATH_CONNECTION> pcs = csc.
Paths( aS2, aMaxWeight, aMaxSquaredWeight );
1204 if( pcs.size() < 2 )
1207 result.push_back( pcs.at( trackSide == 1 ? 1 : 0 ) );
1210 PointOnTrack = start;
1211 PointOnTrack += (
end - start ).Resize( projectedPos1 );
1212 PointOnTrack += (
end - start ).Perpendicular().
Resize( halfWidth ) * trackSide;
1213 PointOnCircle = circleCenter - (
end - start ).Resize( circleRadius );
1214 weightSquared = ( PointOnCircle - PointOnTrack ).SquaredEuclideanNorm();
1216 if( weightSquared < aMaxSquaredWeight )
1219 pc.
a1 = PointOnTrack;
1220 pc.
a2 = PointOnCircle;
1221 pc.
weight = sqrt( weightSquared );
1226 else if( ( ( projectedPos2 >= 0 ) && ( projectedPos2 <= length ) )
1227 && ( ( projectedPos1 > length ) || projectedPos1 < 0 ) )
1230 std::vector<PATH_CONNECTION> pcs = csc.
Paths( aS2, aMaxWeight, aMaxSquaredWeight );
1232 if( pcs.size() < 2 )
1235 result.push_back( pcs.at( trackSide == 1 ? 0 : 1 ) );
1237 PointOnTrack = start;
1238 PointOnTrack += (
end - start ).Resize( projectedPos2 );
1239 PointOnTrack += (
end - start ).Perpendicular().
Resize( halfWidth ) * trackSide;
1240 PointOnCircle = circleCenter + (
end - start ).Resize( circleRadius );
1241 weightSquared = ( PointOnCircle - PointOnTrack ).SquaredEuclideanNorm();
1243 if( weightSquared < aMaxSquaredWeight )
1246 pc.
a1 = PointOnTrack;
1247 pc.
a2 = PointOnCircle;
1248 pc.
weight = sqrt( weightSquared );
1253 else if( projectedPos1 < 0 && projectedPos2 > length )
1258 std::vector<PATH_CONNECTION> startPcs = cscStart.
Paths( aS2, aMaxWeight, aMaxSquaredWeight );
1260 if( startPcs.size() >= 2 )
1261 result.push_back( startPcs.at( trackSide == 1 ? 0 : 1 ) );
1264 std::vector<PATH_CONNECTION> endPcs = cscEnd.
Paths( aS2, aMaxWeight, aMaxSquaredWeight );
1266 if( endPcs.size() >= 2 )
1267 result.push_back( endPcs.at( trackSide == 1 ? 1 : 0 ) );
1275 double aMaxSquaredWeight )
const
1277 std::vector<PATH_CONNECTION>
result;
1301 if( !
segmentIntersectsArc( pc.a1, pc.a2, beArcPos, beArcRadius, beArcStartAngle, beArcEndAngle ) )
1307 if( !
segmentIntersectsArc( pc.a1, pc.a2, beArcPos, beArcRadius, beArcStartAngle, beArcEndAngle ) )
1317 double aMaxSquaredWeight )
const
1319 std::vector<PATH_CONNECTION>
result;
1342 if( !
segmentIntersectsArc( pc.a1, pc.a2, beArcPos, beArcRadius, beArcStartAngle, beArcEndAngle ) )
1348 if( !
segmentIntersectsArc( pc.a1, pc.a2, beArcPos, beArcRadius, beArcStartAngle, beArcEndAngle ) )
1358 double aMaxSquaredWeight )
const
1360 std::vector<PATH_CONNECTION>
result;
1389 double aMaxSquaredWeight )
const
1391 std::vector<PATH_CONNECTION>
result;
1414 if( !
segmentIntersectsArc( pc.a1, pc.a2, beArcPos, beArcRadius, beArcStartAngle, beArcEndAngle ) )
1420 if( !
segmentIntersectsArc( pc.a1, pc.a2, beArcPos, beArcRadius, beArcStartAngle, beArcEndAngle ) )
1430 double aMaxSquaredWeight )
const
1432 std::vector<PATH_CONNECTION>
result;
1437 double weight = (
center - point ).EuclideanNorm() - R;
1439 if( weight > aMaxWeight )
1443 pc.
weight = std::max( weight, 0.0 );
1453 double aMaxSquaredWeight )
const
1455 std::vector<PATH_CONNECTION>
result;
1462 if( ( C1 - C2 ).SquaredEuclideanNorm() < ( R1 - R2 ) * ( R1 - R2 ) )
1468 double weight = ( C1 - C2 ).EuclideanNorm() - R1 - R2;
1470 if( weight > aMaxWeight || weight < 0 )
1474 pc.
weight = std::max( weight, 0.0 );
1475 pc.
a1 = ( C2 - C1 ).Resize( R1 ) + C1;
1476 pc.
a2 = ( C1 - C2 ).Resize( R2 ) + C2;
1483 double aMaxSquaredWeight )
const
1485 std::vector<PATH_CONNECTION>
result;
1489 double halfWidth = this->
GetWidth() / 2;
1491 EDA_ANGLE trackAngle( s_end - s_start );
1494 double length = ( s_start - s_end ).EuclideanNorm();
1495 double projectedPos = cos( trackAngle.
AsRadians() ) * ( pointPos.
x - s_start.
x )
1496 + sin( trackAngle.
AsRadians() ) * ( pointPos.
y - s_start.
y );
1498 if( ( projectedPos <= 0 ) || ( s_start == s_end ) )
1501 return csc.
Paths( aS2, aMaxWeight, aMaxSquaredWeight );
1504 if( projectedPos >= length )
1507 return csc.
Paths( aS2, aMaxWeight, aMaxSquaredWeight );
1511 double trackSide = ( s_end - s_start ).Cross( pointPos - s_start ) > 0 ? 1 : -1;
1514 pc.
a1 = s_start + ( s_end - s_start ).Resize( projectedPos )
1515 + ( s_end - s_start ).Perpendicular().
Resize( halfWidth ) * trackSide;
1516 pc.
a2 = ( pc.
a1 - pointPos ).Resize(
radius ) + pointPos;
1517 pc.
weight = ( pc.
a2 - pc.
a1 ).SquaredEuclideanNorm();
1519 if( pc.
weight <= aMaxSquaredWeight )
1530 double aMaxSquaredWeight )
const
1532 std::vector<PATH_CONNECTION>
result;
1537 double circleRadius = this->
GetRadius();
1545 if( ( circlePos - arcPos ).EuclideanNorm() > arcRadius + circleRadius )
1547 const std::vector<PATH_CONNECTION>& pcs = this->
Paths( csc, aMaxWeight, aMaxSquaredWeight );
1549 if( pcs.size() == 1 )
1555 result.push_back( pcs[0] );
1567 std::vector<PATH_CONNECTION> pcs1 = this->
Paths( csc1, aMaxWeight, aMaxSquaredWeight );
1568 std::vector<PATH_CONNECTION> pcs2 = this->
Paths( csc2, aMaxWeight, aMaxSquaredWeight );
1572 if( !bestPath || ( ( bestPath->
weight > pc.weight ) && ( pc.weight > 0 ) ) )
1578 if( !bestPath || ( ( bestPath->
weight > pc.weight ) && ( pc.weight > 0 ) ) )
1586 if( ( circlePos - arcPos ).SquaredEuclideanNorm() < arcRadius * arcRadius )
1588 if( circlePos != arcPos )
1594 pc3.
weight = std::max( arcRadius - ( circlePos - arcPos ).EuclideanNorm() - circleRadius, 0.0 );
1595 pc3.
a1 = circlePos + ( circlePos - arcPos ).Resize( circleRadius );
1596 pc3.
a2 = arcPos + ( circlePos - arcPos ).Resize( arcRadius - aS2.
GetWidth() / 2 );
1604 if( bestPath && bestPath->
weight > 0 )
1606 result.push_back( *bestPath );
1614 double aMaxSquaredWeight )
const
1616 std::vector<PATH_CONNECTION>
result;
1620 double halfWidth1 = this->
GetWidth() / 2;
1624 double halfWidth2 = aS2.
GetWidth() / 2;
1629 std::vector<PATH_CONNECTION> pcs;
1630 pcs = this->
Paths( csc, aMaxWeight, aMaxSquaredWeight );
1632 if( pcs.size() < 1 )
1638 if( pcs.size() > 0 )
1640 circlePoint = pcs[0].a1;
1644 if( testAngle < aS2.
GetEndAngle() && pcs.size() > 0 )
1646 result.push_back( pcs[0] );
1652 std::optional<PATH_CONNECTION> bestPath;
1656 if( !bestPath || ( bestPath->weight > pc.weight ) )
1662 if( !bestPath || ( bestPath->weight > pc.weight ) )
1671 if( !bestPath || ( bestPath->weight > pc.weight ) )
1678 if( !bestPath || ( bestPath->weight > pc.weight ) )
1683 result.push_back( *bestPath );
1702 t = std::max( 0.0, std::min( 1.0, t ) );
1704 return A + ( AB * t );
1710 double aMaxSquaredWeight )
const
1712 std::vector<PATH_CONNECTION>
result;
1716 double halfWidth1 = this->
GetWidth() / 2;
1721 double halfWidth2 = aS2.
GetWidth() / 2;
1729 double dist1 = ( P1 -
C ).SquaredEuclideanNorm();
1730 double dist2 = ( P2 -
D ).SquaredEuclideanNorm();
1731 double dist3 = ( P3 - A ).SquaredEuclideanNorm();
1732 double dist4 = ( P4 -
B ).SquaredEuclideanNorm();
1735 double min_dist = dist1;
1739 if( dist2 < min_dist )
1746 if( dist3 < min_dist )
1753 if( dist4 < min_dist )
1762 pc.
a1 = closest1 + ( closest2 - closest1 ).Resize( halfWidth1 );
1763 pc.
a2 = closest2 + ( closest1 - closest2 ).Resize( halfWidth2 );
1764 pc.
weight = std::max( sqrt( min_dist ) - halfWidth1 - halfWidth2, 0.0 );
1766 if( pc.
weight <= aMaxWeight )
1774 double aMaxSquaredWeight )
const
1776 std::vector<PATH_CONNECTION>
result;
1782 double dist = ( center1 - center2 ).EuclideanNorm();
1786 double reach = aMaxWeight + R1;
1788 if( dist == 0 || dist * dist > reach * reach + R2 * R2 )
1797 double weight = std::max( R2 - dist - R1, 0.0 );
1799 if( weight > aMaxWeight )
1802 double radialAngle = circleAngle +
M_PI;
1803 double cx = cos( radialAngle );
1804 double cy = sin( radialAngle );
1820 double weight = sqrt( dist * dist - R2 * R2 ) - R1;
1821 double theta = asin( R2 / dist );
1822 double psi = acos( R2 / dist );
1824 if( weight > aMaxWeight )
1828 pc.
weight = std::max( weight, 0.0 );
1833 pStart =
VECTOR2I( R1 * cos( theta + circleAngle ), R1 * sin( theta + circleAngle ) );
1835 pEnd =
VECTOR2I( -R2 * cos( psi - circleAngle ), R2 * sin( psi - circleAngle ) );
1842 pStart =
VECTOR2I( R1 * cos( -theta + circleAngle ), R1 * sin( -theta + circleAngle ) );
1844 pEnd =
VECTOR2I( -R2 * cos( -psi - circleAngle ), R2 * sin( -psi - circleAngle ) );
1856 double aMaxSquaredWeight )
const
1858 std::vector<PATH_CONNECTION>
result;
1874 if( ( point - arcCenter ).SquaredEuclideanNorm() >
radius *
radius )
1877 return circle.Paths( aS2, aMaxWeight, aMaxSquaredWeight );
1882 pc.
weight = std::max( (
radius - width / 2 ) - ( point - arcCenter ).EuclideanNorm(), 0.0 );
1883 pc.
a1 = ( point - arcCenter ).Resize(
radius - width / 2 ) + arcCenter;
1896 if( ( point - this->
GetStartPoint() ).SquaredEuclideanNorm()
1897 > ( point - this->
GetEndPoint() ).SquaredEuclideanNorm() )
1907 return circle.Paths( aS2, aMaxWeight, aMaxSquaredWeight );
1913 double aMaxSquaredWeight )
const
1915 std::vector<PATH_CONNECTION>
result;
1924 bestPath.
weight = std::numeric_limits<double>::infinity();
1933 for(
const std::vector<PATH_CONNECTION>& pcs : { csc1.
Paths( csc2, aMaxWeight, aMaxSquaredWeight ),
1934 this->
Paths( csc2, aMaxWeight, aMaxSquaredWeight ),
1935 csc1.
Paths( aS2, aMaxWeight, aMaxSquaredWeight ) } )
1947 for(
const std::vector<PATH_CONNECTION>& pcs : { this->
Paths( csc5, aMaxWeight, aMaxSquaredWeight ),
1948 this->
Paths( csc6, aMaxWeight, aMaxSquaredWeight ),
1949 csc3.
Paths( aS2, aMaxWeight, aMaxSquaredWeight ),
1950 csc4.
Paths( aS2, aMaxWeight, aMaxSquaredWeight ) } )
1954 if( bestPath.
weight > pc.weight )
1959 if( bestPath.
weight != std::numeric_limits<double>::infinity() )
1960 result.push_back( bestPath );
1967 std::vector<VECTOR2I>* aIntersectPoints )
1969 SEG segment( p1, p2 );
1972 std::vector<VECTOR2I> intersectionPoints;
1977 std::visit( visitor, geom1 );
1985 return ( a - b ).SquaredEuclideanNorm() <= toleranceSq;
1988 std::vector<VECTOR2I> filtered;
1990 for(
const VECTOR2I& ip : intersectionPoints )
1992 if( !coincident( ip, p1 ) && !coincident( ip, p2 ) )
1993 filtered.push_back( ip );
1996 if( aIntersectPoints )
1999 aIntersectPoints->push_back( point );
2002 return filtered.size() > 0;
2006 const std::vector<BOARD_ITEM*>& aBe,
2007 const std::vector<const BOARD_ITEM*>& aDontTestAgainst,
2008 int aMinGrooveWidth )
2010 std::vector<VECTOR2I> intersectionPoints;
2011 bool TestGrooveWidth = aMinGrooveWidth > 0;
2015 if( count( aDontTestAgainst.begin(), aDontTestAgainst.end(), be ) > 0 )
2028 if( intersects && !TestGrooveWidth )
2050 bool intersects =
false;
2055 intersectionPoints );
2057 intersectionPoints );
2063 intersectionPoints );
2065 intersectionPoints );
2068 if( intersects && !TestGrooveWidth )
2074 struct CornerArcRange
2081 std::vector<CornerArcRange> arcs;
2088 arcs.push_back( { { x1 + r, y1 + r },
2091 arcs.push_back( { { x2 - r, y1 + r },
2095 else if( w == 2 * r )
2098 arcs.push_back( { { x1 + r, y1 + r },
2101 arcs.push_back( { { x1 + r, y2 - r },
2119 for(
const CornerArcRange& ca : arcs )
2122 ca.startAngle, ca.endAngle,
2123 &intersectionPoints );
2125 if( arcIntersects && !TestGrooveWidth )
2136 bool intersects =
false;
2142 if( intersects && !TestGrooveWidth )
2153 if( points.size() < 2 )
2156 VECTOR2I prevPoint = points.back();
2158 bool intersects =
false;
2166 if( intersects && !TestGrooveWidth )
2179 if( intersects && !TestGrooveWidth )
2195 if( intersects && !TestGrooveWidth )
2206 if( intersectionPoints.size() <= 0 )
2209 if( intersectionPoints.size() % 2 != 0 )
2212 int minx = intersectionPoints[0].x;
2213 int maxx = intersectionPoints[0].x;
2214 int miny = intersectionPoints[0].y;
2215 int maxy = intersectionPoints[0].y;
2217 for(
const VECTOR2I& v : intersectionPoints )
2219 minx = std::min( v.x, minx );
2220 maxx = std::max( v.x, maxx );
2221 miny = std::min( v.y, miny );
2222 maxy = std::max( v.y, maxy );
2225 if( abs( maxx - minx ) > abs( maxy - miny ) )
2227 std::sort( intersectionPoints.begin(), intersectionPoints.end(),
2235 std::sort( intersectionPoints.begin(), intersectionPoints.end(),
2242 int GVSquared = aMinGrooveWidth * aMinGrooveWidth;
2244 for(
size_t i = 0; i < intersectionPoints.size(); i += 2 )
2246 if( intersectionPoints[i].SquaredDistance( intersectionPoints[i + 1] ) > GVSquared )
2256 double maxWeight = aMaxWeight;
2257 double maxWeightSquared = maxWeight * maxWeight;
2258 std::vector<PATH_CONNECTION>
result;
2277 if( cuarc1 && cuarc2 )
2278 return cuarc1->
Paths( *cuarc2, maxWeight, maxWeightSquared );
2279 if( cuarc1 && cucircle2 )
2280 return cuarc1->
Paths( *cucircle2, maxWeight, maxWeightSquared );
2281 if( cuarc1 && cusegment2 )
2282 return cuarc1->
Paths( *cusegment2, maxWeight, maxWeightSquared );
2283 if( cucircle1 && cuarc2 )
2284 return cucircle1->
Paths( *cuarc2, maxWeight, maxWeightSquared );
2285 if( cucircle1 && cucircle2 )
2286 return cucircle1->
Paths( *cucircle2, maxWeight, maxWeightSquared );
2287 if( cucircle1 && cusegment2 )
2288 return cucircle1->
Paths( *cusegment2, maxWeight, maxWeightSquared );
2289 if( cusegment1 && cuarc2 )
2290 return cusegment1->
Paths( *cuarc2, maxWeight, maxWeightSquared );
2291 if( cusegment1 && cucircle2 )
2292 return cusegment1->
Paths( *cucircle2, maxWeight, maxWeightSquared );
2293 if( cusegment1 && cusegment2 )
2294 return cusegment1->
Paths( *cusegment2, maxWeight, maxWeightSquared );
2299 if( cuarc1 && bearc2 )
2300 return cuarc1->
Paths( *bearc2, maxWeight, maxWeightSquared );
2301 if( cuarc1 && becircle2 )
2302 return cuarc1->
Paths( *becircle2, maxWeight, maxWeightSquared );
2303 if( cuarc1 && bepoint2 )
2304 return cuarc1->
Paths( *bepoint2, maxWeight, maxWeightSquared );
2305 if( cucircle1 && bearc2 )
2306 return cucircle1->
Paths( *bearc2, maxWeight, maxWeightSquared );
2307 if( cucircle1 && becircle2 )
2308 return cucircle1->
Paths( *becircle2, maxWeight, maxWeightSquared );
2309 if( cucircle1 && bepoint2 )
2310 return cucircle1->
Paths( *bepoint2, maxWeight, maxWeightSquared );
2311 if( cusegment1 && bearc2 )
2312 return cusegment1->
Paths( *bearc2, maxWeight, maxWeightSquared );
2313 if( cusegment1 && becircle2 )
2314 return cusegment1->
Paths( *becircle2, maxWeight, maxWeightSquared );
2315 if( cusegment1 && bepoint2 )
2316 return cusegment1->
Paths( *bepoint2, maxWeight, maxWeightSquared );
2320 if( cuarc2 && bearc1 )
2321 return bearc1->
Paths( *cuarc2, maxWeight, maxWeightSquared );
2322 if( cuarc2 && becircle1 )
2323 return becircle1->
Paths( *cuarc2, maxWeight, maxWeightSquared );
2324 if( cuarc2 && bepoint1 )
2325 return bepoint1->
Paths( *cuarc2, maxWeight, maxWeightSquared );
2326 if( cucircle2 && bearc1 )
2327 return bearc1->
Paths( *cucircle2, maxWeight, maxWeightSquared );
2328 if( cucircle2 && becircle1 )
2329 return becircle1->
Paths( *cucircle2, maxWeight, maxWeightSquared );
2330 if( cucircle2 && bepoint1 )
2331 return bepoint1->
Paths( *cucircle2, maxWeight, maxWeightSquared );
2332 if( cusegment2 && bearc1 )
2333 return bearc1->
Paths( *cusegment2, maxWeight, maxWeightSquared );
2334 if( cusegment2 && becircle1 )
2335 return becircle1->
Paths( *cusegment2, maxWeight, maxWeightSquared );
2336 if( cusegment2 && bepoint1 )
2337 return bepoint1->
Paths( *cusegment2, maxWeight, maxWeightSquared );
2342 if( bearc1 && bearc2 )
2343 return bearc1->
Paths( *bearc2, maxWeight, maxWeightSquared );
2344 if( bearc1 && becircle2 )
2345 return bearc1->
Paths( *becircle2, maxWeight, maxWeightSquared );
2346 if( bearc1 && bepoint2 )
2347 return bearc1->
Paths( *bepoint2, maxWeight, maxWeightSquared );
2348 if( becircle1 && bearc2 )
2349 return becircle1->
Paths( *bearc2, maxWeight, maxWeightSquared );
2350 if( becircle1 && becircle2 )
2351 return becircle1->
Paths( *becircle2, maxWeight, maxWeightSquared );
2352 if( becircle1 && bepoint2 )
2353 return becircle1->
Paths( *bepoint2, maxWeight, maxWeightSquared );
2354 if( bepoint1 && bearc2 )
2355 return bepoint1->
Paths( *bearc2, maxWeight, maxWeightSquared );
2356 if( bepoint1 && becircle2 )
2357 return bepoint1->
Paths( *becircle2, maxWeight, maxWeightSquared );
2358 if( bepoint1 && bepoint2 )
2359 return bepoint1->
Paths( *bepoint2, maxWeight, maxWeightSquared );
2365 std::vector<std::shared_ptr<GRAPH_CONNECTION>>& aResult )
2367 if( !aFrom || !aTo )
2374 std::unordered_map<GRAPH_NODE*, double> distances;
2375 std::unordered_map<GRAPH_NODE*, GRAPH_NODE*> previous;
2380 using QUEUE_ITEM = std::pair<double, GRAPH_NODE*>;
2382 auto cmp = [](
const QUEUE_ITEM& aLeft,
const QUEUE_ITEM& aRight )
2384 if( aLeft.first == aRight.first )
2385 return aLeft.second > aRight.second;
2386 return aLeft.first > aRight.first;
2388 std::priority_queue<QUEUE_ITEM, std::vector<QUEUE_ITEM>,
decltype( cmp )> pq( cmp );
2391 for(
const std::shared_ptr<GRAPH_NODE>& node :
m_nodes )
2393 if( node !=
nullptr )
2394 distances[node.get()] = std::numeric_limits<double>::infinity();
2397 distances[aFrom.get()] = 0.0;
2398 distances[aTo.get()] = std::numeric_limits<double>::infinity();
2399 pq.push( { 0.0, aFrom.get() } );
2402 while( !pq.empty() )
2404 auto [dist, current] = pq.top();
2409 if( dist > distances[current] )
2412 if( current == aTo.get() )
2418 for(
const std::shared_ptr<GRAPH_CONNECTION>& connection : current->m_node_conns )
2420 GRAPH_NODE* neighbor = ( connection->n1 ).get() == current ? ( connection->n2 ).get()
2421 : ( connection->n1 ).get();
2427 if( connection->m_path.weight < 0.0 )
2429 wxLogTrace(
"CREEPAGE",
"Negative weight connection found. Ignoring connection." );
2433 double alt = distances[current] + connection->m_path.weight;
2435 if( alt < distances[neighbor] )
2437 distances[neighbor] = alt;
2438 previous[neighbor] = current;
2439 pq.push( { alt, neighbor } );
2444 double pathWeight = distances[aTo.get()];
2447 if( pathWeight == std::numeric_limits<double>::infinity() )
2448 return std::numeric_limits<double>::infinity();
2453 while( step != aFrom.get() )
2457 for(
const std::shared_ptr<GRAPH_CONNECTION>& node_conn : step->
m_node_conns )
2459 if( ( ( node_conn->n1 ).get() == prevNode && ( node_conn->n2 ).get() == step )
2460 || ( ( node_conn->n1 ).get() == step && ( node_conn->n2 ).get() == prevNode ) )
2462 aResult.push_back( node_conn );
2475 std::unique_ptr<CREEP_SHAPE> newshape;
2480 switch( aShape.
Type() )
2485 newshape = std::make_unique<CU_SHAPE_SEGMENT>( segment.
GetSeg().
A, segment.
GetSeg().
B,
2493 newshape = std::make_unique<CU_SHAPE_CIRCLE>(
circle.GetCenter(),
circle.GetRadius() );
2506 auto cuArc = std::make_unique<CU_SHAPE_ARC>( edaArc.
getCenter(), edaArc.
GetRadius(), alpha, beta,
2509 newshape = std::move( cuArc );
2517 for(
const SHAPE* subshape : (
static_cast<const SHAPE_COMPOUND*
>( &aShape )->Shapes() ) )
2522 if( !( ( subshape->Type() ==
SH_RECT ) && ( nbShapes == 5 ) ) )
2523 Addshape( *subshape, aConnectTo, aParent );
2535 const SEG object = *it;
2537 Addshape( segment, aConnectTo, aParent );
2552 Addshape( segment, aConnectTo, aParent );
2575 if( point != prevPoint )
2607 std::shared_ptr<GRAPH_NODE> gnShape =
nullptr;
2609 newshape->SetParent( aParent );
2611 switch( aShape.
Type() )
2622 gnShape->m_net = aConnectTo->m_net;
2623 std::shared_ptr<GRAPH_CONNECTION> gc =
AddConnection( gnShape, aConnectTo );
2626 gc->m_path.m_show =
false;
2631 const std::set<int>* aRelevantNets )
2633 auto irrelevantPair = [&](
const std::shared_ptr<GRAPH_NODE>& gn1,
2634 const std::shared_ptr<GRAPH_NODE>& gn2 ) ->
bool
2636 return aRelevantNets && gn1->m_parent && gn2->m_parent && gn1->m_parent->IsConductive()
2637 && gn2->m_parent->IsConductive() && !aRelevantNets->count( gn1->m_net )
2638 && !aRelevantNets->count( gn2->m_net );
2641 std::vector<std::shared_ptr<GRAPH_NODE>> nodes;
2642 std::mutex nodes_lock;
2645 std::vector<CREEPAGE_TRACK_ENTRY*> trackEntries;
2646 TRACK_RTREE::Builder trackBuilder;
2654 std::shared_ptr<SHAPE> sh = track->GetEffectiveShape();
2659 entry->
segment =
SEG( track->GetStart(), track->GetEnd() );
2660 entry->
layer = aLayer;
2661 entry->
halfWidth = track->GetWidth() / 2;
2662 entry->
track = track;
2664 BOX2I bbox = track->GetBoundingBox();
2665 int minCoords[2] = { bbox.
GetX(), bbox.
GetY() };
2667 trackBuilder.Add( minCoords, maxCoords, entry );
2668 trackEntries.push_back( entry );
2676 std::copy_if(
m_nodes.begin(),
m_nodes.end(), std::back_inserter( nodes ),
2677 [&](
const std::shared_ptr<GRAPH_NODE>& gn )
2679 return gn && gn->m_parent && gn->m_connectDirectly && ( gn->m_type != GRAPH_NODE::TYPE::VIRTUAL );
2682 std::sort( nodes.begin(), nodes.end(),
2683 [](
const std::shared_ptr<GRAPH_NODE>& gn1,
const std::shared_ptr<GRAPH_NODE>& gn2 )
2685 return gn1->m_parent < gn2->m_parent
2686 || ( gn1->m_parent == gn2->m_parent && gn1->m_net < gn2->m_net );
2691 std::unordered_map<const BOARD_ITEM*, std::unordered_map<int, std::vector<std::shared_ptr<GRAPH_NODE>>>> parent_net_groups;
2692 std::unordered_map<const BOARD_ITEM*, BOX2I> parent_bboxes;
2693 std::vector<const BOARD_ITEM*> parent_keys;
2695 for(
const auto& gn : nodes )
2697 const BOARD_ITEM* parent = gn->m_parent->GetParent();
2699 if( parent_net_groups[parent].
empty() )
2701 parent_keys.push_back( parent );
2706 parent_net_groups[parent][gn->m_net].push_back( gn );
2710 std::vector<std::pair<std::shared_ptr<GRAPH_NODE>, std::shared_ptr<GRAPH_NODE>>> work_items;
2715 int64_t maxDist =
static_cast<int64_t
>( aMaxWeight );
2723 std::vector<ParentEntry> parentEntries;
2725 for(
const auto* parent : parent_keys )
2730 entry.parent = parent;
2731 entry.bbox = parent_bboxes[parent];
2732 parentEntries.push_back( entry );
2738 for( ParentEntry& entry : parentEntries )
2740 int minCoords[2] = { entry.bbox.GetLeft(), entry.bbox.GetTop() };
2741 int maxCoords[2] = { entry.bbox.GetRight(), entry.bbox.GetBottom() };
2742 parentBuilder.
Add( minCoords, maxCoords, &entry );
2745 auto parentIndex = parentBuilder.
Build();
2748 std::mutex work_items_lock;
2750 auto searchParent = [&](
size_t i ) ->
bool
2752 const ParentEntry& entry1 = parentEntries[i];
2754 BOX2I bbox1 = entry1.bbox;
2756 std::vector<std::pair<std::shared_ptr<GRAPH_NODE>, std::shared_ptr<GRAPH_NODE>>> localWorkItems;
2759 int searchMin[2] = { bbox1.
GetLeft() - (int) maxDist, bbox1.
GetTop() - (int) maxDist };
2760 int searchMax[2] = { bbox1.
GetRight() + (int) maxDist, bbox1.
GetBottom() + (int) maxDist };
2762 auto parentVisitor = [&]( ParentEntry* entry2 ) ->
bool
2767 if( parent1 >= parent2 )
2771 BOX2I bbox2 = entry2->bbox;
2773 int64_t bboxDistX = 0;
2780 int64_t bboxDistY = 0;
2787 int64_t bboxDistSq = bboxDistX * bboxDistX + bboxDistY * bboxDistY;
2789 if( bboxDistSq > maxDist * maxDist )
2793 auto it1 = parent_net_groups.find( parent1 );
2794 auto it2 = parent_net_groups.find( parent2 );
2796 if( it1 == parent_net_groups.end() || it2 == parent_net_groups.end() )
2799 for(
const auto& [net1, nodes1] : it1->second )
2801 for(
const auto& [net2, nodes2] : it2->second )
2804 if( net1 == net2 && !nodes1.empty() && !nodes2.empty() )
2806 if( nodes1[0]->m_parent->IsConductive()
2807 && nodes2[0]->m_parent->IsConductive() )
2811 for(
const auto& gn1 : nodes1 )
2813 for(
const auto& gn2 : nodes2 )
2815 VECTOR2I pos1 = gn1->m_parent->GetPos();
2816 VECTOR2I pos2 = gn2->m_parent->GetPos();
2817 int r1 = gn1->m_parent->GetRadius();
2818 int r2 = gn2->m_parent->GetRadius();
2820 int64_t centerDistSq = ( pos1 - pos2 ).SquaredEuclideanNorm();
2821 double threshold = aMaxWeight + r1 + r2;
2822 double thresholdSq = threshold * threshold;
2824 if( (
double) centerDistSq > thresholdSq )
2827 if( irrelevantPair( gn1, gn2 ) )
2830 localWorkItems.push_back( { gn1, gn2 } );
2839 parentIndex.Search( searchMin, searchMax, parentVisitor );
2842 if( !localWorkItems.empty() )
2844 std::lock_guard<std::mutex> lock( work_items_lock );
2845 work_items.insert( work_items.end(), localWorkItems.begin(), localWorkItems.end() );
2852 if( parentEntries.size() > 100 &&
tp.get_tasks_total() <
tp.get_thread_count() - 4 )
2854 auto ret =
tp.submit_loop( 0, parentEntries.size(), searchParent );
2856 for(
auto& r : ret )
2864 for(
size_t i = 0; i < parentEntries.size(); ++i )
2873 for(
const auto& [parent, net_groups] : parent_net_groups )
2875 std::vector<std::shared_ptr<GRAPH_NODE>> sameParentNodes;
2877 for(
const auto& [net, nodeList] : net_groups )
2878 sameParentNodes.insert( sameParentNodes.end(), nodeList.begin(), nodeList.end() );
2880 for(
size_t i = 0; i < sameParentNodes.size(); i++ )
2882 for(
size_t j = i + 1; j < sameParentNodes.size(); j++ )
2884 auto& gn1 = sameParentNodes[i];
2885 auto& gn2 = sameParentNodes[j];
2888 if( gn1->m_parent == gn2->m_parent )
2892 if( gn1->m_parent->IsConductive() && gn2->m_parent->IsConductive()
2893 && gn1->m_net == gn2->m_net )
2898 VECTOR2I pos1 = gn1->m_parent->GetPos();
2899 VECTOR2I pos2 = gn2->m_parent->GetPos();
2900 int r1 = gn1->m_parent->GetRadius();
2901 int r2 = gn2->m_parent->GetRadius();
2903 int64_t centerDistSq = ( pos1 - pos2 ).SquaredEuclideanNorm();
2904 double threshold = aMaxWeight + r1 + r2;
2905 double thresholdSq = threshold * threshold;
2907 if( (
double) centerDistSq > thresholdSq )
2910 if( irrelevantPair( gn1, gn2 ) )
2913 work_items.push_back( { gn1, gn2 } );
2918 auto processWorkItems =
2919 [&](
size_t idx ) ->
bool
2921 auto& [gn1, gn2] = work_items[idx];
2929 std::vector<const BOARD_ITEM*> IgnoreForTest;
2940 IgnoreForTest.push_back( shape1->
GetParent() );
2943 IgnoreForTest.push_back( shape2->
GetParent() );
2953 std::shared_ptr<GRAPH_NODE> connect1 = gn1, connect2 = gn2;
2954 std::lock_guard<std::mutex> lock( nodes_lock );
2957 if( gn1->m_parent->GetType() != CREEP_SHAPE::TYPE::POINT_TYPE )
2960 gnt1->m_connectDirectly =
false;
2963 if( gn1->m_parent->IsConductive() )
2965 if( std::shared_ptr<GRAPH_CONNECTION> gc =
AddConnection( gn1, gnt1 ) )
2966 gc->m_path.m_show =
false;
2971 if( gn2->m_parent->GetType() != CREEP_SHAPE::TYPE::POINT_TYPE )
2974 gnt2->m_connectDirectly =
false;
2977 if( gn2->m_parent->IsConductive() )
2979 if( std::shared_ptr<GRAPH_CONNECTION> gc =
AddConnection( gn2, gnt2 ) )
2980 gc->m_path.m_show =
false;
2992 if(
tp.get_tasks_total() >=
tp.get_thread_count() - 4 )
2994 for(
size_t ii = 0; ii < work_items.size(); ii++ )
2995 processWorkItems( ii );
2999 auto ret =
tp.submit_loop( 0, work_items.size(), processWorkItems );
3001 for(
size_t ii = 0; ii < ret.size(); ii++ )
3008 while( r.wait_for( std::chrono::milliseconds( 100 ) ) != std::future_status::ready ){}
3023 for(
const std::shared_ptr<GRAPH_NODE>& gn : { aGc->n1, aGc->n2 } )
3026 gn->m_node_conns.erase( aGc );
3036 for(
size_t i = aConnectionCount; i < vectorSize; i++ )
3040 m_nodes.resize( aNodeCount,
nullptr );
3045 for(
size_t i = 0; i < aNodeCount; ++i )
3056 std::shared_ptr<GRAPH_NODE> gn =
FindNode( aType, parent, pos );
3061 gn = std::make_shared<GRAPH_NODE>( aType, parent, pos );
3071 std::shared_ptr<GRAPH_NODE> gn = std::make_shared<GRAPH_NODE>( GRAPH_NODE::TYPE::VIRTUAL,
nullptr );
3079 std::shared_ptr<GRAPH_NODE>& aN2,
3085 wxASSERT_MSG( ( aN1 != aN2 ),
"Creepage: a connection connects a node to itself" );
3087 std::shared_ptr<GRAPH_CONNECTION> gc = std::make_shared<GRAPH_CONNECTION>( aN1, aN2, aPc );
3089 aN1->m_node_conns.insert( gc );
3090 aN2->m_node_conns.insert( gc );
3097 std::shared_ptr<GRAPH_NODE>& aN2 )
3114 auto it =
m_nodeset.find( std::make_shared<GRAPH_NODE>( aType, aParent, aPos ) );
3127 virtualNode->m_net = aNetCode;
3131 for(
PAD*
pad : footprint->Pads() )
3133 if(
pad->GetNetCode() != aNetCode || !
pad->IsOnLayer( aLayer ) )
3136 if(
pad->HasCopperRemoved( aLayer ) )
3139 if( std::shared_ptr<SHAPE> padShape =
pad->GetEffectiveShape( aLayer ) )
3146 if( track->GetNetCode() != aNetCode || !track->IsOnLayer( aLayer ) )
3152 if( std::shared_ptr<SHAPE> shape = track->GetEffectiveShape() )
3153 Addshape( *shape, virtualNode, track );
3159 if( zone->GetIsRuleArea() )
3162 if( zone->GetNetCode() != aNetCode || !zone->IsOnLayer( aLayer ) )
3165 if( std::shared_ptr<SHAPE> shape = zone->GetEffectiveShape( aLayer ) )
3166 Addshape( *shape, virtualNode, zone );
3173 if( drawing->IsConnected() )
3181 Addshape( *shape, virtualNode, bci );
Creepage: a board edge arc.
std::pair< bool, bool > IsThereATangentPassingThroughPoint(const BE_SHAPE_POINT aPoint) const
EDA_ANGLE GetStartAngle() const override
int GetRadius() const override
BE_SHAPE_ARC(VECTOR2I aPos, int aRadius, EDA_ANGLE aStartAngle, EDA_ANGLE aEndAngle, VECTOR2D aStartPoint, VECTOR2D aEndPoint)
VECTOR2I GetStartPoint() const override
std::vector< PATH_CONNECTION > Paths(const BE_SHAPE_POINT &aS2, double aMaxWeight, double aMaxSquaredWeight) const override
void ConnectChildren(std::shared_ptr< GRAPH_NODE > &a1, std::shared_ptr< GRAPH_NODE > &a2, CREEPAGE_GRAPH &aG) const override
EDA_ANGLE GetEndAngle() const override
VECTOR2I GetEndPoint() const override
EDA_ANGLE AngleBetweenStartAndEnd(const VECTOR2I aPoint) const
Creepage: a board edge circle.
int GetRadius() const override
BE_SHAPE_CIRCLE(VECTOR2I aPos=VECTOR2I(0, 0), int aRadius=0)
void ShortenChildDueToGV(std::shared_ptr< GRAPH_NODE > &a1, std::shared_ptr< GRAPH_NODE > &a2, CREEPAGE_GRAPH &aG, double aNormalWeight) const
std::vector< PATH_CONNECTION > Paths(const BE_SHAPE_POINT &aS2, double aMaxWeight, double aMaxSquaredWeight) const override
void ConnectChildren(std::shared_ptr< GRAPH_NODE > &a1, std::shared_ptr< GRAPH_NODE > &a2, CREEPAGE_GRAPH &aG) const override
Creepage: a board edge point.
BE_SHAPE_POINT(VECTOR2I aPos)
void ConnectChildren(std::shared_ptr< GRAPH_NODE > &a1, std::shared_ptr< GRAPH_NODE > &a2, CREEPAGE_GRAPH &aG) const override
std::vector< PATH_CONNECTION > Paths(const BE_SHAPE_POINT &aS2, double aMaxWeight, double aMaxSquaredWeight) const override
A base class derived from BOARD_ITEM for items that can be connected and have a net,...
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
virtual bool IsOnLayer(PCB_LAYER_ID aLayer) const
Test to see if this object is on the given layer.
virtual std::shared_ptr< SHAPE > GetEffectiveShape(PCB_LAYER_ID aLayer=UNDEFINED_LAYER, FLASHING aFlash=FLASHING::DEFAULT, DRC_CONSTRAINT_T aUsage=NULL_CONSTRAINT) const
Some pad shapes can be complex (rounded/chamfered rectangle), even without considering custom shapes.
Information pertinent to a Pcbnew printed circuit board.
const std::vector< PAD * > GetPads() const
Return a reference to a list of all the pads.
const FOOTPRINTS & Footprints() const
BOARD_DESIGN_SETTINGS & GetDesignSettings()
const DRAWINGS & Drawings() const
constexpr coord_type GetY() const
constexpr coord_type GetX() const
constexpr coord_type GetLeft() const
constexpr coord_type GetRight() const
constexpr coord_type GetTop() const
constexpr coord_type GetBottom() const
Represent basic circle geometry with utility geometry functions.
A graph with nodes and connections for creepage calculation.
std::shared_ptr< GRAPH_NODE > AddNode(GRAPH_NODE::TYPE aType, CREEP_SHAPE *aParent=nullptr, const VECTOR2I &aPos=VECTOR2I())
std::shared_ptr< GRAPH_CONNECTION > AddConnection(std::shared_ptr< GRAPH_NODE > &aN1, std::shared_ptr< GRAPH_NODE > &aN2, const PATH_CONNECTION &aPc)
void SetTarget(double aTarget)
double Solve(std::shared_ptr< GRAPH_NODE > &aFrom, std::shared_ptr< GRAPH_NODE > &aTo, std::vector< std::shared_ptr< GRAPH_CONNECTION > > &aResult)
void Addshape(const SHAPE &aShape, std::shared_ptr< GRAPH_NODE > &aConnectTo, BOARD_ITEM *aParent=nullptr)
void GeneratePaths(double aMaxWeight, PCB_LAYER_ID aLayer, const std::set< int > *aRelevantNets=nullptr)
Generate creepage paths between graph nodes.
void TransformEdgeToCreepShapes()
std::shared_ptr< GRAPH_NODE > AddNodeVirtual()
bool m_hasOverlappingCutouts
SHAPE_POLY_SET * m_boardOutline
void TransformCreepShapesToNodes(const std::vector< std::unique_ptr< CREEP_SHAPE > > &aShapes)
void RemoveDuplicatedShapes()
void TruncateToPrefix(size_t aNodeCount, size_t aConnectionCount)
Remove every node and connection added after the given prefix sizes, then rebuild the node lookup set...
std::vector< BOARD_ITEM * > m_boardEdge
double m_creepageTargetSquared
std::vector< std::unique_ptr< CREEP_SHAPE > > m_shapeCollection
std::unordered_set< std::shared_ptr< GRAPH_NODE >, GraphNodeHash, GraphNodeEqual > m_nodeset
std::vector< std::shared_ptr< GRAPH_NODE > > m_nodes
std::vector< std::shared_ptr< GRAPH_CONNECTION > > m_connections
std::shared_ptr< GRAPH_NODE > AddNetElements(int aNetCode, PCB_LAYER_ID aLayer, int aMaxCreepage)
std::shared_ptr< GRAPH_NODE > FindNode(GRAPH_NODE::TYPE aType, CREEP_SHAPE *aParent, const VECTOR2I &aPos)
void detachConnection(const std::shared_ptr< GRAPH_CONNECTION > &aGc)
A class used to represent the shapes for creepage calculation.
CREEP_SHAPE::TYPE GetType() const
virtual int GetRadius() const
const BOARD_ITEM * GetParent() const
virtual void ConnectChildren(std::shared_ptr< GRAPH_NODE > &a1, std::shared_ptr< GRAPH_NODE > &a2, CREEPAGE_GRAPH &aG) const
Creepage: a conductive arc.
VECTOR2I GetStartPoint() const override
EDA_ANGLE AngleBetweenStartAndEnd(const VECTOR2I aPoint) const
VECTOR2I GetEndPoint() const override
EDA_ANGLE GetStartAngle() const override
CU_SHAPE_ARC(VECTOR2I aPos, double aRadius, EDA_ANGLE aStartAngle, EDA_ANGLE aEndAngle, VECTOR2D aStartPoint, VECTOR2D aEndPoint)
int GetRadius() const override
EDA_ANGLE GetEndAngle() const override
std::vector< PATH_CONNECTION > Paths(const BE_SHAPE_POINT &aS2, double aMaxWeight, double aMaxSquaredWeight) const override
Creepage: a conductive circle.
int GetRadius() const override
CU_SHAPE_CIRCLE(VECTOR2I aPos, double aRadius=0)
std::vector< PATH_CONNECTION > Paths(const BE_SHAPE_POINT &aS2, double aMaxWeight, double aMaxSquaredWeight) const override
Creepage: a conductive segment.
std::vector< PATH_CONNECTION > Paths(const BE_SHAPE_POINT &aS2, double aMaxWeight, double aMaxSquaredWeight) const override
VECTOR2I GetStart() const
CU_SHAPE_SEGMENT(VECTOR2I aStart, VECTOR2I aEnd, double aWidth=0)
virtual const BOX2I GetBoundingBox() const
Return the orthogonal bounding box of this object for display purposes.
VECTOR2I getCenter() const
std::vector< VECTOR2I > GetPolyPoints() const
Duplicate the polygon outlines into a flat list of VECTOR2I points.
void CalcArcAngles(EDA_ANGLE &aStartAngle, EDA_ANGLE &aEndAngle) const
Calc arc start and end angles such that aStartAngle < aEndAngle.
void RebuildBezierToSegmentsPointsList(int aMaxError)
Rebuild the m_bezierPoints vertex list that approximate the Bezier curve by a list of segments.
const VECTOR2I & GetEnd() const
Return the ending point of the graphic.
const VECTOR2I & GetStart() const
Return the starting point of the graphic.
const std::vector< VECTOR2I > & GetBezierPoints() const
int GetCornerRadius() const
VECTOR2I GetArcMid() const
std::shared_ptr< GRAPH_NODE > n2
void GetShapes(std::vector< PCB_SHAPE > &aShapes)
std::shared_ptr< GRAPH_NODE > n1
std::set< std::shared_ptr< GRAPH_CONNECTION > > m_node_conns
Builder for constructing a PACKED_RTREE from a set of items.
void Add(const ELEMTYPE aMin[NUMDIMS], const ELEMTYPE aMax[NUMDIMS], const DATATYPE &aData)
const BOX2I GetBoundingBox() const override
Return the orthogonal bounding box of this object for display purposes.
void SetCenter(const VECTOR2I &aCenter) override
VECTOR2I GetCenter() const override
This defaults to the center of the bounding box if not overridden.
void SetEnd(const VECTOR2I &aEnd) override
void SetStart(const VECTOR2I &aStart) override
bool HasCopperRemoved(PCB_LAYER_ID aLayer) const
Check whether backdrilling or post-machining left no copper at all on a layer.
int GetWidth() const override
const VECTOR2I & GetP1() const
const VECTOR2I & GetP0() const
SHAPE_TYPE Type() const
Return the type of the shape.
const std::vector< SHAPE * > & Shapes() const
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
int PointCount() const
Return the number of points (vertices) in this line chain.
const VECTOR2I & CLastPoint() const
Return the last point in the line chain.
const std::vector< VECTOR2I > & CPoints() const
Represent a set of closed polygons.
bool PointOnEdge(const VECTOR2I &aP, int aAccuracy=0) const
Check if point aP lies on an edge or vertex of some of the outlines or holes.
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles() const
Return an iterator object, for the aOutline-th outline in the set (with holes).
bool Contains(const VECTOR2I &aP, int aSubpolyIndex=-1, int aAccuracy=0, bool aUseBBoxCaches=false) const
Return true if a given subpolygon contains the point aP.
const SEG & GetSeg() const
int GetWidth() const override
Represent a simple polygon consisting of a zero-thickness closed chain of connected line segments.
const SHAPE_LINE_CHAIN & Vertices() const
Return the list of vertices defining this simple polygon.
An abstract shape on 2D plane.
constexpr extended_type Cross(const VECTOR2< T > &aVector) const
Compute cross product of self with aVector.
constexpr extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
VECTOR2_TRAITS< int32_t >::extended_type extended_type
constexpr VECTOR2< T > Perpendicular() const
Compute the perpendicular vector.
constexpr extended_type Dot(const VECTOR2< T > &aVector) const
Compute dot product of self with aVector.
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Handle a list of polygons defining a copper zone.
static bool empty(const wxTextEntryBase *aCtrl)
VECTOR2I closestPointOnSegment(const VECTOR2I &A, const VECTOR2I &B, const VECTOR2I &P)
bool SegmentIntersectsBoard(const VECTOR2I &aP1, const VECTOR2I &aP2, const std::vector< BOARD_ITEM * > &aBe, const std::vector< const BOARD_ITEM * > &aDontTestAgainst, int aMinGrooveWidth)
std::vector< PATH_CONNECTION > GetPaths(CREEP_SHAPE *aS1, CREEP_SHAPE *aS2, double aMaxWeight)
bool segmentIntersectsArc(const VECTOR2I &p1, const VECTOR2I &p2, const VECTOR2I ¢er, double radius, EDA_ANGLE startAngle, EDA_ANGLE endAngle, std::vector< VECTOR2I > *aIntersectionPoints=nullptr)
bool compareShapes(const CREEP_SHAPE *a, const CREEP_SHAPE *b)
bool segments_intersect(const VECTOR2I &p1, const VECTOR2I &q1, const VECTOR2I &p2, const VECTOR2I &q2, std::vector< VECTOR2I > &aIntersectionPoints)
void BuildCreepageBoardEdges(BOARD &aBoard, std::vector< BOARD_ITEM * > &aVector, std::vector< std::unique_ptr< PCB_SHAPE > > &aOwned, const std::set< const BOARD_ITEM * > *aExclude)
Collect the board-edge items used by the creepage graph.
bool areEquivalent(const CREEP_SHAPE *a, const CREEP_SHAPE *b)
bool segmentIntersectsCircle(const VECTOR2I &p1, const VECTOR2I &p2, const VECTOR2I ¢er, double radius, std::vector< VECTOR2I > *aIntersectPoints)
KIRTREE::PACKED_RTREE< CREEPAGE_TRACK_ENTRY *, int, 2 > TRACK_RTREE
static constexpr EDA_ANGLE ANGLE_0
static constexpr EDA_ANGLE ANGLE_360
@ RECTANGLE
Use RECTANGLE instead of RECT to avoid collision in a Windows header.
std::variant< LINE, HALF_LINE, SEG, CIRCLE, SHAPE_ARC, SHAPE_ELLIPSE, BOX2I > INTERSECTABLE_GEOM
A variant type that can hold any of the supported geometry types for intersection calculations.
PCB_LAYER_ID
A quick note on layer IDs:
@ NPTH
like PAD_PTH, but not plated mechanical use only, no connection allowed
std::deque< BOARD_ITEM * > DRAWINGS
static float distance(const SFVEC2UI &a, const SFVEC2UI &b)
@ SH_POLY_SET
set of polygons (with holes, etc.)
@ SH_RECT
axis-aligned rectangle
@ SH_SIMPLE
simple polygon
@ SH_LINE_CHAIN
line chain (polyline)
@ SH_COMPOUND
compound shape, consisting of multiple simple shapes
A visitor that visits INTERSECTABLE_GEOM variant objects with another (which is held as state: m_othe...
SHAPE_CIRCLE circle(c.m_circle_center, c.m_circle_radius)
wxString result
Test unit parsing edge cases and error handling.
thread_pool & GetKiCadThreadPool()
Get a reference to the current thread pool.
BS::priority_thread_pool thread_pool
@ PCB_VIA_T
class PCB_VIA, a via (like a track segment on a copper layer)
@ PCB_TRACE_T
class PCB_TRACK, a track segment (segment on a copper layer)
VECTOR2< int32_t > VECTOR2I
VECTOR2< double > VECTOR2D
static PIECE rect(double aLeft, double aTop, double aRight, double aBottom, bool aMixed=false)