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 );
633 wxString::Format(
"opt limit-corner-count root %d maxc %d mask %x",
634 rootObtuseCorners, aLine->
SegmentCount(), angleMask ) );
656 PNS_DBG( dbg, AddShape, &r,
YELLOW, 0, wxT(
"area-constraint" ) );
705 for(
int n = 0; n < n_segs - step; n++ )
709 || aCurrentPath.
IsArcSegment(
static_cast<std::size_t
>( n ) + step ) )
721 for(
int i = 0; i < 2; i++ )
735 path[i] = aCurrentPath;
742 if( cost[0] < cost_orig && cost[0] < cost[1] )
744 else if( cost[1] < cost_orig )
750 aCurrentPath = *picked;
760 bool aPermitDiagonal )
const
775 breakouts.push_back( l );
783 bool aPermitDiagonal )
const
818 l.
Append( intersections[0].p );
820 breakouts.push_back( l );
829 bool aPermitDiagonal )
const
836 breakouts.reserve( 12 );
840 d_offset.
x = ( s.
x > s.
y ) ? ( s.
x - s.
y ) / 2 : 0;
841 d_offset.
y = ( s.
x < s.
y ) ? ( s.
y - s.
x ) / 2 : 0;
851 if( aPermitDiagonal )
853 int l = aWidth + std::min( s.
x, s.
y ) / 2;
858 breakouts.emplace_back(
860 breakouts.emplace_back(
862 breakouts.emplace_back(
864 breakouts.emplace_back(
870 breakouts.emplace_back(
872 breakouts.emplace_back(
874 breakouts.emplace_back(
876 breakouts.emplace_back(
886 bool aPermitDiagonal )
const
888 switch( aItem->
Kind() )
892 const VIA*
via =
static_cast<const VIA*
>( aItem );
900 switch( shape->
Type() )
957 typedef std::tuple<int, long long int, SHAPE_LINE_CHAIN> RtVariant;
958 std::vector<RtVariant> variants;
960 SOLID* solid = dyn_cast<SOLID*>( aPad );
973 int p_end = std::min( aEndVertex, std::min( 3, line.
PointCount() - 1 ) );
976 for(
int p = 1; p <= p_end; p++ )
987 for(
int diag = 0; diag < 2; diag++ )
991 breakout.CPoint( -1 ), line.
CPoint( p ), diag == 0 );
1000 if( ang1 & ForbiddenAngles )
1003 if( breakout.Length() > line.
Length() )
1009 for(
int i = p + 1; i < line.
PointCount(); i++ )
1012 LINE tmp( *aLine, v );
1018 std::get<0>( vp ) = p;
1019 std::get<1>( vp ) = breakout.Length();
1020 std::get<2>( vp ) = aEnd ? v.
Reverse() : v;
1022 variants.push_back( vp );
1034 long long int max_length = 0;
1039 for( RtVariant& vp : variants )
1041 LINE tmp( *aLine, std::get<2>( vp ) );
1043 long long int len = std::get<1>( vp );
1047 if( cost < min_cost || ( cost == min_cost && len > max_length ) )
1049 l_best = std::get<2>( vp );
1050 p_best = std::get<0>( vp );
1053 if( cost <= min_cost )
1054 max_length = std::max<int>( len, max_length );
1056 min_cost = std::min( cost, min_cost );
1124 int thr = aLine->
Width() * 10;
1131 bool endMatch =
false;
1142 if( startMatch && endMatch && len < thr )
1144 for(
int i = 0; i < 2; i++ )
1148 repl =
LINE( *aLine, l2 );
1192 LINE refLine ( aRefIsP ? aPair->
PLine() : aPair->
NLine(), aNewRef );
1193 LINE coupledLine ( aRefIsP ? aPair->
NLine() : aPair->
PLine(), aNewCoupled );
1195 if( refLine.
Collide( &coupledLine, aNode ) )
1212 int vStartIdx[1024];
1215 aCoupled, aPair, vStartIdx );
1218 int64_t bestLength = -1;
1223 for(
int i=0; i< nStarts; i++ )
1225 for(
int j = 1; j < aCoupled.
PointCount() - 1; j++ )
1235 int64_t coupledLength = aPair->
CoupledLength( aRef, bypass );
1243 newCoupled.
Replace( si, ei, bypass );
1247 if( coupledLength > bestLength &&
verifyDpBypass( aNode, aPair, aRefIsP, aRef,
1250 bestBypass = newCoupled;
1251 bestLength = coupledLength;
1259 aNewCoupled = bestBypass;
1282 int64_t clenPre = aPair->
CoupledLength( currentPath, coupledPath );
1283 int64_t budget = clenPre / 10;
1285 while( n < n_segs - step )
1299 int64_t deltaCoupled = -1, deltaUni = -1;
1301 newRef = currentPath;
1304 deltaUni = aPair->
CoupledLength ( newRef, coupledPath ) - clenPre + budget;
1308 deltaCoupled = aPair->
CoupledLength( newRef, newCoup ) - clenPre + budget;
1310 if( deltaCoupled >= 0 )
1315 aPair->
SetShape( newRef, newCoup, !aTryP );
1324 aPair->
SetShape( newRef, coupledPath, !aTryP );
1346 int max_step_p = n_segs_p - 2;
1347 int max_step_n = n_segs_n - 2;
1349 if( step_p > max_step_p )
1350 step_p = max_step_p;
1352 if( step_n > max_step_n )
1353 step_n = max_step_n;
1355 if( step_p < 1 && step_n < 1 )
1358 bool found_anything_p =
false;
1359 bool found_anything_n =
false;
1362 found_anything_p =
mergeDpStep( aPair,
true, step_p );
1365 found_anything_n =
mergeDpStep( aPair,
false, step_n );
1367 if( !found_anything_n && !found_anything_p )
1388 const int total = oc + nc;
1390 for(
int i = 0; i < total; i++)
1392 int i_next = (i + 1 == total ? 0 : i + 1);
1395 : aNew.
CPoint( nc - 1 - (i - oc) );
1397 : aNew.
CPoint( nc - 1 - (i_next - oc) );
1398 area += -(int64_t) v0.
y *
v1.
x + (int64_t) v0.
x *
v1.
y;
1461 initial = guide.
Length();
1483 else if ( current + step >= initial )
1492 if ( current == initial )
1516 for(
int step = 0; step < 3; step++ )
1524 l_in = current.
Slice( i, i + 3 );
1526 for(
int dir = 0; dir <= 1; dir++ )
1528 if(
tightenSegment( dir ?
true :
false, aNode, aNewLine, l_in, l_out ) )
1531 opt.
Replace( i, i + 3, l_out );
1535 if( optArea < prevArea )
1544 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.
@ ROUNDED_90
H/V with filleted corners.
@ MITERED_90
H/V only (90-degree corners)
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.
virtual NET_HANDLE Net() const
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
bool Collide(const ITEM *aHead, const NODE *aNode, COLLISION_SEARCH_CONTEXT *aCtx=nullptr) const
Check for a collision (clearance violation) with between us and item aOther.
A 2D point on a given set of layers and belonging to a certain net, that links together a number of b...
const std::vector< ITEM * > & 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.
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.
int QueryJoints(const BOX2I &aBox, std::vector< JOINT * > &aJoints, LAYER_RANGE aLayerMask=LAYER_RANGE::All(), int aKindMask=ITEM::ANY_T)
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.
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)
ITEM * findPadOrVia(int aLayer, NET_HANDLE aNet, const VECTOR2I &aP) const
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
ROUTING_SETTINGS & Settings()
static ROUTER * GetInstance()
DIRECTION_45::CORNER_MODE GetCornerMode() const
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,...)
@ 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)
Calculate the new point of coord coord pX, pY, for a rotation center 0, 0.
double EuclideanNorm(const VECTOR2I &vector)