64 if( aIncludeInChangedArea )
71 PNS_DBG(
Dbg(), AddShape, &r,
BLUE, 0, wxT(
"shove-changed-area" ) );
78 bool foundPredecessor =
false;
79 LINE* rootLine =
nullptr;
88 for(
auto link : aOld.
Links() )
94 rootLine = oldLineIter->second;
95 foundPredecessor =
true;
101 if( !foundPredecessor )
103 for(
auto link : aOld.
Links() )
107 rootLine = aOld.
Clone();
125 for(
auto link : aNew.
Links() )
177 std::unordered_set<LINE*> alreadyDeleted;
181 auto it2 = alreadyDeleted.find( it.second );
183 if( it2 == alreadyDeleted.end() )
185 alreadyDeleted.insert( it.second );
207 const LINE& aShovedLine )
const
231 int obstacleLineWidth = aObstacleLine.
Width();
232 int clearance =
getClearance( &aCurLine, &aObstacleLine );
244 if( ! aObstacleLine.
Walkaround( hull, path_cw,
true ) )
247 if( ! aObstacleLine.
Walkaround( hull, path_ccw,
false ) )
255 if( aObstacleLine.
CPoint( -1 ) != shortest.
CPoint( -1 ) )
280 PNS_DBG(
Dbg(), BeginGroup,
"shove-details", 1 );
282 for( attempt = 0; attempt < 4; attempt++ )
284 bool invertTraversal = ( attempt >= 2 );
285 bool clockwise = attempt % 2;
286 int vFirst = -1, vLast = -1;
288 LINE l( aObstacleLine );
291 for(
int i = 0; i < (int) aHulls.size(); i++ )
293 const SHAPE_LINE_CHAIN& hull = aHulls[invertTraversal ? aHulls.size() - 1 - i : i];
319 for(
int i = 0; i < std::min(
path.PointCount(), obs.
PointCount() ); i++ )
330 for(
int i =
path.PointCount() - 1; i >= 0 && k >= 0; i--, k-- )
339 if( ( vFirst < 0 || vLast < 0 ) && !
path.CompareGeometry( aObstacleLine.
CLine() ) )
361 if(
path.SelfIntersecting() )
410 bool obstacleIsHead =
false;
416 obstacleIsHead =
true;
440 int obstacleLineWidth = aObstacleLine.
Width();
441 int clearance =
getClearance( &aCurLine, &aObstacleLine ) + 1;
445 hulls.reserve( currentLineSegmentCount + 1 );
448 aCurLine.
Net(), aObstacleLine.
Net(), clearance ) );
450 for(
int i = 0; i < currentLineSegmentCount; i++ )
466 seg.
Hull( clearance + extra, obstacleLineWidth, aObstacleLine.
Layer() );
468 hulls.push_back( hull );
480 hulls.push_back( aCurLine.
Via().
Hull( viaClearance, obstacleLineWidth ) );
500 LINE shovedLine( obstacleLine );
505 PNS_DBG(
Dbg(), Message,
"try walk (locked segments)");
511 const double extensionWalkThreshold = 1.0;
515 double extensionFactor = 0.0;
518 extensionFactor = shovedLen / obsLen - 1.0;
520 if( extensionFactor > extensionWalkThreshold )
527 PNS_DBG(
Dbg(), AddItem, aObstacleSeg,
BLUE, 0, wxT(
"shove-changed-area" ) );
530 PNS_DBG(
Dbg(), AddItem, &shovedLine,
BLUE, 10000, wxT(
"shoved-line" ) );
543 int rank = aCurrent.
Rank();
544 shovedLine.
SetRank( rank - 1 );
564 LINE shovedLine( obstacleLine );
565 ARC tmp( *aObstacleArc );
572 const double extensionWalkThreshold = 1.0;
576 double extensionFactor = 0.0;
579 extensionFactor = shovedLen / obsLen - 1.0;
581 if( extensionFactor > extensionWalkThreshold )
587 PNS_DBG(
Dbg(), AddItem, &aCurrent,
RED, 10000, wxT(
"current-line" ) );
588 PNS_DBG(
Dbg(), AddItem, &obstacleLine,
GREEN, 10000, wxT(
"obstacle-line" ) );
589 PNS_DBG(
Dbg(), AddItem, &shovedLine,
BLUE, 10000, wxT(
"shoved-line" ) );
601 int rank = aCurrent.
Rank();
602 shovedLine.
SetRank( rank - 1 );
620 LINE shovedLine( aObstacle );
624 PNS_DBG(
Dbg(), AddItem, &aObstacle,
RED, 100000, wxT(
"obstacle-line" ) );
625 PNS_DBG(
Dbg(), AddItem, &aCurrent,
GREEN, 150000, wxT(
"current-line" ) );
626 PNS_DBG(
Dbg(), AddItem, &shovedLine,
BLUE, 200000, wxT(
"shoved-line" ) );
641 int rank = aObstacle.
Rank();
642 shovedLine.
SetRank( rank - 1 );
661 LINE walkaroundLine( aCurrent );
691 PNS_DBG(
Dbg(), BeginGroup,
"walk-cluster", 1 );
693 for(
auto item : cluster )
695 PNS_DBG(
Dbg(), AddItem, item,
RED, 10000, wxT(
"cl-item" ) );
706 int currentRank = aCurrent.
Rank();
709 bool success =
false;
711 for(
int attempt = 0; attempt < 2; attempt++ )
713 if( attempt == 1 ||
Settings().JumpOverObstacles() )
716 nextRank = currentRank - 1;
720 nextRank = currentRank + 10000;
774 walkaroundLine.
SetRank( nextRank );
776 PNS_DBG(
Dbg(), AddItem, &aCurrent,
RED, 10000, wxT(
"current-line" ) );
777 PNS_DBG(
Dbg(), AddItem, &walkaroundLine,
BLUE, 10000, wxT(
"walk-line" ) );
808 aDraggedVia.
valid =
true;
877 if ( aForce.
x == 0 && aForce.
y == 0 )
901 p0_pushed += aForce.
Resize( 2 );
904 std::unique_ptr<VIA> pushedVia =
Clone( *aVia );
905 pushedVia->SetPos( p0_pushed );
906 pushedVia->Mark( aVia->
Marker() );
918 if( lp.first.HasLockedSegments() )
921 assert( segIndex == 0 || ( segIndex == ( lp.first.SegmentCount() - 1 ) ) );
926 lp.second = lp.first;
927 lp.second.ClearLinks();
928 lp.second.DragCorner( p0_pushed, lp.second.CLine().Find( p0 ) );
929 lp.second.AppendVia( *pushedVia );
930 draggedLines.push_back( lp );
934 pushedVia->SetRank( aCurrentRank - 1 );
954 if( lp.first.Marker() &
MK_HEAD )
966 if( lp.second.SegmentCount() )
969 lp.second.SetRank( aCurrentRank - 1 );
996 assert( aObstacleVia );
1002 bool lineCollision =
false;
1003 bool viaCollision =
false;
1006 PNS_DBG(
Dbg(), BeginGroup,
"push-via-by-line", 1 );
1010 VIA vtmp ( *aObstacleVia );
1017 LINE* currentLine = (
LINE*) aCurrent;
1029 clearance + currentLine->
Width() / 2,
1035 const VIA& currentVia = currentLine->
Via();
1038 viaCollision = currentVia.
Shape()->
Collide( vtmp.
Shape(), viaClearance, &mtvVia );
1050 else if ( lineCollision )
1070 LINE cur( aCurrent );
1074 LINE shoved( aCurrent );
1116 LINE head( aCurrent );
1140 PNS_DBG(
Dbg(), AddItem, &aCurrent,
BLUE, 0, wxT(
"rr-current-line" ) );
1141 PNS_DBG(
Dbg(), AddItem, &shoved,
GREEN, 0, wxT(
"rr-shoved-line" ) );
1143 int currentRank = aCurrent.
Rank();
1149 shoved.
SetRank( currentRank );
1161 if( i->ContainsLink( aSeg ) )
1174 if( i->ContainsLink( aSeg ) )
1188 LINE* l =
static_cast<LINE*
>( aItem );
1200 PNS_DBG(
Dbg(), AddItem, &aL,
BLUE, 10000, wxT(
"push line stack failed" ) );
1230 if( i->ContainsLink( s ) )
1260 for(
auto link : jv->
Links() )
1264 auto seg =
static_cast<SEGMENT*
>( link.item );
1265 maxw = std::max( seg->Width(), maxw );
1269 auto arc =
static_cast<ARC*
>( link.item );
1270 maxw = std::max( arc->Width(), maxw );
1276 if( maxw > 0 && maxw >= v->
Diameter() )
1299 for(
int i = 0; i < 2; i++ )
1305 if( !v || v->
Diameter() > s->Width() )
1347 nearest->m_item->KindStr(), nearest->m_item->Rank() ) );
1349 PNS_DBG(
Dbg(), AddShape, nearest->m_item->Shape(),
YELLOW, 10000, wxT(
"nearest") );
1359 PNS_DBG(
Dbg(), Message,
"no-nearest-item ");
1368 ITEM* ni = nearest->m_item;
1376 switch( ni->
Kind() )
1399 aIter ).ToStdString(), 0 );
1442 switch( ni->
Kind() )
1578 LINE head( aCurrentHead );
1592 headSet.
Add( aCurrentHead );
1611 PNS_DBG(
Dbg(), AddItem, &head,
CYAN, 0, wxT(
"head, after shove" ) );
1615 std::unique_ptr< VIA >headVia =
Clone( head.
Via() );
1617 headVia->SetRank( 100000 );
1682 const LINE* headOrig =
static_cast<const LINE*
>( item );
1688 headSet.
Add( *headOrig );
1708 const LINE* headOrig =
static_cast<const LINE*
>( item );
1709 LINE head( *headOrig );
1723 std::unique_ptr< VIA > headVia =
Clone( head.
Via() );
1725 headVia->SetRank( 100000 );
1765 if( item->Net() == handle.
net && item->Layers().Overlaps(handle.
layers) )
1766 return static_cast<VIA*
>( item );
1792 VIA headVia ( *viaToDrag );
1793 headVia.
SetPos( aWhere );
1794 headSet.
Add( headVia );
1798 if( prevViaHandle.
valid )
1800 aNewVia = prevViaHandle;
1844 for(
auto link : aLine->
Links() )
1846 if(
auto seg = dyn_cast<SEGMENT*>( link ) )
1872 maxWidth = std::max( line.Width(), maxWidth );
1876 area->Inflate( maxWidth );
1921 for(
int pass = 0; pass < n_passes; pass++ )
1929 if( !( line.Marker() &
MK_HEAD ) )
1934 if( optimizer.
Optimize( &line, &optimized, root ) )
1936 PNS_DBG(
Dbg(), AddShape, &line.CLine(),
BLUE, 0, wxT(
"shove-pre-opt" ) );
1939 PNS_DBG(
Dbg(), AddItem, root,
RED, 0, wxT(
"shove-root-opt" ) );
1944 PNS_DBG(
Dbg(), AddShape, &line.CLine(),
GREEN, 0, wxT(
"shove-post-opt" ) );
1992 if ( iter->m_node == aNode )
2031 if ( iter->m_node == aNode )
2033 iter->m_locked =
false;
std::optional< BOX2I > OPT_BOX2I
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
virtual void SetIteration(int iter)
void Add(const LINE &aLine)
const ENTRIES & CItems() const
Base class for PNS router board items.
bool Collide(const ITEM *aOther, const NODE *aNode, bool aDifferentNetsOnly=true, int aOverrideClearance=-1) const
Check for a collision (clearance violation) with between us and item aOther.
PnsKind Kind() const
Return the type (kind) of the item.
virtual void SetRank(int aRank)
virtual int Layer() const
const LAYER_RANGE & Layers() const
bool OfKind(int aKindMask) const
Return true if the item's type matches the mask aKindMask.
bool LayersOverlap(const ITEM *aOther) const
Return true if the set of layers spanned by aOther overlaps our layers.
virtual void Mark(int aMarker) 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 LINKED_ITEMS & LinkList() const
bool IsStitchingVia() const
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
virtual void Unmark(int aMarker=-1) const override
const VECTOR2I & CPoint(int aIdx) const
const SHAPE * Shape() const override
Modifiable accessor to the underlying shape.
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
bool HasLockedSegments() const
SHAPE_LINE_CHAIN & Line()
virtual LINE * Clone() const override
Return a deep copy of the item.
bool IsLinkedChecked() const
Assign a shape to the line (a polyline/line chain).
virtual int Marker() const override
void AppendVia(const VIA &aVia)
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.
int Width() const
Return true if the line is geometrically identical as line aOther.
int Rank() const override
virtual void ClearLinks()
Return the number of segments that were assembled together to form this line.
void Log(EVENT_TYPE evt, const VECTOR2I &pos=VECTOR2I(), const ITEM *item=nullptr, const SIZES_SETTINGS *sizes=nullptr)
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...
void RemoveByMarker(int aMarker)
int GetClearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true) const
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Replace an item with another one.
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
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION|MK_HOLE)
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
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).
OPT_OBSTACLE NearestObstacle(const LINE *aLine, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=nullptr, bool aUseClearanceEpsilon=true)
Follow the line in search of an obstacle that is nearest to the starting to the line's starting point...
int GetHoleClearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true) const
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
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 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
const SHAPE_LINE_CHAIN Hull(int aClearance, int aWalkaroundThickness, int aLayer=-1) const override
SHOVE_STATUS shoveIteration(int aIter)
SHOVE_STATUS shoveMainLoop()
std::vector< SHAPE_LINE_CHAIN > HULL_SET
std::pair< LINE, LINE > LINE_PAIR
int getHoleClearance(const ITEM *aA, const ITEM *aB) const
std::vector< LINE > m_lineStack
LINE * findRootLine(LINE *aLine)
std::vector< SPRINGBACK_TAG > m_nodeStack
SHOVE_STATUS onCollidingArc(LINE &aCurrent, ARC *aObstacleArc)
SHOVE_STATUS ShoveObstacleLine(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=nullptr)
std::optional< LINE > OPT_LINE
void SetInitialLine(LINE &aInitial)
bool checkShoveDirection(const LINE &aCurLine, const LINE &aObstacleLine, const LINE &aShovedLine) const
SHOVE_STATUS pushOrShoveVia(VIA *aVia, const VECTOR2I &aForce, int aCurrentRank)
SHOVE_STATUS onCollidingSegment(LINE &aCurrent, SEGMENT *aObstacleSeg)
SHOVE(NODE *aWorld, ROUTER *aRouter)
void DisablePostShoveOptimizations(int aMask)
SHOVE_STATUS ShoveLines(const LINE &aCurrentHead)
bool RewindSpringbackTo(NODE *aNode)
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
OPT_BOX2I totalAffectedArea() const
bool RewindToLastLockedNode()
void replaceLine(LINE &aOld, LINE &aNew, bool aIncludeInChangedArea=true, NODE *aNode=nullptr)
SHOVE_STATUS ShoveDraggingVia(const VIA_HANDLE aOldVia, const VECTOR2I &aWhere, VIA_HANDLE &aNewVia)
void sanityCheck(LINE *aOld, LINE *aNew)
int m_restrictSpringbackTagId
NODE * reduceSpringback(const ITEM_SET &aHeadSet, VIA_HANDLE &aDraggedVia)
void runOptimizer(NODE *aNode)
SHOVE_STATUS shoveLineToHullSet(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine, const HULL_SET &aHulls)
bool pushSpringback(NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
SHOVE_STATUS onCollidingLine(LINE &aCurrent, LINE &aObstacle)
void UnlockSpringbackNode(NODE *aNode)
bool AddLockedSpringbackNode(NODE *aNode)
NODE * m_springbackDoNotTouchNode
SHOVE_STATUS shoveLineFromLoneVia(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
int getClearance(const ITEM *aA, const ITEM *aB) const
SHOVE_STATUS onReverseCollidingVia(LINE &aCurrent, VIA *aObstacleVia)
std::vector< LINE > m_optimizerQueue
SHOVE_STATUS onCollidingSolid(LINE &aCurrent, ITEM *aObstacle, OBSTACLE &aObstacleInfo)
void unwindLineStack(LINKED_ITEM *aSeg)
bool fixupViaCollisions(const LINE *aCurrent, OBSTACLE &obs)
void replaceItems(ITEM *aOld, std::unique_ptr< ITEM > aNew)
SHOVE_STATUS ShoveMultiLines(const ITEM_SET &aHeadSet)
std::unordered_map< const LINKED_ITEM *, LINE * > m_rootLineHistory
const LINE NewHead() const
std::vector< LINE_PAIR > LINE_PAIR_VEC
void SetSpringbackDoNotTouchNode(NODE *aNode)
SHOVE_STATUS onCollidingVia(ITEM *aCurrent, VIA *aObstacleVia, OBSTACLE &aObstacleInfo)
const std::set< ITEM * > AssembleCluster(ITEM *aStart, int aLayer)
const VECTOR2I & Pos() const
const SHAPE * Shape() const override
Return the geometrical shape of the item.
const VIA_HANDLE MakeHandle() const
void SetDiameter(int aDiameter)
void SetPos(const VECTOR2I &aPos)
const SHAPE_LINE_CHAIN Hull(int aClearance=0, int aWalkaroundThickness=0, int aLayer=-1) const override
void SetIterationLimit(const int aIterLimit)
void SetSolidsOnly(bool aSolidsOnly)
WALKAROUND_STATUS Route(const LINE &aInitialPath, LINE &aWalkPath, bool aOptimize=true)
void RestrictToSet(bool aEnabled, const std::set< ITEM * > &aSet)
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)
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.
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
int PointCount() const
Return the number of points (vertices) in this line chain.
void Clear()
Remove all points from the line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
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,...
VECTOR2_TRAITS< int >::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.
static VIA * findViaByHandle(NODE *aNode, const VIA_HANDLE &handle)
OPT_BOX2I ChangedArea(const ITEM *aItemA, const ITEM *aItemB)
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
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
std::vector< FAB_LAYER_COLOR > dummy
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.