137 if( i.index_our < n )
145 if( ipoint == head.
CPoint( 0 ) || ipoint == tail.
CPoint( -1 ) )
212 bool pullback_1 =
false;
219 if( pullback_1 || pullback_2 )
276 int reduce_index = -1;
303 if( reduce_index >= 0 )
309 tail.
Remove( reduce_index + 1, -1 );
338 PNS_DBG(
Dbg(), Message, wxT(
"Merge failed: not enough head segs." ) );
344 PNS_DBG(
Dbg(), Message, wxT(
"Merge failed: head and tail discontinuous." ) );
368 if( dir_head.
Angle( dir_tail ) & ForbiddenAngles )
405 int d_sq = (a - p).SquaredEuclideanNorm();
407 if( d_sq < min_dist_sq )
420 int idx = l.
Split( aP );
431 PNS_DBG(
Dbg(), AddShape, &l2,
BLUE, 500000, wxT(
"hug-target-line" ) );
433 if( dist < thresholdDist )
444 thresholdDist = dist;
453 std::vector<int> dists;
454 std::vector<VECTOR2I> pts;
460 int accumulatedDist = 0;
468 dists.push_back( ( aCursor - s.
A ).EuclideanNorm() );
469 pts.push_back( s.
A );
472 if( pn != s.
A && pn != s.
B )
478 accumulatedDist += s.
Length();
480 if ( accumulatedDist > lengthThreshold )
488 pts.push_back( lastP );
490 int minDistLoc = std::numeric_limits<int>::max();
492 int minDistGlob = std::numeric_limits<int>::max();
495 for(
int i = 0; i < dists.size(); i++ )
499 if( d < minDistGlob )
506 if( dists.size() >= 3 )
508 for(
int i = 0; i < dists.size() - 3; i++ )
510 if( dists[i + 2] > dists[i + 1] && dists[i] > dists[i + 1] )
512 int d = dists[i + 1];
521 if( dists.back() < minDistLoc && minPLoc >= 0 )
523 minDistLoc = dists.back();
524 minPLoc = dists.size() - 1;
530 minDistLoc = minDistGlob;
541 preferred = minPGlob;
548 int thresholdDist = 0;
556 int minDist = std::numeric_limits<int>::max();
560 for(
int i = 0; i < pts.size() ; i++)
600 PNS_DBG(
Dbg(), AddItem, &l1,
BLUE, 20000, wxT(
"walk-base-l1" ) );
610 double hugThresholdLengthComplete =
614 std::optional<LINE> bestLine;
622 : std::numeric_limits<int>::max();
624 : std::numeric_limits<int>::max();
629 LINE tmpHead, tmpTail;
647 LINE tmpHead, tmpTail;
658 if( len_ccw < len_cw )
664 int bestLength = len_cw < len_ccw ? len_cw : len_ccw;
666 if( bestLength < hugThresholdLengthComplete && bestLine.has_value() )
668 walkFull.
SetShape( bestLine->CLine() );
674 bool validCw =
false;
675 bool validCcw =
false;
676 int distCcw = std::numeric_limits<int>::max();
677 int distCw = std::numeric_limits<int>::max();
690 validCw ?
"non-colliding" :
"colliding" ) );
702 validCcw ?
"non-colliding" :
"colliding" ) );
706 if( distCw < distCcw && validCw )
733 PNS_DBG(
Dbg(), AddItem, &walkFull,
GREEN, 200000, wxT(
"walk-full" ) );
736 aWalkLine = walkFull;
752 switch(
Settings().OptimizerEffort() )
807 PNS_DBG(
Dbg(), AddItem, &aNewTail,
BLUE, 100000, wxT(
"walk-new-tail" ) );
826 auto hull = obs->m_item->Hull( cl,
m_head.
Width() );
828 auto nearest = hull.NearestPoint( aP );
841 if( !
Settings().AllowDRCViolations() )
845 if( obs && obs->m_distFirst != INT_MAX )
863 LINE newTail( aOldTail );
864 LINE newHead( aOldTail );
912 PNS_DBG(
Dbg(), AddItem, &newHead,
BLUE, 500000, wxT(
"head-post-split" ) );
941 LINE newHead( walkSolids );
961 switch(
Settings().OptimizerEffort() )
1057 int tailLookbackSegments = 3;
1062 int threshold = std::min( tail.
PointCount(), tailLookbackSegments + 1 );
1070 int end = std::min(2, head.
PointCount() - 1 );
1114 bool go_back =
false;
1124 PNS_DBG(
Dbg(), BeginGroup, wxT(
"route-step" ), 0 );
1129 for( i = 0; i < n_iter; i++ )
1133 LINE newHead, newTail;
1135 if( !go_back &&
Settings().FollowMouse() )
1145 if( !
routeHead( aP, newHead, newTail ) )
1189 if( !fail &&
Settings().FollowMouse() )
1278 std::unique_ptr<SEGMENT> s_new[2] = {
Clone( *s_old ),
Clone( *s_old ) };
1280 s_new[0]->SetEnds( s_old->
Seg().
A, aP );
1281 s_new[1]->SetEnds( aP, s_old->
Seg().
B );
1284 aNode->
Add( std::move( s_new[0] ),
true );
1285 aNode->
Add( std::move( s_new[1] ),
true );
1349 SEG seg =
static_cast<SEGMENT*
>( aStartItem )->Seg();
1353 else if( aP == seg.
B )
1359 double angle =
static_cast<SOLID*
>( aStartItem )->GetOrientation().AsDegrees();
1414 wxLogTrace( wxT(
"PNS" ), wxT(
"world %p, intitial-direction %s layer %d" ),
1432 if( aEndItem && aEndItem->
Owner() )
1433 eiDepth =
static_cast<NODE*
>( aEndItem->
Owner() )->Depth();
1443 bool reachesEnd =
route( p );
1457 && aEndItem && latestNode->
Depth() >= eiDepth
1475 bool realEnd =
false;
1493 else if (aEndItem->
Net() <= 0 )
1541 p_pre_last = l.
CPoint( -2 );
1570 for(
int i = 0; i < lastV; i++ )
1572 ssize_t arcIndex = l.
ArcIndex( i );
1574 if( arcIndex < 0 || ( lastArc >= 0 && i == lastV - 1 && !l.
IsPtOnArc( lastV ) ) )
1580 std::unique_ptr<SEGMENT> sp = std::make_unique<SEGMENT>( seg );
1581 lastItem = sp.get();
1588 if( arcIndex == lastArc )
1595 std::unique_ptr<ARC> ap = std::make_unique<ARC>( arc );
1596 lastItem = ap.get();
1608 if( realEnd && lastItem )
1708 m_shove->RewindToLastLockedNode();
1730 std::set<LINKED_ITEM *> toErase;
1731 aNode->
Add( aLatest,
true );
1733 for(
int s = 0; s < aLatest.
LinkCount(); s++ )
1738 std::vector<LINE> lines;
1747 int removedCount = 0;
1750 for(
LINE& line : lines )
1754 if( !( line.ContainsLink( seg ) ) && line.SegmentCount() )
1757 toErase.insert( ss );
1769 aNode->
Remove( aLatest );
1783 std::set<ITEM*> cleanup;
1791 SEG refSeg =
static_cast<SEGMENT*
>( aItem )->Seg();
1797 if( neighbor == aItem
1799 || !neighbor->LayersOverlap( aItem ) )
1805 !=
static_cast<SEGMENT*
>( aItem )->Width() )
1810 const SEG& testSeg =
static_cast<SEGMENT*
>( neighbor )->Seg();
1817 if( ( nA == aJoint && nB->
LinkCount() == 1 ) ||
1818 ( nB == aJoint && nA->
LinkCount() == 1 ) )
1820 cleanup.insert( neighbor );
1826 for(
ITEM* item : added )
1834 processJoint( jA, item );
1835 processJoint( jB, item );
1838 for(
ITEM* seg : cleanup )
1909 wxString::Format(
"buildInitialLine: m_direction %s, guessedDir %s, tail points %d",
1915 cornerMode = DIRECTION_45::CORNER_MODE::MITERED_45;
1950 PNS_DBG(
Dbg(), AddItem, &aHead,
CYAN, 10000, wxT(
"initial-trace" ) );
1968 for(
int attempt = 0; attempt < 2; attempt++)
1982 aHead =
LINE( aHead, line );
2040 st.
pts.push_back(pt);
Represent route directions & corner angles in a 45-degree metric.
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false, CORNER_MODE aMode=CORNER_MODE::MITERED_45) const
Build a 2-segment line chain between points aP0 and aP1 and following 45-degree routing regime.
AngleType Angle(const DIRECTION_45 &aOther) const
Return the type of angle between directions (this) and aOther.
AngleType
Represent kind of angle formed by vectors heading in two DIRECTION_45s.
Directions
Available directions, there are 8 of them, as on a rectilinear map (north = up) + an extra undefined ...
@ ROUNDED_45
H/V/45 with filleted corners.
@ MITERED_45
H/V/45 with mitered corners (default)
const std::string Format() const
Format the direction in a human readable word.
KICAD_T Type() const
Returns the type of object.
Represent a contiguous set of PCB layers.
bool Overlaps(const LAYER_RANGE &aOther) const
void SetDebugDecorator(DEBUG_DECORATOR *aDecorator)
Assign a debug decorator allowing this algo to draw extra graphics for visual debugging.
void SetLogger(LOGGER *aLogger)
virtual LOGGER * Logger()
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
void SetWidth(int aWidth) override
FIXED_TAIL(int aLineCount=1)
bool PopStage(STAGE &aStage)
void AddStage(const VECTOR2I &aStart, int aLayer, bool placingVias, DIRECTION_45 direction, NODE *aNode)
std::vector< STAGE > m_stages
Base class for PNS router board items.
BOARD_ITEM * Parent() const
PnsKind Kind() const
Return the type (kind) of the item.
NODE * Owner() const
Return the owner of this item, or NULL if there's none.
void SetLayer(int aLayer)
const LAYER_RANGE & Layers() const
bool OfKind(int aKindMask) const
Return true if the item's type matches the mask aKindMask.
A 2D point on a given set of layers and belonging to a certain net, that links together a number of b...
int LinkCount(int aMask=-1) const
bool IsLineCorner(bool aAllowLockedSegs=false) const
Checks if a joint connects two segments of the same net, layer, and width.
bool mergeHead()
Moves "established" segments from the head to the tail if certain conditions are met.
bool handleSelfIntersections()
Check if the head of the track intersects its tail.
LINE_PLACER(ROUTER *aRouter)
bool SetLayer(int aLayer) override
Set the current routing layer.
NODE * m_lastNode
Postprocessed world state (including marked collisions & removed loops)
bool route(const VECTOR2I &aP)
Re-route the current track to point aP.
void updatePStart(const LINE &tail)
bool AbortPlacement() override
std::unique_ptr< SHOVE > m_shove
The shove engine.
const LINE Trace() const
Return the complete routed line.
bool splitHeadTail(const LINE &aNewLine, const LINE &aOldTail, LINE &aNewHead, LINE &aNewTail)
bool handlePullback()
Deal with pull-back: reduces the tail if head trace is moved backwards wrs to the current tail direct...
void setWorld(NODE *aWorld)
Set the board to route.
void UpdateSizes(const SIZES_SETTINGS &aSizes) override
Perform on-the-fly update of the width, via diameter & drill size from a settings class.
bool reduceTail(const VECTOR2I &aEnd)
Attempt to reduce the number of segments in the tail by trying to replace a certain number of latest ...
void SetOrthoMode(bool aOrthoMode) override
Function SetOrthoMode()
LINE m_tail
routing "tail": part of the track that has been already fixed due to collisions with obstacles
MOUSE_TRAIL_TRACER m_mouseTrailTracer
bool clipAndCheckCollisions(VECTOR2I aP, SHAPE_LINE_CHAIN aL, SHAPE_LINE_CHAIN &aOut, int &thresholdDist)
bool Start(const VECTOR2I &aP, ITEM *aStartItem) override
Start routing a single track at point aP, taking item aStartItem as anchor (unless NULL).
std::optional< VECTOR2I > m_last_p_end
bool optimizeTailHeadTransition()
Try to reduce the corner count of the most recent part of tail/head by merging obtuse/collinear segme...
bool HasPlacedAnything() const override
void routeStep(const VECTOR2I &aP)
Perform a single routing algorithm step, for the end point aP.
bool buildInitialLine(const VECTOR2I &aP, LINE &aHead, bool aForceNoVia=false)
NODE * m_currentNode
Current world state.
bool cursorDistMinimum(const SHAPE_LINE_CHAIN &aL, const VECTOR2I &aCursor, double lengthThreshold, SHAPE_LINE_CHAIN &aOut)
LINE m_head
the volatile part of the track from the previously analyzed point to the current routing destination
void removeLoops(NODE *aNode, LINE &aLatest)
Searches aNode for traces concurrent to aLatest and removes them.
VECTOR2I m_fixStart
start point of the last 'fix'
bool rhMarkObstacles(const VECTOR2I &aP, LINE &aNewHead, LINE &aNewTail)
NODE * m_world
pointer to world to search colliding items
DIRECTION_45 m_initial_direction
routing direction for new traces
NODE * CurrentNode(bool aLoopsRemoved=false) const override
Return the most recent world state.
bool SplitAdjacentSegments(NODE *aNode, ITEM *aSeg, const VECTOR2I &aP)
Check if point aP lies on segment aSeg.
void setInitialDirection(const DIRECTION_45 &aDirection)
Set preferred direction of the very first track segment to be laid.
void updateLeadingRatLine()
Draw the "leading" rats nest line, which connects the end of currently routed track and the nearest y...
bool routeHead(const VECTOR2I &aP, LINE &aNewHead, LINE &aNewTail)
Compute the head trace between the current start point (m_p_start) and point aP, starting with direct...
bool rhWalkOnly(const VECTOR2I &aP, LINE &aNewHead, LINE &aNewTail)
bool UnfixRoute() override
void FlipPosture() override
Toggle the current posture (straight/diagonal) of the trace head.
const VIA makeVia(const VECTOR2I &aP)
bool rhShoveOnly(const VECTOR2I &aP, LINE &aNewHead, LINE &aNewTail)
< Route step shove mode.
void GetModifiedNets(std::vector< int > &aNets) const override
Function GetModifiedNets.
bool rhWalkBase(const VECTOR2I &aP, LINE &aWalkLine, int aCollisionMask, bool &aViaOk)
bool CommitPlacement() override
VECTOR2I m_p_start
current routing start (end of tail, beginning of head)
bool Move(const VECTOR2I &aP, ITEM *aEndItem) override
Move the end of the currently routed trace to the point aP, taking aEndItem as anchor (if not NULL).
void simplifyNewLine(NODE *aNode, LINKED_ITEM *aLatest)
Assemble a line starting from segment or arc aLatest, removes collinear segments and redundant vertic...
DIRECTION_45 m_direction
current routing direction
void initPlacement()
Initialize placement of a new line with given parameters.
const ITEM_SET Traces() override
Return the complete routed line, as a single-member ITEM_SET.
bool FixRoute(const VECTOR2I &aP, ITEM *aEndItem, bool aForceFinish) override
Commit the currently routed track to the parent node taking aP as the final end point and aEndItem as...
bool ToggleVia(bool aEnabled) override
Enable/disable a via at the end of currently routed trace.
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
void SetViaDrill(int aDrill)
const VECTOR2I & CPoint(int aIdx) const
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Return the shape of the line.
int CountCorners(int aAngles) const
const SHAPE_LINE_CHAIN & CLine() const
SHAPE_LINE_CHAIN & Line()
void SetViaDiameter(int aDiameter)
int ShapeCount() const
Return the aIdx-th point of the line.
void AppendVia(const VIA &aVia)
void SetWidth(int aWidth)
Return line width.
void SetBlockingObstacle(ITEM *aObstacle)
const SEG CSegment(int aIdx) const
Set line width.
int Width() const
Return true if the line is geometrically identical as line aOther.
LINKED_ITEM * GetLink(int aIndex) const
Erase the linking information. Used to detach the line from the owning node.
void SetTolerance(int toll)
void SetDefaultDirections(DIRECTION_45 aInitDirection, DIRECTION_45 aLastSegDir)
void SetMouseDisabled(bool aDisabled=true)
Disables the mouse-trail portion of the posture solver; leaving only the manual posture switch and th...
void AddTrailPoint(const VECTOR2I &aP)
DIRECTION_45 GetPosture(const VECTOR2I &aP)
bool IsManuallyForced() const
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...
int FindLinesBetweenJoints(const JOINT &aA, const JOINT &aB, std::vector< LINE > &aLines)
Find the joints corresponding to the ends of line aLine.
std::vector< ITEM * > ITEM_VECTOR
int GetClearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true) const
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
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
Destroy all child nodes. Applicable only to the root node.
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current 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...
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 SetCollisionMask(int aMask)
void SetEffortLevel(int aEffort)
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I &aV=VECTOR2I(0, 0))
@ SMART_PADS
Reroute pad exits.
@ FANOUT_CLEANUP
Simplify pad-pad and pad-via connections if possible.
@ MERGE_SEGMENTS
Reduce corner cost iteratively.
@ MERGE_COLINEAR
Merge co-linear segments.
virtual void DisplayRatline(const SHAPE_LINE_CHAIN &aRatline, int aNetCode)=0
ROUTER_IFACE * GetInterface() const
int ViaForcePropIterationLimit() const
double WalkaroundHugLengthThreshold() const
bool GetFixAllSegments() const
PNS_MODE Mode() const
Set the routing mode.
DIRECTION_45::CORNER_MODE GetCornerMode() const
int Width() const override
void SetWidth(int aWidth) override
int GetLayerBottom() const
bool TrackWidthIsExplicit() const
bool LeadingRatLine(const LINE *aTrack, SHAPE_LINE_CHAIN &aRatLine)
const VECTOR2I & Pos() const
bool PushoutForce(NODE *aNode, const VECTOR2I &aDirection, VECTOR2I &aForce, int aCollisionMask=ITEM::ANY_T, int aMaxIterations=10)
void SetPos(const VECTOR2I &aPos)
void SetIterationLimit(const int aIterLimit)
void SetSolidsOnly(bool aSolidsOnly)
void SetItemMask(int aMask)
WALKAROUND_STATUS Route(const LINE &aInitialPath, LINE &aWalkPath, bool aOptimize=true)
VECTOR2I::extended_type ecoord
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
int Length() const
Return the length (this).
bool Contains(const SEG &aSeg) const
VECTOR2I LineProject(const VECTOR2I &aP) const
Compute the perpendicular projection point of aP on a line passing through ends of the segment.
SEG Reversed() const
Returns the center point of the line.
bool PointOnEdge(const VECTOR2I &aP, int aAccuracy=0) const
Check if point aP lies on an edge or vertex of the line chain.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
bool IsPtOnArc(size_t aPtIndex) const
const SHAPE_ARC & Arc(size_t aArc) const
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
void SetPoint(int aIndex, const VECTOR2I &aPos)
Move a point to a specific location.
int Split(const VECTOR2I &aP)
Insert the point aP belonging to one of the our segments, splitting the adjacent segment in two.
int PrevShape(int aPointIndex) const
int ShapeCount() const
Return the number of shapes (line segments or arcs) in this line chain.
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Find all intersection points between our line chain and the segment aSeg.
int PointCount() const
Return the number of points (vertices) in this line chain.
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Replace points with indices in range [start_index, end_index] with a single point aP.
ssize_t ArcIndex(size_t aSegment) const
Return the arc index for the given segment index.
void Clear()
Remove all points from the line chain.
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Return a subset of this line chain containing the [start_index, end_index] range of points.
const std::vector< SHAPE_ARC > & CArcs() const
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.
int SegmentCount() const
Return the number of segments in this line chain.
void Remove(int aStartIndex, int aEndIndex)
Remove the range of points [start_index, end_index] from the line chain.
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
bool IsArcSegment(size_t aSegment) const
void RemoveShape(int aPointIndex)
Remove the shape at the given index from the line chain.
std::vector< INTERSECTION > INTERSECTIONS
long long int Length() const
Return length of the line chain in Euclidean metric.
int Find(const VECTOR2I &aP, int aThreshold=0) const
Search for point aP.
static constexpr extended_type ECOORD_MAX
Push and Shove diff pair dimensions (gap) settings dialog.
@ RM_MarkObstacles
Ignore collisions, mark obstacles.
@ RM_Walkaround
Only walk around.
VECTOR2I closestProjectedPoint(const SHAPE_LINE_CHAIN &line, const VECTOR2I &p)
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
#define PNS_DBG(dbg, method,...)
#define PNS_DBGN(dbg, method)
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
std::vector< FIX_POINT > pts
WALKAROUND_STATUS statusCcw
WALKAROUND_STATUS statusCw
Represent an intersection between two line segments.
double EuclideanNorm(const VECTOR2I &vector)
@ PCB_PAD_T
class PAD, a pad in a footprint