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" ) );
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++ )
732 path[i] = aCurrentPath;
739 if( cost[0] < cost_orig && cost[0] < cost[1] )
741 else if( cost[1] < cost_orig )
747 aCurrentPath = *picked;
757 bool aPermitDiagonal )
const
772 breakouts.push_back( l );
780 bool aPermitDiagonal )
const
815 l.
Append( intersections[0].p );
817 breakouts.push_back( l );
826 bool aPermitDiagonal )
const
833 breakouts.reserve( 12 );
837 d_offset.
x = ( s.
x > s.
y ) ? ( s.
x - s.
y ) / 2 : 0;
838 d_offset.
y = ( s.
x < s.
y ) ? ( s.
y - s.
x ) / 2 : 0;
848 if( aPermitDiagonal )
850 int l = aWidth + std::min( s.
x, s.
y ) / 2;
855 breakouts.emplace_back(
857 breakouts.emplace_back(
859 breakouts.emplace_back(
861 breakouts.emplace_back(
867 breakouts.emplace_back(
869 breakouts.emplace_back(
871 breakouts.emplace_back(
873 breakouts.emplace_back(
883 bool aPermitDiagonal )
const
885 switch( aItem->
Kind() )
889 const VIA*
via =
static_cast<const VIA*
>( aItem );
897 switch( shape->
Type() )
954 typedef std::tuple<int, long long int, SHAPE_LINE_CHAIN> RtVariant;
955 std::vector<RtVariant> variants;
957 SOLID* solid = dyn_cast<SOLID*>( aPad );
970 int p_end = std::min( aEndVertex, std::min( 3, line.
PointCount() - 1 ) );
973 for(
int p = 1; p <= p_end; p++ )
984 for(
int diag = 0; diag < 2; diag++ )
988 breakout.CPoint( -1 ), line.
CPoint( p ), diag == 0 );
997 if( ang1 & ForbiddenAngles )
1000 if( breakout.Length() > line.
Length() )
1006 for(
int i = p + 1; i < line.
PointCount(); i++ )
1009 LINE tmp( *aLine, v );
1015 std::get<0>( vp ) = p;
1016 std::get<1>( vp ) = breakout.Length();
1017 std::get<2>( vp ) = aEnd ? v.
Reverse() : v;
1019 variants.push_back( vp );
1031 long long int max_length = 0;
1036 for( RtVariant& vp : variants )
1038 LINE tmp( *aLine, std::get<2>( vp ) );
1040 long long int len = std::get<1>( vp );
1044 if( cost < min_cost || ( cost == min_cost && len > max_length ) )
1046 l_best = std::get<2>( vp );
1047 p_best = std::get<0>( vp );
1050 if( cost <= min_cost )
1051 max_length = std::max<int>( len, max_length );
1053 min_cost = std::min( cost, min_cost );
1119 int thr = aLine->
Width() * 10;
1126 bool endMatch =
false;
1137 if( startMatch && endMatch && len < thr )
1139 for(
int i = 0; i < 2; i++ )
1143 repl =
LINE( *aLine, l2 );
1187 LINE refLine ( aRefIsP ? aPair->
PLine() : aPair->
NLine(), aNewRef );
1188 LINE coupledLine ( aRefIsP ? aPair->
NLine() : aPair->
PLine(), aNewCoupled );
1190 if( refLine.
Collide( &coupledLine, aNode ) )
1207 int vStartIdx[1024];
1210 aCoupled, aPair, vStartIdx );
1213 int64_t bestLength = -1;
1218 for(
int i=0; i< nStarts; i++ )
1220 for(
int j = 1; j < aCoupled.
PointCount() - 1; j++ )
1230 int64_t coupledLength = aPair->
CoupledLength( aRef, bypass );
1238 newCoupled.
Replace( si, ei, bypass );
1242 if( coupledLength > bestLength &&
verifyDpBypass( aNode, aPair, aRefIsP, aRef,
1245 bestBypass = newCoupled;
1246 bestLength = coupledLength;
1254 aNewCoupled = bestBypass;
1277 int64_t clenPre = aPair->
CoupledLength( currentPath, coupledPath );
1278 int64_t budget = clenPre / 10;
1280 while( n < n_segs - step )
1294 int64_t deltaCoupled = -1, deltaUni = -1;
1296 newRef = currentPath;
1299 deltaUni = aPair->
CoupledLength ( newRef, coupledPath ) - clenPre + budget;
1303 deltaCoupled = aPair->
CoupledLength( newRef, newCoup ) - clenPre + budget;
1305 if( deltaCoupled >= 0 )
1310 aPair->
SetShape( newRef, newCoup, !aTryP );
1319 aPair->
SetShape( newRef, coupledPath, !aTryP );
1341 int max_step_p = n_segs_p - 2;
1342 int max_step_n = n_segs_n - 2;
1344 if( step_p > max_step_p )
1345 step_p = max_step_p;
1347 if( step_n > max_step_n )
1348 step_n = max_step_n;
1350 if( step_p < 1 && step_n < 1 )
1353 bool found_anything_p =
false;
1354 bool found_anything_n =
false;
1357 found_anything_p =
mergeDpStep( aPair,
true, step_p );
1360 found_anything_n =
mergeDpStep( aPair,
false, step_n );
1362 if( !found_anything_n && !found_anything_p )
1383 const int total = oc + nc;
1385 for(
int i = 0; i < total; i++)
1387 int i_next = (i + 1 == total ? 0 : i + 1);
1390 : aNew.
CPoint( nc - 1 - (i - oc) );
1392 : aNew.
CPoint( nc - 1 - (i_next - oc) );
1393 area += -(int64_t) v0.
y *
v1.
x + (int64_t) v0.
x *
v1.
y;
1456 initial = guide.
Length();
1478 else if ( current + step >= initial )
1487 if ( current == initial )
1511 for(
int step = 0; step < 3; step++ )
1519 l_in = current.
Slice( i, i + 3 );
1521 for(
int dir = 0; dir <= 1; dir++ )
1523 if(
tightenSegment( dir ?
true :
false, aNode, aNewLine, l_in, l_out ) )
1526 opt.
Replace( i, i + 3, l_out );
1530 if( optArea < prevArea )
1539 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.
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.
int QueryJoints(const BOX2I &aBox, std::vector< JOINT * > &aJoints, LAYER_RANGE aLayerMask=LAYER_RANGE::All(), int aKindMask=ITEM::ANY_T)
const JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet) const
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,...)
@ 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)