61 VIA* vold =
static_cast<VIA*
>( aOld );
62 VIA* vnew =
static_cast<VIA*
>( aNew.get() );
65 newId =
static_cast<VIA*
>( aNew.get() )->Uid();
68 wxString::Format(
"replace-via node=%p vold=%p [%d %d]-> vnew=%p [%d %d] nid %llu",
m_currentNode, aOld,
70 vnew->
Pos().
y, newId ) );
82 if( aIncludeInChangedArea )
89 PNS_DBG(
Dbg(), AddShape, &r,
BLUE, 0, wxT(
"shove-changed-area" ) );
111 bool foundPredecessor =
false;
127 rootEntry = oldLineIter->second;
128 foundPredecessor =
true;
134 if( !foundPredecessor )
149 aNode->
Replace( aOld, aNew, aAllowRedundantSegments );
239 const LINE& aShovedLine )
const
263 int obstacleLineWidth = aObstacleLine.
Width();
267 int holeClearance =
getClearance( viaHole, &aObstacleLine );
269 if( holeClearance +
via.Drill() / 2 > clearance +
via.Diameter( aObstacleLine.
Layer() ) / 2 )
270 clearance = holeClearance +
via.Drill() / 2 -
via.Diameter( aObstacleLine.
Layer() ) / 2;
276 if( ! aObstacleLine.
Walkaround( hull, path_cw,
true ) )
279 if( ! aObstacleLine.
Walkaround( hull, path_ccw,
false ) )
287 if( aObstacleLine.
CPoint( -1 ) != shortest.
CPoint( -1 ) )
306 LINE& aResultLine,
const HULL_SET& aHulls,
bool aPermitAdjustingEndpoints )
308 const int c_ENDPOINT_ON_HULL_THRESHOLD = 10000;
311 PNS_DBG(
Dbg(), BeginGroup,
"shove-details", 1 );
313 for( attempt = 0; attempt < 4; attempt++ )
315 bool invertTraversal = ( attempt >= 2 );
316 bool clockwise = attempt % 2;
317 int vFirst = -1, vLast = -1;
319 LINE l( aObstacleLine );
322 if( aPermitAdjustingEndpoints )
326 int min_dist = std::numeric_limits<int>::max();
329 for(
int i = 0; i < (int) aHulls.size(); i++ )
332 aHulls[invertTraversal ? aHulls.size() - 1 - i : i];
339 dist = ( p - pref ).EuclideanNorm();
341 if( dist < c_ENDPOINT_ON_HULL_THRESHOLD && dist < min_dist )
358 minhull = invertTraversal ? aHulls.size() - 1 - i : i;
366 int minDist0, minDist1, minhull0, minhull1 ;
370 PNS_DBG(
Dbg(), Message, wxString::Format(
"mindists : %d %d hulls %d %d\n", minDist0, minDist1, minhull0, minhull1 ) );
372 if( minDist1 < c_ENDPOINT_ON_HULL_THRESHOLD )
379 if( minDist0 < c_ENDPOINT_ON_HULL_THRESHOLD )
388 bool failWalk =
false;
390 for(
int i = 0; i < (int) aHulls.size(); i++ )
392 const SHAPE_LINE_CHAIN& hull = aHulls[invertTraversal ? aHulls.size() - 1 - i : i];
394 PNS_DBG(
Dbg(), AddShape, &hull,
YELLOW, 10000, wxString::Format(
"hull[%d]", i ) );
400 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"Fail-Walk %s %s %d\n" ),
416 for(
int i = 0; i < std::min(
path.PointCount(), obs.
PointCount() ); i++ )
427 for(
int i =
path.PointCount() - 1; i >= 0 && k >= 0; i--, k-- )
436 if( ( vFirst < 0 || vLast < 0 ) && !
path.CompareGeometry( obs ) )
438 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"attempt %d fail vfirst-last" ),
445 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"attempt %d fail vend-start\n" ),
452 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"attempt %d fail direction-check" ),
458 if(
path.SelfIntersecting() )
460 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"attempt %d fail self-intersect" ),
482 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"attempt %d fail coll-check" ),
507 const int cHullFailureExpansionFactor = 1000;
508 int extraHullExpansion = 0;
514 LINE obstacleLine( aObstacleLine );
515 std::optional<VIA> obsVia;
519 obsVia = aObstacleLine.
Via();
523 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"shove process-single: voe-cur %d voe-obs %d" ),
538 int obstacleLineWidth = obstacleLine.
Width();
539 int clearance =
getClearance( &aCurLine, &obstacleLine );
547 for(
int attempt = 0; attempt < 3; attempt++ )
551 hulls.reserve( currentLineSegmentCount + 1 );
553 for(
int i = 0; i < currentLineSegmentCount; i++ )
560 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"shove add-extra-clearance %d" ),
567 hulls.push_back( hull );
575 int holeClearance =
getClearance( viaHole, &obstacleLine );
576 int layer = aObstacleLine.
Layer();
578 if( holeClearance +
via.Drill() / 2 > viaClearance +
via.Diameter( layer ) / 2 )
580 viaClearance = holeClearance +
via.Drill() / 2 -
via.Diameter( layer ) / 2;
583 hulls.push_back( aCurLine.
Via().
Hull( viaClearance, obstacleLineWidth, layer ) );
586 bool permitMovingEndpoints = (attempt >= 2);
588 if (
shoveLineToHullSet( aCurLine, obstacleLine, aResultLine, hulls, permitMovingEndpoints ) )
596 extraHullExpansion += cHullFailureExpansionFactor;
612 LINE shovedLine( obstacleLine );
617 PNS_DBG(
Dbg(), Message,
"try walk (locked segments)");
623 const double extensionWalkThreshold = 1.0;
627 double extensionFactor = 0.0;
630 extensionFactor = shovedLen / obsLen - 1.0;
639 PNS_DBG(
Dbg(), AddItem, aObstacleSeg,
BLUE, 0, wxT(
"colliding-segment" ) );
641 PNS_DBG(
Dbg(), AddItem, &obstacleLine,
GREEN, 10000, wxString::Format(
"obstacle-line [l %d v %d]", obstacleLine.
Layer(), obstacleLine.
EndsWithVia() ) );
642 PNS_DBG(
Dbg(), AddItem, &shovedLine,
BLUE, 10000, wxT(
"shoved-line" ) );
647 int rank = aCurrent.
Rank();
648 shovedLine.
SetRank( rank - 1 );
652 replaceLine( obstacleLine, shovedLine,
true,
false );
671 LINE shovedLine( obstacleLine );
672 ARC tmp( *aObstacleArc );
679 const double extensionWalkThreshold = 1.0;
683 double extensionFactor = 0.0;
686 extensionFactor = shovedLen / obsLen - 1.0;
688 if( extensionFactor > extensionWalkThreshold )
694 PNS_DBG(
Dbg(), AddItem, &aCurrent,
RED, 10000, wxT(
"current-line" ) );
695 PNS_DBG(
Dbg(), AddItem, &obstacleLine,
GREEN, 10000, wxT(
"obstacle-line" ) );
696 PNS_DBG(
Dbg(), AddItem, &shovedLine,
BLUE, 10000, wxT(
"shoved-line" ) );
700 int rank = aCurrent.
Rank();
701 shovedLine.
SetRank( rank - 1 );
703 replaceLine( obstacleLine, shovedLine,
true,
false );
718 LINE shovedLine( aObstacle );
722 PNS_DBG(
Dbg(), AddItem, &aObstacle,
RED, 100000, wxT(
"obstacle-line" ) );
723 PNS_DBG(
Dbg(), AddItem, &aCurrent,
GREEN, 150000, wxT(
"current-line" ) );
724 PNS_DBG(
Dbg(), AddItem, &shovedLine,
BLUE, 200000, wxT(
"shoved-line" ) );
734 m_newHead = shovedLine;
739 shovedLine.
SetRank( aNextRank );
754 LINE walkaroundLine( aCurrent );
782 PNS_DBG(
Dbg(), BeginGroup,
"walk-cluster", 1 );
785 PNS_DBG(
Dbg(), AddItem, item,
RED, 10000, wxT(
"cl-item" ) );
796 int currentRank = aCurrent.
Rank();
799 bool success =
false;
801 PNS_DBG(
Dbg(), AddItem, &aCurrent,
RED, 10000, wxT(
"current-line" ) );
803 for(
int attempt = 0; attempt < 2; attempt++ )
805 if( attempt == 1 ||
Settings().JumpOverObstacles() )
806 nextRank = currentRank - 1;
808 nextRank = currentRank + 10000;
824 PNS_DBG(
Dbg(), AddItem, &walkaroundLine,
BLUE, 10000, wxT(
"walk-line" ) );
834 m_newHead = walkaroundLine;
864 replaceLine( aCurrent, walkaroundLine,
true,
false );
865 walkaroundLine.
SetRank( nextRank );
879 PNS_DBG(
Dbg(), Message, wxString::Format(
"prune called" ) );
884 for(
const ITEM* item : added )
943 wxString::Format(
"restore-springback-via depth=%d %d %d %d %d ",
979 wxString::Format(
"push-sp via depth=%d %d %d %d %d ", aNode->
Depth(), vhandle.
pos.
x,
1026 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"via force [%d %d]\n" ), aForce.
x, aForce.
y ) );
1029 if ( aForce.
x == 0 && aForce.
y == 0 )
1034 PNS_DBG(
Dbg(), Message, wxT(
"weird, can't find the center-of-via joint\n" ) );
1052 p0_pushed += aForce.
Resize( 2 );
1055 std::unique_ptr<VIA> pushedVia =
Clone( *aVia );
1056 pushedVia->SetPos( p0_pushed );
1057 pushedVia->Mark( aVia->
Marker() );
1069 if( lp.first.HasLockedSegments() )
1072 assert( segIndex == 0 || ( segIndex == ( lp.first.SegmentCount() - 1 ) ) );
1077 lp.second = lp.first;
1078 lp.second.ClearLinks();
1079 lp.second.DragCorner( p0_pushed, lp.second.CLine().Find( p0 ) );
1080 lp.second.Line().Simplify2();
1081 draggedLines.push_back( lp );
1085 pushedVia->SetRank( aNewRank );
1086 PNS_DBG(
Dbg(), Message, wxString::Format(
"via rank %d, fanout %d\n", pushedVia->Rank(), (
int) draggedLines.size() ) );
1091 VIA *
v2 = pushedVia.get();
1093 if( !aDontUnwindStack )
1098 if( draggedLines.empty() )
1109 if( !aDontUnwindStack )
1112 PNS_DBG(
Dbg(), Message, wxString::Format(
"fan %d/%d\n", n, (
int) draggedLines.size() ) );
1115 if( lp.second.SegmentCount() )
1117 lp.second.ClearLinks();
1120 lp.second.LinkVia(
v2 );
1122 if( !aDontUnwindStack )
1125 lp.second.SetRank( aNewRank );
1128 rootEntry->
newLine = lp.second;
1131 PNS_DBG(
Dbg(), Message, wxString::Format(
"PushViaF %p %d eov %d\n", &lp.second, lp.second.SegmentCount(), lp.second.EndsWithVia()?1:0 ) );
1155 assert( aObstacleVia );
1157 int clearance =
getClearance( aCurrent, aObstacleVia );
1161 bool lineCollision =
false;
1162 bool viaCollision =
false;
1163 bool solidCollision =
false;
1164 VECTOR2I mtvLine, mtvVia, mtvSolid;
1166 PNS_DBG(
Dbg(), BeginGroup,
"push-via-by-line", 1 );
1170 VIA vtmp ( *aObstacleVia );
1171 int layer = aCurrent->
Layer();
1179 LINE* currentLine = (
LINE*) aCurrent;
1191 clearance + currentLine->
Width() / 2,
1197 const VIA& currentVia = currentLine->
Via();
1214 PNS_DBG(
Dbg(), Message, wxT(
"collidee-is-solid" ) );
1216 solidCollision = aCurrent->
Shape( -1 )->
Collide( aObstacleVia->
Shape( -1 ), clearance,
1227 else if ( lineCollision )
1229 else if ( solidCollision )
1235 PNS_DBG(
Dbg(), Message, wxString::Format(
"push-or-shove-via st %d", st ) );
1255 int layer = aCurrent.
Layer();
1256 int dist = (p0 - p1).EuclideanNorm() - aCurrent.
Via().
Diameter( layer ) / 2
1257 - aObstacleVia->
Diameter( layer ) / 2;
1266 PNS_DBG(
Dbg(), Message, wxString::Format(
"via2via coll check dist %d cl %d delta %d pi %d\n", dist, clearance, dist - clearance, epInsideHull ? 1 : 0) );
1268 bool viaCollision =
false;
1279 return onCollidingVia( &aCurrent, aObstacleVia, aObstacleInfo, aCurrent.
Rank() - 1 );
1283 LINE cur( aCurrent );
1287 LINE shoved( aCurrent );
1333 LINE head( aCurrent );
1351 PNS_DBG(
Dbg(), AddItem, &aCurrent,
BLUE, 0, wxT(
"rr-current-line" ) );
1352 PNS_DBG(
Dbg(), AddItem, &shoved,
GREEN, 0, wxT(
"rr-shoved-line" ) );
1355 int currentRank = aCurrent.
Rank();
1361 shoved.
SetRank( currentRank );
1373 if( i->ContainsLink( aSeg ) )
1375 PNS_DBG(
Dbg(), Message, wxString::Format(
"Unwind lc %d (depth %d/%d)", i->SegmentCount(), d, (
int)
m_lineStack.size() ) );
1391 via =
static_cast<VIA*
>( l );
1413 if( i->ContainsLink( aSeg ) )
1429 const LINE* l =
static_cast<const LINE*
>( aItem );
1441 PNS_DBG(
Dbg(), AddItem, &aL,
BLUE, 10000, wxT(
"push line stack failed" ) );
1473 wxString::Format(
"cur lc %d lnk %p cnt %d", i->LinkCount(), s, aLine.
LinkCount() ) );
1475 if( i->ContainsLink( s ) && !s->OfKind(
ITEM::VIA_T ) )
1501 int layer = aCurrent->
Layer();
1517 for(
ITEM* link : links )
1522 maxw = std::max( seg->
Width(), maxw );
1526 const ARC* arc =
static_cast<const ARC*
>( link );
1527 maxw = std::max( arc->
Width(), maxw );
1533 if( maxw > 0 && maxw >= v->
Diameter( layer ) )
1537 wxString::Format(
"Fixup via: new-w %d via-w %d", maxw, v->
Diameter( layer ) ) );
1550 int sl = s->
Layer();
1557 for(
int i = 0; i < 2; i++ )
1596 wxString::Format( wxT(
"current sc=%d net=%s evia=%d" ),
1634 wxString::Format(
"nearest %p %s rank %d",
1636 nearest->m_item->KindStr(),
1637 nearest->m_item->Rank() ) );
1647 PNS_DBG(
Dbg(), Message, wxT(
"no-nearest-item ") );
1653 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"iter %d: via-fixup %d" ), aIter, viaFixup?1:0 ) );
1656 ITEM* ni = nearest->m_item;
1659 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"NI: %s (%s) %p %d" ),
1663 : wxString( wxT(
"null" ) ),
1673 switch( ni->
Kind() )
1677 PNS_DBG(
Dbg(), BeginGroup, wxString::Format( wxT(
"iter %d: reverse-collide-via" ), aIter ), 0 );
1682 nearest->m_item->Layer() ) )
1684 PNS_DBG(
Dbg(), AddItem, nearest->m_item,
YELLOW, 100000, wxT(
"v2v nearesti" ) );
1703 PNS_DBG(
Dbg(), BeginGroup, wxString::Format( wxT(
"iter %d: reverse-collide-segment" ),
1744 PNS_DBG(
Dbg(), BeginGroup, wxString::Format( wxT(
"iter %d: reverse-collide-arc " ), aIter ), 0 );
1766 switch( ni->
Kind() )
1769 PNS_DBG(
Dbg(), BeginGroup, wxString::Format( wxT(
"iter %d: collide-segment " ), aIter ), 0 );
1782 PNS_DBG(
Dbg(), BeginGroup, wxString::Format( wxT(
"iter %d: collide-arc " ), aIter ), 0 );
1794 PNS_DBG(
Dbg(), BeginGroup, wxString::Format( wxT(
"iter %d: collide-via (fixup: %d)" ), aIter, 0 ), 0 );
1806 PNS_DBG(
Dbg(), BeginGroup, wxString::Format( wxT(
"iter %d: walk-solid " ), aIter ), 0);
1834 PNS_DBG(
Dbg(), Message, wxString::Format(
"ShoveStart [root: %d jts, current: %d jts]",
1854 PNS_DBG(
Dbg(), Message, wxString::Format(
"iter %d: node %p stack %d ",
m_iter,
1863 PNS_DBG(
Dbg(), Message, wxString::Format(
"Fail [time limit expired: %d iter %d iter limit %d",
1922 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"touch [found] uid=%llu type=%s"), link->Uid(), link->KindStr() ) );
1933 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"touch [create] uid=%llu type=%s"), link->Uid(), link->KindStr() ) );
1948 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"touch [create] uid=%llu"), aItem->
Uid() ) );
1954 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"touch [create] uid=%llu"), aItem->
Uid() ) );
1974 maxWidth = std::max( line.Width(), maxWidth );
1978 area->Inflate( maxWidth );
2028 std::set<const ITEM*> itemsChk;
2032 for(
int pass = 0; pass < n_passes; pass++ )
2041 LINE* rootLine =
nullptr;
2046 rootLine = rootEntry->rootLine;
2050 if( rootEntry->isHead )
2055 if( optimizer.
Optimize( &lineToOpt, &optimized, rootLine ) )
2061 PNS_DBG(
Dbg(), AddItem, rootLine,
RED, 0, wxT(
"shove-root-opt" ) );
2063 replaceLine( lineToOpt, optimized,
false, aNode );
2101 if ( iter->m_node == aNode )
2147 if ( iter->m_node == aNode )
2149 iter->m_locked =
false;
2179 rl->policy = aPolicy;
2185 rl->policy = aPolicy;
2212 for (
auto lnk : head.
Links() )
2214 if( lnk->BelongsTo( aNode ) )
2225 if( headEntry.newHead )
2228 int n_lc = headEntry.newHead->LinkCount();
2233 wxString msg = wxString::Format(
2234 "remove newhead [net %-20s]: sc %d lc %d\n",
2235 iface->GetNetName( headEntry.newHead->Net() ).c_str().AsChar(),
2236 headEntry.newHead->SegmentCount(), n_lc );
2239 else if( headEntry.origHead )
2241 wxString msg = wxString::Format(
2242 "remove orighead [net %-20s]: sc %d lc %d node %p depth %d\n",
2243 iface->GetNetName( headEntry.origHead->Net() ).c_str().AsChar(),
2244 headEntry.origHead->SegmentCount(), headEntry.origHead->LinkCount(),
2264 if( headEntry.origHead )
2268 PNS_DBG(
Dbg(), Message, wxString::Format(
"orig LinkC=%d RE=%p", headEntry.origHead->LinkCount(), rootEntry ) );
2270 assert( rootEntry );
2271 assert( rootEntry->rootLine );
2273 if( rootEntry->newLine )
2275 headEntry.newHead = rootEntry->newLine;
2276 headEntry.geometryModified = !rootEntry->newLine->CLine().CompareGeometry( rootEntry->rootLine->CLine() );
2278 wxString msg = wxString::Format(
2279 "head %d/%d [net %-20s]: root %p, lc-root %d, lc-new %d\n", i, (
int)
m_headLines.size(),
2280 iface->GetNetName( rootEntry->rootLine->Net() ).c_str().AsChar(), rootEntry->rootLine, rootEntry->rootLine->LinkCount(), headEntry.newHead->LinkCount() );
2287 wxString msg = wxString::Format(
2288 "head %d/%d [net %-20s]: unmodified, lc-orig %d\n", i, (
int)
m_headLines.size(),
2289 iface->GetNetName( headEntry.origHead->Net() ).c_str().AsChar(),
2290 headEntry.origHead->LinkCount() );
2298 if( rootEntry->newVia )
2300 headEntry.geometryModified =
true;
2301 headEntry.theVia =
VIA_HANDLE( rootEntry->newVia->Pos(), rootEntry->newVia->Layers(), rootEntry->newVia->Net() );
2303 wxString msg = wxString::Format(
"[modif] via orig %p chk %p\n", headEntry.draggedVia, chk );
2306 assert( chk !=
nullptr );
2310 headEntry.theVia =
VIA_HANDLE( rootEntry->oldVia->Pos(), rootEntry->oldVia->Layers(), rootEntry->oldVia->Net() );
2312 wxString msg = wxString::Format(
"[unmodif] via orig %p chk %p\n", headEntry.draggedVia, chk );
2314 assert( chk !=
nullptr );
2342 PNS_DBG(
Dbg(), Message, wxString::Format(
"**** PreshoveCleanup %d -> %d\n", vc_prev, vc_post ) );
2344 if( vc_prev != vc_post )
2361 int currentHeadId = 0;
2376 PNS_DBG(
Dbg(), Message, wxString::Format(
"process head-via [%d %d] node=%p", l.theVia->pos.x, l.theVia->pos.y,
m_currentNode ) );
2378 assert( realVia !=
nullptr );
2379 headSet.
Add( realVia->Clone() );
2383 headSet.
Add( *l.origHead->Clone() );
2417 if( headLineEntry.theVia )
2428 viaRoot->oldVia = viaToDrag;
2429 headLineEntry.draggedVia = viaToDrag;
2431 st =
pushOrShoveVia( viaToDrag, ( headLineEntry.viaNewPos - viaToDrag->
Pos() ), 0,
true );
2439 assert( headLineEntry.origHead->LinkCount() == 0 );
2447 wxString::Format(
"touchRoot ohlc %d roots %d re=%p\n",
2448 headLineEntry.origHead->LinkCount(),
2453 LINE head( *headLineEntry.origHead );
2476 auto headVia =
Clone( head.
Via() );
2477 headVia->SetRank( 100000 );
2478 headLineEntry.origHead->LinkVia( headVia.get() );
2479 head.
LinkVia( headVia.get() );
2484 headRoot->isHead =
true;
2485 headRoot->rootLine =
new PNS::LINE( *headLineEntry.origHead );
2486 headRoot->policy = headLineEntry.policy;
2490 wxString::Format(
"headLC %d, rlLC %d oolc %d eov %d\n", head.
LinkCount(),
2491 headRoot->rootLine->LinkCount(),
2492 headLineEntry.origHead->LinkCount(),
2498 wxString::Format(
"Shove heads %d/%d h-lc=%d net=%s Line=%d Policy=%s",
2499 currentHeadId, totalHeads, head.
LinkCount(),
2500 iface->GetNetName( head.
Net() ), headRoot->newLine ? 1 : 0,
2502 : wxString( wxT(
"default[ne]" ) ) ) );
2523 wxString::Format(
"Shove status : %s after %d iterations, heads: %d",
2544 if( headEntry.prevVia )
2548 wxString::Format(
"Fail-restore via mod [%d, %d] orig [%d, %d]",
2549 headEntry.theVia->pos.x,
2550 headEntry.theVia->pos.y,
2551 headEntry.prevVia->pos.x,
2552 headEntry.prevVia->pos.y ) );
2554 headEntry.theVia = headEntry.prevVia;
2555 headEntry.geometryModified =
true;
2587 rv.Append(
"shove ");
2589 rv.Append(
"walk-forward ");
2591 rv.Append(
"walk-back ");
2593 rv.Append(
"ignore ");
2595 rv.Append(
"dont-optimize ");
constexpr EDA_IU_SCALE pcbIUScale
std::optional< BOX2I > OPT_BOX2I
constexpr BOX2I KiROUND(const BOX2D &aBoxD)
@ ROUNDED_45
H/V/45 with filleted corners.
@ MITERED_45
H/V/45 with mitered corners (default)
virtual wxString GetItemDescription(UNITS_PROVIDER *aUnitsProvider, bool aFull) const
Return a user-visible description string of this item.
Base class for all P&S algorithms (shoving, walkaround, line placement, dragging, etc....
const BOX2I & VisibleViewArea() const
void SetDebugDecorator(DEBUG_DECORATOR *aDecorator)
Assign a debug decorator allowing this algo to draw extra graphics for visual debugging.
ROUTER * Router() const
Return current router settings.
ROUTING_SETTINGS & Settings() const
Return the logger object, allowing to dump geometry to a file.
DEBUG_DECORATOR * Dbg() const
int Width() const override
virtual void SetIteration(int iter)
void Add(const LINE &aLine)
Base class for PNS router board items.
BOARD_ITEM * Parent() const
virtual const std::string Format() const
virtual const SHAPE * Shape(int aLayer) const
Return the geometrical shape of the item.
const PNS_LAYER_RANGE & Layers() const
virtual NET_HANDLE Net() const
PnsKind Kind() const
Return the type (kind) of the item.
std::set< int > RelevantShapeLayers(const ITEM *aOther) const
Returns the set of layers on which either this or the other item can have a unique shape.
virtual int Layer() const
PnsKind
< Supported item types
bool Collide(const ITEM *aHead, const NODE *aNode, int aLayer, COLLISION_SEARCH_CONTEXT *aCtx=nullptr) const
Check for a collision (clearance violation) with between us and item aOther.
virtual const NODE * OwningNode() const
bool OfKind(int aKindMask) const
bool LayersOverlap(const ITEM *aOther) const
Return true if the set of layers spanned by aOther overlaps our layers.
virtual HOLE * Hole() const
virtual bool HasHole() const
virtual int Marker() const
A 2D point on a given set of layers and belonging to a certain net, that links together a number of b...
const std::vector< ITEM * > & LinkList() const
const ITEM_SET & CLinks() const
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
const VECTOR2I & CPoint(int aIdx) const
bool HasLockedSegments() const
int Rank() const override
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Return the shape of the line.
virtual void Mark(int aMarker) const override
const SHAPE_LINE_CHAIN & CLine() const
void SetRank(int aRank) override
SHAPE_LINE_CHAIN & Line()
const SHAPE * Shape(int aLayer) const override
Modifiable accessor to the underlying shape.
virtual int Marker() const override
void AppendVia(const VIA &aVia)
virtual void Unmark(int aMarker=-1) const override
bool Walkaround(SHAPE_LINE_CHAIN aObstacle, SHAPE_LINE_CHAIN &aPre, SHAPE_LINE_CHAIN &aWalk, SHAPE_LINE_CHAIN &aPost, bool aCw) const
Calculate a line tightly wrapping a convex hull of an obstacle object (aObstacle).
const SEG CSegment(int aIdx) const
Set line width.
virtual LINE * Clone() const override
Return a deep copy of the item.
int Width() const
Return true if the line is geometrically identical as line aOther.
void Unlink(const LINKED_ITEM *aLink)
Return the list of links from the owning node that constitute this line (or NULL if the line is not l...
bool IsLinked() const
Check if the segment aLink is a part of the line.
std::vector< LINKED_ITEM * > & Links()
virtual void ClearLinks()
Return the number of segments that were assembled together to form this line.
Keep the router "world" - i.e.
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
std::vector< ITEM * > ITEM_VECTOR
int GetClearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true) const
Return the pre-set worst case clearance between any pair of items.
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Replace an item with another one.
void GetUpdatedItems(ITEM_VECTOR &aRemoved, ITEM_VECTOR &aAdded)
Return the list of items removed and added in this branch with respect to the root branch.
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Check if the item collides with anything else in the world, and if found, returns the obstacle.
const JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, NET_HANDLE aNet) const
Search for a joint at a given position, layer and belonging to given net.
std::optional< OBSTACLE > OPT_OBSTACLE
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
OPT_OBSTACLE NearestObstacle(const LINE *aLine, const COLLISION_SEARCH_OPTIONS &aOpts=COLLISION_SEARCH_OPTIONS())
Follow the line in search of an obstacle that is nearest to the starting to the line's starting point...
void LockJoint(const VECTOR2I &aPos, const ITEM *aItem, bool aLock)
int JointCount() const
Return the number of nodes in the inheritance chain (wrs to the root node).
VIA * FindViaByHandle(const VIA_HANDLE &handle) const
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION)
void Remove(ARC *aArc)
Remove an item from this branch.
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false, bool aFollowLockedSegments=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Perform various optimizations of the lines being routed, attempting to make the lines shorter and les...
void SetRestrictArea(const BOX2I &aArea, bool aStrict=true)
void SetCollisionMask(int aMask)
void SetEffortLevel(int aEffort)
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I &aV=VECTOR2I(0, 0))
@ LIMIT_CORNER_COUNT
Do not attempt to optimize if the resulting line's corner count is outside the predefined range.
@ SMART_PADS
Reroute pad exits.
@ MERGE_SEGMENTS
Reduce corner cost iteratively.
@ MERGE_OBTUSE
Reduce corner cost by merging obtuse segments.
virtual wxString GetNetName(PNS::NET_HANDLE aNet) const =0
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
ROUTER_IFACE * GetInterface() const
TIME_LIMIT ShoveTimeLimit() const
PNS_OPTIMIZATION_EFFORT OptimizerEffort() const
Set the optimizer effort. Bigger means cleaner traces, but slower routing.
int ShoveIterationLimit() const
DIRECTION_45::CORNER_MODE GetCornerMode() const
int Width() const override
const SHAPE_LINE_CHAIN Hull(int aClearance, int aWalkaroundThickness, int aLayer=-1) const override
void SetSpringbackDoNotTouchNode(const NODE *aNode)
SHOVE_STATUS shoveIteration(int aIter)
SHOVE_STATUS shoveMainLoop()
std::vector< SHAPE_LINE_CHAIN > HULL_SET
void reconstructHeads(bool aShoveFailed)
std::pair< LINE, LINE > LINE_PAIR
SHOVE_STATUS pushOrShoveVia(VIA *aVia, const VECTOR2I &aForce, int aNextRank, bool aDontUnwindStack=false)
SHOVE_STATUS onReverseCollidingVia(LINE &aCurrent, VIA *aObstacleVia, OBSTACLE &aObstacleInfo)
std::vector< LINE > m_lineStack
ROOT_LINE_ENTRY * findRootLine(const LINE &aLine)
std::vector< SPRINGBACK_TAG > m_nodeStack
bool shoveLineToHullSet(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine, const HULL_SET &aHulls, bool aPermitAdjustingEndpoints=false)
SHOVE_STATUS onCollidingArc(LINE &aCurrent, ARC *aObstacleArc)
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=nullptr, bool aPreCleanup=false)
bool checkShoveDirection(const LINE &aCurLine, const LINE &aObstacleLine, const LINE &aShovedLine) const
SHOVE_STATUS onCollidingSegment(LINE &aCurrent, SEGMENT *aObstacleSeg)
SHOVE(NODE *aWorld, ROUTER *aRouter)
void DisablePostShoveOptimizations(int aMask)
bool RewindSpringbackTo(NODE *aNode)
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
OPT_BOX2I totalAffectedArea() const
bool RewindToLastLockedNode()
std::deque< HEAD_LINE_ENTRY > m_headLines
const wxString formatPolicy(int aPolicy)
bool ShoveObstacleLine(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
SHOVE_STATUS onCollidingVia(ITEM *aCurrent, VIA *aObstacleVia, OBSTACLE &aObstacleInfo, int aNextRank)
void sanityCheck(LINE *aOld, LINE *aNew)
int m_restrictSpringbackTagId
void runOptimizer(NODE *aNode)
ROOT_LINE_ENTRY * touchRootLine(const LINE &aLine)
const PNS::LINE GetModifiedHead(int aIndex) const
bool HeadsModified(int aIndex=-1) const
void UnlockSpringbackNode(NODE *aNode)
NODE * reduceSpringback(const ITEM_SET &aHeadSet)
bool AddLockedSpringbackNode(NODE *aNode)
void SetDefaultShovePolicy(int aPolicy)
void AddHeads(const LINE &aHead, int aPolicy=SHP_DEFAULT)
void SetShovePolicy(const LINKED_ITEM *aItem, int aPolicy)
void unwindLineStack(const LINKED_ITEM *aSeg)
bool preShoveCleanup(LINE *aOld, LINE *aNew)
int getClearance(const ITEM *aA, const ITEM *aB) const
std::vector< LINE > m_optimizerQueue
SHOVE_STATUS onCollidingSolid(LINE &aCurrent, ITEM *aObstacle, OBSTACLE &aObstacleInfo)
bool pushSpringback(NODE *aNode, const OPT_BOX2I &aAffectedArea)
SHOVE_STATUS onCollidingLine(LINE &aCurrent, LINE &aObstacle, int aNextRank)
bool fixupViaCollisions(const LINE *aCurrent, OBSTACLE &obs)
bool pruneLineFromOptimizerQueue(const LINE &aLine)
void replaceItems(ITEM *aOld, std::unique_ptr< ITEM > aNew)
bool shoveLineFromLoneVia(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
const NODE * m_springbackDoNotTouchNode
std::unordered_map< LINKED_ITEM::UNIQ_ID, ROOT_LINE_ENTRY * > m_rootLineHistory
void pruneRootLines(NODE *aRemovedNode)
const VIA_HANDLE GetModifiedHeadVia(int aIndex) const
ROOT_LINE_ENTRY * replaceLine(LINE &aOld, LINE &aNew, bool aIncludeInChangedArea=true, bool aAllowRedundantSegments=true, NODE *aNode=nullptr)
std::vector< LINE_PAIR > LINE_PAIR_VEC
const CLUSTER AssembleCluster(ITEM *aStart, int aLayer, double aAreaExpansionLimit=0.0, NET_HANDLE aExcludedNet=nullptr)
int Diameter(int aLayer) const
void SetDiameter(int aLayer, int aDiameter)
const VECTOR2I & Pos() const
const SHAPE * Shape(int aLayer) const override
Return the geometrical shape of the item.
const SHAPE_LINE_CHAIN Hull(int aClearance=0, int aWalkaroundThickness=0, int aLayer=-1) const override
VIA * Clone() const override
Return a deep copy of the item.
void SetIterationLimit(const int aIterLimit)
void RestrictToCluster(bool aEnabled, const TOPOLOGY::CLUSTER &aCluster)
void SetSolidsOnly(bool aSolidsOnly)
STATUS Route(const LINE &aInitialPath, LINE &aWalkPath, bool aOptimize=true)
void SetAllowedPolicies(std::vector< WALK_POLICY > aPolicies)
static double DefaultAccuracyForPCB()
A dynamic state checking if a point lies within polygon with a dynamically built outline ( with each ...
void AddPolyline(const SHAPE_LINE_CHAIN &aPolyline)
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const override
Check if point aP lies inside a closed shape.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
const SHAPE_LINE_CHAIN Reverse() const
Reverse point order in the line chain.
void SetPoint(int aIndex, const VECTOR2I &aPos)
Move a point to a specific location.
int PointCount() const
Return the number of points (vertices) in this line chain.
void Clear()
Remove all points from the line chain.
SHAPE_LINE_CHAIN & Simplify2(bool aRemoveColinear=true)
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
const VECTOR2I NearestPoint(const VECTOR2I &aP, bool aAllowInternalShapePoints=true) const
Find a point on the line chain that is closest to point aP.
const std::string Format(bool aCplusPlus=true) const override
bool IsArcSegment(size_t aSegment) const
long long int Length() const
Return length of the line chain in Euclidean metric.
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const
Check if the boundary of shape (this) lies closer to the point aP than aClearance,...
constexpr extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
VECTOR2_TRAITS< int32_t >::extended_type extended_type
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Push and Shove diff pair dimensions (gap) settings dialog.
OPT_BOX2I ChangedArea(const ITEM *aItemA, const ITEM *aItemB)
void removeHead(NODE *aNode, LINE &head)
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
#define PNS_DBG(dbg, method,...)
#define PNS_DBGN(dbg, method)
VECTOR2I::extended_type ecoord
std::vector< FAB_LAYER_COLOR > dummy
std::function< bool(const ITEM *)> m_filter
Hold an object colliding with another object, along with some useful data about the collision.
int m_maxFanoutWidth
worst case (largest) width of the tracks connected to the item
ITEM * m_item
Item found to be colliding with m_head.
std::optional< VIA_HANDLE > theVia
std::optional< VIA_HANDLE > prevVia
std::optional< LINE > newLine
std::vector< VIA_HANDLE > m_draggedVias
std::set< ITEM * > m_items
LINE lines[MaxWalkPolicies]
STATUS status[MaxWalkPolicies]
VECTOR2< int32_t > VECTOR2I