KiCad PCB EDA Suite
PNS::OPTIMIZER Class Reference

OPTIMIZER. 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
}
 

Public Member Functions

 OPTIMIZER (NODE *aWorld)
 Optimizer. More...
 
 ~OPTIMIZER ()
 
bool Optimize (LINE *aLine, LINE *aResult=NULL)
 
bool Optimize (DIFF_PAIR *aPair)
 
void SetWorld (NODE *aNode)
 
void CacheStaticItem (ITEM *aItem)
 
void CacheRemove (ITEM *aItem)
 
void ClearCache (bool aStaticOnly=false)
 
void SetCollisionMask (int aMask)
 
void SetEffortLevel (int aEffort)
 
void SetRestrictArea (const BOX2I &aArea)
 
void ClearConstraints ()
 
void AddConstraint (OPT_CONSTRAINT *aConstraint)
 
bool extractPadGrids (std::vector< JOINT * > &aPadJoints)
 
void BuildPadGrids ()
 

Static Public Member Functions

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

a quick shortcut to optmize a line without creating and setting up an optimizer

More...
 

Private Types

typedef std::vector< SHAPE_LINE_CHAINBREAKOUT_LIST
 
typedef std::unordered_map< ITEM *, CACHED_ITEMCachedItemTags
 

Private Member Functions

bool mergeObtuse (LINE *aLine)
 
bool mergeFull (LINE *aLine)
 
bool removeUglyCorners (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 ovalBreakouts (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
 
CachedItemTags m_cacheTags
 
NODEm_world
 
int m_collisionKindMask
 
int m_effortLevel
 
bool m_keepPostures
 
BOX2I m_restrictArea
 
bool m_restrictAreaActive
 

Static Private Attributes

static const int MaxCachedItems = 256
 

Detailed Description

OPTIMIZER.

Performs 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 95 of file pns_optimizer.h.

Member Typedef Documentation

◆ BREAKOUT_LIST

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

Definition at line 149 of file pns_optimizer.h.

◆ CachedItemTags

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

Definition at line 191 of file pns_optimizer.h.

Member Enumeration Documentation

◆ OptimizationEffort

Enumerator
MERGE_SEGMENTS 
SMART_PADS 
MERGE_OBTUSE 
FANOUT_CLEANUP 
KEEP_TOPOLOGY 
PRESERVE_VERTEX 

Definition at line 98 of file pns_optimizer.h.

Constructor & Destructor Documentation

◆ OPTIMIZER()

PNS::OPTIMIZER::OPTIMIZER ( NODE aWorld)

Optimizer.

Definition at line 133 of file pns_optimizer.cpp.

133  :
134  m_world( aWorld ),
137  m_keepPostures( false ),
138  m_restrictAreaActive( false )
139 {
140 }
bool m_restrictAreaActive

◆ ~OPTIMIZER()

PNS::OPTIMIZER::~OPTIMIZER ( )

Definition at line 143 of file pns_optimizer.cpp.

144 {
145 }

Member Function Documentation

◆ AddConstraint()

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

Definition at line 445 of file pns_optimizer.cpp.

446  {
447  m_constraints.push_back(aConstraint);
448 }
std::vector< OPT_CONSTRAINT * > m_constraints

References m_constraints.

Referenced by Optimize().

◆ BuildPadGrids()

void PNS::OPTIMIZER::BuildPadGrids ( )

◆ cacheAdd()

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

Definition at line 178 of file pns_optimizer.cpp.

179 {
180  if( m_cacheTags.find( aItem ) != m_cacheTags.end() )
181  return;
182 
183  m_cache.Add( aItem );
184  m_cacheTags[aItem].m_hits = 1;
185  m_cacheTags[aItem].m_isStatic = aIsStatic;
186 }
CachedItemTags m_cacheTags
SHAPE_INDEX_LIST< ITEM * > m_cache

References m_cache, and m_cacheTags.

Referenced by CacheStaticItem().

◆ CacheRemove()

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

Definition at line 207 of file pns_optimizer.cpp.

208 {
209  if( aItem->Kind() == ITEM::LINE_T )
210  removeCachedSegments( static_cast<LINE*>( aItem ) );
211 }
void removeCachedSegments(LINE *aLine, int aStartVertex=0, int aEndVertex=-1)

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

◆ CacheStaticItem()

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

Definition at line 214 of file pns_optimizer.cpp.

215 {
216  cacheAdd( aItem, true );
217 }
void cacheAdd(ITEM *aItem, bool aIsStatic)

References cacheAdd().

◆ checkColliding() [1/2]

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

Definition at line 431 of file pns_optimizer.cpp.

432 {
433  CACHE_VISITOR v( aItem, m_world, m_collisionKindMask );
434 
435  return static_cast<bool>( m_world->CheckColliding( aItem ) );
436 }
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:427

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 464 of file pns_optimizer.cpp.

465 {
466  LINE tmp( *aLine, aOptPath );
467 
468  return checkColliding( &tmp );
469 }
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 450 of file pns_optimizer.cpp.

451 {
452  for( auto c: m_constraints)
453  {
454  if ( !c->Check( aVertex1, aVertex2, aOriginLine, aCurrentPath, aReplacement ) )
455  {
456  return false;
457  }
458  }
459 
460  return true;
461 }
std::vector< OPT_CONSTRAINT * > m_constraints

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 691 of file pns_optimizer.cpp.

693 {
694  BREAKOUT_LIST breakouts;
695 
696  for( int angle = 0; angle < 360; angle += 45 )
697  {
698  const SHAPE_CIRCLE* cir = static_cast<const SHAPE_CIRCLE*>( aShape );
700  VECTOR2I p0 = cir->GetCenter();
701  VECTOR2I v0( cir->GetRadius() * M_SQRT2, 0 );
702  l.Append( p0 );
703  l.Append( p0 + v0.Rotate( angle * M_PI / 180.0 ) );
704  breakouts.push_back( l );
705  }
706 
707  return breakouts;
708 }
int GetRadius() const
Definition: shape_circle.h:83
const VECTOR2I GetCenter() const
Definition: shape_circle.h:88
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
SHAPE_LINE_CHAIN.
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
std::vector< SHAPE_LINE_CHAIN > BREAKOUT_LIST

References PNS::angle(), SHAPE_LINE_CHAIN::Append(), SHAPE_CIRCLE::GetCenter(), SHAPE_CIRCLE::GetRadius(), and VECTOR2< T >::Rotate().

Referenced by computeBreakouts().

◆ ClearCache()

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

Definition at line 220 of file pns_optimizer.cpp.

221 {
222  if( !aStaticOnly )
223  {
224  m_cacheTags.clear();
225  m_cache.Clear();
226  return;
227  }
228 
229  for( CachedItemTags::iterator i = m_cacheTags.begin(); i!= m_cacheTags.end(); ++i )
230  {
231  if( i->second.m_isStatic )
232  {
233  m_cache.Remove( i->first );
234  m_cacheTags.erase( i->first );
235  }
236  }
237 }
CachedItemTags m_cacheTags
SHAPE_INDEX_LIST< ITEM * > m_cache

References m_cache, and m_cacheTags.

◆ ClearConstraints()

void PNS::OPTIMIZER::ClearConstraints ( )

Definition at line 438 of file pns_optimizer.cpp.

439 {
440  for (auto c : m_constraints)
441  delete c;
442  m_constraints.clear();
443 }
std::vector< OPT_CONSTRAINT * > m_constraints

References m_constraints.

◆ computeBreakouts()

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

Definition at line 808 of file pns_optimizer.cpp.

810 {
811  switch( aItem->Kind() )
812  {
813  case ITEM::VIA_T:
814  {
815  const VIA* via = static_cast<const VIA*>( aItem );
816  return circleBreakouts( aWidth, via->Shape(), aPermitDiagonal );
817  }
818 
819  case ITEM::SOLID_T:
820  {
821  const SHAPE* shape = aItem->Shape();
822 
823  switch( shape->Type() )
824  {
825  case SH_RECT:
826  return rectBreakouts( aWidth, shape, aPermitDiagonal );
827 
828  case SH_SEGMENT:
829  {
830  const SHAPE_SEGMENT* seg = static_cast<const SHAPE_SEGMENT*> (shape);
831  const SHAPE_RECT rect = ApproximateSegmentAsRect ( *seg );
832  return rectBreakouts( aWidth, &rect, aPermitDiagonal );
833  }
834 
835  case SH_CIRCLE:
836  return circleBreakouts( aWidth, shape, aPermitDiagonal );
837 
838  case SH_SIMPLE:
839  return customBreakouts( aWidth, aItem, aPermitDiagonal );
840 
841  default:
842  break;
843  }
844 
845  break;
846  }
847 
848  default:
849  break;
850  }
851 
852  return BREAKOUT_LIST();
853 }
BREAKOUT_LIST circleBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
SHAPE_TYPE Type() const
Function Type()
Definition: shape.h:85
BREAKOUT_LIST rectBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
BREAKOUT_LIST customBreakouts(int aWidth, const ITEM *aItem, bool aPermitDiagonal) const
SHAPE.
Definition: shape.h:60
line chain (polyline)
Definition: shape.h:48
SHAPE_RECT ApproximateSegmentAsRect(const SHAPE_SEGMENT &aSeg)
Definition: pns_utils.cpp:216
Definition: shape.h:45
std::vector< SHAPE_LINE_CHAIN > BREAKOUT_LIST
circle
Definition: shape.h:49
axis-aligned rectangle
Definition: shape.h:46

References PNS::ApproximateSegmentAsRect(), circleBreakouts(), customBreakouts(), PNS::ITEM::Kind(), rectBreakouts(), SH_CIRCLE, SH_RECT, SH_SEGMENT, SH_SIMPLE, PNS::VIA::Shape(), PNS::ITEM::Shape(), PNS::ITEM::SOLID_T, SHAPE::Type(), 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 711 of file pns_optimizer.cpp.

713 {
714  BREAKOUT_LIST breakouts;
715  const SHAPE_SIMPLE* convex = static_cast<const SHAPE_SIMPLE*>( aItem->Shape() );
716 
717  BOX2I bbox = convex->BBox( 0 );
718  VECTOR2I p0 = static_cast<const SOLID*>( aItem )->Pos();
719  // must be large enough to guarantee intersecting the convex polygon
720  int length = std::max( bbox.GetWidth(), bbox.GetHeight() ) / 2 + 5;
721 
722  for( int angle = 0; angle < 360; angle += ( aPermitDiagonal ? 45 : 90 ) )
723  {
725  VECTOR2I v0( p0 + VECTOR2I( length, 0 ).Rotate( angle * M_PI / 180.0 ) );
726  SHAPE_LINE_CHAIN::INTERSECTIONS intersections;
727  int n = convex->Vertices().Intersect( SEG( p0, v0 ), intersections );
728  // if n == 1 intersected a segment
729  // if n == 2 intersected the common point of 2 segments
730  // n == 0 can not happen I think, but...
731  if( n > 0 )
732  {
733  l.Append( p0 );
734 
735  // for a breakout distance relative to the distance between
736  // center and polygon edge
737  //l.Append( intersections[0].p + (v0 - p0).Resize( (intersections[0].p - p0).EuclideanNorm() * 0.4 ) );
738 
739  // for an absolute breakout distance, e.g. 0.1 mm
740  //l.Append( intersections[0].p + (v0 - p0).Resize( 100000 ) );
741 
742  // for the breakout right on the polygon edge
743  l.Append( intersections[0].p );
744 
745  breakouts.push_back( l );
746  }
747  }
748 
749  return breakouts;
750 }
SHAPE_SIMPLE.
Definition: shape_simple.h:42
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
std::vector< INTERSECTION > INTERSECTIONS
const BOX2I BBox(int aClearance=0) const override
Function BBox()
Definition: shape_simple.h:74
VECTOR2< int > VECTOR2I
Definition: vector2d.h:594
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
const SHAPE_LINE_CHAIN & Vertices() const
Function Vertices()
Definition: shape_simple.h:125
Definition: seg.h:39
SHAPE_LINE_CHAIN.
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
std::vector< SHAPE_LINE_CHAIN > BREAKOUT_LIST

References PNS::angle(), SHAPE_LINE_CHAIN::Append(), SHAPE_SIMPLE::BBox(), SHAPE_LINE_CHAIN::Intersect(), PNS::ITEM::Shape(), and SHAPE_SIMPLE::Vertices().

Referenced by computeBreakouts().

◆ extractPadGrids()

bool PNS::OPTIMIZER::extractPadGrids ( std::vector< JOINT * > &  aPadJoints)

◆ fanoutCleanup()

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

Definition at line 1040 of file pns_optimizer.cpp.

1041 {
1042  if( aLine->PointCount() < 3 )
1043  return false;
1044 
1045  VECTOR2I p_start = aLine->CPoint( 0 ), p_end = aLine->CPoint( -1 );
1046 
1047  ITEM* startPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_start );
1048  ITEM* endPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_end );
1049 
1050  int thr = aLine->Width() * 10;
1051  int len = aLine->CLine().Length();
1052 
1053  if( !startPad )
1054  return false;
1055 
1056  bool startMatch = startPad->OfKind( ITEM::VIA_T | ITEM::SOLID_T );
1057  bool endMatch = false;
1058 
1059  if(endPad)
1060  {
1061  endMatch = endPad->OfKind( ITEM::VIA_T | ITEM::SOLID_T );
1062  }
1063  else
1064  {
1065  endMatch = aLine->EndsWithVia();
1066  }
1067 
1068  if( startMatch && endMatch && len < thr )
1069  {
1070  for( int i = 0; i < 2; i++ )
1071  {
1072  SHAPE_LINE_CHAIN l2 = DIRECTION_45().BuildInitialTrace( p_start, p_end, i );
1073  LINE repl;
1074  repl = LINE( *aLine, l2 );
1075 
1076  if( !m_world->CheckColliding( &repl ) )
1077  {
1078  aLine->SetShape( repl.CLine() );
1079  return true;
1080  }
1081  }
1082  }
1083 
1084  return false;
1085 }
ITEM * findPadOrVia(int aLayer, int aNet, const VECTOR2I &aP) const
DIRECTION_45.
Definition: direction45.h:37
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false, int aMaxRadius=0) const
Function BuildInitialTrace()
SHAPE_LINE_CHAIN.
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:427
bool OfKind(int aKindMask) const
Function OfKind()
Definition: pns_item.h:133

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 856 of file pns_optimizer.cpp.

857 {
858  JOINT* jt = m_world->FindJoint( aP, aLayer, aNet );
859 
860  if( !jt )
861  return NULL;
862 
863  for( ITEM* item : jt->LinkList() )
864  {
865  if( item->OfKind( ITEM::VIA_T | ITEM::SOLID_T ) )
866  return item;
867  }
868 
869  return NULL;
870 }
#define NULL
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:1027

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

Referenced by fanoutCleanup(), and runSmartPads().

◆ mergeDpSegments()

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

Definition at line 1253 of file pns_optimizer.cpp.

1254 {
1255  int step_p = aPair->CP().SegmentCount() - 2;
1256  int step_n = aPair->CN().SegmentCount() - 2;
1257 
1258  while( 1 )
1259  {
1260  int n_segs_p = aPair->CP().SegmentCount();
1261  int n_segs_n = aPair->CN().SegmentCount();
1262 
1263  int max_step_p = n_segs_p - 2;
1264  int max_step_n = n_segs_n - 2;
1265 
1266  if( step_p > max_step_p )
1267  step_p = max_step_p;
1268 
1269  if( step_n > max_step_n )
1270  step_n = max_step_n;
1271 
1272  if( step_p < 1 && step_n < 1)
1273  break;
1274 
1275  bool found_anything_p = false;
1276  bool found_anything_n = false;
1277 
1278  if( step_p > 1 )
1279  found_anything_p = mergeDpStep( aPair, true, step_p );
1280 
1281  if( step_n > 1 )
1282  found_anything_n = mergeDpStep( aPair, false, step_n );
1283 
1284  if( !found_anything_n && !found_anything_p )
1285  {
1286  step_n--;
1287  step_p--;
1288  }
1289  }
1290  return true;
1291 }
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 1191 of file pns_optimizer.cpp.

1192 {
1193  int n = 1;
1194 
1195  SHAPE_LINE_CHAIN currentPath = aTryP ? aPair->CP() : aPair->CN();
1196  SHAPE_LINE_CHAIN coupledPath = aTryP ? aPair->CN() : aPair->CP();
1197 
1198  int n_segs = currentPath.SegmentCount() - 1;
1199 
1200  int64_t clenPre = aPair->CoupledLength( currentPath, coupledPath );
1201  int64_t budget = clenPre / 10; // fixme: come up with somethig more intelligent here...
1202 
1203  while( n < n_segs - step )
1204  {
1205  const SEG s1 = currentPath.CSegment( n );
1206  const SEG s2 = currentPath.CSegment( n + step );
1207 
1208  DIRECTION_45 dir1( s1 );
1209  DIRECTION_45 dir2( s2 );
1210 
1211  if( dir1.IsObtuse( dir2 ) )
1212  {
1213  SHAPE_LINE_CHAIN bypass = DIRECTION_45().BuildInitialTrace( s1.A, s2.B, dir1.IsDiagonal() );
1214  SHAPE_LINE_CHAIN newRef;
1215  SHAPE_LINE_CHAIN newCoup;
1216  int64_t deltaCoupled = -1, deltaUni = -1;
1217 
1218  newRef = currentPath;
1219  newRef.Replace( s1.Index(), s2.Index(), bypass );
1220 
1221  deltaUni = aPair->CoupledLength ( newRef, coupledPath ) - clenPre + budget;
1222 
1223  if ( coupledBypass( m_world, aPair, aTryP, newRef, bypass, coupledPath, newCoup ) )
1224  {
1225  deltaCoupled = aPair->CoupledLength( newRef, newCoup ) - clenPre + budget;
1226 
1227  if( deltaCoupled >= 0 )
1228  {
1229  newRef.Simplify();
1230  newCoup.Simplify();
1231 
1232  aPair->SetShape( newRef, newCoup, !aTryP );
1233  return true;
1234  }
1235  }
1236  else if( deltaUni >= 0 && verifyDpBypass ( m_world, aPair, aTryP, newRef, coupledPath ) )
1237  {
1238  newRef.Simplify();
1239  coupledPath.Simplify();
1240 
1241  aPair->SetShape( newRef, coupledPath, !aTryP );
1242  return true;
1243  }
1244  }
1245 
1246  n++;
1247  }
1248 
1249  return false;
1250 }
int Index() const
Function Index()
Definition: seg.h:332
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
DIRECTION_45.
Definition: direction45.h:37
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)
int SegmentCount() const
Function SegmentCount()
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false, int aMaxRadius=0) const
Function BuildInitialTrace()
Definition: seg.h:39
bool verifyDpBypass(NODE *aNode, DIFF_PAIR *aPair, bool aRefIsP, const SHAPE_LINE_CHAIN &aNewRef, const SHAPE_LINE_CHAIN &aNewCoupled)
const SEG CSegment(int aIndex) const
Function CSegment()
SHAPE_LINE_CHAIN.
VECTOR2I A
Definition: seg.h:47
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Function Replace()
VECTOR2I B
Definition: seg.h:48

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 560 of file pns_optimizer.cpp.

561 {
562  SHAPE_LINE_CHAIN& line = aLine->Line();
563  int step = line.SegmentCount() - 1;
564 
565  int segs_pre = line.SegmentCount();
566 
567  line.Simplify();
568 
569  if( step < 0 )
570  return false;
571 
572  SHAPE_LINE_CHAIN current_path( line );
573 
574  while( 1 )
575  {
576  int n_segs = current_path.SegmentCount();
577  int max_step = n_segs - 2;
578 
579  if( step > max_step )
580  step = max_step;
581 
582  if( step < 1 )
583  break;
584 
585  bool found_anything = mergeStep( aLine, current_path, step );
586 
587  if( !found_anything )
588  step--;
589 
590  if( !step )
591  break;
592  }
593 
594  aLine->SetShape( current_path );
595 
596  return current_path.SegmentCount() < segs_pre;
597 }
bool mergeStep(LINE *aLine, SHAPE_LINE_CHAIN &aCurrentLine, int step)
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
int SegmentCount() const
Function SegmentCount()
SHAPE_LINE_CHAIN.

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 472 of file pns_optimizer.cpp.

473 {
474  SHAPE_LINE_CHAIN& line = aLine->Line();
475 
476  int step = line.PointCount() - 3;
477  int iter = 0;
478  int segs_pre = line.SegmentCount();
479 
480  if( step < 0 )
481  return false;
482 
483  SHAPE_LINE_CHAIN current_path( line );
484 
485  while( 1 )
486  {
487  iter++;
488  int n_segs = current_path.SegmentCount();
489  int max_step = n_segs - 2;
490 
491  if( step > max_step )
492  step = max_step;
493 
494  if( step < 2 )
495  {
496  line = current_path;
497  return current_path.SegmentCount() < segs_pre;
498  }
499 
500  bool found_anything = false;
501 
502  for( int n = 0; n < n_segs - step; n++ )
503  {
504  const SEG s1 = current_path.CSegment( n );
505  const SEG s2 = current_path.CSegment( n + step );
506  SEG s1opt, s2opt;
507 
508  if( DIRECTION_45( s1 ).IsObtuse( DIRECTION_45( s2 ) ) )
509  {
510  VECTOR2I ip = *s1.IntersectLines( s2 );
511 
512  if( s1.Distance( ip ) <= 1 || s2.Distance( ip ) <= 1 )
513  {
514  s1opt = SEG( s1.A, ip );
515  s2opt = SEG( ip, s2.B );
516  }
517  else
518  {
519  s1opt = SEG( s1.A, ip );
520  s2opt = SEG( ip, s2.B );
521  }
522 
523  if( DIRECTION_45( s1opt ).IsObtuse( DIRECTION_45( s2opt ) ) )
524  {
525  SHAPE_LINE_CHAIN opt_path;
526  opt_path.Append( s1opt.A );
527  opt_path.Append( s1opt.B );
528  opt_path.Append( s2opt.B );
529 
530  LINE opt_track( *aLine, opt_path );
531 
532  if( !checkColliding( &opt_track ) )
533  {
534  current_path.Replace( s1.Index() + 1, s2.Index(), ip );
535  // removeCachedSegments(aLine, s1.Index(), s2.Index());
536  n_segs = current_path.SegmentCount();
537  found_anything = true;
538  break;
539  }
540  }
541  }
542  }
543 
544  if( !found_anything )
545  {
546  if( step <= 2 )
547  {
548  line = current_path;
549  return line.SegmentCount() < segs_pre;
550  }
551 
552  step--;
553  }
554  }
555 
556  return line.SegmentCount() < segs_pre;
557 }
int Index() const
Function Index()
Definition: seg.h:332
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:202
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Function IntersectLines()
Definition: seg.h:186
int PointCount() const
Function PointCount()
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
DIRECTION_45.
Definition: direction45.h:37
int SegmentCount() const
Function SegmentCount()
Definition: seg.h:39
SHAPE_LINE_CHAIN.
VECTOR2I A
Definition: seg.h:47
bool checkColliding(ITEM *aItem, bool aUpdateCache=true)
VECTOR2I B
Definition: seg.h:48

References SEG::A, SHAPE_LINE_CHAIN::Append(), SEG::B, checkColliding(), SHAPE_LINE_CHAIN::CSegment(), SEG::Distance(), 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 627 of file pns_optimizer.cpp.

628 {
629  int n_segs = aCurrentPath.SegmentCount();
630 
631  int cost_orig = COST_ESTIMATOR::CornerCost( aCurrentPath );
632 
633  if( aLine->SegmentCount() < 2 )
634  return false;
635 
636  DIRECTION_45 orig_start( aLine->CSegment( 0 ) );
637  DIRECTION_45 orig_end( aLine->CSegment( -1 ) );
638 
639 
640  for( int n = 0; n < n_segs - step; n++ )
641  {
642  // Do not attempt to merge false segments that are part of an arc
643  if( aCurrentPath.isArc( n ) || aCurrentPath.isArc( n + step ) )
644  continue;
645 
646  const SEG s1 = aCurrentPath.CSegment( n );
647  const SEG s2 = aCurrentPath.CSegment( n + step );
648 
649  SHAPE_LINE_CHAIN path[2];
650  SHAPE_LINE_CHAIN* picked = NULL;
651  int cost[2];
652 
653  for( int i = 0; i < 2; i++ )
654  {
655  SHAPE_LINE_CHAIN bypass = DIRECTION_45().BuildInitialTrace( s1.A, s2.B, i );
656  cost[i] = INT_MAX;
657 
658 
659  bool ok = false;
660  if ( !checkColliding( aLine, bypass ) )
661  {
662  ok = checkConstraints ( n, n + step + 1, aLine, aCurrentPath, bypass );
663  }
664 
665  if( ok )
666  {
667  path[i] = aCurrentPath;
668  path[i].Replace( s1.Index(), s2.Index(), bypass );
669  path[i].Simplify();
670  cost[i] = COST_ESTIMATOR::CornerCost( path[i] );
671  }
672  }
673 
674  if( cost[0] < cost_orig && cost[0] < cost[1] )
675  picked = &path[0];
676  else if( cost[1] < cost_orig )
677  picked = &path[1];
678 
679  if( picked )
680  {
681  n_segs = aCurrentPath.SegmentCount();
682  aCurrentPath = *picked;
683  return true;
684  }
685  }
686 
687  return false;
688 }
int Index() const
Function Index()
Definition: seg.h:332
bool checkConstraints(int aVertex1, int aVertex2, LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement)
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
#define NULL
DIRECTION_45.
Definition: direction45.h:37
int SegmentCount() const
Function SegmentCount()
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false, int aMaxRadius=0) const
Function BuildInitialTrace()
Definition: seg.h:39
SHAPE_LINE_CHAIN.
VECTOR2I A
Definition: seg.h:47
bool checkColliding(ITEM *aItem, bool aUpdateCache=true)
static int CornerCost(const SEG &aA, const SEG &aB)
Cost Estimator Methods.
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Function Replace()
VECTOR2I B
Definition: seg.h:48

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::isArc(), NULL, SHAPE_LINE_CHAIN::Replace(), PNS::LINE::SegmentCount(), SHAPE_LINE_CHAIN::SegmentCount(), and SHAPE_LINE_CHAIN::Simplify().

Referenced by mergeFull().

◆ Optimize() [1/3]

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

a quick shortcut to optmize a line without creating and setting up an optimizer

Definition at line 1014 of file pns_optimizer.cpp.

1015 {
1016  OPTIMIZER opt( aWorld );
1017 
1019 
1020  opt.SetEffortLevel( aEffortLevel );
1021  opt.SetCollisionMask( -1 );
1022 
1023  if ( aEffortLevel & PRESERVE_VERTEX )
1024  {
1025  auto c = new PRESERVE_VERTEX_CONSTRAINT( aWorld, aV );
1026  opt.AddConstraint( c );
1027  //printf("pres-v %d %d\n", aV.x, aV.y );
1028  }
1029 
1030  if ( aEffortLevel & KEEP_TOPOLOGY )
1031  {
1032  auto c = new KEEP_TOPOLOGY_CONSTRAINT( aWorld );
1033  opt.AddConstraint( c );
1034  }
1035 
1036  return opt.Optimize( aLine );
1037 }
static DEBUG_DECORATOR * g_dbg
OPTIMIZER(NODE *aWorld)
Optimizer.
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:230
static ROUTER * GetInstance()
Definition: pns_router.cpp:83

References AddConstraint(), PNS::g_dbg, PNS::ROUTER_IFACE::GetDebugDecorator(), PNS::ROUTER::GetInstance(), PNS::ROUTER::GetInterface(), KEEP_TOPOLOGY, Optimize(), PRESERVE_VERTEX, SetCollisionMask(), and SetEffortLevel().

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

◆ Optimize() [2/3]

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

Definition at line 600 of file pns_optimizer.cpp.

601 {
602  if( !aResult )
603  aResult = aLine;
604  else
605  *aResult = *aLine;
606 
607  m_keepPostures = false;
608 
609  bool rv = false;
610 
612  rv |= mergeFull( aResult );
613 
615  rv |= mergeObtuse( aResult );
616 
617  if( m_effortLevel & SMART_PADS )
618  rv |= runSmartPads( aResult );
619 
621  rv |= fanoutCleanup( aResult );
622 
623  return rv;
624 }
bool runSmartPads(LINE *aLine)
bool mergeFull(LINE *aLine)
bool mergeObtuse(LINE *aLine)
bool fanoutCleanup(LINE *aLine)

References FANOUT_CLEANUP, fanoutCleanup(), m_effortLevel, m_keepPostures, MERGE_OBTUSE, MERGE_SEGMENTS, mergeFull(), mergeObtuse(), runSmartPads(), and SMART_PADS.

◆ Optimize() [3/3]

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

Definition at line 1294 of file pns_optimizer.cpp.

1295 {
1296  return mergeDpSegments( aPair );
1297 }
bool mergeDpSegments(DIFF_PAIR *aPair)

References mergeDpSegments().

◆ ovalBreakouts()

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

◆ rectBreakouts()

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

Definition at line 753 of file pns_optimizer.cpp.

755 {
756  const SHAPE_RECT* rect = static_cast<const SHAPE_RECT*>(aShape);
757  VECTOR2I s = rect->GetSize();
758  VECTOR2I c = rect->GetPosition() + VECTOR2I( s.x / 2, s.y / 2 );
759  BREAKOUT_LIST breakouts;
760 
761  VECTOR2I d_offset;
762 
763  d_offset.x = ( s.x > s.y ) ? ( s.x - s.y ) / 2 : 0;
764  d_offset.y = ( s.x < s.y ) ? ( s.y - s.x ) / 2 : 0;
765 
766  VECTOR2I d_vert = VECTOR2I( 0, s.y / 2 + aWidth );
767  VECTOR2I d_horiz = VECTOR2I( s.x / 2 + aWidth, 0 );
768 
769  breakouts.push_back( SHAPE_LINE_CHAIN( { c, c + d_horiz } ) );
770  breakouts.push_back( SHAPE_LINE_CHAIN( { c, c - d_horiz } ) );
771  breakouts.push_back( SHAPE_LINE_CHAIN( { c, c + d_vert } ) );
772  breakouts.push_back( SHAPE_LINE_CHAIN( { c, c - d_vert } ) );
773 
774  if( aPermitDiagonal )
775  {
776  int l = aWidth + std::min( s.x, s.y ) / 2;
777  VECTOR2I d_diag;
778 
779  if( s.x >= s.y )
780  {
781  breakouts.push_back(
782  SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( l, l ) } ) );
783  breakouts.push_back(
784  SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset - VECTOR2I( -l, l ) } ) );
785  breakouts.push_back(
786  SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset + VECTOR2I( -l, l ) } ) );
787  breakouts.push_back(
788  SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( l, l ) } ) );
789  }
790  else
791  {
792  // fixme: this could be done more efficiently
793  breakouts.push_back(
794  SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( l, l ) } ) );
795  breakouts.push_back(
796  SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( -l, l ) } ) );
797  breakouts.push_back(
798  SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( -l, l ) } ) );
799  breakouts.push_back(
800  SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( l, l ) } ) );
801  }
802  }
803 
804  return breakouts;
805 }
VECTOR2< int > VECTOR2I
Definition: vector2d.h:594
const VECTOR2I GetSize() const
Function GetSize()
Definition: shape_rect.h:111
const VECTOR2I & GetPosition() const
Function GetPosition()
Definition: shape_rect.h:101
SHAPE_LINE_CHAIN.
std::vector< SHAPE_LINE_CHAIN > BREAKOUT_LIST

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 189 of file pns_optimizer.cpp.

190 {
191  if( !aLine->IsLinked() ) return;
192 
193  LINE::SEGMENT_REFS& segs = aLine->LinkedSegments();
194 
195  if( aEndVertex < 0 )
196  aEndVertex += aLine->PointCount();
197 
198  for( int i = aStartVertex; i < aEndVertex - 1; i++ )
199  {
200  LINKED_ITEM* s = segs[i];
201  m_cacheTags.erase( s );
202  m_cache.Remove( s );
203  }
204 }
std::vector< LINKED_ITEM * > SEGMENT_REFS
Definition: pns_line.h:64
CachedItemTags m_cacheTags
SHAPE_INDEX_LIST< ITEM * > m_cache

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

Referenced by CacheRemove().

◆ removeUglyCorners()

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

◆ runSmartPads()

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

Definition at line 987 of file pns_optimizer.cpp.

988 {
989  SHAPE_LINE_CHAIN& line = aLine->Line();
990 
991  if( line.PointCount() < 3 )
992  return false;
993 
994  VECTOR2I p_start = line.CPoint( 0 ), p_end = line.CPoint( -1 );
995 
996  ITEM* startPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_start );
997  ITEM* endPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_end );
998 
999  int vtx = -1;
1000 
1001  if( startPad )
1002  vtx = smartPadsSingle( aLine, startPad, false, 3 );
1003 
1004  if( endPad )
1005  smartPadsSingle( aLine, endPad, true,
1006  vtx < 0 ? line.PointCount() - 1 : line.PointCount() - 1 - vtx );
1007 
1008  aLine->Line().Simplify();
1009 
1010  return true;
1011 }
ITEM * findPadOrVia(int aLayer, int aNet, const VECTOR2I &aP) const
int PointCount() const
Function PointCount()
const VECTOR2I & CPoint(int aIndex) const
Function Point()
SHAPE_LINE_CHAIN.
int smartPadsSingle(LINE *aLine, ITEM *aPad, bool aEnd, int aEndVertex)

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

Definition at line 123 of file pns_optimizer.h.

124  {
125  m_collisionKindMask = aMask;
126  }

References m_collisionKindMask.

Referenced by Optimize(), PNS::LINE_PLACER::rhShoveOnly(), and PNS::SHOVE::runOptimizer().

◆ SetEffortLevel()

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

Definition at line 128 of file pns_optimizer.h.

129  {
130  m_effortLevel = aEffort;
131  }

References m_effortLevel.

Referenced by Optimize(), PNS::LINE_PLACER::rhShoveOnly(), and PNS::SHOVE::runOptimizer().

◆ SetRestrictArea()

void PNS::OPTIMIZER::SetRestrictArea ( const BOX2I aArea)
inline

Definition at line 134 of file pns_optimizer.h.

135  {
136  m_restrictArea = aArea;
137  m_restrictAreaActive = true;
138  }
bool m_restrictAreaActive

References m_restrictArea, and m_restrictAreaActive.

Referenced by PNS::SHOVE::runOptimizer().

◆ SetWorld()

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

Definition at line 118 of file pns_optimizer.h.

118 { m_world = aNode; }

References m_world.

Referenced by PNS::LINE_PLACER::rhShoveOnly().

◆ smartPadsSingle()

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

Definition at line 873 of file pns_optimizer.cpp.

874 {
875  DIRECTION_45 dir;
876 
877  const int ForbiddenAngles = DIRECTION_45::ANG_ACUTE | DIRECTION_45::ANG_RIGHT |
879 
880  typedef std::tuple<int, long long int, SHAPE_LINE_CHAIN> RtVariant;
881  std::vector<RtVariant> variants;
882 
883  SOLID* solid = dyn_cast<SOLID*>( aPad );
884 
885  // don't do optimized connections for offset pads
886  if( solid && solid->Offset() != VECTOR2I( 0, 0 ) )
887  return -1;
888 
889 
890  BREAKOUT_LIST breakouts = computeBreakouts( aLine->Width(), aPad, true );
891  SHAPE_LINE_CHAIN line = ( aEnd ? aLine->CLine().Reverse() : aLine->CLine() );
892  int p_end = std::min( aEndVertex, std::min( 3, line.PointCount() - 1 ) );
893 
894  // Start at 1 to find a potentially better breakout (0 is the pad connection)
895  for( int p = 1; p <= p_end; p++ )
896  {
897  // If the line is contained inside the pad, don't optimize
898  if( solid && solid->Shape() && !solid->Shape()->Collide(
899  SEG( line.CPoint( 0 ), line.CPoint( p ) ), aLine->Width() / 2 ) )
900  continue;
901 
902  for( SHAPE_LINE_CHAIN & breakout : breakouts ) {
903 
904  for( int diag = 0; diag < 2; diag++ )
905  {
907  SHAPE_LINE_CHAIN connect = dir.BuildInitialTrace(
908  breakout.CPoint( -1 ), line.CPoint( p ), diag == 0 );
909 
910  DIRECTION_45 dir_bkout( breakout.CSegment( -1 ) );
911 
912  if(!connect.SegmentCount())
913  continue;
914 
915  int ang1 = dir_bkout.Angle( DIRECTION_45( connect.CSegment( 0 ) ) );
916 
917  if( ang1 & ForbiddenAngles )
918  continue;
919 
920  if( breakout.Length() > line.Length() )
921  continue;
922 
923  v = breakout;
924  v.Append( connect );
925 
926  for( int i = p + 1; i < line.PointCount(); i++ )
927  v.Append( line.CPoint( i ) );
928 
929  LINE tmp( *aLine, v );
930  int cc = tmp.CountCorners( ForbiddenAngles );
931 
932  if( cc == 0 )
933  {
934  RtVariant vp;
935  std::get<0>( vp ) = p;
936  std::get<1>( vp ) = breakout.Length();
937  std::get<2>( vp ) = aEnd ? v.Reverse() : v;
938  std::get<2>( vp ).Simplify();
939  variants.push_back( vp );
940  }
941  }
942  }
943  }
944 
945  // We attempt to minimize the corner cost (minimizes the segments and types of corners)
946  // but given two, equally valid costs, we want to pick the longer pad exit. The logic
947  // here is that if the pad is oblong, the track should not exit the shorter side and parallel
948  // the pad but should follow the pad's preferential direction before exiting.
949  // The baseline guess is to start with the existing line the user has drawn.
950  int min_cost = COST_ESTIMATOR::CornerCost( *aLine );
951  long long int max_length = 0;
952  bool found = false;
953  int p_best = -1;
954  SHAPE_LINE_CHAIN l_best;
955 
956  for( RtVariant& vp : variants )
957  {
958  LINE tmp( *aLine, std::get<2>( vp ) );
959  int cost = COST_ESTIMATOR::CornerCost( std::get<2>( vp ) );
960  long long int len = std::get<1>( vp );
961 
962  if( !checkColliding( &tmp ) )
963  {
964  if( cost < min_cost || ( cost == min_cost && len > max_length ) )
965  {
966  l_best = std::get<2>( vp );
967  p_best = std::get<0>( vp );
968  found = true;
969 
970  if( cost <= min_cost )
971  max_length = std::max<int>( len, max_length );
972 
973  min_cost = std::min( cost, min_cost );
974  }
975  }
976  }
977 
978  if( found )
979  {
980  aLine->SetShape( l_best );
981  return p_best;
982  }
983 
984  return -1;
985 }
BREAKOUT_LIST computeBreakouts(int aWidth, const ITEM *aItem, bool aPermitDiagonal) const
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
VECTOR2< int > VECTOR2I
Definition: vector2d.h:594
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
AngleType Angle(const DIRECTION_45 &aOther) const
Function Angle() Returns the type of angle between directions (this) and aOther.
Definition: direction45.h:153
DIRECTION_45.
Definition: direction45.h:37
int SegmentCount() const
Function SegmentCount()
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false, int aMaxRadius=0) const
Function BuildInitialTrace()
Definition: seg.h:39
const SEG CSegment(int aIndex) const
Function CSegment()
SHAPE_LINE_CHAIN.
bool checkColliding(ITEM *aItem, bool aUpdateCache=true)
static int CornerCost(const SEG &aA, const SEG &aB)
Cost Estimator Methods.
std::vector< SHAPE_LINE_CHAIN > BREAKOUT_LIST

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::CSegment(), PNS::SOLID::Offset(), SHAPE_LINE_CHAIN::Reverse(), SHAPE_LINE_CHAIN::SegmentCount(), PNS::LINE::SetShape(), PNS::SOLID::Shape(), SHAPE_LINE_CHAIN::Simplify(), and PNS::LINE::Width().

Referenced by runSmartPads().

Member Data Documentation

◆ m_cache

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

Definition at line 188 of file pns_optimizer.h.

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

◆ m_cacheTags

CachedItemTags PNS::OPTIMIZER::m_cacheTags
private

Definition at line 192 of file pns_optimizer.h.

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

◆ m_collisionKindMask

int PNS::OPTIMIZER::m_collisionKindMask
private

Definition at line 194 of file pns_optimizer.h.

Referenced by checkColliding(), and SetCollisionMask().

◆ m_constraints

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

Definition at line 190 of file pns_optimizer.h.

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

◆ m_effortLevel

int PNS::OPTIMIZER::m_effortLevel
private

Definition at line 195 of file pns_optimizer.h.

Referenced by Optimize(), and SetEffortLevel().

◆ m_keepPostures

bool PNS::OPTIMIZER::m_keepPostures
private

Definition at line 196 of file pns_optimizer.h.

Referenced by Optimize().

◆ m_restrictArea

BOX2I PNS::OPTIMIZER::m_restrictArea
private

Definition at line 198 of file pns_optimizer.h.

Referenced by SetRestrictArea().

◆ m_restrictAreaActive

bool PNS::OPTIMIZER::m_restrictAreaActive
private

Definition at line 199 of file pns_optimizer.h.

Referenced by SetRestrictArea().

◆ m_world

NODE* PNS::OPTIMIZER::m_world
private

Definition at line 193 of file pns_optimizer.h.

Referenced by checkColliding(), fanoutCleanup(), findPadOrVia(), mergeDpStep(), and SetWorld().

◆ MaxCachedItems

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

Definition at line 147 of file pns_optimizer.h.


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