64 if( aIncludeInChangedArea )
80 bool foundPredecessor =
false;
81 LINE* rootLine =
nullptr;
90 for(
auto link : aOld.
Links() )
96 rootLine = oldLineIter->second;
97 foundPredecessor =
true;
103 if( !foundPredecessor )
105 for(
auto link : aOld.
Links() )
109 rootLine = aOld.
Clone();
127 for(
auto link : aNew.
Links() )
179 std::unordered_set<LINE*> alreadyDeleted;
183 auto it2 = alreadyDeleted.find( it.second );
185 if( it2 == alreadyDeleted.end() )
187 alreadyDeleted.insert( it.second );
209 const LINE& aShovedLine )
const 215 bool inside = checker.IsInside();
233 int obstacleLineWidth = aObstacleLine.
Width();
234 int clearance =
getClearance( &aCurLine, &aObstacleLine );
237 if( holeClearance + aCurLine.
Via().
Drill() / 2 > clearance + aCurLine.
Via().
Diameter() / 2 )
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 for( attempt = 0; attempt < 4; attempt++ )
282 bool invertTraversal = ( attempt >= 2 );
283 bool clockwise = attempt % 2;
284 int vFirst = -1, vLast = -1;
286 LINE l( aObstacleLine );
289 for(
int i = 0; i < (int) aHulls.size(); i++ )
291 const SHAPE_LINE_CHAIN& hull = aHulls[invertTraversal ? aHulls.size() - 1 - i : i];
310 for(
int i = 0; i < std::min(
path.PointCount(), obs.
PointCount() ); i++ )
321 for(
int i =
path.PointCount() - 1; i >= 0 && k >= 0; i--, k-- )
330 if( ( vFirst < 0 || vLast < 0 ) && !
path.CompareGeometry( aObstacleLine.
CLine() ) )
352 if(
path.SelfIntersecting() )
363 sprintf( str,
"att-%d-shoved", attempt );
403 bool obstacleIsHead =
false;
409 obstacleIsHead =
true;
429 int obstacleLineWidth = aObstacleLine.
Width();
430 int clearance =
getClearance( &aCurLine, &aObstacleLine ) + 1;
434 hulls.reserve( currentLineSegmentCount + 1 );
438 aCurLine.
Net(), aObstacleLine.
Net(), clearance ) );
441 for(
int i = 0; i < currentLineSegmentCount; i++ )
451 seg.Hull( clearance + extra, obstacleLineWidth, aObstacleLine.
Layer() );
453 hulls.push_back( hull );
462 if( holeClearance +
via.Drill() / 2 > viaClearance +
via.Diameter() / 2 )
463 viaClearance = holeClearance +
via.Drill() / 2 -
via.Diameter() / 2;
465 hulls.push_back( aCurLine.
Via().
Hull( viaClearance, obstacleLineWidth ) );
470 sprintf( str,
"current-cl-%d", clearance );
491 LINE shovedLine( obstacleLine );
499 const double extensionWalkThreshold = 1.0;
503 double extensionFactor = 0.0;
506 extensionFactor = shovedLen / obsLen - 1.0;
508 if( extensionFactor > extensionWalkThreshold )
540 int rank = aCurrent.
Rank();
541 shovedLine.
SetRank( rank - 1 );
561 LINE shovedLine( obstacleLine );
562 ARC tmp( *aObstacleArc );
569 const double extensionWalkThreshold = 1.0;
573 double extensionFactor = 0.0;
576 extensionFactor = shovedLen / obsLen - 1.0;
578 if( extensionFactor > extensionWalkThreshold )
604 int rank = aCurrent.
Rank();
605 shovedLine.
SetRank( rank - 1 );
623 LINE shovedLine( aObstacle );
645 int rank = aObstacle.
Rank();
646 shovedLine.
SetRank( rank - 1 );
665 LINE walkaroundLine( aCurrent );
697 int currentRank = aCurrent.
Rank();
700 bool success =
false;
702 for(
int attempt = 0; attempt < 2; attempt++ )
704 if( attempt == 1 ||
Settings().JumpOverObstacles() )
707 nextRank = currentRank - 1;
712 nextRank = currentRank + 10000;
767 walkaroundLine.
SetRank( nextRank );
806 aDraggedVia.
valid =
true;
875 if ( aForce.
x == 0 && aForce.
y == 0 )
899 p0_pushed += aForce.
Resize( 2 );
902 std::unique_ptr<VIA> pushedVia =
Clone( *aVia );
903 pushedVia->SetPos( p0_pushed );
904 pushedVia->Mark( aVia->
Marker() );
906 for(
ITEM* item : jt->LinkList() )
910 LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
916 if( lp.first.HasLockedSegments() )
919 assert( segIndex == 0 || ( segIndex == ( lp.first.SegmentCount() - 1 ) ) );
924 lp.second = lp.first;
925 lp.second.ClearLinks();
926 lp.second.DragCorner( p0_pushed, lp.second.CLine().Find( p0 ) );
927 lp.second.AppendVia( *pushedVia );
928 draggedLines.push_back( lp );
932 pushedVia->SetRank( aCurrentRank - 1 );
940 if( jt->IsStitchingVia() )
951 if( lp.first.Marker() &
MK_HEAD )
963 if( lp.second.SegmentCount() )
966 lp.second.SetRank( aCurrentRank - 1 );
994 bool lineCollision =
false;
995 bool viaCollision =
false;
998 PNS_DBG(
Dbg(), BeginGroup,
"push-via-by-line" );
1002 LINE* currentLine = (
LINE*) aCurrent;
1010 clearance + currentLine->
Width() / 2,
1016 const VIA& currentVia = currentLine->
Via();
1017 int viaClearance =
getClearance( ¤tVia, aObstacleVia );
1019 viaCollision = aObstacleVia->
Shape()->
Collide( currentVia.
Shape(), viaClearance,
1032 else if ( lineCollision )
1051 LINE cur( aCurrent );
1055 LINE shoved( aCurrent );
1065 LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
1097 LINE head( aCurrent );
1119 int currentRank = aCurrent.
Rank();
1125 shoved.
SetRank( currentRank );
1135 if( i->ContainsLink( aSeg ) )
1143 if( i->ContainsLink( aSeg ) )
1157 LINE* l = static_cast<LINE*>( aItem );
1195 if( i->ContainsLink( s ) )
1231 nearest->m_item->KindStr() ) );
1240 PNS_DBG(
Dbg(), Message,
"no-nearest-item ");
1244 ITEM* ni = nearest->m_item;
1252 switch( ni->
Kind() )
1308 switch( ni->
Kind() )
1433 LINE head( aCurrentHead );
1447 headSet.
Add( aCurrentHead );
1470 std::unique_ptr< VIA >headVia =
Clone( head.
Via() );
1472 headVia->SetRank( 100000 );
1537 const LINE* headOrig = static_cast<const LINE*>( item );
1543 headSet.
Add( *headOrig );
1563 const LINE* headOrig = static_cast<const LINE*>( item );
1564 LINE head( *headOrig );
1578 std::unique_ptr< VIA > headVia =
Clone( head.
Via() );
1580 headVia->SetRank( 100000 );
1620 if( item->Net() == handle.
net && item->Layers().Overlaps(handle.
layers) )
1621 return static_cast<VIA*>( item );
1647 VIA headVia ( *viaToDrag );
1648 headVia.
SetPos( aWhere );
1649 headSet.
Add( headVia );
1653 if( prevViaHandle.
valid )
1655 aNewVia = prevViaHandle;
1699 for(
auto link : aLine->
Links() )
1701 if(
auto seg = dyn_cast<SEGMENT*>( link ) )
1727 maxWidth = std::max( line.Width(), maxWidth );
1731 area->Inflate( maxWidth );
1777 for(
int pass = 0; pass < n_passes; pass++ )
1783 if( !( line.Marker() &
MK_HEAD ) )
1788 if( optimizer.
Optimize( &line, &optimized, root ) )
1839 if ( iter->m_node == aNode )
1878 if ( iter->m_node == aNode )
1880 iter->m_locked =
false;
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION|MK_HOLE)
LINE * findRootLine(LINE *aLine)
const SHAPE_LINE_CHAIN & CLine() const
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
VECTOR2_TRAITS< int >::extended_type extended_type
#define PNS_DBGN(dbg, method)
virtual void SetIteration(int iter)
Base class for PNS router board items.
const VIA_HANDLE MakeHandle() const
ROUTER * Router() const
Return current router settings.
long long int Length() const
Return length of the line chain in Euclidean metric.
int m_restrictSpringbackTagId
virtual int Layer() const
Keep the router "world" - i.e.
VECTOR2I::extended_type ecoord
SHOVE_STATUS onCollidingSolid(LINE &aCurrent, ITEM *aObstacle)
void unwindLineStack(LINKED_ITEM *aSeg)
virtual void Mark(int aMarker) const
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).
int GetClearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true) const
const LINE NewHead() const
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
const SEG CSegment(int aIdx) const
Set line width.
SHOVE_STATUS shoveLineToHullSet(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine, const HULL_SET &aHulls)
SHOVE_STATUS onCollidingArc(LINE &aCurrent, ARC *aObstacleArc)
const SHAPE_LINE_CHAIN Hull(int aClearance=0, int aWalkaroundThickness=0, int aLayer=-1) const override
int Rank() const override
Base class for all P&S algorithms (shoving, walkaround, line placement, dragging, etc....
void SetRestrictArea(const BOX2I &aArea, bool aStrict=true)
std::vector< LINE > m_optimizerQueue
bool RewindSpringbackTo(NODE *aNode)
void SetSingleDirection(bool aForceSingleDirection)
int JointCount() const
Return the number of nodes in the inheritance chain (wrs to the root node).
std::pair< LINE, LINE > LINE_PAIR
WALKAROUND_STATUS Route(const LINE &aInitialPath, LINE &aWalkPath, bool aOptimize=true)
void AppendVia(const VIA &aVia)
virtual void EndGroup(const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
void AddPolyline(const SHAPE_LINE_CHAIN &aPolyline)
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
SHOVE_STATUS ShoveObstacleLine(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
static double DefaultAccuracyForPCB()
OPT_BOX2I ChangedArea(const ITEM *aItemA, const ITEM *aItemB)
const SHAPE_LINE_CHAIN Reverse() const
Reverse point order in the line chain.
NODE * m_springbackDoNotTouchNode
int PointCount() const
Return the number of points (vertices) in this line chain.
SHOVE_STATUS pushOrShoveVia(VIA *aVia, const VECTOR2I &aForce, int aCurrentRank)
void Add(const LINE &aLine)
const SHAPE * Shape() const override
Return the geometrical shape of the item.
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
const VECTOR2I & Pos() const
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,...
void SetSpringbackDoNotTouchNode(NODE *aNode)
int GetHoleClearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true) const
void DisablePostShoveOptimizations(int aMask)
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I &aV=VECTOR2I(0, 0))
void Remove(ARC *aArc)
Remove an item from this branch.
std::vector< LINE_PAIR > LINE_PAIR_VEC
SHOVE_STATUS onCollidingLine(LINE &aCurrent, LINE &aObstacle)
bool LayersOverlap(const ITEM *aOther) const
Return true if the set of layers spanned by aOther overlaps our layers.
const VECTOR2I & CPoint(int aIdx) const
SHOVE_STATUS onReverseCollidingVia(LINE &aCurrent, VIA *aObstacleVia)
std::vector< SHAPE_LINE_CHAIN > HULL_SET
void SetCollisionMask(int aMask)
const std::set< ITEM * > AssembleCluster(ITEM *aStart, int aLayer)
static LIB_SYMBOL * dummy()
Used to draw a dummy shape when a LIB_SYMBOL is not found in library.
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Return the shape of the line.
ROUTING_SETTINGS & Settings() const
Return the logger object, allowing to dump geometry to a file.
bool IsLinkedChecked() const
Assign a shape to the line (a polyline/line chain).
OPT_BOX2I totalAffectedArea() const
NODE * reduceSpringback(const ITEM_SET &aHeadSet, VIA_HANDLE &aDraggedVia)
const SHAPE * Shape() const override
Modifiable accessor to the underlying shape.
SHOVE_STATUS ShoveLines(const LINE &aCurrentHead)
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
A 2D point on a given set of layers and belonging to a certain net, that links together a number of b...
bool IsArcSegment(size_t aSegment) const
bool AddLockedSpringbackNode(NODE *aNode)
SHOVE_STATUS onCollidingVia(ITEM *aCurrent, VIA *aObstacleVia)
void runOptimizer(NODE *aNode)
virtual void AddBox(const BOX2I &aB, const KIGFX::COLOR4D &aColor, const std::string &aName, const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
void sanityCheck(LINE *aOld, LINE *aNew)
SHOVE_STATUS shoveIteration(int aIter)
static VIA * findViaByHandle(NODE *aNode, const VIA_HANDLE &handle)
PNS_OPTIMIZATION_EFFORT OptimizerEffort() const
Set the optimizer effort. Bigger means cleaner traces, but slower routing.
virtual void AddSegment(const SEG &aS, const KIGFX::COLOR4D &aColor, const std::string &aName, const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
void RestrictToSet(bool aEnabled, const std::set< ITEM * > &aSet)
#define PNS_DBG(dbg, method,...)
SHOVE(NODE *aWorld, ROUTER *aRouter)
DEBUG_DECORATOR * Dbg() const
bool Collide(const ITEM *aOther, const NODE *aNode, bool aDifferentNetsOnly=true) const
Check for a collision (clearance violation) with between us and item aOther.
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, const KIGFX::COLOR4D &aColor, int aWidth, const std::string &aName, const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
void SetSolidsOnly(bool aSolidsOnly)
std::unordered_map< const LINKED_ITEM *, LINE * > m_rootLineHistory
bool pushSpringback(NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
virtual void SetRank(int aRank)
int ShoveIterationLimit() const
SHOVE_STATUS onCollidingSegment(LINE &aCurrent, SEGMENT *aObstacleSeg)
const LINKED_ITEMS & LinkList() const
const std::string Format() const override
void SetRank(int aRank) override
Reduce corner cost iteratively.
void UnlockSpringbackNode(NODE *aNode)
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
SHAPE_LINE_CHAIN & Line()
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 SetPos(const VECTOR2I &aPos)
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Replace an item with another one.
void RemoveByMarker(int aMarker)
std::vector< SPRINGBACK_TAG > m_nodeStack
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
const BOX2I & VisibleViewArea() const
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
virtual void BeginGroup(const std::string &name, const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
virtual int Marker() const override
Reduce corner cost by merging obtuse segments.
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
virtual void Message(const wxString &msg, const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
Do not attempt to optimize if the resulting line's corner count is outside the predefined range.
virtual void ClearLinks()
Return the number of segments that were assembled together to form this line.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
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 SHAPE_LINE_CHAIN CLine() const
bool RewindToLastLockedNode()
bool checkShoveDirection(const LINE &aCurLine, const LINE &aObstacleLine, const LINE &aShovedLine) const
bool OfKind(int aKindMask) const
Return true if the item's type matches the mask aKindMask.
const ENTRIES & CItems() const
int Width() const
Return true if the line is geometrically identical as line aOther.
SHOVE_STATUS shoveMainLoop()
void SetInitialLine(LINE &aInitial)
void SetDebugDecorator(DEBUG_DECORATOR *aDecorator)
Assign a debug decorator allowing this algo to draw extra graphics for visual debugging.
A dynamic state checking if a point lies within polygon with a dynamically built outline ( with each ...
PnsKind Kind() const
Return the type (kind) of the item.
Perform various optimizations of the lines being routed, attempting to make the lines shorter and les...
void Clear()
Remove all points from the line chain.
OPT< OBSTACLE > OPT_OBSTACLE
int getClearance(const ITEM *aA, const ITEM *aB) const
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.
int getHoleClearance(const ITEM *aA, const ITEM *aB) const
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...
void replaceItems(ITEM *aOld, std::unique_ptr< ITEM > aNew)
void SetEffortLevel(int aEffort)
std::vector< LINE > m_lineStack
SHOVE_STATUS ShoveMultiLines(const ITEM_SET &aHeadSet)
Push and Shove diff pair dimensions (gap) settings dialog.
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
ROUTER_IFACE * GetInterface() const
virtual LINE * Clone() const override
Return a deep copy of the item.
SHOVE_STATUS shoveLineFromLoneVia(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
void SetIterationLimit(const int aIterLimit)
void Log(EVENT_TYPE evt, const VECTOR2I &pos, const ITEM *item=nullptr)
const LAYER_RANGE & Layers() const
void LockJoint(const VECTOR2I &aPos, const ITEM *aItem, bool aLock)
virtual int Marker() const
virtual void Unmark(int aMarker=-1) const override
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=nullptr)
bool HasLockedSegments() const
virtual void Mark(int aMarker) const override
TIME_LIMIT ShoveTimeLimit() const