KiCad PCB EDA Suite
PNS::OPTIMIZER Class Reference

Class 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 }
 

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)
 

Static Public Member Functions

static bool Optimize (LINE *aLine, int aEffortLevel, NODE *aWorld)
 

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)
 
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 convexBreakouts (int aWidth, const SHAPE *aShape, 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
 
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

Class 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 90 of file pns_optimizer.h.

Member Typedef Documentation

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

Definition at line 136 of file pns_optimizer.h.

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

Definition at line 173 of file pns_optimizer.h.

Member Enumeration Documentation

Enumerator
MERGE_SEGMENTS 
SMART_PADS 
MERGE_OBTUSE 
FANOUT_CLEANUP 

Definition at line 93 of file pns_optimizer.h.

Constructor & Destructor Documentation

PNS::OPTIMIZER::OPTIMIZER ( NODE aWorld)

Optimizer.

Definition at line 126 of file pns_optimizer.cpp.

126  :
127  m_world( aWorld ),
130  m_keepPostures( false ),
131  m_restrictAreaActive( false )
132 {
133 }
bool m_restrictAreaActive
PNS::OPTIMIZER::~OPTIMIZER ( )

Definition at line 136 of file pns_optimizer.cpp.

137 {
138 }

Member Function Documentation

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

Definition at line 171 of file pns_optimizer.cpp.

References m_cache, and m_cacheTags.

Referenced by CacheStaticItem(), and checkColliding().

172 {
173  if( m_cacheTags.find( aItem ) != m_cacheTags.end() )
174  return;
175 
176  m_cache.Add( aItem );
177  m_cacheTags[aItem].m_hits = 1;
178  m_cacheTags[aItem].m_isStatic = aIsStatic;
179 }
CachedItemTags m_cacheTags
SHAPE_INDEX_LIST< ITEM * > m_cache
void PNS::OPTIMIZER::CacheRemove ( ITEM aItem)

Definition at line 200 of file pns_optimizer.cpp.

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

201 {
202  if( aItem->Kind() == ITEM::LINE_T )
203  removeCachedSegments( static_cast<LINE*>( aItem ) );
204 }
void removeCachedSegments(LINE *aLine, int aStartVertex=0, int aEndVertex=-1)
void PNS::OPTIMIZER::CacheStaticItem ( ITEM aItem)

Definition at line 207 of file pns_optimizer.cpp.

References cacheAdd().

208 {
209  cacheAdd( aItem, true );
210 }
void cacheAdd(ITEM *aItem, bool aIsStatic)
bool PNS::OPTIMIZER::checkColliding ( ITEM aItem,
bool  aUpdateCache = true 
)
private

Definition at line 385 of file pns_optimizer.cpp.

References cacheAdd(), PNS::NODE::CheckColliding(), PNS::NODE::GetMaxClearance(), m_cache, m_cacheTags, PNS::OPTIMIZER::CACHE_VISITOR::m_collidingItem, m_collisionKindMask, m_world, and PNS::ITEM::Shape().

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

386 {
387  CACHE_VISITOR v( aItem, m_world, m_collisionKindMask );
388 
389  return static_cast<bool>( m_world->CheckColliding( aItem ) );
390 
391 #if 0
392  // something is wrong with the cache, need to investigate.
393  m_cache.Query( aItem->Shape(), m_world->GetMaxClearance(), v, false );
394 
395  if( !v.m_collidingItem )
396  {
397  NODE::OPT_OBSTACLE obs = m_world->CheckColliding( aItem );
398 
399  if( obs )
400  {
401  if( aUpdateCache )
402  cacheAdd( obs->m_item );
403 
404  return true;
405  }
406  }
407  else
408  {
409  m_cacheTags[v.m_collidingItem].m_hits++;
410  return true;
411  }
412 
413  return false;
414 #endif
415 }
int GetMaxClearance() const
Returns the pre-set worst case clearance between any pair of items
Definition: pns_node.h:151
CachedItemTags m_cacheTags
void cacheAdd(ITEM *aItem, bool aIsStatic)
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:425
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:140
SHAPE_INDEX_LIST< ITEM * > m_cache
bool PNS::OPTIMIZER::checkColliding ( LINE aLine,
const SHAPE_LINE_CHAIN aOptPath 
)
private

Definition at line 418 of file pns_optimizer.cpp.

References checkColliding().

419 {
420  LINE tmp( *aLine, aOptPath );
421 
422  return checkColliding( &tmp );
423 }
bool checkColliding(ITEM *aItem, bool aUpdateCache=true)
OPTIMIZER::BREAKOUT_LIST PNS::OPTIMIZER::circleBreakouts ( int  aWidth,
const SHAPE aShape,
bool  aPermitDiagonal 
) const
private

Definition at line 648 of file pns_optimizer.cpp.

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

Referenced by computeBreakouts().

650 {
651  BREAKOUT_LIST breakouts;
652 
653  for( int angle = 0; angle < 360; angle += 45 )
654  {
655  const SHAPE_CIRCLE* cir = static_cast<const SHAPE_CIRCLE*>( aShape );
657  VECTOR2I p0 = cir->GetCenter();
658  VECTOR2I v0( cir->GetRadius() * M_SQRT2, 0 );
659  l.Append( p0 );
660  l.Append( p0 + v0.Rotate( angle * M_PI / 180.0 ) );
661  breakouts.push_back( l );
662  }
663 
664  return breakouts;
665 }
const VECTOR2I GetCenter() const
Definition: shape_circle.h:84
int GetRadius() const
Definition: shape_circle.h:79
VECTOR2< T > Rotate(double aAngle) const
Function Rotate rotates the vector by a given angle.
Definition: vector2d.h:372
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
Class SHAPE_LINE_CHAIN.
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
std::vector< SHAPE_LINE_CHAIN > BREAKOUT_LIST
void PNS::OPTIMIZER::ClearCache ( bool  aStaticOnly = false)

Definition at line 213 of file pns_optimizer.cpp.

References m_cache, and m_cacheTags.

214 {
215  if( !aStaticOnly )
216  {
217  m_cacheTags.clear();
218  m_cache.Clear();
219  return;
220  }
221 
222  for( CachedItemTags::iterator i = m_cacheTags.begin(); i!= m_cacheTags.end(); ++i )
223  {
224  if( i->second.m_isStatic )
225  {
226  m_cache.Remove( i->first );
227  m_cacheTags.erase( i->first );
228  }
229  }
230 }
CachedItemTags m_cacheTags
SHAPE_INDEX_LIST< ITEM * > m_cache
OPTIMIZER::BREAKOUT_LIST PNS::OPTIMIZER::computeBreakouts ( int  aWidth,
const ITEM aItem,
bool  aPermitDiagonal 
) const
private

Definition at line 764 of file pns_optimizer.cpp.

References PNS::ApproximateSegmentAsRect(), circleBreakouts(), convexBreakouts(), PNS::ITEM::Kind(), rectBreakouts(), SH_CIRCLE, SH_CONVEX, SH_RECT, SH_SEGMENT, PNS::VIA::Shape(), PNS::ITEM::Shape(), PNS::ITEM::SOLID_T, SHAPE::Type(), and PNS::ITEM::VIA_T.

Referenced by smartPadsSingle().

766 {
767  switch( aItem->Kind() )
768  {
769  case ITEM::VIA_T:
770  {
771  const VIA* via = static_cast<const VIA*>( aItem );
772  return circleBreakouts( aWidth, via->Shape(), aPermitDiagonal );
773  }
774 
775  case ITEM::SOLID_T:
776  {
777  const SHAPE* shape = aItem->Shape();
778 
779  switch( shape->Type() )
780  {
781  case SH_RECT:
782  return rectBreakouts( aWidth, shape, aPermitDiagonal );
783 
784  case SH_SEGMENT:
785  {
786  const SHAPE_SEGMENT* seg = static_cast<const SHAPE_SEGMENT*> (shape);
787  const SHAPE_RECT rect = ApproximateSegmentAsRect ( *seg );
788  return rectBreakouts( aWidth, &rect, aPermitDiagonal );
789  }
790 
791  case SH_CIRCLE:
792  return circleBreakouts( aWidth, shape, aPermitDiagonal );
793 
794  case SH_CONVEX:
795  return convexBreakouts( aWidth, shape, aPermitDiagonal );
796 
797  default:
798  break;
799  }
800  }
801 
802  default:
803  break;
804  }
805 
806  return BREAKOUT_LIST();
807 }
BREAKOUT_LIST circleBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
BREAKOUT_LIST convexBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
BREAKOUT_LIST rectBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
Class SHAPE.
Definition: shape.h:57
line chain (polyline)
Definition: shape.h:46
SHAPE_TYPE Type() const
Function Type()
Definition: shape.h:82
SHAPE_RECT ApproximateSegmentAsRect(const SHAPE_SEGMENT &aSeg)
Definition: pns_utils.cpp:157
Definition: shape.h:43
std::vector< SHAPE_LINE_CHAIN > BREAKOUT_LIST
circle
Definition: shape.h:47
axis-aligned rectangle
Definition: shape.h:44
OPTIMIZER::BREAKOUT_LIST PNS::OPTIMIZER::convexBreakouts ( int  aWidth,
const SHAPE aShape,
bool  aPermitDiagonal 
) const
private

Definition at line 668 of file pns_optimizer.cpp.

References PNS::angle(), SHAPE_LINE_CHAIN::Append(), SHAPE_CONVEX::BBox(), BOX2< Vec >::Centre(), VECTOR2< T >::EuclideanNorm(), BOX2< Vec >::GetSize(), SHAPE_LINE_CHAIN::Intersect(), and SHAPE_CONVEX::Vertices().

Referenced by computeBreakouts().

670 {
671  BREAKOUT_LIST breakouts;
672  const SHAPE_CONVEX* convex = static_cast<const SHAPE_CONVEX*>( aShape );
673 
674  BOX2I bbox = convex->BBox( 0 );
675  VECTOR2I p0 = bbox.Centre();
676  // must be large enough to guarantee intersecting the convex polygon
677  int length = bbox.GetSize().EuclideanNorm() / 2 + 5;
678 
679  for( int angle = 0; angle < 360; angle += ( aPermitDiagonal ? 45 : 90 ) )
680  {
682  VECTOR2I v0( p0 + VECTOR2I( length, 0 ).Rotate( angle * M_PI / 180.0 ) );
683  SHAPE_LINE_CHAIN::INTERSECTIONS intersections;
684  int n = convex->Vertices().Intersect( SEG( p0, v0 ), intersections );
685  // if n == 1 intersected a segment
686  // if n == 2 intersected the common point of 2 segments
687  // n == 0 can not happen I think, but...
688  if( n > 0 )
689  {
690  l.Append( p0 );
691 
692  // for a breakout distance relative to the distance between
693  // center and polygon edge
694  //l.Append( intersections[0].p + (v0 - p0).Resize( (intersections[0].p - p0).EuclideanNorm() * 0.4 ) );
695 
696  // for an absolute breakout distance, e.g. 0.1 mm
697  l.Append( intersections[0].p + (v0 - p0).Resize( 100000 ) );
698 
699  // for the breakout right on the polygon edge
700  //l.Append( intersections[0].p );
701 
702  breakouts.push_back( l );
703  }
704  }
705 
706  return breakouts;
707 }
const BOX2I BBox(int aClearance=0) const override
Function BBox()
Definition: shape_convex.h:74
std::vector< INTERSECTION > INTERSECTIONS
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
Class SHAPE_CONVEX.
Definition: shape_convex.h:42
const Vec & GetSize() const
Definition: box2.h:177
VECTOR2< int > VECTOR2I
Definition: vector2d.h:589
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
T EuclideanNorm() const
Destructor.
Definition: vector2d.h:294
const SHAPE_LINE_CHAIN & Vertices() const
Function Vertices()
Definition: shape_convex.h:139
Vec Centre() const
Definition: box2.h:67
Definition: seg.h:36
Class SHAPE_LINE_CHAIN.
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
std::vector< SHAPE_LINE_CHAIN > BREAKOUT_LIST
bool PNS::OPTIMIZER::fanoutCleanup ( LINE aLine)
private

Definition at line 971 of file pns_optimizer.cpp.

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().

972 {
973  if( aLine->PointCount() < 3 )
974  return false;
975 
976  VECTOR2I p_start = aLine->CPoint( 0 ), p_end = aLine->CPoint( -1 );
977 
978  ITEM* startPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_start );
979  ITEM* endPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_end );
980 
981  int thr = aLine->Width() * 10;
982  int len = aLine->CLine().Length();
983 
984  if( !startPad )
985  return false;
986 
987  bool startMatch = startPad->OfKind( ITEM::VIA_T | ITEM::SOLID_T );
988  bool endMatch = false;
989 
990  if(endPad)
991  {
992  endMatch = endPad->OfKind( ITEM::VIA_T | ITEM::SOLID_T );
993  }
994  else
995  {
996  endMatch = aLine->EndsWithVia();
997  }
998 
999  if( startMatch && endMatch && len < thr )
1000  {
1001  for( int i = 0; i < 2; i++ )
1002  {
1003  SHAPE_LINE_CHAIN l2 = DIRECTION_45().BuildInitialTrace( p_start, p_end, i );
1004  LINE repl;
1005  repl = LINE( *aLine, l2 );
1006 
1007  if( !m_world->CheckColliding( &repl ) )
1008  {
1009  aLine->SetShape( repl.CLine() );
1010  return true;
1011  }
1012  }
1013  }
1014 
1015  return false;
1016 }
ITEM * findPadOrVia(int aLayer, int aNet, const VECTOR2I &aP) const
bool OfKind(int aKindMask) const
Function OfKind()
Definition: pns_item.h:130
Class DIRECTION_45.
Definition: direction45.h:33
Class SHAPE_LINE_CHAIN.
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:425
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false) const
Function BuildInitialTrace()
Definition: direction45.h:199
ITEM * PNS::OPTIMIZER::findPadOrVia ( int  aLayer,
int  aNet,
const VECTOR2I aP 
) const
private

Definition at line 810 of file pns_optimizer.cpp.

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

Referenced by fanoutCleanup(), and runSmartPads().

811 {
812  JOINT* jt = m_world->FindJoint( aP, aLayer, aNet );
813 
814  if( !jt )
815  return NULL;
816 
817  for( ITEM* item : jt->LinkList() )
818  {
819  if( item->OfKind( ITEM::VIA_T | ITEM::SOLID_T ) )
820  return item;
821  }
822 
823  return NULL;
824 }
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:966
bool PNS::OPTIMIZER::mergeDpSegments ( DIFF_PAIR aPair)
private

Definition at line 1184 of file pns_optimizer.cpp.

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

Referenced by Optimize().

1185 {
1186  int step_p = aPair->CP().SegmentCount() - 2;
1187  int step_n = aPair->CN().SegmentCount() - 2;
1188 
1189  while( 1 )
1190  {
1191  int n_segs_p = aPair->CP().SegmentCount();
1192  int n_segs_n = aPair->CN().SegmentCount();
1193 
1194  int max_step_p = n_segs_p - 2;
1195  int max_step_n = n_segs_n - 2;
1196 
1197  if( step_p > max_step_p )
1198  step_p = max_step_p;
1199 
1200  if( step_n > max_step_n )
1201  step_n = max_step_n;
1202 
1203  if( step_p < 1 && step_n < 1)
1204  break;
1205 
1206  bool found_anything_p = false;
1207  bool found_anything_n = false;
1208 
1209  if( step_p > 1 )
1210  found_anything_p = mergeDpStep( aPair, true, step_p );
1211 
1212  if( step_n > 1 )
1213  found_anything_n = mergeDpStep( aPair, false, step_n );
1214 
1215  if( !found_anything_n && !found_anything_p )
1216  {
1217  step_n--;
1218  step_p--;
1219  }
1220  }
1221  return true;
1222 }
bool mergeDpStep(DIFF_PAIR *aPair, bool aTryP, int step)
bool PNS::OPTIMIZER::mergeDpStep ( DIFF_PAIR aPair,
bool  aTryP,
int  step 
)
private

Definition at line 1122 of file pns_optimizer.cpp.

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().

1123 {
1124  int n = 1;
1125 
1126  SHAPE_LINE_CHAIN currentPath = aTryP ? aPair->CP() : aPair->CN();
1127  SHAPE_LINE_CHAIN coupledPath = aTryP ? aPair->CN() : aPair->CP();
1128 
1129  int n_segs = currentPath.SegmentCount() - 1;
1130 
1131  int64_t clenPre = aPair->CoupledLength( currentPath, coupledPath );
1132  int64_t budget = clenPre / 10; // fixme: come up with somethig more intelligent here...
1133 
1134  while( n < n_segs - step )
1135  {
1136  const SEG s1 = currentPath.CSegment( n );
1137  const SEG s2 = currentPath.CSegment( n + step );
1138 
1139  DIRECTION_45 dir1( s1 );
1140  DIRECTION_45 dir2( s2 );
1141 
1142  if( dir1.IsObtuse( dir2 ) )
1143  {
1144  SHAPE_LINE_CHAIN bypass = DIRECTION_45().BuildInitialTrace( s1.A, s2.B, dir1.IsDiagonal() );
1145  SHAPE_LINE_CHAIN newRef;
1146  SHAPE_LINE_CHAIN newCoup;
1147  int64_t deltaCoupled = -1, deltaUni = -1;
1148 
1149  newRef = currentPath;
1150  newRef.Replace( s1.Index(), s2.Index(), bypass );
1151 
1152  deltaUni = aPair->CoupledLength ( newRef, coupledPath ) - clenPre + budget;
1153 
1154  if ( coupledBypass( m_world, aPair, aTryP, newRef, bypass, coupledPath, newCoup ) )
1155  {
1156  deltaCoupled = aPair->CoupledLength( newRef, newCoup ) - clenPre + budget;
1157 
1158  if( deltaCoupled >= 0 )
1159  {
1160  newRef.Simplify();
1161  newCoup.Simplify();
1162 
1163  aPair->SetShape( newRef, newCoup, !aTryP );
1164  return true;
1165  }
1166  }
1167  else if( deltaUni >= 0 && verifyDpBypass ( m_world, aPair, aTryP, newRef, coupledPath ) )
1168  {
1169  newRef.Simplify();
1170  coupledPath.Simplify();
1171 
1172  aPair->SetShape( newRef, coupledPath, !aTryP );
1173  return true;
1174  }
1175  }
1176 
1177  n++;
1178  }
1179 
1180  return false;
1181 }
int Index() const
Function Index()
Definition: seg.h:300
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
const SEG CSegment(int aIndex) const
Function CSegment()
Class DIRECTION_45.
Definition: direction45.h:33
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)
Definition: seg.h:36
bool verifyDpBypass(NODE *aNode, DIFF_PAIR *aPair, bool aRefIsP, const SHAPE_LINE_CHAIN &aNewRef, const SHAPE_LINE_CHAIN &aNewCoupled)
Class SHAPE_LINE_CHAIN.
VECTOR2I A
Definition: seg.h:46
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false) const
Function BuildInitialTrace()
Definition: direction45.h:199
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Function Replace()
int SegmentCount() const
Function SegmentCount()
VECTOR2I B
Definition: seg.h:47
bool PNS::OPTIMIZER::mergeFull ( LINE aLine)
private

Definition at line 517 of file pns_optimizer.cpp.

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

Referenced by Optimize().

518 {
519  SHAPE_LINE_CHAIN& line = aLine->Line();
520  int step = line.SegmentCount() - 1;
521 
522  int segs_pre = line.SegmentCount();
523 
524  line.Simplify();
525 
526  if( step < 0 )
527  return false;
528 
529  SHAPE_LINE_CHAIN current_path( line );
530 
531  while( 1 )
532  {
533  int n_segs = current_path.SegmentCount();
534  int max_step = n_segs - 2;
535 
536  if( step > max_step )
537  step = max_step;
538 
539  if( step < 1 )
540  break;
541 
542  bool found_anything = mergeStep( aLine, current_path, step );
543 
544  if( !found_anything )
545  step--;
546  }
547 
548  aLine->SetShape( current_path );
549 
550  return current_path.SegmentCount() < segs_pre;
551 }
bool mergeStep(LINE *aLine, SHAPE_LINE_CHAIN &aCurrentLine, int step)
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
Class SHAPE_LINE_CHAIN.
int SegmentCount() const
Function SegmentCount()
bool PNS::OPTIMIZER::mergeObtuse ( LINE aLine)
private

Definition at line 426 of file pns_optimizer.cpp.

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().

427 {
428  SHAPE_LINE_CHAIN& line = aLine->Line();
429 
430  int step = line.PointCount() - 3;
431  int iter = 0;
432  int segs_pre = line.SegmentCount();
433 
434  if( step < 0 )
435  return false;
436 
437  SHAPE_LINE_CHAIN current_path( line );
438 
439  while( 1 )
440  {
441  iter++;
442  int n_segs = current_path.SegmentCount();
443  int max_step = n_segs - 2;
444 
445  if( step > max_step )
446  step = max_step;
447 
448  if( step < 2 )
449  {
450  line = current_path;
451  return current_path.SegmentCount() < segs_pre;
452  }
453 
454  bool found_anything = false;
455  int n = 0;
456 
457  while( n < n_segs - step )
458  {
459  const SEG s1 = current_path.CSegment( n );
460  const SEG s2 = current_path.CSegment( n + step );
461  SEG s1opt, s2opt;
462 
463  if( DIRECTION_45( s1 ).IsObtuse( DIRECTION_45( s2 ) ) )
464  {
465  VECTOR2I ip = *s1.IntersectLines( s2 );
466 
467  if( s1.Distance( ip ) <= 1 || s2.Distance( ip ) <= 1 )
468  {
469  s1opt = SEG( s1.A, ip );
470  s2opt = SEG( ip, s2.B );
471  }
472  else
473  {
474  s1opt = SEG( s1.A, ip );
475  s2opt = SEG( ip, s2.B );
476  }
477 
478  if( DIRECTION_45( s1opt ).IsObtuse( DIRECTION_45( s2opt ) ) )
479  {
480  SHAPE_LINE_CHAIN opt_path;
481  opt_path.Append( s1opt.A );
482  opt_path.Append( s1opt.B );
483  opt_path.Append( s2opt.B );
484 
485  LINE opt_track( *aLine, opt_path );
486 
487  if( !checkColliding( &opt_track ) )
488  {
489  current_path.Replace( s1.Index() + 1, s2.Index(), ip );
490  // removeCachedSegments(aLine, s1.Index(), s2.Index());
491  n_segs = current_path.SegmentCount();
492  found_anything = true;
493  break;
494  }
495  }
496  }
497 
498  n++;
499  }
500 
501  if( !found_anything )
502  {
503  if( step <= 2 )
504  {
505  line = current_path;
506  return line.SegmentCount() < segs_pre;
507  }
508 
509  step--;
510  }
511  }
512 
513  return line.SegmentCount() < segs_pre;
514 }
int Index() const
Function Index()
Definition: seg.h:300
int PointCount() const
Function PointCount()
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Function IntersectLines()
Definition: seg.h:169
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
Class DIRECTION_45.
Definition: direction45.h:33
Definition: seg.h:36
Class SHAPE_LINE_CHAIN.
VECTOR2I A
Definition: seg.h:46
bool checkColliding(ITEM *aItem, bool aUpdateCache=true)
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:185
int SegmentCount() const
Function SegmentCount()
VECTOR2I B
Definition: seg.h:47
bool PNS::OPTIMIZER::mergeStep ( LINE aLine,
SHAPE_LINE_CHAIN aCurrentLine,
int  step 
)
private

Definition at line 581 of file pns_optimizer.cpp.

References SEG::A, SEG::B, PNS::LINE_RESTRICTIONS::Build(), DIRECTION_45::BuildInitialTrace(), PNS::LINE_RESTRICTIONS::Check(), checkColliding(), PNS::COST_ESTIMATOR::CornerCost(), PNS::LINE::CSegment(), SHAPE_LINE_CHAIN::CSegment(), SEG::Index(), m_keepPostures, m_restrictArea, m_restrictAreaActive, m_world, SHAPE_LINE_CHAIN::Replace(), PNS::LINE::SegmentCount(), SHAPE_LINE_CHAIN::SegmentCount(), and SHAPE_LINE_CHAIN::Simplify().

Referenced by mergeFull().

582 {
583  int n = 0;
584  int n_segs = aCurrentPath.SegmentCount();
585 
586  int cost_orig = COST_ESTIMATOR::CornerCost( aCurrentPath );
587 
588  LINE_RESTRICTIONS restr;
589 
590  if( aLine->SegmentCount() < 4 )
591  return false;
592 
593  DIRECTION_45 orig_start( aLine->CSegment( 0 ) );
594  DIRECTION_45 orig_end( aLine->CSegment( -1 ) );
595 
596  restr.Build( m_world, aLine, aCurrentPath, m_restrictArea, m_restrictAreaActive );
597 
598  while( n < n_segs - step )
599  {
600  const SEG s1 = aCurrentPath.CSegment( n );
601  const SEG s2 = aCurrentPath.CSegment( n + step );
602 
603  SHAPE_LINE_CHAIN path[2];
604  SHAPE_LINE_CHAIN* picked = NULL;
605  int cost[2];
606 
607  for( int i = 0; i < 2; i++ )
608  {
609  bool postureMatch = true;
610  SHAPE_LINE_CHAIN bypass = DIRECTION_45().BuildInitialTrace( s1.A, s2.B, i );
611  cost[i] = INT_MAX;
612 
613  bool restrictionsOK = restr.Check ( n, n + step + 1, bypass );
614 
615  if( n == 0 && orig_start != DIRECTION_45( bypass.CSegment( 0 ) ) )
616  postureMatch = false;
617  else if( n == n_segs - step && orig_end != DIRECTION_45( bypass.CSegment( -1 ) ) )
618  postureMatch = false;
619 
620  if( restrictionsOK && (postureMatch || !m_keepPostures) && !checkColliding( aLine, bypass ) )
621  {
622  path[i] = aCurrentPath;
623  path[i].Replace( s1.Index(), s2.Index(), bypass );
624  path[i].Simplify();
625  cost[i] = COST_ESTIMATOR::CornerCost( path[i] );
626  }
627  }
628 
629  if( cost[0] < cost_orig && cost[0] < cost[1] )
630  picked = &path[0];
631  else if( cost[1] < cost_orig )
632  picked = &path[1];
633 
634  if( picked )
635  {
636  n_segs = aCurrentPath.SegmentCount();
637  aCurrentPath = *picked;
638  return true;
639  }
640 
641  n++;
642  }
643 
644  return false;
645 }
int Index() const
Function Index()
Definition: seg.h:300
bool m_restrictAreaActive
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
const SEG CSegment(int aIndex) const
Function CSegment()
Class DIRECTION_45.
Definition: direction45.h:33
Definition: seg.h:36
Class SHAPE_LINE_CHAIN.
VECTOR2I A
Definition: seg.h:46
bool checkColliding(ITEM *aItem, bool aUpdateCache=true)
static int CornerCost(const SEG &aA, const SEG &aB)
Cost Estimator Methods.
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false) const
Function BuildInitialTrace()
Definition: direction45.h:199
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Function Replace()
int SegmentCount() const
Function SegmentCount()
VECTOR2I B
Definition: seg.h:47
bool PNS::OPTIMIZER::Optimize ( LINE aLine,
int  aEffortLevel,
NODE aWorld 
)
static

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

Definition at line 961 of file pns_optimizer.cpp.

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

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

962 {
963  OPTIMIZER opt( aWorld );
964 
965  opt.SetEffortLevel( aEffortLevel );
966  opt.SetCollisionMask( -1 );
967  return opt.Optimize( aLine );
968 }
OPTIMIZER(NODE *aWorld)
Optimizer.
bool PNS::OPTIMIZER::Optimize ( LINE aLine,
LINE aResult = NULL 
)

Definition at line 554 of file pns_optimizer.cpp.

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

555 {
556  if( !aResult )
557  aResult = aLine;
558  else
559  *aResult = *aLine;
560 
561  m_keepPostures = false;
562 
563  bool rv = false;
564 
566  rv |= mergeFull( aResult );
567 
569  rv |= mergeObtuse( aResult );
570 
571  if( m_effortLevel & SMART_PADS )
572  rv |= runSmartPads( aResult );
573 
575  rv |= fanoutCleanup( aResult );
576 
577  return rv;
578 }
bool runSmartPads(LINE *aLine)
bool mergeFull(LINE *aLine)
bool mergeObtuse(LINE *aLine)
bool fanoutCleanup(LINE *aLine)
bool PNS::OPTIMIZER::Optimize ( DIFF_PAIR aPair)

Definition at line 1225 of file pns_optimizer.cpp.

References mergeDpSegments().

1226 {
1227  return mergeDpSegments( aPair );
1228 }
bool mergeDpSegments(DIFF_PAIR *aPair)
BREAKOUT_LIST PNS::OPTIMIZER::ovalBreakouts ( int  aWidth,
const SHAPE aShape,
bool  aPermitDiagonal 
) const
private
OPTIMIZER::BREAKOUT_LIST PNS::OPTIMIZER::rectBreakouts ( int  aWidth,
const SHAPE aShape,
bool  aPermitDiagonal 
) const
private

Definition at line 710 of file pns_optimizer.cpp.

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

Referenced by computeBreakouts().

712 {
713  const SHAPE_RECT* rect = static_cast<const SHAPE_RECT*>(aShape);
714  VECTOR2I s = rect->GetSize(), c = rect->GetPosition() + VECTOR2I( s.x / 2, s.y / 2 );
715  BREAKOUT_LIST breakouts;
716 
717  VECTOR2I d_offset;
718 
719  d_offset.x = ( s.x > s.y ) ? ( s.x - s.y ) / 2 : 0;
720  d_offset.y = ( s.x < s.y ) ? ( s.y - s.x ) / 2 : 0;
721 
722  VECTOR2I d_vert = VECTOR2I( 0, s.y / 2 + aWidth );
723  VECTOR2I d_horiz = VECTOR2I( s.x / 2 + aWidth, 0 );
724 
725  breakouts.push_back( SHAPE_LINE_CHAIN( c, c + d_horiz ) );
726  breakouts.push_back( SHAPE_LINE_CHAIN( c, c - d_horiz ) );
727  breakouts.push_back( SHAPE_LINE_CHAIN( c, c + d_vert ) );
728  breakouts.push_back( SHAPE_LINE_CHAIN( c, c - d_vert ) );
729 
730  if( aPermitDiagonal )
731  {
732  int l = aWidth + std::min( s.x, s.y ) / 2;
733  VECTOR2I d_diag;
734 
735  if( s.x >= s.y )
736  {
737  breakouts.push_back( SHAPE_LINE_CHAIN( c, c + d_offset,
738  c + d_offset + VECTOR2I( l, l ) ) );
739  breakouts.push_back( SHAPE_LINE_CHAIN( c, c + d_offset,
740  c + d_offset - VECTOR2I( -l, l ) ) );
741  breakouts.push_back( SHAPE_LINE_CHAIN( c, c - d_offset,
742  c - d_offset + VECTOR2I( -l, l ) ) );
743  breakouts.push_back( SHAPE_LINE_CHAIN( c, c - d_offset,
744  c - d_offset - VECTOR2I( l, l ) ) );
745  }
746  else
747  {
748  // fixme: this could be done more efficiently
749  breakouts.push_back( SHAPE_LINE_CHAIN( c, c + d_offset,
750  c + d_offset + VECTOR2I( l, l ) ) );
751  breakouts.push_back( SHAPE_LINE_CHAIN( c, c - d_offset,
752  c - d_offset - VECTOR2I( -l, l ) ) );
753  breakouts.push_back( SHAPE_LINE_CHAIN( c, c + d_offset,
754  c + d_offset + VECTOR2I( -l, l ) ) );
755  breakouts.push_back( SHAPE_LINE_CHAIN( c, c - d_offset,
756  c - d_offset - VECTOR2I( l, l ) ) );
757  }
758  }
759 
760  return breakouts;
761 }
VECTOR2< int > VECTOR2I
Definition: vector2d.h:589
const VECTOR2I & GetPosition() const
Function GetPosition()
Definition: shape_rect.h:100
Class SHAPE_LINE_CHAIN.
std::vector< SHAPE_LINE_CHAIN > BREAKOUT_LIST
const VECTOR2I GetSize() const
Function GetSize()
Definition: shape_rect.h:110
#define min(a, b)
Definition: auxiliary.h:85
void PNS::OPTIMIZER::removeCachedSegments ( LINE aLine,
int  aStartVertex = 0,
int  aEndVertex = -1 
)
private

Definition at line 182 of file pns_optimizer.cpp.

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

Referenced by CacheRemove().

183 {
184  if( !aLine->IsLinked() ) return;
185 
186  LINE::SEGMENT_REFS& segs = aLine->LinkedSegments();
187 
188  if( aEndVertex < 0 )
189  aEndVertex += aLine->PointCount();
190 
191  for( int i = aStartVertex; i < aEndVertex - 1; i++ )
192  {
193  SEGMENT* s = segs[i];
194  m_cacheTags.erase( s );
195  m_cache.Remove( s );
196  }
197 }
std::vector< SEGMENT * > SEGMENT_REFS
Definition: pns_line.h:63
CachedItemTags m_cacheTags
Struct SEGMENT is a simple container used when filling areas with segments.
Definition: class_zone.h:57
SHAPE_INDEX_LIST< ITEM * > m_cache
bool PNS::OPTIMIZER::removeUglyCorners ( LINE aLine)
private
bool PNS::OPTIMIZER::runSmartPads ( LINE aLine)
private

Definition at line 934 of file pns_optimizer.cpp.

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().

935 {
936  SHAPE_LINE_CHAIN& line = aLine->Line();
937 
938  if( line.PointCount() < 3 )
939  return false;
940 
941  VECTOR2I p_start = line.CPoint( 0 ), p_end = line.CPoint( -1 );
942 
943  ITEM* startPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_start );
944  ITEM* endPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_end );
945 
946  int vtx = -1;
947 
948  if( startPad )
949  vtx = smartPadsSingle( aLine, startPad, false, 3 );
950 
951  if( endPad )
952  smartPadsSingle( aLine, endPad, true,
953  vtx < 0 ? line.PointCount() - 1 : line.PointCount() - 1 - vtx );
954 
955  aLine->Line().Simplify();
956 
957  return true;
958 }
int PointCount() const
Function PointCount()
ITEM * findPadOrVia(int aLayer, int aNet, const VECTOR2I &aP) const
Class SHAPE_LINE_CHAIN.
int smartPadsSingle(LINE *aLine, ITEM *aPad, bool aEnd, int aEndVertex)
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
void PNS::OPTIMIZER::SetCollisionMask ( int  aMask)
inline

Definition at line 116 of file pns_optimizer.h.

References m_collisionKindMask.

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

117  {
118  m_collisionKindMask = aMask;
119  }
void PNS::OPTIMIZER::SetEffortLevel ( int  aEffort)
inline

Definition at line 121 of file pns_optimizer.h.

References m_effortLevel.

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

122  {
123  m_effortLevel = aEffort;
124  }
void PNS::OPTIMIZER::SetRestrictArea ( const BOX2I aArea)
inline

Definition at line 127 of file pns_optimizer.h.

References m_restrictArea, and m_restrictAreaActive.

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

128  {
129  m_restrictArea = aArea;
130  m_restrictAreaActive = true;
131  }
bool m_restrictAreaActive
void PNS::OPTIMIZER::SetWorld ( NODE aNode)
inline

Definition at line 111 of file pns_optimizer.h.

References m_world.

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

111 { m_world = aNode; }
int PNS::OPTIMIZER::smartPadsSingle ( LINE aLine,
ITEM aPad,
bool  aEnd,
int  aEndVertex 
)
private

Definition at line 827 of file pns_optimizer.cpp.

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(), computeBreakouts(), PNS::COST_ESTIMATOR::CornerCost(), PNS::LINE::CountCorners(), SHAPE_LINE_CHAIN::CSegment(), dyn_cast(), min, PNS::SOLID::Offset(), SHAPE_LINE_CHAIN::Reverse(), SHAPE_LINE_CHAIN::SegmentCount(), PNS::LINE::SetShape(), SHAPE_LINE_CHAIN::Simplify(), and PNS::LINE::Width().

Referenced by runSmartPads().

828 {
829  int min_cost = INT_MAX; // COST_ESTIMATOR::CornerCost( line );
830  int min_len = INT_MAX;
831  DIRECTION_45 dir;
832 
833  const int ForbiddenAngles = DIRECTION_45::ANG_ACUTE | DIRECTION_45::ANG_RIGHT |
835 
836  typedef std::pair<int, SHAPE_LINE_CHAIN> RtVariant;
837  std::vector<RtVariant> variants;
838 
839  SOLID* solid = dyn_cast<SOLID*>( aPad );
840 
841  // don't do auto-neckdown for offset pads
842  if( solid && solid->Offset() != VECTOR2I( 0, 0 ) )
843  return -1;
844 
845 
846  BREAKOUT_LIST breakouts = computeBreakouts( aLine->Width(), aPad, true );
847 
848  SHAPE_LINE_CHAIN line = ( aEnd ? aLine->CLine().Reverse() : aLine->CLine() );
849 
850 
851  int p_end = std::min( aEndVertex, std::min( 3, line.PointCount() - 1 ) );
852 
853  for( int p = 1; p <= p_end; p++ )
854  {
855  for( SHAPE_LINE_CHAIN & l : breakouts ) {
856 
857  for( int diag = 0; diag < 2; diag++ )
858  {
860  SHAPE_LINE_CHAIN connect = dir.BuildInitialTrace( l.CPoint( -1 ),
861  line.CPoint( p ), diag == 0 );
862 
863  DIRECTION_45 dir_bkout( l.CSegment( -1 ) );
864 
865  if(!connect.SegmentCount())
866  continue;
867 
868  int ang1 = dir_bkout.Angle( DIRECTION_45( connect.CSegment( 0 ) ) );
869  int ang2 = 0;
870 
871  if( (ang1 | ang2) & ForbiddenAngles )
872  continue;
873 
874  if( l.Length() > line.Length() )
875  continue;
876 
877  v = l;
878 
879  v.Append( connect );
880 
881  for( int i = p + 1; i < line.PointCount(); i++ )
882  v.Append( line.CPoint( i ) );
883 
884  LINE tmp( *aLine, v );
885  int cc = tmp.CountCorners( ForbiddenAngles );
886 
887  if( cc == 0 )
888  {
889  RtVariant vp;
890  vp.first = p;
891  vp.second = aEnd ? v.Reverse() : v;
892  vp.second.Simplify();
893  variants.push_back( vp );
894  }
895  }
896  }
897  }
898 
899  SHAPE_LINE_CHAIN l_best;
900  bool found = false;
901  int p_best = -1;
902 
903  for( RtVariant& vp : variants )
904  {
905  LINE tmp( *aLine, vp.second );
906  int cost = COST_ESTIMATOR::CornerCost( vp.second );
907  int len = vp.second.Length();
908 
909  if( !checkColliding( &tmp ) )
910  {
911  if( cost < min_cost || ( cost == min_cost && len < min_len ) )
912  {
913  l_best = vp.second;
914  p_best = vp.first;
915  found = true;
916 
917  if( cost == min_cost )
918  min_len = std::min( len, min_len );
919 
920  min_cost = std::min( cost, min_cost );
921  }
922  }
923  }
924 
925  if( found )
926  {
927  aLine->SetShape( l_best );
928  return p_best;
929  }
930 
931  return -1;
932 }
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
VECTOR2< int > VECTOR2I
Definition: vector2d.h:589
Casted dyn_cast(From aObject)
Function dyn_cast()
Definition: typeinfo.h:61
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
const SEG CSegment(int aIndex) const
Function CSegment()
Class DIRECTION_45.
Definition: direction45.h:33
Class SHAPE_LINE_CHAIN.
bool checkColliding(ITEM *aItem, bool aUpdateCache=true)
AngleType Angle(const DIRECTION_45 &aOther) const
Function Angle() Returns the type of angle between directions (this) and aOther.
Definition: direction45.h:146
static int CornerCost(const SEG &aA, const SEG &aB)
Cost Estimator Methods.
std::vector< SHAPE_LINE_CHAIN > BREAKOUT_LIST
BREAKOUT_LIST computeBreakouts(int aWidth, const ITEM *aItem, bool aPermitDiagonal) const
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false) const
Function BuildInitialTrace()
Definition: direction45.h:199
int SegmentCount() const
Function SegmentCount()
#define min(a, b)
Definition: auxiliary.h:85

Member Data Documentation

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

Definition at line 171 of file pns_optimizer.h.

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

CachedItemTags PNS::OPTIMIZER::m_cacheTags
private

Definition at line 174 of file pns_optimizer.h.

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

int PNS::OPTIMIZER::m_collisionKindMask
private

Definition at line 176 of file pns_optimizer.h.

Referenced by checkColliding(), and SetCollisionMask().

int PNS::OPTIMIZER::m_effortLevel
private

Definition at line 177 of file pns_optimizer.h.

Referenced by Optimize(), and SetEffortLevel().

bool PNS::OPTIMIZER::m_keepPostures
private

Definition at line 178 of file pns_optimizer.h.

Referenced by mergeStep(), and Optimize().

BOX2I PNS::OPTIMIZER::m_restrictArea
private

Definition at line 180 of file pns_optimizer.h.

Referenced by mergeStep(), and SetRestrictArea().

bool PNS::OPTIMIZER::m_restrictAreaActive
private

Definition at line 181 of file pns_optimizer.h.

Referenced by mergeStep(), and SetRestrictArea().

NODE* PNS::OPTIMIZER::m_world
private
const int PNS::OPTIMIZER::MaxCachedItems = 256
staticprivate

Definition at line 134 of file pns_optimizer.h.


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