KiCad PCB EDA Suite
PNS::OPTIMIZER Class Reference

Perform various optimizations of the lines being routed, attempting to make the lines shorter and less cornery. More...

#include <pns_optimizer.h>

Classes

struct  CACHE_VISITOR
 
struct  CACHED_ITEM
 

Public Types

enum  OptimizationEffort {
  MERGE_SEGMENTS = 0x01 , SMART_PADS = 0x02 , MERGE_OBTUSE = 0x04 , FANOUT_CLEANUP = 0x08 ,
  KEEP_TOPOLOGY = 0x10 , PRESERVE_VERTEX = 0x20 , RESTRICT_VERTEX_RANGE = 0x40 , MERGE_COLINEAR = 0x80 ,
  RESTRICT_AREA = 0x100 , LIMIT_CORNER_COUNT = 0x200
}
 

Public Member Functions

 OPTIMIZER (NODE *aWorld)
 
 ~OPTIMIZER ()
 A quick shortcut to optimize a line without creating and setting up an optimizer. More...
 
bool Optimize (LINE *aLine, LINE *aResult=nullptr, LINE *aRoot=nullptr)
 
bool Optimize (DIFF_PAIR *aPair)
 
void SetWorld (NODE *aNode)
 
void CacheRemove (ITEM *aItem)
 
void ClearCache (bool aStaticOnly=false)
 
void SetCollisionMask (int aMask)
 
void SetEffortLevel (int aEffort)
 
void SetPreserveVertex (const VECTOR2I &aV)
 
void SetRestrictVertexRange (int aStart, int aEnd)
 
void SetRestrictArea (const BOX2I &aArea, bool aStrict=true)
 
void ClearConstraints ()
 
void AddConstraint (OPT_CONSTRAINT *aConstraint)
 

Static Public Member Functions

static bool Optimize (LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I &aV=VECTOR2I(0, 0))
 

Private Types

typedef std::vector< SHAPE_LINE_CHAINBREAKOUT_LIST
 

Private Member Functions

bool mergeObtuse (LINE *aLine)
 
bool mergeFull (LINE *aLine)
 
bool mergeColinear (LINE *aLine)
 
bool runSmartPads (LINE *aLine)
 
bool mergeStep (LINE *aLine, SHAPE_LINE_CHAIN &aCurrentLine, int step)
 
bool fanoutCleanup (LINE *aLine)
 
bool mergeDpSegments (DIFF_PAIR *aPair)
 
bool mergeDpStep (DIFF_PAIR *aPair, bool aTryP, int step)
 
bool checkColliding (ITEM *aItem, bool aUpdateCache=true)
 
bool checkColliding (LINE *aLine, const SHAPE_LINE_CHAIN &aOptPath)
 
void cacheAdd (ITEM *aItem, bool aIsStatic)
 
void removeCachedSegments (LINE *aLine, int aStartVertex=0, int aEndVertex=-1)
 
bool checkConstraints (int aVertex1, int aVertex2, LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement)
 
BREAKOUT_LIST circleBreakouts (int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
 
BREAKOUT_LIST rectBreakouts (int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
 
BREAKOUT_LIST customBreakouts (int aWidth, const ITEM *aItem, bool aPermitDiagonal) const
 
BREAKOUT_LIST computeBreakouts (int aWidth, const ITEM *aItem, bool aPermitDiagonal) const
 
int smartPadsSingle (LINE *aLine, ITEM *aPad, bool aEnd, int aEndVertex)
 
ITEMfindPadOrVia (int aLayer, int aNet, const VECTOR2I &aP) const
 

Private Attributes

SHAPE_INDEX_LIST< ITEM * > m_cache
 
std::vector< OPT_CONSTRAINT * > m_constraints
 
std::unordered_map< ITEM *, CACHED_ITEMm_cacheTags
 
NODEm_world
 
int m_collisionKindMask
 
int m_effortLevel
 
VECTOR2I m_preservedVertex
 
std::pair< int, int > m_restrictedVertexRange
 
BOX2I m_restrictArea
 
bool m_restrictAreaIsStrict
 

Static Private Attributes

static const int MaxCachedItems = 256
 

Detailed Description

Perform various optimizations of the lines being routed, attempting to make the lines shorter and less cornery.

There are 3 kinds of optimizations so far:

  • Merging obtuse segments (MERGE_OBTUSE): tries to join together as many obtuse segments as possible without causing collisions.
  • Rerouting path between pair of line corners with a 2-segment "\__" line and iteratively repeating the procedure as long as the total cost of the line keeps decreasing.
  • "Smart Pads" - that is, rerouting pad/via exits to make them look nice (SMART_PADS).

Definition at line 94 of file pns_optimizer.h.

Member Typedef Documentation

◆ BREAKOUT_LIST

typedef std::vector<SHAPE_LINE_CHAIN> PNS::OPTIMIZER::BREAKOUT_LIST
private

Definition at line 162 of file pns_optimizer.h.

Member Enumeration Documentation

◆ OptimizationEffort

Enumerator
MERGE_SEGMENTS 

Reduce corner cost iteratively.

SMART_PADS 

Reroute pad exits.

MERGE_OBTUSE 

Reduce corner cost by merging obtuse segments.

FANOUT_CLEANUP 

Simplify pad-pad and pad-via connections if possible.

KEEP_TOPOLOGY 
PRESERVE_VERTEX 
RESTRICT_VERTEX_RANGE 
MERGE_COLINEAR 

Merge co-linear segments.

RESTRICT_AREA 
LIMIT_CORNER_COUNT 

Do not attempt to optimize if the resulting line's corner count is outside the predefined range.

Definition at line 97 of file pns_optimizer.h.

98 {
99 MERGE_SEGMENTS = 0x01,
100 SMART_PADS = 0x02,
101 MERGE_OBTUSE = 0x04,
102 FANOUT_CLEANUP = 0x08,
103 KEEP_TOPOLOGY = 0x10,
104 PRESERVE_VERTEX = 0x20,
106 MERGE_COLINEAR = 0x80,
107 RESTRICT_AREA = 0x100,
108 LIMIT_CORNER_COUNT = 0x200
110 };
@ 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.
Definition: pns_optimizer.h:99
@ MERGE_COLINEAR
Merge co-linear segments.
@ MERGE_OBTUSE
Reduce corner cost by merging obtuse segments.

Constructor & Destructor Documentation

◆ OPTIMIZER()

PNS::OPTIMIZER::OPTIMIZER ( NODE aWorld)

Definition at line 112 of file pns_optimizer.cpp.

112 :
113 m_world( aWorld ),
117{
118}
bool m_restrictAreaIsStrict

◆ ~OPTIMIZER()

PNS::OPTIMIZER::~OPTIMIZER ( )

A quick shortcut to optimize a line without creating and setting up an optimizer.

Definition at line 121 of file pns_optimizer.cpp.

122{
123}

Member Function Documentation

◆ AddConstraint()

void PNS::OPTIMIZER::AddConstraint ( OPT_CONSTRAINT aConstraint)

Definition at line 429 of file pns_optimizer.cpp.

430{
431 m_constraints.push_back( aConstraint );
432}
std::vector< OPT_CONSTRAINT * > m_constraints

References m_constraints.

Referenced by Optimize().

◆ cacheAdd()

void PNS::OPTIMIZER::cacheAdd ( ITEM aItem,
bool  aIsStatic = false 
)
private

Definition at line 154 of file pns_optimizer.cpp.

155{
156 if( m_cacheTags.find( aItem ) != m_cacheTags.end() )
157 return;
158
159 m_cache.Add( aItem );
160 m_cacheTags[aItem].m_hits = 1;
161 m_cacheTags[aItem].m_isStatic = aIsStatic;
162}
std::unordered_map< ITEM *, CACHED_ITEM > m_cacheTags
SHAPE_INDEX_LIST< ITEM * > m_cache

References m_cache, and m_cacheTags.

◆ CacheRemove()

void PNS::OPTIMIZER::CacheRemove ( ITEM aItem)

Definition at line 184 of file pns_optimizer.cpp.

185{
186 if( aItem->Kind() == ITEM::LINE_T )
187 removeCachedSegments( static_cast<LINE*>( aItem ) );
188}
@ LINE_T
Definition: pns_item.h:64
void removeCachedSegments(LINE *aLine, int aStartVertex=0, int aEndVertex=-1)

References PNS::ITEM::Kind(), PNS::ITEM::LINE_T, and removeCachedSegments().

◆ checkColliding() [1/2]

bool PNS::OPTIMIZER::checkColliding ( ITEM aItem,
bool  aUpdateCache = true 
)
private

Definition at line 412 of file pns_optimizer.cpp.

413{
414 CACHE_VISITOR v( aItem, m_world, m_collisionKindMask );
415
416 return static_cast<bool>( m_world->CheckColliding( aItem ) );
417}
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.
Definition: pns_node.cpp:472

References PNS::NODE::CheckColliding(), m_collisionKindMask, and m_world.

Referenced by checkColliding(), mergeObtuse(), mergeStep(), and smartPadsSingle().

◆ checkColliding() [2/2]

bool PNS::OPTIMIZER::checkColliding ( LINE aLine,
const SHAPE_LINE_CHAIN aOptPath 
)
private

Definition at line 449 of file pns_optimizer.cpp.

450{
451 LINE tmp( *aLine, aOptPath );
452
453 return checkColliding( &tmp );
454}
bool checkColliding(ITEM *aItem, bool aUpdateCache=true)

References checkColliding().

◆ checkConstraints()

bool PNS::OPTIMIZER::checkConstraints ( int  aVertex1,
int  aVertex2,
LINE aOriginLine,
const SHAPE_LINE_CHAIN aCurrentPath,
const SHAPE_LINE_CHAIN aReplacement 
)
private

Definition at line 435 of file pns_optimizer.cpp.

438{
439 for( OPT_CONSTRAINT* c : m_constraints )
440 {
441 if( !c->Check( aVertex1, aVertex2, aOriginLine, aCurrentPath, aReplacement ) )
442 return false;
443 }
444
445 return true;
446}

References m_constraints.

Referenced by mergeStep().

◆ circleBreakouts()

OPTIMIZER::BREAKOUT_LIST PNS::OPTIMIZER::circleBreakouts ( int  aWidth,
const SHAPE aShape,
bool  aPermitDiagonal 
) const
private

Definition at line 757 of file pns_optimizer.cpp.

759{
760 BREAKOUT_LIST breakouts;
761
763 {
764 const SHAPE_CIRCLE* cir = static_cast<const SHAPE_CIRCLE*>( aShape );
766 VECTOR2I p0 = cir->GetCenter();
767 VECTOR2I v0( cir->GetRadius() * M_SQRT2, 0 );
768
769 RotatePoint( v0, -angle );
770
771 l.Append( p0 );
772 l.Append( p0 + v0 );
773 breakouts.push_back( l );
774 }
775
776 return breakouts;
777}
std::vector< SHAPE_LINE_CHAIN > BREAKOUT_LIST
int GetRadius() const
Definition: shape_circle.h:108
const VECTOR2I GetCenter() const
Definition: shape_circle.h:113
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
static constexpr EDA_ANGLE & ANGLE_360
Definition: eda_angle.h:418
static constexpr EDA_ANGLE & ANGLE_45
Definition: eda_angle.h:413
static constexpr EDA_ANGLE & ANGLE_0
Definition: eda_angle.h:412
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
void RotatePoint(int *pX, int *pY, const EDA_ANGLE &aAngle)
Definition: trigo.cpp:183

References PNS::angle(), ANGLE_0, ANGLE_360, ANGLE_45, SHAPE_LINE_CHAIN::Append(), SHAPE_CIRCLE::GetCenter(), SHAPE_CIRCLE::GetRadius(), and RotatePoint().

Referenced by computeBreakouts().

◆ ClearCache()

void PNS::OPTIMIZER::ClearCache ( bool  aStaticOnly = false)

Definition at line 191 of file pns_optimizer.cpp.

192{
193 if( !aStaticOnly )
194 {
195 m_cacheTags.clear();
196 m_cache.Clear();
197 return;
198 }
199
200 for( auto i = m_cacheTags.begin(); i!= m_cacheTags.end(); ++i )
201 {
202 if( i->second.m_isStatic )
203 {
204 m_cache.Remove( i->first );
205 m_cacheTags.erase( i->first );
206 }
207 }
208}

References m_cache, and m_cacheTags.

◆ ClearConstraints()

void PNS::OPTIMIZER::ClearConstraints ( )

Definition at line 420 of file pns_optimizer.cpp.

421{
422 for( OPT_CONSTRAINT* c : m_constraints )
423 delete c;
424
425 m_constraints.clear();
426}

References m_constraints.

◆ computeBreakouts()

OPTIMIZER::BREAKOUT_LIST PNS::OPTIMIZER::computeBreakouts ( int  aWidth,
const ITEM aItem,
bool  aPermitDiagonal 
) const
private

Definition at line 883 of file pns_optimizer.cpp.

885{
886 switch( aItem->Kind() )
887 {
888 case ITEM::VIA_T:
889 {
890 const VIA* via = static_cast<const VIA*>( aItem );
891 return circleBreakouts( aWidth, via->Shape(), aPermitDiagonal );
892 }
893
894 case ITEM::SOLID_T:
895 {
896 const SHAPE* shape = aItem->Shape();
897
898 switch( shape->Type() )
899 {
900 case SH_RECT:
901 return rectBreakouts( aWidth, shape, aPermitDiagonal );
902
903 case SH_SEGMENT:
904 {
905 const SHAPE_SEGMENT* seg = static_cast<const SHAPE_SEGMENT*> (shape);
906 const SHAPE_RECT rect = ApproximateSegmentAsRect ( *seg );
907 return rectBreakouts( aWidth, &rect, aPermitDiagonal );
908 }
909
910 case SH_CIRCLE:
911 return circleBreakouts( aWidth, shape, aPermitDiagonal );
912
913 case SH_SIMPLE:
914 return customBreakouts( aWidth, aItem, aPermitDiagonal );
915
916 default:
917 break;
918 }
919
920 break;
921 }
922
923 default:
924 break;
925 }
926
927 return BREAKOUT_LIST();
928}
@ SOLID_T
Definition: pns_item.h:63
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
SHAPE_TYPE Type() const
Return the type of the shape.
Definition: shape.h:95
An abstract shape on 2D plane.
Definition: shape.h:123
SHAPE_RECT ApproximateSegmentAsRect(const SHAPE_SEGMENT &aSeg)
Definition: pns_utils.cpp:345
@ VIA
Normal via.
Definition: router_tool.cpp:89
@ SH_RECT
axis-aligned rectangle
Definition: shape.h:44
@ SH_CIRCLE
circle
Definition: shape.h:47
@ SH_SIMPLE
simple polygon
Definition: shape.h:48
@ SH_SEGMENT
line segment
Definition: shape.h:45

References PNS::ApproximateSegmentAsRect(), circleBreakouts(), customBreakouts(), PNS::ITEM::Kind(), rectBreakouts(), SH_CIRCLE, SH_RECT, SH_SEGMENT, SH_SIMPLE, PNS::ITEM::Shape(), PNS::ITEM::SOLID_T, SHAPE_BASE::Type(), via, and PNS::ITEM::VIA_T.

Referenced by smartPadsSingle().

◆ customBreakouts()

OPTIMIZER::BREAKOUT_LIST PNS::OPTIMIZER::customBreakouts ( int  aWidth,
const ITEM aItem,
bool  aPermitDiagonal 
) const
private

Definition at line 780 of file pns_optimizer.cpp.

782{
783 BREAKOUT_LIST breakouts;
784 const SHAPE_SIMPLE* convex = static_cast<const SHAPE_SIMPLE*>( aItem->Shape() );
785
786 BOX2I bbox = convex->BBox( 0 );
787 VECTOR2I p0 = static_cast<const SOLID*>( aItem )->Pos();
788 // must be large enough to guarantee intersecting the convex polygon
789 int length = std::max( bbox.GetWidth(), bbox.GetHeight() ) / 2 + 5;
790 EDA_ANGLE increment = ( aPermitDiagonal ? ANGLE_45 : ANGLE_90 );
791
792 for( EDA_ANGLE angle = ANGLE_0; angle < ANGLE_360; angle += increment )
793 {
795 VECTOR2I v0( p0 + VECTOR2I( length, 0 ) );
796 RotatePoint( v0, p0, -angle );
797
799 int n = convex->Vertices().Intersect( SEG( p0, v0 ), intersections );
800
801 // if n == 1 intersected a segment
802 // if n == 2 intersected the common point of 2 segments
803 // n == 0 can not happen I think, but...
804 if( n > 0 )
805 {
806 l.Append( p0 );
807
808 // for a breakout distance relative to the distance between
809 // center and polygon edge
810 //l.Append( intersections[0].p + (v0 - p0).Resize( (intersections[0].p - p0).EuclideanNorm() * 0.4 ) );
811
812 // for an absolute breakout distance, e.g. 0.1 mm
813 //l.Append( intersections[0].p + (v0 - p0).Resize( 100000 ) );
814
815 // for the breakout right on the polygon edge
816 l.Append( intersections[0].p );
817
818 breakouts.push_back( l );
819 }
820 }
821
822 return breakouts;
823}
coord_type GetHeight() const
Definition: box2.h:188
coord_type GetWidth() const
Definition: box2.h:187
Definition: seg.h:42
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Find all intersection points between our line chain and the segment aSeg.
std::vector< INTERSECTION > INTERSECTIONS
Represent a simple polygon consisting of a zero-thickness closed chain of connected line segments.
Definition: shape_simple.h:42
const SHAPE_LINE_CHAIN & Vertices() const
Return the list of vertices defining this simple polygon.
Definition: shape_simple.h:124
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
Definition: shape_simple.h:78
static constexpr EDA_ANGLE & ANGLE_90
Definition: eda_angle.h:414
VECTOR2< int > VECTOR2I
Definition: vector2d.h:618

References PNS::angle(), ANGLE_0, ANGLE_360, ANGLE_45, ANGLE_90, SHAPE_LINE_CHAIN::Append(), SHAPE_SIMPLE::BBox(), BOX2< Vec >::GetHeight(), BOX2< Vec >::GetWidth(), SHAPE_LINE_CHAIN::Intersect(), RotatePoint(), PNS::ITEM::Shape(), and SHAPE_SIMPLE::Vertices().

Referenced by computeBreakouts().

◆ fanoutCleanup()

bool PNS::OPTIMIZER::fanoutCleanup ( LINE aLine)
private

Definition at line 1110 of file pns_optimizer.cpp.

1111{
1112 if( aLine->PointCount() < 3 )
1113 return false;
1114
1115 VECTOR2I p_start = aLine->CPoint( 0 ), p_end = aLine->CPoint( -1 );
1116
1117 ITEM* startPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_start );
1118 ITEM* endPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_end );
1119
1120 int thr = aLine->Width() * 10;
1121 int len = aLine->CLine().Length();
1122
1123 if( !startPad )
1124 return false;
1125
1126 bool startMatch = startPad->OfKind( ITEM::VIA_T | ITEM::SOLID_T );
1127 bool endMatch = false;
1128
1129 if(endPad)
1130 {
1131 endMatch = endPad->OfKind( ITEM::VIA_T | ITEM::SOLID_T );
1132 }
1133 else
1134 {
1135 endMatch = aLine->EndsWithVia();
1136 }
1137
1138 if( startMatch && endMatch && len < thr )
1139 {
1140 for( int i = 0; i < 2; i++ )
1141 {
1142 SHAPE_LINE_CHAIN l2 = DIRECTION_45().BuildInitialTrace( p_start, p_end, i );
1143 LINE repl;
1144 repl = LINE( *aLine, l2 );
1145
1146 if( !m_world->CheckColliding( &repl ) )
1147 {
1148 aLine->SetShape( repl.CLine() );
1149 return true;
1150 }
1151 }
1152 }
1153
1154 return false;
1155}
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:37
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.
ITEM * findPadOrVia(int aLayer, int aNet, const VECTOR2I &aP) const

References DIRECTION_45::BuildInitialTrace(), PNS::NODE::CheckColliding(), PNS::LINE::CLine(), PNS::LINE::CPoint(), PNS::LINE::EndsWithVia(), findPadOrVia(), PNS::ITEM::Layer(), SHAPE_LINE_CHAIN::Length(), m_world, PNS::ITEM::Net(), PNS::ITEM::OfKind(), PNS::LINE::PointCount(), PNS::LINE::SetShape(), PNS::ITEM::SOLID_T, PNS::ITEM::VIA_T, and PNS::LINE::Width().

Referenced by Optimize().

◆ findPadOrVia()

ITEM * PNS::OPTIMIZER::findPadOrVia ( int  aLayer,
int  aNet,
const VECTOR2I aP 
) const
private

Definition at line 931 of file pns_optimizer.cpp.

932{
933 JOINT* jt = m_world->FindJoint( aP, aLayer, aNet );
934
935 if( !jt )
936 return nullptr;
937
938 for( ITEM* item : jt->LinkList() )
939 {
940 if( item->OfKind( ITEM::VIA_T | ITEM::SOLID_T ) )
941 return item;
942 }
943
944 return nullptr;
945}
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
Definition: pns_node.cpp:1197

References PNS::NODE::FindJoint(), PNS::JOINT::LinkList(), m_world, PNS::ITEM::SOLID_T, and PNS::ITEM::VIA_T.

Referenced by fanoutCleanup(), and runSmartPads().

◆ mergeColinear()

bool PNS::OPTIMIZER::mergeColinear ( LINE aLine)
private

Definition at line 578 of file pns_optimizer.cpp.

579{
580 SHAPE_LINE_CHAIN& line = aLine->Line();
581
582 int nSegs = line.SegmentCount();
583
584 for( int segIdx = 0; segIdx < line.SegmentCount() - 1; ++segIdx )
585 {
586 SEG s1 = line.CSegment( segIdx );
587 SEG s2 = line.CSegment( segIdx + 1 );
588
589 // Skip zero-length segs caused by abutting arcs
590 if( s1.SquaredLength() == 0 || s2.SquaredLength() == 0 )
591 continue;
592
593 if( s1.Collinear( s2 ) && !line.IsPtOnArc( segIdx + 1 ) )
594 {
595 line.Remove( segIdx + 1 );
596 }
597 }
598
599 return line.SegmentCount() < nSegs;
600}
bool Collinear(const SEG &aSeg) const
Check if segment aSeg lies on the same line as (this).
Definition: seg.h:269
ecoord SquaredLength() const
Definition: seg.h:331
bool IsPtOnArc(size_t aPtIndex) const
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.

References SEG::Collinear(), SHAPE_LINE_CHAIN::CSegment(), SHAPE_LINE_CHAIN::IsPtOnArc(), PNS::LINE::Line(), SHAPE_LINE_CHAIN::Remove(), SHAPE_LINE_CHAIN::SegmentCount(), and SEG::SquaredLength().

Referenced by Optimize().

◆ mergeDpSegments()

bool PNS::OPTIMIZER::mergeDpSegments ( DIFF_PAIR aPair)
private

Definition at line 1332 of file pns_optimizer.cpp.

1333{
1334 int step_p = aPair->CP().SegmentCount() - 2;
1335 int step_n = aPair->CN().SegmentCount() - 2;
1336
1337 while( 1 )
1338 {
1339 int n_segs_p = aPair->CP().SegmentCount();
1340 int n_segs_n = aPair->CN().SegmentCount();
1341
1342 int max_step_p = n_segs_p - 2;
1343 int max_step_n = n_segs_n - 2;
1344
1345 if( step_p > max_step_p )
1346 step_p = max_step_p;
1347
1348 if( step_n > max_step_n )
1349 step_n = max_step_n;
1350
1351 if( step_p < 1 && step_n < 1 )
1352 break;
1353
1354 bool found_anything_p = false;
1355 bool found_anything_n = false;
1356
1357 if( step_p > 1 )
1358 found_anything_p = mergeDpStep( aPair, true, step_p );
1359
1360 if( step_n > 1 )
1361 found_anything_n = mergeDpStep( aPair, false, step_n );
1362
1363 if( !found_anything_n && !found_anything_p )
1364 {
1365 step_n--;
1366 step_p--;
1367 }
1368 }
1369 return true;
1370}
bool mergeDpStep(DIFF_PAIR *aPair, bool aTryP, int step)

References PNS::DIFF_PAIR::CN(), PNS::DIFF_PAIR::CP(), mergeDpStep(), and SHAPE_LINE_CHAIN::SegmentCount().

Referenced by Optimize().

◆ mergeDpStep()

bool PNS::OPTIMIZER::mergeDpStep ( DIFF_PAIR aPair,
bool  aTryP,
int  step 
)
private

Definition at line 1269 of file pns_optimizer.cpp.

1270{
1271 int n = 1;
1272
1273 SHAPE_LINE_CHAIN currentPath = aTryP ? aPair->CP() : aPair->CN();
1274 SHAPE_LINE_CHAIN coupledPath = aTryP ? aPair->CN() : aPair->CP();
1275
1276 int n_segs = currentPath.SegmentCount() - 1;
1277
1278 int64_t clenPre = aPair->CoupledLength( currentPath, coupledPath );
1279 int64_t budget = clenPre / 10; // fixme: come up with something more intelligent here...
1280
1281 while( n < n_segs - step )
1282 {
1283 const SEG s1 = currentPath.CSegment( n );
1284 const SEG s2 = currentPath.CSegment( n + step );
1285
1286 DIRECTION_45 dir1( s1 );
1287 DIRECTION_45 dir2( s2 );
1288
1289 if( dir1.IsObtuse( dir2 ) )
1290 {
1292 dir1.IsDiagonal() );
1293 SHAPE_LINE_CHAIN newRef;
1294 SHAPE_LINE_CHAIN newCoup;
1295 int64_t deltaCoupled = -1, deltaUni = -1;
1296
1297 newRef = currentPath;
1298 newRef.Replace( s1.Index(), s2.Index(), bypass );
1299
1300 deltaUni = aPair->CoupledLength ( newRef, coupledPath ) - clenPre + budget;
1301
1302 if( coupledBypass( m_world, aPair, aTryP, newRef, bypass, coupledPath, newCoup ) )
1303 {
1304 deltaCoupled = aPair->CoupledLength( newRef, newCoup ) - clenPre + budget;
1305
1306 if( deltaCoupled >= 0 )
1307 {
1308 newRef.Simplify();
1309 newCoup.Simplify();
1310
1311 aPair->SetShape( newRef, newCoup, !aTryP );
1312 return true;
1313 }
1314 }
1315 else if( deltaUni >= 0 && verifyDpBypass( m_world, aPair, aTryP, newRef, coupledPath ) )
1316 {
1317 newRef.Simplify();
1318 coupledPath.Simplify();
1319
1320 aPair->SetShape( newRef, coupledPath, !aTryP );
1321 return true;
1322 }
1323 }
1324
1325 n++;
1326 }
1327
1328 return false;
1329}
VECTOR2I A
Definition: seg.h:49
VECTOR2I B
Definition: seg.h:50
int Index() const
Return the index of this segment in its parent shape (applicable only to non-local segments).
Definition: seg.h:344
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Replace points with indices in range [start_index, end_index] with a single point aP.
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)
bool verifyDpBypass(NODE *aNode, DIFF_PAIR *aPair, bool aRefIsP, const SHAPE_LINE_CHAIN &aNewRef, const SHAPE_LINE_CHAIN &aNewCoupled)

References SEG::A, SEG::B, DIRECTION_45::BuildInitialTrace(), PNS::DIFF_PAIR::CN(), PNS::coupledBypass(), PNS::DIFF_PAIR::CoupledLength(), PNS::DIFF_PAIR::CP(), SHAPE_LINE_CHAIN::CSegment(), SEG::Index(), DIRECTION_45::IsDiagonal(), DIRECTION_45::IsObtuse(), m_world, SHAPE_LINE_CHAIN::Replace(), SHAPE_LINE_CHAIN::SegmentCount(), PNS::DIFF_PAIR::SetShape(), SHAPE_LINE_CHAIN::Simplify(), and PNS::verifyDpBypass().

Referenced by mergeDpSegments().

◆ mergeFull()

bool PNS::OPTIMIZER::mergeFull ( LINE aLine)
private

Definition at line 538 of file pns_optimizer.cpp.

539{
540 SHAPE_LINE_CHAIN& line = aLine->Line();
541 int step = line.SegmentCount() - 1;
542
543 int segs_pre = line.SegmentCount();
544
545 line.Simplify();
546
547 if( step < 0 )
548 return false;
549
550 SHAPE_LINE_CHAIN current_path( line );
551
552 while( 1 )
553 {
554 int n_segs = current_path.SegmentCount();
555 int max_step = n_segs - 2;
556
557 if( step > max_step )
558 step = max_step;
559
560 if( step < 1 )
561 break;
562
563 bool found_anything = mergeStep( aLine, current_path, step );
564
565 if( !found_anything )
566 step--;
567
568 if( !step )
569 break;
570 }
571
572 aLine->SetShape( current_path );
573
574 return current_path.SegmentCount() < segs_pre;
575}
bool mergeStep(LINE *aLine, SHAPE_LINE_CHAIN &aCurrentLine, int step)

References PNS::LINE::Line(), mergeStep(), SHAPE_LINE_CHAIN::SegmentCount(), PNS::LINE::SetShape(), and SHAPE_LINE_CHAIN::Simplify().

Referenced by Optimize().

◆ mergeObtuse()

bool PNS::OPTIMIZER::mergeObtuse ( LINE aLine)
private

Definition at line 457 of file pns_optimizer.cpp.

458{
459 SHAPE_LINE_CHAIN& line = aLine->Line();
460
461 int step = line.PointCount() - 3;
462 int iter = 0;
463 int segs_pre = line.SegmentCount();
464
465 if( step < 0 )
466 return false;
467
468 SHAPE_LINE_CHAIN current_path( line );
469
470 while( 1 )
471 {
472 iter++;
473 int n_segs = current_path.SegmentCount();
474 int max_step = n_segs - 2;
475
476 if( step > max_step )
477 step = max_step;
478
479 if( step < 2 )
480 {
481 line = current_path;
482 return current_path.SegmentCount() < segs_pre;
483 }
484
485 bool found_anything = false;
486
487 for( int n = 0; n < n_segs - step; n++ )
488 {
489 const SEG s1 = current_path.CSegment( n );
490 const SEG s2 = current_path.CSegment( n + step );
491 SEG s1opt, s2opt;
492
493 if( DIRECTION_45( s1 ).IsObtuse( DIRECTION_45( s2 ) ) )
494 {
495 VECTOR2I ip = *s1.IntersectLines( s2 );
496
497 s1opt = SEG( s1.A, ip );
498 s2opt = SEG( ip, s2.B );
499
500 if( DIRECTION_45( s1opt ).IsObtuse( DIRECTION_45( s2opt ) ) )
501 {
502 SHAPE_LINE_CHAIN opt_path;
503 opt_path.Append( s1opt.A );
504 opt_path.Append( s1opt.B );
505 opt_path.Append( s2opt.B );
506
507 LINE opt_track( *aLine, opt_path );
508
509 if( !checkColliding( &opt_track ) )
510 {
511 current_path.Replace( s1.Index() + 1, s2.Index(), ip );
512
513 // removeCachedSegments(aLine, s1.Index(), s2.Index());
514 n_segs = current_path.SegmentCount();
515 found_anything = true;
516 break;
517 }
518 }
519 }
520 }
521
522 if( !found_anything )
523 {
524 if( step <= 2 )
525 {
526 line = current_path;
527 return line.SegmentCount() < segs_pre;
528 }
529
530 step--;
531 }
532 }
533
534 return line.SegmentCount() < segs_pre;
535}
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
Definition: seg.h:210
int PointCount() const
Return the number of points (vertices) in this line chain.

References SEG::A, SHAPE_LINE_CHAIN::Append(), SEG::B, checkColliding(), SHAPE_LINE_CHAIN::CSegment(), SEG::Index(), SEG::IntersectLines(), PNS::LINE::Line(), SHAPE_LINE_CHAIN::PointCount(), SHAPE_LINE_CHAIN::Replace(), and SHAPE_LINE_CHAIN::SegmentCount().

Referenced by Optimize().

◆ mergeStep()

bool PNS::OPTIMIZER::mergeStep ( LINE aLine,
SHAPE_LINE_CHAIN aCurrentLine,
int  step 
)
private

Definition at line 689 of file pns_optimizer.cpp.

690{
691 int n_segs = aCurrentPath.SegmentCount();
692
693 int cost_orig = COST_ESTIMATOR::CornerCost( aCurrentPath );
694
695 if( aLine->SegmentCount() < 2 )
696 return false;
697
698 DIRECTION_45 orig_start( aLine->CSegment( 0 ) );
699 DIRECTION_45 orig_end( aLine->CSegment( -1 ) );
700
701
702 for( int n = 0; n < n_segs - step; n++ )
703 {
704 // Do not attempt to merge false segments that are part of an arc
705 if( aCurrentPath.IsArcSegment( n )
706 || aCurrentPath.IsArcSegment( static_cast<std::size_t>( n ) + step ) )
707 {
708 continue;
709 }
710
711 const SEG s1 = aCurrentPath.CSegment( n );
712 const SEG s2 = aCurrentPath.CSegment( n + step );
713
715 SHAPE_LINE_CHAIN* picked = nullptr;
716 int cost[2];
717
718 for( int i = 0; i < 2; i++ )
719 {
720 SHAPE_LINE_CHAIN bypass = DIRECTION_45().BuildInitialTrace( s1.A, s2.B, i );
721 cost[i] = INT_MAX;
722
723 bool ok = false;
724
725 if( !checkColliding( aLine, bypass ) )
726 {
727 //printf("Chk-constraints: %d %d\n", n, n+step+1 );
728 ok = checkConstraints ( n, n + step + 1, aLine, aCurrentPath, bypass );
729 }
730
731 if( ok )
732 {
733 path[i] = aCurrentPath;
734 path[i].Replace( s1.Index(), s2.Index(), bypass );
735 path[i].Simplify();
736 cost[i] = COST_ESTIMATOR::CornerCost( path[i] );
737 }
738 }
739
740 if( cost[0] < cost_orig && cost[0] < cost[1] )
741 picked = &path[0];
742 else if( cost[1] < cost_orig )
743 picked = &path[1];
744
745 if( picked )
746 {
747 n_segs = aCurrentPath.SegmentCount();
748 aCurrentPath = *picked;
749 return true;
750 }
751 }
752
753 return false;
754}
static int CornerCost(const SEG &aA, const SEG &aB)
bool checkConstraints(int aVertex1, int aVertex2, LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement)

References SEG::A, SEG::B, DIRECTION_45::BuildInitialTrace(), checkColliding(), checkConstraints(), PNS::COST_ESTIMATOR::CornerCost(), PNS::LINE::CSegment(), SHAPE_LINE_CHAIN::CSegment(), SEG::Index(), SHAPE_LINE_CHAIN::IsArcSegment(), path, SHAPE_LINE_CHAIN::SegmentCount(), and PNS::LINE::SegmentCount().

Referenced by mergeFull().

◆ Optimize() [1/3]

bool PNS::OPTIMIZER::Optimize ( DIFF_PAIR aPair)

Definition at line 1373 of file pns_optimizer.cpp.

1374{
1375 return mergeDpSegments( aPair );
1376}
bool mergeDpSegments(DIFF_PAIR *aPair)

References mergeDpSegments().

◆ Optimize() [2/3]

bool PNS::OPTIMIZER::Optimize ( LINE aLine,
int  aEffortLevel,
NODE aWorld,
const VECTOR2I aV = VECTOR2I(0, 0) 
)
static

Definition at line 1096 of file pns_optimizer.cpp.

1097{
1098 OPTIMIZER opt( aWorld );
1099
1100 opt.SetEffortLevel( aEffortLevel );
1101 opt.SetCollisionMask( -1 );
1102
1103 if( aEffortLevel & OPTIMIZER::PRESERVE_VERTEX )
1104 opt.SetPreserveVertex( aV );
1105
1106 return opt.Optimize( aLine );
1107}
OPTIMIZER(NODE *aWorld)

References Optimize(), PRESERVE_VERTEX, SetCollisionMask(), SetEffortLevel(), and SetPreserveVertex().

Referenced by Optimize(), PNS::DRAGGER::optimizeAndUpdateDraggedLine(), PNS::LINE_PLACER::optimizeTailHeadTransition(), PNS::LINE_PLACER::rhShoveOnly(), PNS::LINE_PLACER::rhWalkBase(), PNS::LINE_PLACER::rhWalkOnly(), PNS::WALKAROUND::Route(), PNS::SHOVE::runOptimizer(), PNS::LINE_PLACER::simplifyNewLine(), and PNS::DIFF_PAIR_PLACER::tryWalkDp().

◆ Optimize() [3/3]

bool PNS::OPTIMIZER::Optimize ( LINE aLine,
LINE aResult = nullptr,
LINE aRoot = nullptr 
)

Definition at line 603 of file pns_optimizer.cpp.

604{
605 DEBUG_DECORATOR* dbg = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
606
607 if( aRoot )
608 {
609 PNS_DBG( dbg, AddItem, aRoot, BLUE, 100000, wxT( "root-line" ) );
610 }
611
612
613 if( !aResult )
614 {
615 aResult = aLine;
616 }
617 else
618 {
619 *aResult = *aLine;
620 aResult->ClearLinks();
621 }
622
623 bool hasArcs = aLine->ArcCount();
624 bool rv = false;
625
626 if( (m_effortLevel & LIMIT_CORNER_COUNT) && aRoot )
627 {
628 const int angleMask = DIRECTION_45::ANG_OBTUSE;
629 int rootObtuseCorners = aRoot->CountCorners( angleMask );
630 auto c = new CORNER_COUNT_LIMIT_CONSTRAINT( m_world, rootObtuseCorners,
631 aLine->SegmentCount(), angleMask );
632 PNS_DBG( dbg, Message,
633 wxString::Format( "opt limit-corner-count root %d maxc %d mask %x",
634 rootObtuseCorners, aLine->SegmentCount(), angleMask ) );
635
636 AddConstraint( c );
637 }
638
640 {
641 auto c = new PRESERVE_VERTEX_CONSTRAINT( m_world, m_preservedVertex );
642 AddConstraint( c );
643 }
644
646 {
647 auto c = new RESTRICT_VERTEX_RANGE_CONSTRAINT( m_world, m_restrictedVertexRange.first,
649 AddConstraint( c );
650 }
651
653 {
654 auto c = new AREA_CONSTRAINT( m_world, m_restrictArea, m_restrictAreaIsStrict );
656 PNS_DBG( dbg, AddShape, &r, YELLOW, 0, wxT( "area-constraint" ) );
657 AddConstraint( c );
658 }
659
661 {
662 auto c = new KEEP_TOPOLOGY_CONSTRAINT( m_world );
663 AddConstraint( c );
664 }
665
666 // TODO: Fix for arcs
667 if( !hasArcs && m_effortLevel & MERGE_SEGMENTS )
668 rv |= mergeFull( aResult );
669
670 // TODO: Fix for arcs
671 if( !hasArcs && m_effortLevel & MERGE_OBTUSE )
672 rv |= mergeObtuse( aResult );
673
675 rv |= mergeColinear( aResult );
676
677 // TODO: Fix for arcs
678 if( !hasArcs && m_effortLevel & SMART_PADS )
679 rv |= runSmartPads( aResult );
680
681 // TODO: Fix for arcs
682 if( !hasArcs && m_effortLevel & FANOUT_CLEANUP )
683 rv |= fanoutCleanup( aResult );
684
685 return rv;
686}
std::pair< int, int > m_restrictedVertexRange
bool mergeColinear(LINE *aLine)
bool fanoutCleanup(LINE *aLine)
bool mergeFull(LINE *aLine)
void AddConstraint(OPT_CONSTRAINT *aConstraint)
bool mergeObtuse(LINE *aLine)
bool runSmartPads(LINE *aLine)
VECTOR2I m_preservedVertex
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:214
static ROUTER * GetInstance()
Definition: pns_router.cpp:78
@ BLUE
Definition: color4d.h:56
@ YELLOW
Definition: color4d.h:67
#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.
Definition: ptree.cpp:200

References AddConstraint(), DIRECTION_45::ANG_OBTUSE, PNS::LINE::ArcCount(), BLUE, PNS::LINK_HOLDER::ClearLinks(), PNS::LINE::CountCorners(), FANOUT_CLEANUP, fanoutCleanup(), Format(), PNS::ROUTER_IFACE::GetDebugDecorator(), PNS::ROUTER::GetInstance(), PNS::ROUTER::GetInterface(), KEEP_TOPOLOGY, LIMIT_CORNER_COUNT, m_effortLevel, m_preservedVertex, m_restrictArea, m_restrictAreaIsStrict, m_restrictedVertexRange, m_world, MERGE_COLINEAR, MERGE_OBTUSE, MERGE_SEGMENTS, mergeColinear(), mergeFull(), mergeObtuse(), PNS_DBG, PRESERVE_VERTEX, RESTRICT_AREA, RESTRICT_VERTEX_RANGE, runSmartPads(), PNS::LINE::SegmentCount(), SMART_PADS, and YELLOW.

◆ rectBreakouts()

OPTIMIZER::BREAKOUT_LIST PNS::OPTIMIZER::rectBreakouts ( int  aWidth,
const SHAPE aShape,
bool  aPermitDiagonal 
) const
private

Definition at line 826 of file pns_optimizer.cpp.

828{
829 const SHAPE_RECT* rect = static_cast<const SHAPE_RECT*>(aShape);
830 VECTOR2I s = rect->GetSize();
831 VECTOR2I c = rect->GetPosition() + VECTOR2I( s.x / 2, s.y / 2 );
832
833 BREAKOUT_LIST breakouts;
834 breakouts.reserve( 12 );
835
836 VECTOR2I d_offset;
837
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;
840
841 VECTOR2I d_vert = VECTOR2I( 0, s.y / 2 + aWidth );
842 VECTOR2I d_horiz = VECTOR2I( s.x / 2 + aWidth, 0 );
843
844 breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c + d_horiz } ) );
845 breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c - d_horiz } ) );
846 breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c + d_vert } ) );
847 breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c - d_vert } ) );
848
849 if( aPermitDiagonal )
850 {
851 int l = aWidth + std::min( s.x, s.y ) / 2;
852 VECTOR2I d_diag;
853
854 if( s.x >= s.y )
855 {
856 breakouts.emplace_back(
857 SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( l, l ) } ) );
858 breakouts.emplace_back(
859 SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset - VECTOR2I( -l, l ) } ) );
860 breakouts.emplace_back(
861 SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset + VECTOR2I( -l, l ) } ) );
862 breakouts.emplace_back(
863 SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( l, l ) } ) );
864 }
865 else
866 {
867 // fixme: this could be done more efficiently
868 breakouts.emplace_back(
869 SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( l, l ) } ) );
870 breakouts.emplace_back(
871 SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( -l, l ) } ) );
872 breakouts.emplace_back(
873 SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( -l, l ) } ) );
874 breakouts.emplace_back(
875 SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( l, l ) } ) );
876 }
877 }
878
879 return breakouts;
880}
const VECTOR2I & GetPosition() const
Definition: shape_rect.h:127
const VECTOR2I GetSize() const
Definition: shape_rect.h:135

References SHAPE_RECT::GetPosition(), SHAPE_RECT::GetSize(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by computeBreakouts().

◆ removeCachedSegments()

void PNS::OPTIMIZER::removeCachedSegments ( LINE aLine,
int  aStartVertex = 0,
int  aEndVertex = -1 
)
private

Definition at line 165 of file pns_optimizer.cpp.

166{
167 if( !aLine->IsLinked() )
168 return;
169
170 auto links = aLine->Links();
171
172 if( aEndVertex < 0 )
173 aEndVertex += aLine->PointCount();
174
175 for( int i = aStartVertex; i < aEndVertex - 1; i++ )
176 {
177 LINKED_ITEM* s = links[i];
178 m_cacheTags.erase( s );
179 m_cache.Remove( s );
180 }
181}

References PNS::LINK_HOLDER::IsLinked(), PNS::LINK_HOLDER::Links(), m_cache, m_cacheTags, and PNS::LINE::PointCount().

Referenced by CacheRemove().

◆ runSmartPads()

bool PNS::OPTIMIZER::runSmartPads ( LINE aLine)
private

Definition at line 1069 of file pns_optimizer.cpp.

1070{
1071 SHAPE_LINE_CHAIN& line = aLine->Line();
1072
1073 if( line.PointCount() < 3 )
1074 return false;
1075
1076 VECTOR2I p_start = line.CPoint( 0 ), p_end = line.CPoint( -1 );
1077
1078 ITEM* startPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_start );
1079 ITEM* endPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_end );
1080
1081 int vtx = -1;
1082
1083 if( startPad )
1084 vtx = smartPadsSingle( aLine, startPad, false, 3 );
1085
1086 if( endPad )
1087 smartPadsSingle( aLine, endPad, true,
1088 vtx < 0 ? line.PointCount() - 1 : line.PointCount() - 1 - vtx );
1089
1090 aLine->Line().Simplify();
1091
1092 return true;
1093}
int smartPadsSingle(LINE *aLine, ITEM *aPad, bool aEnd, int aEndVertex)
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.

References SHAPE_LINE_CHAIN::CPoint(), findPadOrVia(), PNS::ITEM::Layer(), PNS::LINE::Line(), PNS::ITEM::Net(), SHAPE_LINE_CHAIN::PointCount(), SHAPE_LINE_CHAIN::Simplify(), and smartPadsSingle().

Referenced by Optimize().

◆ SetCollisionMask()

void PNS::OPTIMIZER::SetCollisionMask ( int  aMask)
inline

◆ SetEffortLevel()

void PNS::OPTIMIZER::SetEffortLevel ( int  aEffort)
inline

◆ SetPreserveVertex()

void PNS::OPTIMIZER::SetPreserveVertex ( const VECTOR2I aV)
inline

◆ SetRestrictArea()

void PNS::OPTIMIZER::SetRestrictArea ( const BOX2I aArea,
bool  aStrict = true 
)
inline

Definition at line 150 of file pns_optimizer.h.

151 {
152 m_restrictArea = aArea;
153 m_restrictAreaIsStrict = aStrict;
154 }

References m_restrictArea, and m_restrictAreaIsStrict.

Referenced by PNS::DRAGGER::optimizeAndUpdateDraggedLine(), and PNS::SHOVE::runOptimizer().

◆ SetRestrictVertexRange()

void PNS::OPTIMIZER::SetRestrictVertexRange ( int  aStart,
int  aEnd 
)
inline

Definition at line 143 of file pns_optimizer.h.

144 {
145 m_restrictedVertexRange.first = aStart;
146 m_restrictedVertexRange.second = aEnd;
148 }

References m_effortLevel, m_restrictedVertexRange, and RESTRICT_VERTEX_RANGE.

◆ SetWorld()

void PNS::OPTIMIZER::SetWorld ( NODE aNode)
inline

Definition at line 123 of file pns_optimizer.h.

123{ m_world = aNode; }

References m_world.

◆ smartPadsSingle()

int PNS::OPTIMIZER::smartPadsSingle ( LINE aLine,
ITEM aPad,
bool  aEnd,
int  aEndVertex 
)
private

Definition at line 948 of file pns_optimizer.cpp.

949{
950 DIRECTION_45 dir;
951
952 const int ForbiddenAngles = DIRECTION_45::ANG_ACUTE | DIRECTION_45::ANG_RIGHT |
954
955 typedef std::tuple<int, long long int, SHAPE_LINE_CHAIN> RtVariant;
956 std::vector<RtVariant> variants;
957
958 SOLID* solid = dyn_cast<SOLID*>( aPad );
959
960 // don't do optimized connections for offset pads
961 if( solid && solid->Offset() != VECTOR2I( 0, 0 ) )
962 return -1;
963
964 // don't do optimization on vias, they are always round at the moment and the optimizer
965 // will possibly mess up an intended via exit posture
966 if( aPad->Kind() == ITEM::VIA_T )
967 return -1;
968
969 BREAKOUT_LIST breakouts = computeBreakouts( aLine->Width(), aPad, true );
970 SHAPE_LINE_CHAIN line = ( aEnd ? aLine->CLine().Reverse() : aLine->CLine() );
971 int p_end = std::min( aEndVertex, std::min( 3, line.PointCount() - 1 ) );
972
973 // Start at 1 to find a potentially better breakout (0 is the pad connection)
974 for( int p = 1; p <= p_end; p++ )
975 {
976 // If the line is contained inside the pad, don't optimize
977 if( solid && solid->Shape() && !solid->Shape()->Collide(
978 SEG( line.CPoint( 0 ), line.CPoint( p ) ), aLine->Width() / 2 ) )
979 {
980 continue;
981 }
982
983 for( SHAPE_LINE_CHAIN & breakout : breakouts )
984 {
985 for( int diag = 0; diag < 2; diag++ )
986 {
989 breakout.CPoint( -1 ), line.CPoint( p ), diag == 0 );
990
991 DIRECTION_45 dir_bkout( breakout.CSegment( -1 ) );
992
993 if( !connect.SegmentCount() )
994 continue;
995
996 int ang1 = dir_bkout.Angle( DIRECTION_45( connect.CSegment( 0 ) ) );
997
998 if( ang1 & ForbiddenAngles )
999 continue;
1000
1001 if( breakout.Length() > line.Length() )
1002 continue;
1003
1004 v = breakout;
1005 v.Append( connect );
1006
1007 for( int i = p + 1; i < line.PointCount(); i++ )
1008 v.Append( line.CPoint( i ) );
1009
1010 LINE tmp( *aLine, v );
1011 int cc = tmp.CountCorners( ForbiddenAngles );
1012
1013 if( cc == 0 )
1014 {
1015 RtVariant vp;
1016 std::get<0>( vp ) = p;
1017 std::get<1>( vp ) = breakout.Length();
1018 std::get<2>( vp ) = aEnd ? v.Reverse() : v;
1019 std::get<2>( vp ).Simplify();
1020 variants.push_back( vp );
1021 }
1022 }
1023 }
1024 }
1025
1026 // We attempt to minimize the corner cost (minimizes the segments and types of corners)
1027 // but given two, equally valid costs, we want to pick the longer pad exit. The logic
1028 // here is that if the pad is oblong, the track should not exit the shorter side and parallel
1029 // the pad but should follow the pad's preferential direction before exiting.
1030 // The baseline guess is to start with the existing line the user has drawn.
1031 int min_cost = COST_ESTIMATOR::CornerCost( *aLine );
1032 long long int max_length = 0;
1033 bool found = false;
1034 int p_best = -1;
1035 SHAPE_LINE_CHAIN l_best;
1036
1037 for( RtVariant& vp : variants )
1038 {
1039 LINE tmp( *aLine, std::get<2>( vp ) );
1040 int cost = COST_ESTIMATOR::CornerCost( std::get<2>( vp ) );
1041 long long int len = std::get<1>( vp );
1042
1043 if( !checkColliding( &tmp ) )
1044 {
1045 if( cost < min_cost || ( cost == min_cost && len > max_length ) )
1046 {
1047 l_best = std::get<2>( vp );
1048 p_best = std::get<0>( vp );
1049 found = true;
1050
1051 if( cost <= min_cost )
1052 max_length = std::max<int>( len, max_length );
1053
1054 min_cost = std::min( cost, min_cost );
1055 }
1056 }
1057 }
1058
1059 if( found )
1060 {
1061 aLine->SetShape( l_best );
1062 return p_best;
1063 }
1064
1065 return -1;
1066}
BREAKOUT_LIST computeBreakouts(int aWidth, const ITEM *aItem, bool aPermitDiagonal) const
const SHAPE_LINE_CHAIN Reverse() const
Reverse point order in the line chain.
long long int Length() const
Return length of the line chain in Euclidean metric.

References DIRECTION_45::ANG_ACUTE, DIRECTION_45::ANG_HALF_FULL, DIRECTION_45::ANG_RIGHT, DIRECTION_45::ANG_UNDEFINED, DIRECTION_45::Angle(), SHAPE_LINE_CHAIN::Append(), DIRECTION_45::BuildInitialTrace(), checkColliding(), PNS::LINE::CLine(), SHAPE::Collide(), computeBreakouts(), PNS::COST_ESTIMATOR::CornerCost(), PNS::LINE::CountCorners(), SHAPE_LINE_CHAIN::CPoint(), SHAPE_LINE_CHAIN::CSegment(), PNS::ITEM::Kind(), SHAPE_LINE_CHAIN::Length(), PNS::SOLID::Offset(), SHAPE_LINE_CHAIN::PointCount(), SHAPE_LINE_CHAIN::Reverse(), SHAPE_LINE_CHAIN::SegmentCount(), PNS::LINE::SetShape(), PNS::SOLID::Shape(), SHAPE_LINE_CHAIN::Simplify(), PNS::ITEM::VIA_T, and PNS::LINE::Width().

Referenced by runSmartPads().

Member Data Documentation

◆ m_cache

SHAPE_INDEX_LIST<ITEM*> PNS::OPTIMIZER::m_cache
private

Definition at line 201 of file pns_optimizer.h.

Referenced by cacheAdd(), ClearCache(), and removeCachedSegments().

◆ m_cacheTags

std::unordered_map<ITEM*, CACHED_ITEM> PNS::OPTIMIZER::m_cacheTags
private

Definition at line 203 of file pns_optimizer.h.

Referenced by cacheAdd(), ClearCache(), and removeCachedSegments().

◆ m_collisionKindMask

int PNS::OPTIMIZER::m_collisionKindMask
private

Definition at line 206 of file pns_optimizer.h.

Referenced by checkColliding(), and SetCollisionMask().

◆ m_constraints

std::vector<OPT_CONSTRAINT*> PNS::OPTIMIZER::m_constraints
private

Definition at line 202 of file pns_optimizer.h.

Referenced by AddConstraint(), checkConstraints(), and ClearConstraints().

◆ m_effortLevel

int PNS::OPTIMIZER::m_effortLevel
private

◆ m_preservedVertex

VECTOR2I PNS::OPTIMIZER::m_preservedVertex
private

Definition at line 209 of file pns_optimizer.h.

Referenced by Optimize(), and SetPreserveVertex().

◆ m_restrictArea

BOX2I PNS::OPTIMIZER::m_restrictArea
private

Definition at line 211 of file pns_optimizer.h.

Referenced by Optimize(), and SetRestrictArea().

◆ m_restrictAreaIsStrict

bool PNS::OPTIMIZER::m_restrictAreaIsStrict
private

Definition at line 212 of file pns_optimizer.h.

Referenced by Optimize(), and SetRestrictArea().

◆ m_restrictedVertexRange

std::pair<int, int> PNS::OPTIMIZER::m_restrictedVertexRange
private

Definition at line 210 of file pns_optimizer.h.

Referenced by Optimize(), and SetRestrictVertexRange().

◆ m_world

NODE* PNS::OPTIMIZER::m_world
private

◆ MaxCachedItems

const int PNS::OPTIMIZER::MaxCachedItems = 256
staticprivate

Definition at line 160 of file pns_optimizer.h.


The documentation for this class was generated from the following files: