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 )
174 auto links = aLine->
Links();
179 for(
int i = aStartVertex; i < aEndVertex - 1; i++ )
206 if( i->second.m_isStatic )
226 return p1_in && p2_in;
228 return p1_in || p2_in;
238 for(
int i = aVertex1; i < aVertex2; i++ )
276 LINE newPath( *aOriginLine, aCurrentPath );
277 newPath.
Line().
Replace( aVertex1, aVertex2, aReplacement );
312 for(
size_t i = 1; i <= cnt; ++i )
316 if( ipNext.
y == aP.
y )
318 if( ( ipNext.
x == aP.
x )
319 || ( ip.
y == aP.
y && ( ( ipNext.
x > aP.
x ) == ( ip.
x < aP.
x ) ) ) )
323 if( ( ip.
y < aP.
y ) != ( ipNext.
y < aP.
y ) )
333 double d =
static_cast<double>( ip.
x - aP.
x ) *
334 static_cast<double>( ipNext.
y - aP.
y ) -
335 static_cast<double>( ipNext.
x - aP.
x ) *
336 static_cast<double>( ip.
y - aP.
y );
341 if( ( d > 0 ) == ( ipNext.
y > ip.
y ) )
349 double d = ( (double) ip.
x - aP.
x ) * ( (double) ipNext.
y - aP.
y )
350 - ( (double) ipNext.
x - aP.
x ) * ( (double) ip.
y - aP.
y );
355 if( ( d > 0 ) == ( ipNext.
y > ip.
y ) )
379 std::vector<JOINT*> joints;
386 for(
JOINT* j : joints )
388 if( j->Net() == aOriginLine->
Net() )
393 bool falsePositive =
false;
395 for(
int k = 0; k < encPoly.
PointCount(); k++ )
397 if( encPoly.
CPoint(k) == j->Pos() )
399 falsePositive =
true;
436 if( !c->Check( aVertex1, aVertex2, aOriginLine, aCurrentPath, aReplacement ) )
446 LINE tmp( *aLine, aOptPath );
469 int max_step = n_segs - 2;
471 if( step > max_step )
480 bool found_anything =
false;
482 for(
int n = 0; n < n_segs - step; n++ )
492 s1opt =
SEG( s1.
A, ip );
493 s2opt =
SEG( ip, s2.
B );
502 LINE opt_track( *aLine, opt_path );
510 found_anything =
true;
517 if( !found_anything )
550 int max_step = n_segs - 2;
552 if( step > max_step )
558 bool found_anything =
mergeStep( aLine, current_path, step );
560 if( !found_anything )
579 for(
int segIdx = 0; segIdx < line.
SegmentCount() - 1; ++segIdx )
590 line.
Remove( segIdx + 1 );
604 PNS_DBG( dbg, AddItem, aRoot,
BLUE, 100000, wxT(
"root-line" ) );
624 int rootObtuseCorners = aRoot->
CountCorners( angleMask );
628 wxString::Format(
"opt limit-corner-count root %d maxc %d mask %x",
629 rootObtuseCorners, aLine->
SegmentCount(), angleMask ) );
651 PNS_DBG( dbg, AddShape, &r,
YELLOW, 0, wxT(
"area-constraint" ) );
700 for(
int n = 0; n < n_segs - step; n++ )
704 || aCurrentPath.
IsArcSegment(
static_cast<std::size_t
>( n ) + step ) )
716 for(
int i = 0; i < 2; i++ )
730 path[i] = aCurrentPath;
737 if( cost[0] < cost_orig && cost[0] < cost[1] )
739 else if( cost[1] < cost_orig )
745 aCurrentPath = *picked;
755 bool aPermitDiagonal )
const
770 breakouts.push_back( l );
778 bool aPermitDiagonal )
const
813 l.
Append( intersections[0].p );
815 breakouts.push_back( l );
824 bool aPermitDiagonal )
const
831 breakouts.reserve( 12 );
835 d_offset.
x = ( s.
x > s.
y ) ? ( s.
x - s.
y ) / 2 : 0;
836 d_offset.
y = ( s.
x < s.
y ) ? ( s.
y - s.
x ) / 2 : 0;
846 if( aPermitDiagonal )
848 int l = aWidth + std::min( s.
x, s.
y ) / 2;
853 breakouts.emplace_back(
855 breakouts.emplace_back(
857 breakouts.emplace_back(
859 breakouts.emplace_back(
865 breakouts.emplace_back(
867 breakouts.emplace_back(
869 breakouts.emplace_back(
871 breakouts.emplace_back(
881 bool aPermitDiagonal )
const
883 switch( aItem->
Kind() )
887 const VIA*
via =
static_cast<const VIA*
>( aItem );
895 switch( shape->
Type() )
952 typedef std::tuple<int, long long int, SHAPE_LINE_CHAIN> RtVariant;
953 std::vector<RtVariant> variants;
955 SOLID* solid = dyn_cast<SOLID*>( aPad );
968 int p_end = std::min( aEndVertex, std::min( 3, line.
PointCount() - 1 ) );
971 for(
int p = 1; p <= p_end; p++ )
982 for(
int diag = 0; diag < 2; diag++ )
986 breakout.CPoint( -1 ), line.
CPoint( p ), diag == 0 );
995 if( ang1 & ForbiddenAngles )
998 if( breakout.Length() > line.
Length() )
1004 for(
int i = p + 1; i < line.
PointCount(); i++ )
1007 LINE tmp( *aLine, v );
1013 std::get<0>( vp ) = p;
1014 std::get<1>( vp ) = breakout.Length();
1015 std::get<2>( vp ) = aEnd ? v.
Reverse() : v;
1017 variants.push_back( vp );
1029 long long int max_length = 0;
1034 for( RtVariant& vp : variants )
1036 LINE tmp( *aLine, std::get<2>( vp ) );
1038 long long int len = std::get<1>( vp );
1042 if( cost < min_cost || ( cost == min_cost && len > max_length ) )
1044 l_best = std::get<2>( vp );
1045 p_best = std::get<0>( vp );
1048 if( cost <= min_cost )
1049 max_length = std::max<int>( len, max_length );
1051 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 );
1170 int64_t{ ( ( projOverCoupled - aVertex ).EuclideanNorm() ) } - aPair->
Width();
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 );
constexpr size_type GetWidth() const
constexpr size_type GetHeight() const
constexpr 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.
const PNS_LAYER_RANGE & Layers() const
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.
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.
const SHAPE_LINE_CHAIN & CLine() const
int CountCorners(int aAngles) 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.
std::vector< LINKED_ITEM * > & Links()
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, PNS_LAYER_RANGE aLayerMask=PNS_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)
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 addConstraint(OPT_CONSTRAINT *aConstraint)
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
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.
void Simplify(int aMaxError=0)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
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_0
static constexpr EDA_ANGLE ANGLE_90
static constexpr EDA_ANGLE ANGLE_45
static constexpr EDA_ANGLE ANGLE_360
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.
VECTOR2< int32_t > VECTOR2I