64 VIA* vold =
static_cast<VIA*
>( aOld );
65 VIA* vnew =
static_cast<VIA*
>( aNew.get() );
68 newId =
static_cast<VIA*
>( aNew.get() )->
Uid();
71 wxString::Format(
"replace-via node=%p vold=%p [%d %d]-> vnew=%p [%d %d] nid %llu",
m_currentNode, aOld,
73 vnew->
Pos().
y, newId ) );
85 if( aIncludeInChangedArea )
92 PNS_DBG(
Dbg(), AddShape, &r,
BLUE, 0, wxT(
"shove-changed-area" ) );
114 bool foundPredecessor =
false;
130 rootEntry = oldLineIter->second;
131 foundPredecessor =
true;
137 if( !foundPredecessor )
152 aNode->
Replace( aOld, aNew, aAllowRedundantSegments );
154 m_currentNode->Replace( aOld, aNew, aAllowRedundantSegments );
174 if( overriddenClearance >= 0 )
175 return overriddenClearance;
248 const LINE& aShovedLine )
const
257 if( root && ( root->policy &
SHP_REVERSED ) && !loneVia )
259 cp = aCurLine.
CPoint( -1 );
269 wxString::Format(
"chkdir %d", inside?1:0 ) );
287 int obstacleLineWidth = aObstacleLine.
Width();
291 int holeClearance =
getClearance( viaHole, &aObstacleLine );
300 if( ! aObstacleLine.
Walkaround( hull, path_cw,
true ) )
303 if( ! aObstacleLine.
Walkaround( hull, path_ccw,
false ) )
333 const HULL_SET& aHulls,
bool aPermitAdjustingStart,
334 bool aPermitAdjustingEnd )
336 const int c_ENDPOINT_ON_HULL_THRESHOLD = 1000;
338 bool permitAdjustingEndpoints = aPermitAdjustingStart || aPermitAdjustingEnd;
340 PNS_DBG(
Dbg(), BeginGroup,
"shove-details", 1 );
342 for( attempt = 0; attempt < 4; attempt++ )
344 bool invertTraversal = ( attempt >= 2 );
345 bool clockwise = attempt % 2;
346 int vFirst = -1, vLast = -1;
348 LINE l( aObstacleLine );
355 int min_dist = std::numeric_limits<int>::max();
358 for(
int i = 0; i < (int) aHulls.size(); i++ )
361 aHulls[invertTraversal ? aHulls.size() - 1 - i : i];
368 dist = ( p - pref ).EuclideanNorm();
370 if( dist < c_ENDPOINT_ON_HULL_THRESHOLD && dist < min_dist )
378 minhull = invertTraversal ? aHulls.size() - 1 - i : i;
386 int minDist0, minDist1, minhull0 = -1, minhull1 = -1;
390 PNS_DBG(
Dbg(), Message, wxString::Format(
"mindists : %d %d hulls %d %d\n", minDist0, minDist1, minhull0, minhull1 ) );
392 if( minDist1 < c_ENDPOINT_ON_HULL_THRESHOLD && aPermitAdjustingEnd )
399 if( minDist0 < c_ENDPOINT_ON_HULL_THRESHOLD && aPermitAdjustingStart )
408 bool failWalk =
false;
410 for(
int i = 0; i < (int) aHulls.size(); i++ )
412 const SHAPE_LINE_CHAIN& hull = aHulls[invertTraversal ? aHulls.size() - 1 - i : i];
414 PNS_DBG(
Dbg(), AddShape, &hull,
YELLOW, 10000, wxString::Format(
"hull[%d]", i ) );
420 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"Fail-Walk %s %s %d\n" ),
436 for(
int i = 0; i < std::min(
path.PointCount(), obs.
PointCount() ); i++ )
447 for(
int i =
path.PointCount() - 1; i >= 0 && k >= 0; i--, k-- )
456 if( ( vFirst < 0 || vLast < 0 ) && !
path.CompareGeometry( obs ) )
458 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"attempt %d fail vfirst-last" ),
465 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"attempt %d fail vend-start\n" ),
472 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"attempt %d fail direction-check" ),
478 if(
path.SelfIntersecting() )
480 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"attempt %d fail self-intersect" ),
502 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"attempt %d fail coll-check" ),
528 const int cHullFailureExpansionFactor = 1000;
529 int extraHullExpansion = 0;
531 bool voeStart =
false, voeEnd =
false;
532 const JOINT* jtStart =
nullptr;
533 const JOINT* jtEnd =
nullptr;
542 voeStart = jtStart->
Via() !=
nullptr;
544 voeEnd = jtEnd->
Via() !=
nullptr;
549 LINE obstacleLine( aObstacleLine );
550 std::optional<VIA> obsVia;
554 obsVia = aObstacleLine.
Via();
558 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"shove process-single: voe-cur %d voe-obs %d" ),
573 int obstacleLineWidth = obstacleLine.
Width();
582 for(
int attempt = 0; attempt < 3; attempt++ )
586 hulls.reserve( currentLineSegmentCount + 1 );
588 for(
int i = 0; i < currentLineSegmentCount; i++ )
595 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"shove add-extra-clearance %d" ),
602 hulls.push_back( hull );
610 int holeClearance =
getClearance( viaHole, &obstacleLine );
611 int layer = aObstacleLine.
Layer();
613 if( holeClearance +
via.Drill() / 2 > viaClearance +
via.Diameter( layer ) / 2 )
615 viaClearance = holeClearance +
via.Drill() / 2 -
via.Diameter( layer ) / 2;
618 hulls.push_back( aCurLine.
Via().
Hull( viaClearance, obstacleLineWidth, layer ) );
621 bool permitMovingStart = (attempt >= 2) && !voeStart;
622 bool permitMovingEnd = (attempt >= 2) && !voeEnd;
624 if (
shoveLineToHullSet( aCurLine, obstacleLine, aResultLine, hulls, permitMovingStart, permitMovingEnd ) )
632 extraHullExpansion += cHullFailureExpansionFactor;
648 LINE shovedLine( obstacleLine );
653 PNS_DBG(
Dbg(), Message,
"try walk (locked segments)");
663 PNS_DBG(
Dbg(), AddItem, aObstacleSeg,
BLUE, 0, wxT(
"colliding-segment" ) );
666 PNS_DBG(
Dbg(), AddItem, &shovedLine,
BLUE, 10000, wxT(
"shoved-line" ) );
671 int rank = aCurrent.
Rank();
673 shovedLine.
SetRank( rank - 1 );
678 replaceLine( obstacleLine, shovedLine,
true,
false );
697 LINE shovedLine( obstacleLine );
698 ARC tmp( *aObstacleArc );
705 const double extensionWalkThreshold = 1.0;
709 double extensionFactor = 0.0;
712 extensionFactor = shovedLen / obsLen - 1.0;
714 if( extensionFactor > extensionWalkThreshold )
720 PNS_DBG(
Dbg(), AddItem, &aCurrent,
RED, 10000, wxT(
"current-line" ) );
721 PNS_DBG(
Dbg(), AddItem, &obstacleLine,
GREEN, 10000, wxT(
"obstacle-line" ) );
722 PNS_DBG(
Dbg(), AddItem, &shovedLine,
BLUE, 10000, wxT(
"shoved-line" ) );
726 int rank = aCurrent.
Rank();
727 shovedLine.
SetRank( rank - 1 );
729 replaceLine( obstacleLine, shovedLine,
true,
false );
744 LINE shovedLine( aObstacle );
748 PNS_DBG(
Dbg(), AddItem, &aObstacle,
RED, 100000, wxT(
"obstacle-line" ) );
749 PNS_DBG(
Dbg(), AddItem, &aCurrent,
GREEN, 150000, wxT(
"current-line" ) );
750 PNS_DBG(
Dbg(), AddItem, &shovedLine,
BLUE, 200000, wxT(
"shoved-line" ) );
760 m_newHead = shovedLine;
765 shovedLine.
SetRank( aNextRank );
782 LINE walkaroundLine( aCurrent );
810 PNS_DBG(
Dbg(), BeginGroup,
"walk-cluster", 1 );
813 PNS_DBG(
Dbg(), AddItem, item,
RED, 10000, wxT(
"cl-item" ) );
824 int currentRank = aCurrent.
Rank();
827 bool success =
false;
829 PNS_DBG(
Dbg(), AddItem, &aCurrent,
RED, 10000, wxT(
"current-line" ) );
831 for(
int attempt = 0; attempt < 2; attempt++ )
833 if( attempt == 1 ||
Settings().JumpOverObstacles() )
834 nextRank = currentRank - 1;
836 nextRank = currentRank + 10000;
852 PNS_DBG(
Dbg(), AddItem, &walkaroundLine,
BLUE, 10000, wxT(
"walk-line" ) );
862 m_newHead = walkaroundLine;
892 replaceLine( aCurrent, walkaroundLine,
true,
false );
893 walkaroundLine.
SetRank( nextRank );
907 PNS_DBG(
Dbg(), Message, wxString::Format(
"prune called" ) );
912 for(
const ITEM* item : added )
969 wxString::Format(
"restore-springback-via depth=%d %d %d %d %d ",
1005 wxString::Format(
"push-sp via depth=%d %d %d %d %d ", aNode->
Depth(), vhandle.
pos.
x,
1052 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"via force [%d %d]\n" ), aForce.
x, aForce.
y ) );
1055 if ( aForce.
x == 0 && aForce.
y == 0 )
1060 PNS_DBG(
Dbg(), Message, wxT(
"weird, can't find the center-of-via joint\n" ) );
1078 p0_pushed += aForce.
Resize( 2 );
1081 std::unique_ptr<VIA> pushedVia =
Clone( *aVia );
1082 pushedVia->SetPos( p0_pushed );
1083 pushedVia->Mark( aVia->
Marker() );
1095 if( lp.first.HasLockedSegments() )
1098 assert( segIndex == 0 || ( segIndex == ( lp.first.SegmentCount() - 1 ) ) );
1103 lp.second = lp.first;
1104 lp.second.ClearLinks();
1105 lp.second.DragCorner( p0_pushed, lp.second.CLine().Find( p0 ) );
1106 lp.second.Line().Simplify2();
1107 draggedLines.push_back( std::move( lp ) );
1111 pushedVia->SetRank( aNewRank );
1112 PNS_DBG(
Dbg(), Message, wxString::Format(
"via rank %d, fanout %d\n", pushedVia->Rank(), (
int) draggedLines.size() ) );
1117 VIA *
v2 = pushedVia.get();
1119 if( !aDontUnwindStack )
1124 if( draggedLines.empty() )
1135 if( !aDontUnwindStack )
1138 PNS_DBG(
Dbg(), Message, wxString::Format(
"fan %d/%d\n", n, (
int) draggedLines.size() ) );
1141 if( lp.second.SegmentCount() )
1143 lp.second.ClearLinks();
1146 lp.second.LinkVia(
v2 );
1148 if( !aDontUnwindStack )
1151 lp.second.SetRank( aNewRank );
1154 rootEntry->
newLine = lp.second;
1157 PNS_DBG(
Dbg(), Message, wxString::Format(
"PushViaF %p %d eov %d\n", &lp.second, lp.second.SegmentCount(), lp.second.EndsWithVia()?1:0 ) );
1181 assert( aObstacleVia );
1186 bool lineCollision =
false;
1187 bool viaCollision =
false;
1188 bool solidCollision =
false;
1189 VECTOR2I mtvLine, mtvVia, mtvSolid;
1191 PNS_DBG(
Dbg(), BeginGroup,
"push-via-by-line", 1 );
1195 VIA vtmp ( *aObstacleVia );
1196 int layer = aCurrent->
Layer();
1204 LINE* currentLine = (
LINE*) aCurrent;
1222 const VIA& currentVia = currentLine->
Via();
1239 PNS_DBG(
Dbg(), Message, wxT(
"collidee-is-solid" ) );
1252 else if ( lineCollision )
1254 else if ( solidCollision )
1260 PNS_DBG(
Dbg(), Message, wxString::Format(
"push-or-shove-via st %d", st ) );
1280 int layer = aCurrent.
Layer();
1281 int dist = (p0 - p1).EuclideanNorm() - aCurrent.
Via().
Diameter( layer ) / 2
1282 - aObstacleVia->
Diameter( layer ) / 2;
1292 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) );
1294 bool viaCollision =
false;
1305 return onCollidingVia( &aCurrent, aObstacleVia, aObstacleInfo, aCurrent.
Rank() - 1 );
1309 LINE cur( aCurrent );
1313 LINE shoved( aCurrent );
1359 LINE head( aCurrent );
1377 PNS_DBG(
Dbg(), AddItem, &aCurrent,
BLUE, 0, wxT(
"rr-current-line" ) );
1378 PNS_DBG(
Dbg(), AddItem, &shoved,
GREEN, 0, wxT(
"rr-shoved-line" ) );
1381 int currentRank = aCurrent.
Rank();
1388 shoved.
SetRank( currentRank );
1398 if( i->ContainsLink( aSeg ) )
1411 via =
static_cast<VIA*
>( l );
1452 const LINE* l =
static_cast<const LINE*
>( aItem );
1464 PNS_DBG(
Dbg(), AddItem, &aL,
BLUE, 10000, wxT(
"push line stack failed" ) );
1495 wxString::Format(
"cur lc %d lnk %p cnt %d", i->LinkCount(), s, aLine.
LinkCount() ) );
1497 if( i->ContainsLink( s ) && !s->OfKind(
ITEM::VIA_T ) )
1523 int layer = aCurrent->
Layer();
1544 maxw = std::max( seg->
Width(), maxw );
1548 const ARC* arc =
static_cast<const ARC*
>(
link );
1549 maxw = std::max( arc->
Width(), maxw );
1555 if( maxw > 0 && maxw >= v->
Diameter( layer ) )
1559 wxString::Format(
"Fixup via: new-w %d via-w %d", maxw, v->
Diameter( layer ) ) );
1572 int sl = s->
Layer();
1579 for(
int i = 0; i < 2; i++ )
1617 auto viaEnd = jtViaEnd->Via();
1622 bool colliding =
m_currentNode->CheckColliding( viaEnd ).has_value();
1626 if( viaEnd && !current.
EndsWithVia() && colliding )
1649 wxString::Format( wxT(
"current sc=%d net=%s evia=%d" ),
1659 opts.
m_filter = [ this ] (
const ITEM* item,
const ITEM* aRefItem ) ->
bool
1686 nearest =
m_currentNode->NearestObstacle( ¤tLine, opts );
1691 wxString::Format(
"nearest %p %s rank %d",
1693 nearest->m_item->KindStr(),
1694 nearest->m_item->Rank() ) );
1704 PNS_DBG(
Dbg(), Message, wxT(
"no-nearest-item ") );
1710 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"iter %d: via-fixup %d" ), aIter, viaFixup?1:0 ) );
1713 ITEM* ni = nearest->m_item;
1716 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"NI: %s (%s) %p %d" ),
1719 : wxString( wxT(
"null" ) ),
1729 switch( ni->
Kind() )
1733 PNS_DBG(
Dbg(), BeginGroup, wxString::Format( wxT(
"iter %d: reverse-collide-via" ), aIter ), 0 );
1740 nearest->m_item->Layer() ) )
1742 PNS_DBG(
Dbg(), AddItem, nearest->m_item,
YELLOW, 100000, wxT(
"v2v nearesti" ) );
1761 PNS_DBG(
Dbg(), BeginGroup, wxString::Format( wxT(
"iter %d: reverse-collide-segment" ),
1804 PNS_DBG(
Dbg(), BeginGroup, wxString::Format( wxT(
"iter %d: reverse-collide-arc " ), aIter ), 0 );
1826 switch( ni->
Kind() )
1829 PNS_DBG(
Dbg(), BeginGroup, wxString::Format( wxT(
"iter %d: collide-segment " ), aIter ), 0 );
1842 PNS_DBG(
Dbg(), BeginGroup, wxString::Format( wxT(
"iter %d: collide-arc " ), aIter ), 0 );
1854 PNS_DBG(
Dbg(), BeginGroup, wxString::Format( wxT(
"iter %d: collide-via (fixup: %d)" ), aIter, 0 ), 0 );
1866 PNS_DBG(
Dbg(), BeginGroup, wxString::Format( wxT(
"iter %d: walk-solid " ), aIter ), 0);
1894 PNS_DBG(
Dbg(), Message, wxString::Format(
"ShoveStart [root: %d jts, current: %d jts]",
1914 PNS_DBG(
Dbg(), Message, wxString::Format(
"iter %d: node %p stack %d ",
m_iter,
1923 PNS_DBG(
Dbg(), Message, wxString::Format(
"Fail [time limit expired: %d iter %d iter limit %d",
1953 std::make_unique<ROOT_LINE_ENTRY>( std::move( aLine ), aPolicy ) );
1991 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"touch [found] uid=%llu type=%s"),
link->Uid(),
link->KindStr() ) );
2002 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"touch [create] uid=%llu type=%s"),
link->Uid(),
link->KindStr() ) );
2017 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"touch [create] uid=%llu"), aItem->
Uid() ) );
2023 PNS_DBG(
Dbg(), Message, wxString::Format( wxT(
"touch [create] uid=%llu"), aItem->
Uid() ) );
2043 maxWidth = std::max( line.Width(), maxWidth );
2047 area->Inflate( maxWidth );
2097 std::set<const ITEM*> itemsChk;
2099 for(
int pass = 0; pass < n_passes; pass++ )
2108 LINE* rootLine =
nullptr;
2113 rootLine = rootEntry->rootLine.get();
2117 if( rootEntry->isHead )
2122 if( optimizer.
Optimize( &lineToOpt, &optimized, rootLine ) )
2130 replaceLine( lineToOpt, optimized,
false, aNode );
2168 if ( iter->m_node == aNode )
2214 if ( iter->m_node == aNode )
2216 iter->m_locked =
false;
2246 rl->policy = aPolicy;
2252 rl->policy = aPolicy;
2280 for (
auto lnk : head.
Links() )
2282 if( lnk->BelongsTo( aNode ) )
2293 for(
auto& item : added )
2296 if( rootEntry && rootEntry->isHead )
2313 if( headEntry.origHead )
2317 PNS_DBG(
Dbg(), Message, wxString::Format(
"orig LinkC=%d RE=%p", headEntry.origHead->LinkCount(), rootEntry ) );
2319 assert( rootEntry );
2320 assert( rootEntry->rootLine );
2322 if( rootEntry->newLine )
2324 headEntry.newHead = rootEntry->newLine;
2325 headEntry.geometryModified = !rootEntry->newLine->CLine().CompareGeometry( rootEntry->rootLine->CLine() );
2327 wxString msg = wxString::Format(
2328 "head %d/%d [net %-20s]: root %p, lc-root %d, lc-new %d\n", i, (
int)
m_headLines.size(),
2329 iface->GetNetName( rootEntry->rootLine->Net() ).c_str().AsChar(), rootEntry->rootLine.get(), rootEntry->rootLine->LinkCount(), headEntry.newHead->LinkCount() );
2330 PNS_DBG(
Dbg(), AddItem, rootEntry->rootLine.get(),
CYAN, 0, msg );
2336 wxString msg = wxString::Format(
2337 "head %d/%d [net %-20s]: unmodified, lc-orig %d\n", i, (
int)
m_headLines.size(),
2338 iface->GetNetName( headEntry.origHead->Net() ).c_str().AsChar(),
2339 headEntry.origHead->LinkCount() );
2347 if( rootEntry->newVia )
2349 headEntry.geometryModified =
true;
2350 headEntry.theVia =
VIA_HANDLE( rootEntry->newVia->Pos(), rootEntry->newVia->Layers(), rootEntry->newVia->Net() );
2351 auto chk =
m_currentNode->FindViaByHandle( *headEntry.theVia );
2352 wxString msg = wxString::Format(
"[modif] via orig %p chk %p\n", headEntry.draggedVia, chk );
2355 assert( chk !=
nullptr );
2359 headEntry.theVia =
VIA_HANDLE( rootEntry->oldVia->Pos(), rootEntry->oldVia->Layers(), rootEntry->oldVia->Net() );
2360 auto chk =
m_currentNode->FindViaByHandle( *headEntry.theVia );
2361 wxString msg = wxString::Format(
"[unmodif] via orig %p chk %p\n", headEntry.draggedVia, chk );
2363 assert( chk !=
nullptr );
2391 PNS_DBG(
Dbg(), Message, wxString::Format(
"**** PreshoveCleanup %d -> %d\n", vc_prev, vc_post ) );
2393 if( vc_prev != vc_post )
2410 int currentHeadId = 0;
2418 std::vector<std::unique_ptr<ITEM>> heads;
2427 PNS_DBG(
Dbg(), Message, wxString::Format(
"process head-via [%d %d] node=%p", l.theVia->pos.x, l.theVia->pos.y,
m_currentNode ) );
2429 assert( realVia !=
nullptr );
2430 heads.emplace_back( realVia->Clone() );
2431 headSet.
Add( heads.back().get() );
2435 heads.emplace_back( l.origHead->Clone() );
2436 headSet.
Add( heads.back().get() );
2454 if( headLineEntry.theVia )
2465 viaRoot->oldVia = viaToDrag;
2466 headLineEntry.draggedVia = viaToDrag;
2468 st =
pushOrShoveVia( viaToDrag, ( headLineEntry.viaNewPos - viaToDrag->
Pos() ), 0,
true );
2476 assert( headLineEntry.origHead->LinkCount() == 0 );
2484 wxString::Format(
"touchRoot ohlc %d roots %d re=%p\n",
2485 headLineEntry.origHead->LinkCount(),
2490 LINE head( *headLineEntry.origHead );
2517 auto headVia =
Clone( head.
Via() );
2518 headVia->SetRank( 100000 );
2519 headLineEntry.origHead->LinkVia( headVia.get() );
2520 head.
LinkVia( headVia.get() );
2525 headRoot->isHead =
true;
2526 headRoot->rootLine = std::make_unique<PNS::LINE>( *headLineEntry.origHead );
2527 headRoot->policy = headLineEntry.policy;
2535 wxString::Format(
"headLC %d, rlLC %d oolc %d eov %d\n", head.
LinkCount(),
2536 headRoot->rootLine->LinkCount(),
2537 headLineEntry.origHead->LinkCount(),
2543 wxString::Format(
"Shove heads %d/%d h-lc=%d net=%s Line=%d Policy=%s",
2544 currentHeadId, totalHeads, head.
LinkCount(),
2545 iface->GetNetName( head.
Net() ), headRoot->newLine ? 1 : 0,
2547 : wxString( wxT(
"default[ne]" ) ) ) );
2568 wxString::Format(
"Shove status : %s after %d iterations, heads: %d",
2589 if( headEntry.prevVia )
2593 wxString::Format(
"Fail-restore via mod [%d, %d] orig [%d, %d]",
2594 headEntry.theVia->pos.x,
2595 headEntry.theVia->pos.y,
2596 headEntry.prevVia->pos.x,
2597 headEntry.prevVia->pos.y ) );
2599 headEntry.theVia = headEntry.prevVia;
2600 headEntry.geometryModified =
true;
2632 return wxT(
"default" );
2637 rv.Append(
"shove ");
2639 rv.Append(
"walk-forward ");
2641 rv.Append(
"walk-back ");
2643 rv.Append(
"ignore ");
2645 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.
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 the instance of our router.
ALGO_BASE(ROUTER *aRouter)
ROUTING_SETTINGS & Settings() const
Return current router settings.
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
Return the aIdx-th point of the line.
bool HasLockedSegments() const
int Rank() const override
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Assign a shape to the line (a polyline/line chain).
virtual void Mark(int aMarker) const override
const SHAPE_LINE_CHAIN & CLine() const
const VECTOR2I & CLastPoint() const
void SetRank(int aRank) override
bool Walkaround(SHAPE_LINE_CHAIN aObstacle, SHAPE_LINE_CHAIN &aPrePath, SHAPE_LINE_CHAIN &aWalk, SHAPE_LINE_CHAIN &aPost, bool aCw) const
Calculate a line tightly wrapping a convex hull of an obstacle object (aObstacle).
SHAPE_LINE_CHAIN & Line()
Modifiable accessor to the underlying shape.
const SHAPE * Shape(int aLayer) const override
Return the shape of the line.
virtual int Marker() const override
void AppendVia(const VIA &aVia)
virtual void Unmark(int aMarker=-1) const override
const SEG CSegment(int aIdx) const
virtual LINE * Clone() const override
Return a deep copy of the item.
int Width() const
Return line width.
void Unlink(const LINKED_ITEM *aLink)
std::vector< LINKED_ITEM * > & Links()
Return the list of links from the owning node that constitute this line (or NULL if the line is not l...
int LinkCount() const
Return the number of segments that were assembled together to form this line.
virtual void ClearLinks()
Erase the linking information. Used to detach the line from the owning node.
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
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.
std::optional< OBSTACLE > OPT_OBSTACLE
int Depth() const
Return the number of nodes in the inheritance chain (wrs to the root node).
void KillChildren()
Destroy all child nodes. Applicable only to the root node.
void Remove(ARC *aArc)
Remove an item from this branch.
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))
A quick shortcut to optimize a line without creating and setting up an optimizer.
@ 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
Return 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)
COLLISION_FILTER_FUNC m_collisionFilter
void SetCollisionFilter(COLLISION_FILTER_FUNC aFunc)
std::vector< LINE > m_lineStack
std::vector< SPRINGBACK_TAG > m_nodeStack
@ SHP_DONT_LOCK_ENDPOINTS
bool patchTadpoleVia(ITEM *nearest, LINE ¤t)
SHOVE_STATUS onCollidingArc(LINE &aCurrent, ARC *aObstacleArc)
bool shoveLineToHullSet(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine, const HULL_SET &aHulls, bool aPermitAdjustingStart=false, bool aPermitAdjustingEnd=false)
std::vector< std::unique_ptr< ROOT_LINE_ENTRY > > m_rootLineHistoryEntries
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
void SetClearanceOverride(CLEARANCE_OVERRIDE_FUNC aFunc)
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)
ROOT_LINE_ENTRY * allocRootLine(std::unique_ptr< LINE > aLine, int aPolicy=SHP_DEFAULT)
NODE * reduceSpringback(const ITEM_SET &aHeadSet)
bool AddLockedSpringbackNode(NODE *aNode)
ROOT_LINE_ENTRY * findRootLine(const LINE &aLine) const
int getClearance(const ITEM *aA, const ITEM *aB, CLEARANCE_ASPECT aAspect=CLEARANCE_ASPECT::ASP_SHOVE_FORWARD) const
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)
CLEARANCE_OVERRIDE_FUNC m_overrideClearance
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 aOverrideClearance=0)
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
void SetIterationLimit(const int aIterLimit)
void SetAllowedPolicies(std::vector< WALK_POLICY > aPolicies, bool aAnyCompletePolicyIsSuccess=false)
void RestrictToCluster(bool aEnabled, const TOPOLOGY::CLUSTER &aCluster)
void SetSolidsOnly(bool aSolidsOnly)
STATUS Route(const LINE &aInitialPath, LINE &aWalkPath, bool aOptimize=true)
static int 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)
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.
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)
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
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 VECTOR2I & CLastPoint() const
Return the last point in the line chain.
const std::string Format(bool aCplusPlus=true) const override
bool IsArcSegment(size_t aSegment) const
void Insert(size_t aVertex, const VECTOR2I &aP)
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const override
Check if point aP lies inside a closed shape.
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.
std::function< int(const ITEM *, const ITEM *, CLEARANCE_ASPECT)> CLEARANCE_OVERRIDE_FUNC
PNS_OPTIMIZATION_EFFORT
Optimization effort.
std::function< bool(const ITEM *, const ITEM *)> COLLISION_FILTER_FUNC
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
COLLISION_FILTER_FUNC m_filter
CLEARANCE_OVERRIDE_FUNC m_overrideClearance
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::vector< ITEM * > m_items
LINE lines[MaxWalkPolicies]
STATUS status[MaxWalkPolicies]
VECTOR2< int32_t > VECTOR2I