47 switch( dir_a.Angle( dir_b ) )
100 double aCornerTolerance )
const
114 m_collisionKindMask(
ITEM::ANY_T ),
115 m_effortLevel( MERGE_SEGMENTS ),
116 m_restrictAreaIsStrict( false )
170 auto links = aLine->
Links();
175 for(
int i = aStartVertex; i < aEndVertex - 1; i++ )
202 if( i->second.m_isStatic )
222 return p1_in && p2_in;
224 return p1_in || p2_in;
234 for(
int i = aVertex1; i < aVertex2; i++ )
272 LINE newPath( *aOriginLine, aCurrentPath );
273 newPath.
Line().
Replace( aVertex1, aVertex2, aReplacement );
308 for(
size_t i = 1; i <= cnt; ++i )
312 if( ipNext.
y == aP.
y )
314 if( ( ipNext.
x == aP.
x )
315 || ( ip.
y == aP.
y && ( ( ipNext.
x > aP.
x ) == ( ip.
x < aP.
x ) ) ) )
319 if( ( ip.
y < aP.
y ) != ( ipNext.
y < aP.
y ) )
329 double d =
static_cast<double>( ip.
x - aP.
x ) *
330 static_cast<double>( ipNext.
y - aP.
y ) -
331 static_cast<double>( ipNext.
x - aP.
x ) *
332 static_cast<double>( ip.
y - aP.
y );
337 if( ( d > 0 ) == ( ipNext.
y > ip.
y ) )
345 double d = ( (double) ip.
x - aP.
x ) * ( (double) ipNext.
y - aP.
y )
346 - ( (double) ipNext.
x - aP.
x ) * ( (double) ip.
y - aP.
y );
351 if( ( d > 0 ) == ( ipNext.
y > ip.
y ) )
375 std::vector<JOINT*> joints;
382 for(
JOINT* j : joints )
384 if( j->Net() == aOriginLine->
Net() )
389 bool falsePositive =
false;
391 for(
int k = 0; k < encPoly.
PointCount(); k++ )
393 if( encPoly.
CPoint(k) == j->Pos() )
395 falsePositive =
true;
441 if( !c->Check( aVertex1, aVertex2, aOriginLine, aCurrentPath, aReplacement ) )
451 LINE tmp( *aLine, aOptPath );
474 int max_step = n_segs - 2;
476 if( step > max_step )
485 bool found_anything =
false;
487 for(
int n = 0; n < n_segs - step; n++ )
497 s1opt =
SEG( s1.
A, ip );
498 s2opt =
SEG( ip, s2.
B );
507 LINE opt_track( *aLine, opt_path );
515 found_anything =
true;
522 if( !found_anything )
555 int max_step = n_segs - 2;
557 if( step > max_step )
563 bool found_anything =
mergeStep( aLine, current_path, step );
565 if( !found_anything )
584 for(
int segIdx = 0; segIdx < line.
SegmentCount() - 1; ++segIdx )
595 line.
Remove( segIdx + 1 );
609 PNS_DBG( dbg, AddItem, aRoot,
BLUE, 100000, wxT(
"root-line" ) );
629 int rootObtuseCorners = aRoot->
CountCorners( angleMask );
634 rootObtuseCorners, aLine->
SegmentCount(), angleMask ) );
656 PNS_DBG( dbg, AddShape, &r,
YELLOW, 0, wxT(
"area-constraint" ) );
702 for(
int n = 0; n < n_segs - step; n++ )
706 || aCurrentPath.
IsArcSegment(
static_cast<std::size_t
>( n ) + step ) )
718 for(
int i = 0; i < 2; i++ )
733 path[i] = aCurrentPath;
740 if( cost[0] < cost_orig && cost[0] < cost[1] )
742 else if( cost[1] < cost_orig )
748 aCurrentPath = *picked;
758 bool aPermitDiagonal )
const
773 breakouts.push_back( l );
781 bool aPermitDiagonal )
const
816 l.
Append( intersections[0].p );
818 breakouts.push_back( l );
827 bool aPermitDiagonal )
const
834 breakouts.reserve( 12 );
838 d_offset.
x = ( s.
x > s.
y ) ? ( s.
x - s.
y ) / 2 : 0;
839 d_offset.
y = ( s.
x < s.
y ) ? ( s.
y - s.
x ) / 2 : 0;
849 if( aPermitDiagonal )
851 int l = aWidth + std::min( s.
x, s.
y ) / 2;
856 breakouts.emplace_back(
858 breakouts.emplace_back(
860 breakouts.emplace_back(
862 breakouts.emplace_back(
868 breakouts.emplace_back(
870 breakouts.emplace_back(
872 breakouts.emplace_back(
874 breakouts.emplace_back(
884 bool aPermitDiagonal )
const
886 switch( aItem->
Kind() )
890 const VIA*
via =
static_cast<const VIA*
>( aItem );
898 switch( shape->
Type() )
955 typedef std::tuple<int, long long int, SHAPE_LINE_CHAIN> RtVariant;
956 std::vector<RtVariant> variants;
958 SOLID* solid = dyn_cast<SOLID*>( aPad );
971 int p_end = std::min( aEndVertex, std::min( 3, line.
PointCount() - 1 ) );
974 for(
int p = 1; p <= p_end; p++ )
985 for(
int diag = 0; diag < 2; diag++ )
989 breakout.CPoint( -1 ), line.
CPoint( p ), diag == 0 );
998 if( ang1 & ForbiddenAngles )
1001 if( breakout.Length() > line.
Length() )
1007 for(
int i = p + 1; i < line.
PointCount(); i++ )
1010 LINE tmp( *aLine, v );
1016 std::get<0>( vp ) = p;
1017 std::get<1>( vp ) = breakout.Length();
1018 std::get<2>( vp ) = aEnd ? v.
Reverse() : v;
1020 variants.push_back( vp );
1032 long long int max_length = 0;
1037 for( RtVariant& vp : variants )
1039 LINE tmp( *aLine, std::get<2>( vp ) );
1041 long long int len = std::get<1>( vp );
1045 if( cost < min_cost || ( cost == min_cost && len > max_length ) )
1047 l_best = std::get<2>( vp );
1048 p_best = std::get<0>( vp );
1051 if( cost <= min_cost )
1052 max_length = std::max<int>( len, max_length );
1054 min_cost = std::min( cost, min_cost );
1120 int thr = aLine->
Width() * 10;
1127 bool endMatch =
false;
1138 if( startMatch && endMatch && len < thr )
1140 for(
int i = 0; i < 2; i++ )
1144 repl =
LINE( *aLine, l2 );
1188 LINE refLine ( aRefIsP ? aPair->
PLine() : aPair->
NLine(), aNewRef );
1189 LINE coupledLine ( aRefIsP ? aPair->
NLine() : aPair->
PLine(), aNewCoupled );
1191 if( refLine.
Collide( &coupledLine, aNode ) )
1208 int vStartIdx[1024];
1211 aCoupled, aPair, vStartIdx );
1214 int64_t bestLength = -1;
1219 for(
int i=0; i< nStarts; i++ )
1221 for(
int j = 1; j < aCoupled.
PointCount() - 1; j++ )
1231 int64_t coupledLength = aPair->
CoupledLength( aRef, bypass );
1239 newCoupled.
Replace( si, ei, bypass );
1243 if( coupledLength > bestLength &&
verifyDpBypass( aNode, aPair, aRefIsP, aRef,
1246 bestBypass = newCoupled;
1247 bestLength = coupledLength;
1255 aNewCoupled = bestBypass;
1278 int64_t clenPre = aPair->
CoupledLength( currentPath, coupledPath );
1279 int64_t budget = clenPre / 10;
1281 while( n < n_segs - step )
1295 int64_t deltaCoupled = -1, deltaUni = -1;
1297 newRef = currentPath;
1300 deltaUni = aPair->
CoupledLength ( newRef, coupledPath ) - clenPre + budget;
1304 deltaCoupled = aPair->
CoupledLength( newRef, newCoup ) - clenPre + budget;
1306 if( deltaCoupled >= 0 )
1311 aPair->
SetShape( newRef, newCoup, !aTryP );
1320 aPair->
SetShape( newRef, coupledPath, !aTryP );
1342 int max_step_p = n_segs_p - 2;
1343 int max_step_n = n_segs_n - 2;
1345 if( step_p > max_step_p )
1346 step_p = max_step_p;
1348 if( step_n > max_step_n )
1349 step_n = max_step_n;
1351 if( step_p < 1 && step_n < 1 )
1354 bool found_anything_p =
false;
1355 bool found_anything_n =
false;
1358 found_anything_p =
mergeDpStep( aPair,
true, step_p );
1361 found_anything_n =
mergeDpStep( aPair,
false, step_n );
1363 if( !found_anything_n && !found_anything_p )
1384 const int total = oc + nc;
1386 for(
int i = 0; i < total; i++)
1388 int i_next = (i + 1 == total ? 0 : i + 1);
1391 : aNew.
CPoint( nc - 1 - (i - oc) );
1393 : aNew.
CPoint( nc - 1 - (i_next - oc) );
1394 area += -(int64_t) v0.
y *
v1.
x + (int64_t) v0.
x *
v1.
y;
1457 initial = guide.
Length();
1479 else if ( current + step >= initial )
1488 if ( current == initial )
1512 for(
int step = 0; step < 3; step++ )
1520 l_in = current.
Slice( i, i + 3 );
1522 for(
int dir = 0; dir <= 1; dir++ )
1524 if(
tightenSegment( dir ?
true :
false, aNode, aNewLine, l_in, l_out ) )
1527 opt.
Replace( i, i + 3, l_out );
1531 if( optArea < prevArea )
1540 aOptimized =
LINE( aNewLine, current );
coord_type GetHeight() const
coord_type GetWidth() const
bool Contains(const Vec &aPoint) const
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.
bool IsDiagonal() const
Returns true if the direction is diagonal (e.g.
bool IsObtuse(const DIRECTION_45 &aOther) const
bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
virtual bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
Calculate the cost of a given line, taking corner angles and total length into account.
static int CornerCost(const SHAPE_LINE_CHAIN &aLine)
void Replace(const LINE &aOldLine, const LINE &aNewLine)
void Remove(const LINE &aLine)
void Add(const LINE &aLine)
static int CornerCost(const SEG &aA, const SEG &aB)
bool IsBetter(const COST_ESTIMATOR &aOther, double aLengthTolerance, double aCornerTollerace) const
Basic class for a differential pair.
const SHAPE_LINE_CHAIN & CN() const
const RANGED_NUM< int > GapConstraint() const
double CoupledLength() const
void SetShape(const SHAPE_LINE_CHAIN &aP, const SHAPE_LINE_CHAIN &aN, bool aSwapLanes=false)
const SHAPE_LINE_CHAIN & CP() 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 int Layer() const
virtual const SHAPE * Shape() const
Return the geometrical shape of the item.
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...
const LINKED_ITEMS & LinkList() const
bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
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()
const SEG CSegment(int aIdx) const
Set line width.
int Width() const
Return true if the line is geometrically identical as line aOther.
bool IsLinked() const
Check if the segment aLink is a part of the line.
virtual void ClearLinks()
Return the number of segments that were assembled together to form this line.
Keep the router "world" - i.e.
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.
int QueryJoints(const BOX2I &aBox, std::vector< JOINT * > &aJoints, LAYER_RANGE aLayerMask=LAYER_RANGE::All(), int aKindMask=ITEM::ANY_T)
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
Perform various optimizations of the lines being routed, attempting to make the lines shorter and les...
void SetPreserveVertex(const VECTOR2I &aV)
std::pair< int, int > m_restrictedVertexRange
std::vector< OPT_CONSTRAINT * > m_constraints
~OPTIMIZER()
A quick shortcut to optimize a line without creating and setting up an optimizer.
ITEM * findPadOrVia(int aLayer, int aNet, const VECTOR2I &aP) const
bool mergeColinear(LINE *aLine)
void cacheAdd(ITEM *aItem, bool aIsStatic)
void removeCachedSegments(LINE *aLine, int aStartVertex=0, int aEndVertex=-1)
bool m_restrictAreaIsStrict
BREAKOUT_LIST computeBreakouts(int aWidth, const ITEM *aItem, bool aPermitDiagonal) const
bool fanoutCleanup(LINE *aLine)
std::vector< SHAPE_LINE_CHAIN > BREAKOUT_LIST
bool mergeFull(LINE *aLine)
bool mergeStep(LINE *aLine, SHAPE_LINE_CHAIN &aCurrentLine, int step)
void AddConstraint(OPT_CONSTRAINT *aConstraint)
bool mergeDpStep(DIFF_PAIR *aPair, bool aTryP, int step)
void CacheRemove(ITEM *aItem)
bool mergeObtuse(LINE *aLine)
void SetCollisionMask(int aMask)
bool checkConstraints(int aVertex1, int aVertex2, LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement)
bool checkColliding(ITEM *aItem, bool aUpdateCache=true)
std::unordered_map< ITEM *, CACHED_ITEM > m_cacheTags
bool runSmartPads(LINE *aLine)
bool mergeDpSegments(DIFF_PAIR *aPair)
int smartPadsSingle(LINE *aLine, ITEM *aPad, bool aEnd, int aEndVertex)
void SetEffortLevel(int aEffort)
BREAKOUT_LIST rectBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
BREAKOUT_LIST customBreakouts(int aWidth, const ITEM *aItem, bool aPermitDiagonal) const
BREAKOUT_LIST circleBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
VECTOR2I m_preservedVertex
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I &aV=VECTOR2I(0, 0))
void ClearCache(bool aStaticOnly=false)
@ 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.
@ FANOUT_CLEANUP
Simplify pad-pad and pad-via connections if possible.
@ MERGE_SEGMENTS
Reduce corner cost iteratively.
@ MERGE_COLINEAR
Merge co-linear segments.
@ MERGE_OBTUSE
Reduce corner cost by merging obtuse segments.
SHAPE_INDEX_LIST< ITEM * > m_cache
bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
virtual bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
ROUTER_IFACE * GetInterface() const
static ROUTER * GetInstance()
const SHAPE * Shape() const override
Return the geometrical shape of the item.
bool Matches(const T &aOther) const
ecoord SquaredDistance(const SEG &aSeg) const
VECTOR2I::extended_type ecoord
int Index() const
Return the index of this segment in its parent shape (applicable only to non-local segments).
int Length() const
Return the length (this).
bool ApproxParallel(const SEG &aSeg, int aDistanceThreshold=1) const
bool Collinear(const SEG &aSeg) const
Check if segment aSeg lies on the same line as (this).
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
ecoord SquaredLength() const
VECTOR2I LineProject(const VECTOR2I &aP) const
Compute the perpendicular projection point of aP on a line passing through ends of the segment.
SHAPE_TYPE Type() const
Return the type of the shape.
const VECTOR2I GetCenter() const
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.
bool IsPtOnArc(size_t aPtIndex) const
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
bool IsClosed() const override
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
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.
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.
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
std::vector< INTERSECTION > INTERSECTIONS
long long int Length() const
Return length of the line chain in Euclidean metric.
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
const VECTOR2I & GetPosition() const
const VECTOR2I GetSize() const
Represent a simple polygon consisting of a zero-thickness closed chain of connected line segments.
const SHAPE_LINE_CHAIN & Vertices() const
Return the list of vertices defining this simple polygon.
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
An abstract shape on 2D plane.
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< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
static constexpr EDA_ANGLE & ANGLE_360
static constexpr EDA_ANGLE & ANGLE_45
static constexpr EDA_ANGLE & ANGLE_90
static constexpr EDA_ANGLE & ANGLE_0
Push and Shove diff pair dimensions (gap) settings dialog.
bool tightenSegment(bool dir, NODE *aNode, const LINE &cur, const SHAPE_LINE_CHAIN &in, SHAPE_LINE_CHAIN &out)
SHAPE_RECT ApproximateSegmentAsRect(const SHAPE_SEGMENT &aSeg)
int findCoupledVertices(const VECTOR2I &aVertex, const SEG &aOrigSeg, const SHAPE_LINE_CHAIN &aCoupled, DIFF_PAIR *aPair, int *aIndices)
bool coupledBypass(NODE *aNode, DIFF_PAIR *aPair, bool aRefIsP, const SHAPE_LINE_CHAIN &aRef, const SHAPE_LINE_CHAIN &aRefBypass, const SHAPE_LINE_CHAIN &aCoupled, SHAPE_LINE_CHAIN &aNewCoupled)
void Tighten(NODE *aNode, const SHAPE_LINE_CHAIN &aOldLine, const LINE &aNewLine, LINE &aOptimized)
bool verifyDpBypass(NODE *aNode, DIFF_PAIR *aPair, bool aRefIsP, const SHAPE_LINE_CHAIN &aNewRef, const SHAPE_LINE_CHAIN &aNewCoupled)
bool checkDpColliding(NODE *aNode, DIFF_PAIR *aPair, bool aIsP, const SHAPE_LINE_CHAIN &aPath)
static bool pointInside2(const SHAPE_LINE_CHAIN &aL, const VECTOR2I &aP)
Determine if a point is located within a given polygon.
static int64_t shovedArea(const SHAPE_LINE_CHAIN &aOld, const SHAPE_LINE_CHAIN &aNew)
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
#define PNS_DBG(dbg, method,...)
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
@ SH_RECT
axis-aligned rectangle
@ SH_SIMPLE
simple polygon
bool operator()(ITEM *aOtherItem)
CACHE_VISITOR(const ITEM *aOurItem, NODE *aNode, int aMask)
void RotatePoint(int *pX, int *pY, const EDA_ANGLE &aAngle)
double EuclideanNorm(const VECTOR2I &vector)