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 );
305 for(
size_t i = 1; i <= cnt; ++i )
309 if( ipNext.
y == aP.
y )
311 if( ( ipNext.
x == aP.
x )
312 || ( ip.
y == aP.
y && ( ( ipNext.
x > aP.
x ) == ( ip.
x < aP.
x ) ) ) )
316 if( ( ip.
y < aP.
y ) != ( ipNext.
y < aP.
y ) )
326 double d = static_cast<double>( ip.
x - aP.
x ) *
327 static_cast<double>( ipNext.
y - aP.
y ) -
328 static_cast<double>( ipNext.
x - aP.
x ) *
329 static_cast<double>( ip.
y - aP.
y );
334 if( ( d > 0 ) == ( ipNext.
y > ip.
y ) )
342 double d = ( (double) ip.
x - aP.
x ) * ( (double) ipNext.
y - aP.
y )
343 - ( (double) ipNext.
x - aP.
x ) * ( (double) ip.
y - aP.
y );
348 if( ( d > 0 ) == ( ipNext.
y > ip.
y ) )
372 std::vector<JOINT*> joints;
379 for(
JOINT* j : joints )
381 if( j->Net() == aOriginLine->
Net() )
386 bool falsePositive =
false;
388 for(
int k = 0; k < encPoly.
PointCount(); k++ )
390 if( encPoly.
CPoint(k) == j->Pos() )
392 falsePositive =
true;
438 if( !c->Check( aVertex1, aVertex2, aOriginLine, aCurrentPath, aReplacement ) )
448 LINE tmp( *aLine, aOptPath );
471 int max_step = n_segs - 2;
473 if( step > max_step )
482 bool found_anything =
false;
484 for(
int n = 0; n < n_segs - step; n++ )
494 s1opt =
SEG( s1.
A, ip );
495 s2opt =
SEG( ip, s2.
B );
504 LINE opt_track( *aLine, opt_path );
512 found_anything =
true;
519 if( !found_anything )
552 int max_step = n_segs - 2;
554 if( step > max_step )
560 bool found_anything =
mergeStep( aLine, current_path, step );
562 if( !found_anything )
581 for(
int segIdx = 0; segIdx < line.
SegmentCount() - 1; ++segIdx )
592 line.
Remove( segIdx + 1 );
626 int rootObtuseCorners = aRoot->
CountCorners( angleMask );
693 for(
int n = 0; n < n_segs - step; n++ )
697 || aCurrentPath.
IsArcSegment( static_cast<std::size_t>( n ) + step ) )
709 for(
int i = 0; i < 2; i++ )
724 path[i] = aCurrentPath;
731 if( cost[0] < cost_orig && cost[0] < cost[1] )
733 else if( cost[1] < cost_orig )
739 aCurrentPath = *picked;
749 bool aPermitDiagonal )
const 755 const SHAPE_CIRCLE* cir = static_cast<const SHAPE_CIRCLE*>( aShape );
762 breakouts.push_back( l );
770 bool aPermitDiagonal )
const 776 VECTOR2I p0 = static_cast<const SOLID*>( aItem )->Pos();
778 int length = std::max( bbox.GetWidth(), bbox.GetHeight() ) / 2 + 5;
780 for(
int angle = 0;
angle < 360;
angle += ( aPermitDiagonal ? 45 : 90 ) )
802 l.
Append( intersections[0].p );
804 breakouts.push_back( l );
813 bool aPermitDiagonal )
const 815 const SHAPE_RECT* rect = static_cast<const SHAPE_RECT*>(aShape);
822 d_offset.
x = ( s.
x > s.
y ) ? ( s.
x - s.
y ) / 2 : 0;
823 d_offset.
y = ( s.
x < s.
y ) ? ( s.
y - s.
x ) / 2 : 0;
833 if( aPermitDiagonal )
835 int l = aWidth + std::min( s.
x, s.
y ) / 2;
840 breakouts.emplace_back(
842 breakouts.emplace_back(
844 breakouts.emplace_back(
846 breakouts.emplace_back(
852 breakouts.emplace_back(
854 breakouts.emplace_back(
856 breakouts.emplace_back(
858 breakouts.emplace_back(
868 bool aPermitDiagonal )
const 870 switch( aItem->
Kind() )
874 const VIA*
via = static_cast<const VIA*>( aItem );
882 switch( shape->
Type() )
889 const SHAPE_SEGMENT* seg = static_cast<const SHAPE_SEGMENT*> (shape);
939 typedef std::tuple<int, long long int, SHAPE_LINE_CHAIN> RtVariant;
940 std::vector<RtVariant> variants;
942 SOLID* solid = dyn_cast<SOLID*>( aPad );
955 int p_end = std::min( aEndVertex, std::min( 3, line.PointCount() - 1 ) );
958 for(
int p = 1; p <= p_end; p++ )
962 SEG( line.CPoint( 0 ), line.CPoint( p ) ), aLine->
Width() / 2 ) )
969 for(
int diag = 0; diag < 2; diag++ )
973 breakout.CPoint( -1 ), line.CPoint( p ), diag == 0 );
982 if( ang1 & ForbiddenAngles )
985 if( breakout.Length() > line.Length() )
991 for(
int i = p + 1; i < line.PointCount(); i++ )
992 v.
Append( line.CPoint( i ) );
994 LINE tmp( *aLine, v );
1000 std::get<0>( vp ) = p;
1001 std::get<1>( vp ) = breakout.Length();
1002 std::get<2>( vp ) = aEnd ? v.
Reverse() : v;
1004 variants.push_back( vp );
1016 long long int max_length = 0;
1021 for( RtVariant& vp : variants )
1023 LINE tmp( *aLine, std::get<2>( vp ) );
1025 long long int len = std::get<1>( vp );
1029 if( cost < min_cost || ( cost == min_cost && len > max_length ) )
1031 l_best = std::get<2>( vp );
1032 p_best = std::get<0>( vp );
1035 if( cost <= min_cost )
1036 max_length = std::max<int>( len, max_length );
1038 min_cost = std::min( cost, min_cost );
1104 int thr = aLine->
Width() * 10;
1111 bool endMatch =
false;
1122 if( startMatch && endMatch && len < thr )
1124 for(
int i = 0; i < 2; i++ )
1128 repl =
LINE( *aLine, l2 );
1172 LINE refLine ( aRefIsP ? aPair->
PLine() : aPair->
NLine(), aNewRef );
1173 LINE coupledLine ( aRefIsP ? aPair->
NLine() : aPair->
PLine(), aNewCoupled );
1175 if( refLine.Collide( &coupledLine, aNode ) )
1192 int vStartIdx[1024];
1195 aCoupled, aPair, vStartIdx );
1198 int64_t bestLength = -1;
1203 for(
int i=0; i< nStarts; i++ )
1205 for(
int j = 1; j < aCoupled.
PointCount() - 1; j++ )
1207 int delta = std::abs ( vStartIdx[i] - j );
1215 int64_t coupledLength = aPair->CoupledLength( aRef, bypass );
1223 newCoupled.
Replace( si, ei, bypass );
1227 if( coupledLength > bestLength &&
verifyDpBypass( aNode, aPair, aRefIsP, aRef,
1230 bestBypass = newCoupled;
1231 bestLength = coupledLength;
1239 aNewCoupled = bestBypass;
1262 int64_t clenPre = aPair->
CoupledLength( currentPath, coupledPath );
1263 int64_t budget = clenPre / 10;
1265 while( n < n_segs - step )
1279 int64_t deltaCoupled = -1, deltaUni = -1;
1281 newRef = currentPath;
1284 deltaUni = aPair->
CoupledLength ( newRef, coupledPath ) - clenPre + budget;
1288 deltaCoupled = aPair->
CoupledLength( newRef, newCoup ) - clenPre + budget;
1290 if( deltaCoupled >= 0 )
1295 aPair->
SetShape( newRef, newCoup, !aTryP );
1304 aPair->
SetShape( newRef, coupledPath, !aTryP );
1326 int max_step_p = n_segs_p - 2;
1327 int max_step_n = n_segs_n - 2;
1329 if( step_p > max_step_p )
1330 step_p = max_step_p;
1332 if( step_n > max_step_n )
1333 step_n = max_step_n;
1335 if( step_p < 1 && step_n < 1 )
1338 bool found_anything_p =
false;
1339 bool found_anything_n =
false;
1342 found_anything_p =
mergeDpStep( aPair,
true, step_p );
1345 found_anything_n =
mergeDpStep( aPair,
false, step_n );
1347 if( !found_anything_n && !found_anything_p )
1368 const int total = oc + nc;
1370 for(
int i = 0; i < total; i++)
1372 int i_next = (i + 1 == total ? 0 : i + 1);
1375 : aNew.
CPoint( nc - 1 - (i - oc) );
1377 : aNew.
CPoint( nc - 1 - (i_next - oc) );
1378 area += -(int64_t) v0.
y * v1.
x + (int64_t) v0.
x * v1.
y;
1381 return std::abs( area / 2 );
1441 initial = guide.
Length();
1463 else if ( current + step >= initial )
1472 if ( current == initial )
1496 for(
int step = 0; step < 3; step++ )
1500 for(
int i = 0; i <= current.SegmentCount() - 3; i++ )
1504 l_in = current.
Slice( i, i + 3 );
1506 for(
int dir = 0; dir <= 1; dir++ )
1508 if(
tightenSegment( dir ?
true :
false, aNode, aNewLine, l_in, l_out ) )
1511 opt.
Replace( i, i + 3, l_out );
1512 auto optArea = std::abs(
shovedArea( aOldLine, opt ) );
1513 auto prevArea = std::abs(
shovedArea( aOldLine, current ) );
1515 if( optArea < prevArea )
1524 aOptimized =
LINE( aNewLine, current );
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
int Length() const
Return the length (this).
const SHAPE_LINE_CHAIN & CLine() const
static bool pointInside2(const SHAPE_LINE_CHAIN &aL, const VECTOR2I &aP)
Determine if a point is located within a given polygon.
BREAKOUT_LIST computeBreakouts(int aWidth, const ITEM *aItem, bool aPermitDiagonal) const
Base class for PNS router board items.
int Index() const
Return the index of this segment in its parent shape (applicable only to non-local segments).
const SHAPE * Shape() const override
Return the geometrical shape of the item.
long long int Length() const
Return length of the line chain in Euclidean metric.
Represent a simple polygon consisting of a zero-thickness closed chain of connected line segments.
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Find all intersection points between our line chain and the segment aSeg.
std::vector< INTERSECTION > INTERSECTIONS
virtual int Layer() const
BREAKOUT_LIST circleBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
std::unordered_map< ITEM *, CACHED_ITEM > m_cacheTags
Keep the router "world" - i.e.
void CacheRemove(ITEM *aItem)
void removeCachedSegments(LINE *aLine, int aStartVertex=0, int aEndVertex=-1)
void SetShape(const SHAPE_LINE_CHAIN &aP, const SHAPE_LINE_CHAIN &aN, bool aSwapLanes=false)
ecoord SquaredLength() const
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
const SEG CSegment(int aIdx) const
Set line width.
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.
~OPTIMIZER()
A quick shortcut to optimize a line without creating and setting up an optimizer.
Simplify pad-pad and pad-via connections if possible.
const SHAPE_LINE_CHAIN & CN() const
VECTOR2I::extended_type ecoord
bool mergeStep(LINE *aLine, SHAPE_LINE_CHAIN &aCurrentLine, int step)
ITEM * findPadOrVia(int aLayer, int aNet, const VECTOR2I &aP) const
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.
void Add(const LINE &aLine)
ecoord SquaredDistance(const SEG &aSeg) const
double CoupledLength() const
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
const VECTOR2I GetCenter() const
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
BREAKOUT_LIST rectBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
const SHAPE_LINE_CHAIN Reverse() const
Reverse point order in the line chain.
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
bool runSmartPads(LINE *aLine)
bool mergeFull(LINE *aLine)
int PointCount() const
Return the number of points (vertices) in this line chain.
const RANGED_NUM< int > GapConstraint() const
bool checkConstraints(int aVertex1, int aVertex2, LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement)
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,...
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I &aV=VECTOR2I(0, 0))
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
bool m_restrictAreaIsStrict
bool ApproxParallel(const SEG &aSeg, int aDistanceThreshold=1) const
const VECTOR2I & CPoint(int aIdx) const
void SetCollisionMask(int aMask)
const VECTOR2I GetSize() const
bool mergeDpStep(DIFF_PAIR *aPair, bool aTryP, int step)
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Return the shape of the line.
AngleType Angle(const DIRECTION_45 &aOther) const
Return the type of angle between directions (this) and aOther.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
void AddConstraint(OPT_CONSTRAINT *aConstraint)
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
A 2D point on a given set of layers and belonging to a certain net, that links together a number of b...
static int64_t shovedArea(const SHAPE_LINE_CHAIN &aOld, const SHAPE_LINE_CHAIN &aNew)
BREAKOUT_LIST customBreakouts(int aWidth, const ITEM *aItem, bool aPermitDiagonal) const
VECTOR2I LineProject(const VECTOR2I &aP) const
Compute the perpendicular projection point of aP on a line passing through ends of the segment.
virtual bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
bool IsArcSegment(size_t aSegment) const
bool IsClosed() const override
virtual const SHAPE * Shape() const
Return the geometrical shape of the item.
Represent route directions & corner angles in a 45-degree metric.
const VECTOR2I & GetPosition() const
bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
bool IsLinked() const
Check if the segment aLink is a part of the line.
bool Contains(const Vec &aPoint) const
bool mergeDpSegments(DIFF_PAIR *aPair)
#define PNS_DBG(dbg, method,...)
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 SetPreserveVertex(const VECTOR2I &aV)
bool Collide(const ITEM *aOther, const NODE *aNode, bool aDifferentNetsOnly=true) const
Check for a collision (clearance violation) with between us and item aOther.
int QueryJoints(const BOX2I &aBox, std::vector< JOINT * > &aJoints, LAYER_RANGE aLayerMask=LAYER_RANGE::All(), int aKindMask=ITEM::ANY_T)
bool IsDiagonal() const
Returns true if the direction is diagonal (e.g.
const SHAPE_LINE_CHAIN & Vertices() const
Return the list of vertices defining this simple polygon.
virtual bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
bool mergeObtuse(LINE *aLine)
An abstract shape on 2D plane.
void Remove(int aStartIndex, int aEndIndex)
Remove the range of points [start_index, end_index] from the line chain.
const LINKED_ITEMS & LinkList() const
void Remove(const LINE &aLine)
Reduce corner cost iteratively.
int SegmentCount() const
Return the number of segments in this line chain.
bool IsPtOnArc(size_t aPtIndex) const
int findCoupledVertices(const VECTOR2I &aVertex, const SEG &aOrigSeg, const SHAPE_LINE_CHAIN &aCoupled, DIFF_PAIR *aPair, int *aIndices)
bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
std::vector< OPT_CONSTRAINT * > m_constraints
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
SHAPE_LINE_CHAIN & Line()
bool tightenSegment(bool dir, NODE *aNode, const LINE &cur, const SHAPE_LINE_CHAIN &in, SHAPE_LINE_CHAIN &out)
bool Collinear(const SEG &aSeg) const
Check if segment aSeg lies on the same line as (this).
VECTOR2I m_preservedVertex
Basic class for a differential pair.
void cacheAdd(ITEM *aItem, bool aIsStatic)
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
bool operator()(ITEM *aOtherItem)
const SHAPE_LINE_CHAIN & CP() const
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
VECTOR2< T > Rotate(double aAngle) const
Rotate the vector by a given angle.
bool verifyDpBypass(NODE *aNode, DIFF_PAIR *aPair, bool aRefIsP, const SHAPE_LINE_CHAIN &aNewRef, const SHAPE_LINE_CHAIN &aNewCoupled)
CACHE_VISITOR(const ITEM *aOurItem, NODE *aNode, int aMask)
static int CornerCost(const SHAPE_LINE_CHAIN &aLine)
Reduce corner cost by merging obtuse segments.
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
bool IsBetter(const COST_ESTIMATOR &aOther, double aLengthTolerance, double aCornerTollerace) const
bool fanoutCleanup(LINE *aLine)
Do not attempt to optimize if the resulting line's corner count is outside the predefined range.
virtual void ClearLinks()
Return the number of segments that were assembled together to form this line.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
SHAPE_RECT ApproximateSegmentAsRect(const SHAPE_SEGMENT &aSeg)
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.
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
bool mergeColinear(LINE *aLine)
bool OfKind(int aKindMask) const
Return true if the item's type matches the mask aKindMask.
bool checkColliding(ITEM *aItem, bool aUpdateCache=true)
int Width() const
Return true if the line is geometrically identical as line aOther.
static int CornerCost(const SEG &aA, const SEG &aB)
void Replace(const LINE &aOldLine, const LINE &aNewLine)
PnsKind Kind() const
Return the type (kind) of the item.
Perform various optimizations of the lines being routed, attempting to make the lines shorter and les...
void Clear()
Remove all points from the line chain.
bool Matches(const T &aOther) const
Merge co-linear segments.
int smartPadsSingle(LINE *aLine, ITEM *aPad, bool aEnd, int aEndVertex)
SHAPE_INDEX_LIST< ITEM * > m_cache
void SetEffortLevel(int aEffort)
std::vector< SHAPE_LINE_CHAIN > BREAKOUT_LIST
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Replace points with indices in range [start_index, end_index] with a single point aP.
Calculate the cost of a given line, taking corner angles and total length into account.
Push and Shove diff pair dimensions (gap) settings dialog.
bool checkDpColliding(NODE *aNode, DIFF_PAIR *aPair, bool aIsP, const SHAPE_LINE_CHAIN &aPath)
SHAPE_TYPE Type() const
Return the type of the shape.
std::pair< int, int > m_restrictedVertexRange
ROUTER_IFACE * GetInterface() const
void ClearCache(bool aStaticOnly=false)
static ROUTER * GetInstance()
const LAYER_RANGE & Layers() const
bool IsObtuse(const DIRECTION_45 &aOther) const
void Tighten(NODE *aNode, const SHAPE_LINE_CHAIN &aOldLine, const LINE &aNewLine, LINE &aOptimized)
int CountCorners(int aAngles) const