135 if( i.our.Index() < n )
143 if( ipoint == head.
CPoint( 0 ) || ipoint == tail.
CPoint( -1 ) )
195 const std::vector<ssize_t>& headShapes = head.
CShapes();
196 const std::vector<ssize_t>& tailShapes = tail.
CShapes();
200 if( headShapes[0] == -1 )
207 if( tailShapes[lastSegIdx] == -1 )
216 bool pullback_1 =
false;
223 if( pullback_1 || pullback_2 )
227 if( tailShapes[lastSegIdx] == -1 )
240 wxLogTrace(
"PNS",
"Placer: pullback triggered [%d] [%s %s]",
241 n, last_tail.
Format().c_str(), first_head.
Format().c_str() );
280 int reduce_index = -1;
307 if( reduce_index >= 0 )
309 wxLogTrace(
"PNS",
"Placer: reducing tail: %d", reduce_index );
314 tail.
Remove( reduce_index + 1, -1 );
343 wxLogTrace(
"PNS",
"Merge failed: not enough head segs." );
349 wxLogTrace(
"PNS",
"Merge failed: head and tail discontinuous." );
358 const std::vector<ssize_t>& headShapes = head.
CShapes();
359 const std::vector<ssize_t>& tailShapes = tail.
CShapes();
361 if( headShapes[0] == -1 )
371 if( tailShapes[lastSegIdx] == -1 )
376 if( dir_head.
Angle( dir_tail ) & ForbiddenAngles )
389 if( tailShapes[lastSegIdx] == -1 )
396 wxLogTrace(
"PNS",
"Placer: merge %d, new direction: %s", n_head,
416 int d_sq = (a - p).SquaredEuclideanNorm();
418 if( d_sq < min_dist_sq )
434 bool rv =
true, viaOk;
457 int idx_cw = l_cw.
Split( p_cw );
458 int idx_ccw = l_ccw.
Split( p_ccw );
460 l_cw = l_cw.
Slice( 0, idx_cw );
461 l_ccw = l_ccw.
Slice( 0, idx_ccw );
527 if( obs && obs->m_distFirst != INT_MAX )
631 walkaround.
Route( initTrack, l2 );
679 int tailLookbackSegments = 3;
684 int threshold = std::min( tail.
PointCount(), tailLookbackSegments + 1 );
692 int end = std::min(2, head.
PointCount() - 1 );
706 wxLogTrace(
"PNS",
"Placer: optimize tail-head [%d]", threshold );
725 bool go_back =
false;
731 wxLogTrace(
"PNS",
"routeStep: direction: %s head: %d, tail: %d shapes",
736 for( i = 0; i < n_iter; i++ )
834 SEGMENT* s_old = static_cast<SEGMENT*>( aSeg );
836 std::unique_ptr<SEGMENT> s_new[2] = {
Clone( *s_old ),
Clone( *s_old ) };
838 s_new[0]->SetEnds( s_old->
Seg().
A, aP );
839 s_new[1]->SetEnds( aP, s_old->
Seg().
B );
842 aNode->
Add( std::move( s_new[0] ),
true );
843 aNode->
Add( std::move( s_new[1] ),
true );
900 SEG seg = static_cast<SEGMENT*>( aStartItem )->Seg();
904 else if( aP == seg.
B )
908 static_cast<SOLID*>( aStartItem )->Parent()->Type() ==
PCB_PAD_T )
910 double angle = static_cast<SOLID*>( aStartItem )->GetOrientation() / 10.0;
912 initialDir =
DIRECTION_45( static_cast<DIRECTION_45::Directions>(
int(
angle ) ) );
915 wxLogTrace(
"PNS",
"Posture: init %s, last seg %s", initialDir.
Format(), lastSegDir.
Format() );
963 wxLogTrace(
"PNS",
"world %p, intitial-direction %s layer %d",
985 if( aEndItem && aEndItem->
Owner() )
986 eiDepth = static_cast<NODE*>( aEndItem->
Owner() )->Depth();
994 bool reachesEnd =
route( p );
1008 && aEndItem && latestNode->
Depth() > eiDepth
1026 bool realEnd =
false;
1044 else if (aEndItem->
Net() <= 0 )
1089 p_pre_last = l.
CPoint( -2 );
1118 for(
int i = 0; i < lastV; i++ )
1120 ssize_t arcIndex = l.
ArcIndex( i );
1122 if( arcIndex < 0 || ( lastArc >= 0 && i == lastV - 1 && l.
CShapes()[lastV] == -1 ) )
1133 if( arcIndex == lastArc )
1149 if( realEnd && lastItem )
1258 std::set<LINKED_ITEM *> toErase;
1259 aNode->
Add( aLatest,
true );
1261 for(
int s = 0; s < aLatest.
LinkCount(); s++ )
1266 std::vector<LINE> lines;
1275 int removedCount = 0;
1278 for(
LINE& line : lines )
1282 if( !( line.ContainsLink( seg ) ) && line.SegmentCount() )
1285 toErase.insert( ss );
1291 wxLogTrace(
"PNS",
"total segs removed: %d/%d", removedCount, total );
1297 aNode->
Remove( aLatest );
1312 if( optimized || simplified.PointCount() != l.PointCount() )
1315 l.SetShape( simplified );
1368 wxLogTrace(
"PNS",
"buildInitialLine: m_direction %s, guessedDir %s, tail points %d",
1425 aHead =
LINE( aHead, line );
1477 st.
pts.push_back(pt);
const SHAPE_LINE_CHAIN & CLine() const
int PrevShape(int aPointIndex) const
Base class for PNS router board items.
OPT_OBSTACLE NearestObstacle(const LINE *aLine, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=NULL)
Follow the line in search of an obstacle that is nearest to the starting to the line's starting point...
bool SmartPads() const
Enable/disable Smart Pads (optimized connections).
ROUTER * Router() const
Return current router settings.
const SHAPE_ARC & Arc(size_t aArc) const
long long int Length() const
Function Length()
int Split(const VECTOR2I &aP)
Function Split()
void SetViaDiameter(int aDiameter)
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
const ITEM_SET Traces() override
Return the complete routed line, as a single-member ITEM_SET.
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).
VECTOR2I v2(1, 0)
Test suite for KiCad math code.
std::vector< INTERSECTION > INTERSECTIONS
Keep the router "world" - i.e.
NODE * m_lastNode
Postprocessed world state (including marked collisions & removed loops)
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, int aType=0, int aWidth=0, const std::string aName="")
void RemoveShape(int aPointIndex)
Removes the shape at the given index from the line chain.
int GetLayerBottom() const
void routeStep(const VECTOR2I &aP)
Perform a single routing algorithm step, for the end point aP.
bool IsManuallyForced() const
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Function Simplify()
std::vector< STAGE > m_stages
void SetPoint(int aIndex, const VECTOR2I &aPos)
Accessor Function to move a point to a specific location.
NODE * m_world
pointer to world to search colliding items
void SetLayer(int aLayer)
const SEG CSegment(int aIdx) const
Set line width.
const std::string Format() const
Format the direction in a human readable word.
bool Is45Degree() const
Print out all linked segments.
H/V/45 with filleted corners.
void removeLoops(NODE *aNode, LINE &aLatest)
Searches aNode for traces concurrent to aLatest and removes them.
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Function Slice()
Simplify pad-pad and pad-via connections if possible.
WALKAROUND_STATUS statusCw
void simplifyNewLine(NODE *aNode, LINKED_ITEM *aLatest)
Assemble a line starting from segment or arc aLatest, removes collinear segments and redundant vertex...
VECTOR2I::extended_type ecoord
virtual LOGGER * Logger()
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
Destroy all child nodes. Applicable only to the root node.
bool PushoutForce(NODE *aNode, const VECTOR2I &aDirection, VECTOR2I &aForce, bool aSolidsOnly=true, int aMaxIterations=10)
LINE m_head
the volatile part of the track from the previously analyzed point to the current routing destination
bool Overlaps(const LAYER_RANGE &aOther) const
bool rhWalkOnly(const VECTOR2I &aP, LINE &aNewHead)
Route step shove mode.
std::vector< FIX_POINT > pts
int FindLinesBetweenJoints(const JOINT &aA, const JOINT &aB, std::vector< LINE > &aLines)
Find the joints corresponding to the ends of line aLine.
bool PopStage(STAGE &aStage)
WALKAROUND_STATUS Route(const LINE &aInitialPath, LINE &aWalkPath, bool aOptimize=true)
FIXED_TAIL(int aLineCount=1)
const LINE Trace() const
Return the complete routed line.
class PAD, a pad in a footprint
void AppendVia(const VIA &aVia)
virtual void DisplayRatline(const SHAPE_LINE_CHAIN &aRatline, int aColor=-1)=0
bool reduceTail(const VECTOR2I &aEnd)
Attempt to reduce the number of segments in the tail by trying to replace a certain number of latest ...
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
bool buildInitialLine(const VECTOR2I &aP, LINE &aHead)
const std::vector< SHAPE_ARC > & CArcs() const
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...
int PointCount() const
Function PointCount()
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
const VECTOR2I & Pos() const
bool RemoveLoops() const
Enable/disable loop (redundant track) removal.
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
void Remove(ARC *aArc)
Remove an item from this branch.
void SetWidth(int aWidth)
Return line width.
const VECTOR2I & CPoint(int aIdx) const
bool handlePullback()
Deal with pull-back: reduces the tail if head trace is moved backwards wrs to the current tail direct...
void SetCollisionMask(int aMask)
LINE_PLACER(ROUTER *aRouter)
bool FollowMouse() const
Return true if smoothing segments during dragging is enabled.
const std::vector< ssize_t > & CShapes() const
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Return the shape of the line.
ssize_t ArcIndex(size_t aSegment) const
ROUTING_SETTINGS & Settings() const
Return the logger object, allowing to dump geometry to a file.
AngleType Angle(const DIRECTION_45 &aOther) const
Return the type of angle between directions (this) and aOther.
const VECTOR2I & CPoint(int aIndex) const
Function Point()
void SetApproachCursor(bool aEnabled, const VECTOR2I &aPos)
Represents a 2D point on a given set of layers and belonging to a certain net, that links together a ...
void UpdateSizes(const SIZES_SETTINGS &aSizes) override
Perform on-the-fly update of the width, via diameter & drill size from a settings class.
static constexpr extended_type ECOORD_MAX
VECTOR2I LineProject(const VECTOR2I &aP) const
Compute the perpendicular projection point of aP on a line passing through ends of the segment.
DIRECTION_45 m_initial_direction
routing direction for new traces
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
void SetWorld(NODE *aNode)
bool LeadingRatLine(const LINE *aTrack, SHAPE_LINE_CHAIN &aRatLine)
LINE m_tail
routing "tail": part of the track that has been already fixed due to collisions with obstacles
void setInitialDirection(const DIRECTION_45 &aDirection)
Set preferred direction of the very first track segment to be laid.
void SetWidth(int aWidth) override
Represent route directions & corner angles in a 45-degree metric.
bool SplitAdjacentSegments(NODE *aNode, ITEM *aSeg, const VECTOR2I &aP)
Check if point aP lies on segment aSeg.
PNS_OPTIMIZATION_EFFORT OptimizerEffort() const
Set the optimizer effort. Bigger means cleaner traces, but slower routing.
std::unique_ptr< SHOVE > m_shove
The shove engine.
DIRECTION_45 m_direction
current routing direction
const VECTOR2I & GetP0() const
void initPlacement()
Initialize placement of a new line with given parameters.
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I aV=VECTOR2I(0, 0))
DEBUG_DECORATOR * Dbg() const
void AddTrailPoint(const VECTOR2I &aP)
const LINE ClipToNearestObstacle(NODE *aNode) const
Clip the line to a given range of vertices.
void updateLeadingRatLine()
Draw the "leading" rats nest line, which connects the end of currently routed track and the nearest y...
PNS_MODE Mode() const
Set the routing mode.
void SetWidth(int aWidth) override
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
bool routeHead(const VECTOR2I &aP, LINE &aNewHead)
Compute the head trace between the current start point (m_p_start) and point aP, starting with direct...
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false, bool aFillet=false) const
Build a 2-segment line chain between points aP0 and aP1 and following 45-degree routing regime.
void SetSolidsOnly(bool aSolidsOnly)
int ShapeCount() const
Returns the number of shapes (line segments or arcs) in this line chain.
bool HasPlacedAnything() const override
MOUSE_TRAIL_TRACER m_mouseTrailTracer
bool GetFixAllSegments() const
bool handleSelfIntersections()
Check if the head of the track intersects its tail.
void Remove(int aStartIndex, int aEndIndex)
Function Remove()
VECTOR2I closestProjectedPoint(const SHAPE_LINE_CHAIN &line, const VECTOR2I &p)
bool route(const VECTOR2I &aP)
Re-route the current track to point aP.
Reduce corner cost iteratively.
void GetModifiedNets(std::vector< int > &aNets) const override
Function GetModifiedNets.
int SegmentCount() const
Function SegmentCount()
bool CommitPlacement() override
bool rhMarkObstacles(const VECTOR2I &aP, LINE &aNewHead)
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
bool rhShoveOnly(const VECTOR2I &aP, LINE &aNewHead)
Route step mark obstacles mode.
SHAPE_LINE_CHAIN & Line()
void SetPos(const VECTOR2I &aPos)
SEG Reversed() const
Returns the center point of the line.
void SetViaDrill(int aDrill)
Guess what's better, try to make least mess on the PCB.
NODE * m_currentNode
Current world state.
int ShapeCount() const
Return the aIdx-th point of the line.
AngleType
Represent kind of angle formed by vectors heading in two DIRECTION_45s.
void setWorld(NODE *aWorld)
Set the board to route.
bool optimizeTailHeadTransition()
Try to reduce the corner count of the most recent part of tail/head by merging obtuse/collinear segme...
NODE * CurrentNode(bool aLoopsRemoved=false) const override
Return the most recent world state.
Ignore collisions, mark obstacles.
bool ToggleVia(bool aEnabled) override
Enable/disable a via at the end of currently routed trace.
CORNER_MODE GetCornerMode() const
void AddStage(VECTOR2I aStart, int aLayer, bool placingVias, DIRECTION_45 direction, NODE *aNode)
Reduce corner cost by merging obtuse segments.
const SEG CSegment(int aIndex) const
Function CSegment()
void FlipPosture() override
Toggle the current posture (straight/diagonal) of the trace head.
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
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.
WALKAROUND_STATUS statusCcw
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
void SetDefaultDirections(DIRECTION_45 aInitDirection, DIRECTION_45 aLastSegDir)
bool OfKind(int aKindMask) const
Return true if the item's type matches the mask aKindMask.
int Width() const
Return true if the line is geometrically identical as line aOther.
bool SetLayer(int aLayer) override
Set the current routing layer.
DIRECTION_45 GetPosture(const VECTOR2I &aP)
LINKED_ITEM * GetLink(int aIndex) const
Erase the linking information. Used to detach the line from the owning node.
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.
void SetDebugDecorator(DEBUG_DECORATOR *aDecorator)
Assign a debug decorator allowing this algo to draw extra graphics for visual debugging.
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()
Function Clear() Removes all points from the line chain.
OPT< OBSTACLE > OPT_OBSTACLE
VECTOR2I m_p_start
current routing start (end of tail, beginning of head)
void SetWorld(NODE *aNode)
Merge co-linear segments.
bool mergeHead()
Moves "established" segments from the head to the tail if certain conditions are met.
void SetMouseDisabled(bool aDisabled=true)
Disables the mouse-trail portion of the posture solver; leaving only the manual posture switch and th...
int LinkCount(int aMask=-1) const
void SetEffortLevel(int aEffort)
void SetOrthoMode(bool aOrthoMode) override
Function SetOrthoMode()
bool Start(const VECTOR2I &aP, ITEM *aStartItem) override
Start routing a single track at point aP, taking item aStartItem as anchor (unless NULL).
NODE * Owner() const
Return the owner of this item, or NULL if there's none.
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Function Replace()
bool AbortPlacement() override
const VIA makeVia(const VECTOR2I &aP)
Push and Shove diff pair dimensions (gap) settings dialog.
void SetLogger(LOGGER *aLogger)
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
ROUTER_IFACE * GetInterface() const
void SetIterationLimit(const int aIterLimit)
bool UnfixRoute() override
Represent a contiguous set of PCB layers.
const LAYER_RANGE & Layers() const
void SetTolerance(int toll)
std::vector< ITEM * > ITEM_VECTOR
int CountCorners(int aAngles) const
void SetBlockingObstacle(ITEM *aObstacle)