33#undef SPREAD_TRACKS_EXTRA_VERBOSE
74 if( aB.
A == aA.
A || aB.
B == aA.
A )
117 auto rnearest =
m_rootLine.CLine().NearestPoint( aP );
120 PNS_DBG(
Dbg(), AddPoint, rnearest,
GREEN, 300000, wxT(
"move=end" ) );
135#ifdef SPREAD_TRACKS_EXTRA_VERBOSE
137 wxString::Format(
"clip-head %d", (
int) clippedHead->LinkCount() ) );
140 for(
auto& lnk : clippedHead->Links() )
143#ifdef SPREAD_TRACKS_EXTRA_VERBOSE
145 wxString::Format(
"cliplinkd %d", 0 ) );
152 LINE lrem( l.spreadableLine );
153#ifdef SPREAD_TRACKS_EXTRA_VERBOSE
155 wxString::Format(
"rem-line l %d", (
int) l.spreadableLine.LinkCount() ) );
157 spreadNode->
Remove( lrem );
160 std::unordered_set<ITEM*> processedItems;
170 if( aA->
Net() == aB->Net() )
180 processedItems.insert( lnk );
191 PNS_DBG(
Dbg(), BeginGroup, wxT(
"grp-walk-details" ), 0 );
192 auto ret = walkaround.
Route( entry.spreadableLine );
195 bool success =
false;
201 spreadNode->
Add( ret.lines[policy] );
202 entry.forwardLine = ret.lines[policy];
205 for(
auto lnk : ret.lines[policy].Links() )
206 processedItems.insert( lnk );
207#ifdef SPREAD_TRACKS_EXTRA_VERBOSE
209 wxString::Format(
"walk-line l %d pitems %d", ret.lines[policy].LinkCount(),
210 (
int) processedItems.size() ) );
212 for(
auto lnk : ret.lines[policy].Links() )
214 bool spreadable =
true;
216#ifdef SPREAD_TRACKS_EXTRA_VERBOSE
217 PNS_DBG(
Dbg(), BeginGroup,
"spreadable-propagate", 0 );
218 PNS_DBG(
Dbg(), AddItem, lnk,
WHITE, 100000, wxString::Format(
"lnk" ) );
220 for(
int i = 0; i < entry.spreadableLine.SegmentCount(); i++ )
222 const SEG& s = entry.spreadableLine.CSegment( i );
234 overlapDist = c1.
Length();
236#ifdef SPREAD_TRACKS_EXTRA_VERBOSE
238 wxString::Format(
"ns-dist %d", overlapDist ) );
241 if( overlapDist > 100 )
248#ifdef SPREAD_TRACKS_EXTRA_VERBOSE
255#ifdef SPREAD_TRACKS_EXTRA_VERBOSE
256 PNS_DBG(
Dbg(), AddItem, lnk,
WHITE, 100000, wxString::Format(
"spreadable" ) );
266 PNS_DBG(
Dbg(), AddItem, &entry.originLine,
WHITE, 100000, wxString::Format(
"failing-line" ) );
273 spreadNode->
Remove( ent.forwardLine );
274 ent.forwardLine.Line().Simplify2();
287 PNS_DBG(
Dbg(), BeginGroup, wxT(
"grp-back-details" ), 0 );
288 auto ret = walkaround.
Route( entry.forwardLine );
291 bool success =
false;
296 entry.backwardLine = ret.lines[policy];
297 OPT_BOX2I affectedArea = entry.backwardLine.ChangedArea( &entry.spreadableLine );
298 if( affectedArea.has_value() )
300 if( !totalAffectedArea )
301 totalAffectedArea = affectedArea;
303 totalAffectedArea->Merge( affectedArea.value() );
305 entry.backwardLine.Line().Simplify2();
306 spreadNode->
Add( entry.backwardLine );
314 PNS_DBG(
Dbg(), AddItem, &entry.originLine,
WHITE, 100000, wxString::Format(
"failing-line-back" ) );
321 if( totalAffectedArea )
324 totalAffectedArea->Inflate(
delta );
331 std::vector<SEG> doNotOptimizeSegs =
findNoOptSegments( clippedHead.value(), entry );
341 if( totalAffectedArea )
344 spreadNode->
Remove( entry.backwardLine );
345 optimizer.
Optimize( &entry.backwardLine, &entry.optimizedLine );
346 spreadNode->
Add( entry.optimizedLine );
417 return std::vector<NET_HANDLE>();
433 std::deque<LINKED_ITEM*> pending;
438 pending.push_back(
static_cast<LINKED_ITEM*
>( item ) );
445 while( !pending.empty() )
450 bool alreadyAssembled =
454 return aLine.originLine.ContainsLink( item ) || m_rootLine.ContainsLink( item );
457 if( alreadyAssembled )
468 margin += entry.originLine.Width();
487 if( !entry.originLine.ContainsLink( litem ) )
498 if( plNearest < 0 || pl < plNearest )
501 if( pl > plFarthest )
513 int lineLength =
static_cast<int>( shape.
Length() );
519 shape.
Split( pNearest, pFarthest, pre, mid, post );
521 entry.spreadableLine =
LINE( entry.originLine, mid );
522 entry.p_start = pNearest;
523 entry.p_end = pFarthest;
526 PNS_DBG(
Dbg(), BeginGroup,
"spreadable-lines", 0 );
529 PNS_DBG(
Dbg(), AddItem, &entry.originLine,
GREEN, 10000, wxT(
"origin-line" ) );
533 PNS_DBG(
Dbg(), BeginGroup,
"spreadable-spans", 0 );
539 for(
size_t i = 0; i <
m_lines.size(); i++ )
543 PNS_DBG(
Dbg(), AddPoint, entry.
p_start,
CYAN, 200000, wxString::Format( wxT(
"span-nearest-%d" ), (
int) i ) );
545 wxString::Format( wxT(
"span-farthest-%d" ), (
int) i ) );
551 wxString::Format( wxT(
"spreadable-line-%d sc %d lc %d adj %d" ), (
int) i, 0, 0,
552 adjusted.has_value() ? 1 : 0 ) );
557 PNS_DBG(
Dbg(), AddItem, &( *adjusted ),
YELLOW, 20000, wxString::Format( wxT(
"adj-line-%d" ), (
int) i ) );
580 ( aA.originLine.CLine().NearestPoint( m_startAnchor ) - m_startAnchor ).SquaredEuclideanNorm();
582 ( aB.originLine.CLine().NearestPoint( m_startAnchor ) - m_startAnchor ).SquaredEuclideanNorm();
584 return distA < distB;
592 LINE current( *aOrigLine );
593 aNode->
Remove( aOrigLine );
595 newShape.
Split( aP1 );
596 newShape.
Split( aP2 );
597 LINE newLine( *aOrigLine, newShape );
598 aNode->
Add( newLine );
600 auto jtA = aNode->
FindJoint( aP1, &newLine );
601 auto jtB = aNode->
FindJoint( aP2, &newLine );
606 std::vector<LINE> adjustedLines;
610 if( adjustedLines.empty() )
613 return adjustedLines[0];
626 std::vector<SEG> segs;
640 int dist = headSeg.
Distance( spreadSeg );
642 PNS_DBG(
Dbg(), AddShape, spreadSeg,
LIGHTBLUE, 200000, wxString::Format(
"com-par dist %d", dist ) );
643 segs.push_back( spreadSeg );
std::optional< BOX2I > OPT_BOX2I
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.
DEBUG_DECORATOR * Dbg() const
Base class for PNS router board items.
virtual NET_HANDLE Net() const
bool OfKind(int aKindMask) const
virtual VECTOR2I Anchor(int n) const
virtual int AnchorCount() const
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
const SHAPE_LINE_CHAIN & CLine() const
const SEG CSegment(int aIdx) 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 all lines between a pair of joints. Used by the loop removal procedure.
const JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, NET_HANDLE aNet) const
Search for a joint at a given position, layer and belonging to given net.
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false, bool aFollowLockedSegments=false, bool aAllowSegmentSizeMismatch=true)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
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 SetPreserveSegments(const std::vector< SEG > &aSegs)
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.
@ MERGE_SEGMENTS
Reduce corner cost iteratively.
@ MERGE_COLINEAR
Merge co-linear segments.
@ REQUIRE_OBTUSE_ANGLES
Try to prevent 90-degree or acute corners in a drag.
PLACEMENT_ALGO(ROUTER *aRouter)
ROUTING_SETTINGS & Settings()
int GetSpreadTracksDistance() const
NODE * CurrentNode(bool aLoopsRemoved=false) const override
Return the most recent board state.
std::vector< SPREADABLE_LINE > m_lines
LINKED_ITEM * m_startItem
virtual bool Start(const VECTOR2I &aP, ITEM *aStartItem) override
Start placement/drag operation at point aP, taking item aStartItem as anchor (unless NULL).
const std::vector< NET_HANDLE > CurrentNets() const override
Returns the net(s) of currently routed track(s).
void SetSpreadableItems(const ITEM_SET &aAuxItems)
const VECTOR2I & CurrentStart() const override
Return the current start of the line(s) being placed/tuned.
TRACKS_SPREADER(ROUTER *aRouter)
const std::vector< SEG > findNoOptSegments(const LINE &aClippedHead, const TRACKS_SPREADER::SPREADABLE_LINE &aEntry) const
virtual bool Move(const VECTOR2I &aP, ITEM *aEndItem) override
Move the end of the currently routed primtive(s) to the point aP, taking aEndItem as the anchor (if n...
std::unordered_set< const LINKED_ITEM * > m_spreadableItems
const ITEM_SET Traces() override
Return all routed/tuned traces.
bool prepareSpreadableLines()
bool AbortPlacement() override
int CurrentLayer() const override
Return the layer of currently routed track.
virtual bool FixRoute(const VECTOR2I &aP, ITEM *aEndItem, bool aForceFinish=false) override
Commit the currently routed items to the parent node, taking aP as the final end point and aEndItem a...
static std::optional< LINE > breakAndReassemble(NODE *aNode, LINE *aOrigLine, const VECTOR2I &aP1, const VECTOR2I &aP2)
const VECTOR2I & CurrentEnd() const override
Return the current end of the line(s) being placed/tuned.
bool CommitPlacement() override
bool HasPlacedAnything() const override
void determineWalkOrder()
virtual ~TRACKS_SPREADER()
void SetLengthLimit(bool aEnable, double aLengthExpansionFactor)
void SetUseClustering(bool aEnabled)
void SetAllowedPolicies(std::vector< WALK_POLICY > aPolicies, bool aAnyCompletePolicyIsSuccess=false)
STATUS Route(const LINE &aInitialPath, LINE &aWalkPath, bool aOptimize=true)
void SetClearanceOverride(CLEARANCE_OVERRIDE_FUNC aFunc)
int Length() const
Return the length (this).
bool ApproxCollinear(const SEG &aSeg, int aDistanceThreshold=1) const
bool ApproxOverlaps(const SEG &aSeg, int aThreshold=3) const
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
bool Contains(const SEG &aSeg) const
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
const VECTOR2I PointAlong(int aPathLength) const
int Split(const VECTOR2I &aP, bool aExact=false)
Insert the point aP belonging to one of the our segments, splitting the adjacent segment in two.
const VECTOR2I NearestPoint(const VECTOR2I &aP, bool aAllowInternalShapePoints=true) const
Find a point on the line chain that is closest to point aP.
int SegmentCount() const
Return the number of segments in this line chain.
int PathLength(const VECTOR2I &aP, int aIndex=-1) const
Compute the walk path length from the beginning of the line chain and the point aP belonging to our l...
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
long long int Length() const
Return length of the line chain in Euclidean metric.
Push and Shove diff pair dimensions (gap) settings dialog.
bool commonParallelProjection(SEG p, SEG n, SEG &pClip, SEG &nClip)
bool approxSegOverlaps(const SEG &aA, const SEG &aB, int aThreshold, int &aOverlapDist)
bool contains(const _Container &__container, _Value __value)
Returns true if the container contains the given value.
#define PNS_DBG(dbg, method,...)
#define PNS_DBGN(dbg, method)
VECTOR2< int32_t > VECTOR2I