KiCad PCB EDA Suite
PNS::SHOVE Class Reference

SHOVE. More...

#include <pns_shove.h>

Inheritance diagram for PNS::SHOVE:
PNS::ALGO_BASE

Classes

struct  SPRINGBACK_TAG
 

Public Types

enum  SHOVE_STATUS {
  SH_OK = 0, SH_NULL, SH_INCOMPLETE, SH_HEAD_MODIFIED,
  SH_TRY_WALK
}
 

Public Member Functions

 SHOVE (NODE *aWorld, ROUTER *aRouter)
 
 ~SHOVE ()
 
virtual LOGGERLogger () override
 

Returns the logger object, allowing to dump geometry to a file.

More...
 
SHOVE_STATUS ShoveLines (const LINE &aCurrentHead)
 
SHOVE_STATUS ShoveMultiLines (const ITEM_SET &aHeadSet)
 
SHOVE_STATUS ShoveDraggingVia (const VIA_HANDLE aOldVia, const VECTOR2I &aWhere, VIA_HANDLE &aNewVia)
 
SHOVE_STATUS ProcessSingleLine (LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
 
void ForceClearance (bool aEnabled, int aClearance)
 
NODECurrentNode ()
 
const LINE NewHead () const
 
void SetInitialLine (LINE &aInitial)
 
bool AddLockedSpringbackNode (NODE *aNode)
 
void UnlockSpringbackNode (NODE *aNode)
 
bool RewindSpringbackTo (NODE *aNode)
 
ROUTERRouter () const
 

Returns the instance of our router

More...
 
ROUTING_SETTINGSSettings () const
 

Returns current router settings

More...
 
void SetLogger (LOGGER *aLogger)
 
void SetDebugDecorator (DEBUG_DECORATOR *aDecorator)
 Function SetDebugDecorator. More...
 
DEBUG_DECORATORDbg () const
 

Protected Attributes

DEBUG_DECORATORm_debugDecorator
 
ROUTERm_router
 

Private Types

typedef std::vector< SHAPE_LINE_CHAINHULL_SET
 
typedef OPT< LINEOPT_LINE
 
typedef std::pair< LINE, LINELINE_PAIR
 
typedef std::vector< LINE_PAIRLINE_PAIR_VEC
 

Private Member Functions

SHOVE_STATUS processHullSet (LINE &aCurrent, LINE &aObstacle, LINE &aShoved, const HULL_SET &hulls)
 
NODEreduceSpringback (const ITEM_SET &aHeadSet, VIA_HANDLE &aDraggedVia)
 
bool pushSpringback (NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
 
SHOVE_STATUS walkaroundLoneVia (LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
 
bool checkBumpDirection (const LINE &aCurrent, const LINE &aShoved) const
 
SHOVE_STATUS onCollidingArc (LINE &aCurrent, ARC *aObstacleArc)
 
SHOVE_STATUS onCollidingLine (LINE &aCurrent, LINE &aObstacle)
 
SHOVE_STATUS onCollidingSegment (LINE &aCurrent, SEGMENT *aObstacleSeg)
 
SHOVE_STATUS onCollidingSolid (LINE &aCurrent, ITEM *aObstacle)
 
SHOVE_STATUS onCollidingVia (ITEM *aCurrent, VIA *aObstacleVia)
 
SHOVE_STATUS onReverseCollidingVia (LINE &aCurrent, VIA *aObstacleVia)
 
SHOVE_STATUS pushOrShoveVia (VIA *aVia, const VECTOR2I &aForce, int aCurrentRank)
 
OPT_BOX2I totalAffectedArea () const
 
void unwindLineStack (LINKED_ITEM *aSeg)
 
void unwindLineStack (ITEM *aItem)
 
void runOptimizer (NODE *aNode)
 
bool pushLineStack (const LINE &aL, bool aKeepCurrentOnTop=false)
 
void popLineStack ()
 
LINE assembleLine (const LINKED_ITEM *aSeg, int *aIndex=NULL)
 
void replaceItems (ITEM *aOld, std::unique_ptr< ITEM > aNew)
 
void replaceLine (LINE &aOld, LINE &aNew)
 
SHOVE_STATUS shoveIteration (int aIter)
 
SHOVE_STATUS shoveMainLoop ()
 
int getClearance (const ITEM *aA, const ITEM *aB) const
 
void sanityCheck (LINE *aOld, LINE *aNew)
 

Private Attributes

OPT_BOX2I m_affectedArea
 
std::vector< SPRINGBACK_TAGm_nodeStack
 
std::vector< LINEm_lineStack
 
std::vector< LINEm_optimizerQueue
 
NODEm_root
 
NODEm_currentNode
 
int m_restrictSpringbackTagId
 
OPT_LINE m_newHead
 
LOGGER m_logger
 
VIAm_draggedVia
 
int m_iter
 
int m_forceClearance
 
bool m_multiLineMode
 

Detailed Description

SHOVE.

The actual Push and Shove algorithm.

Definition at line 48 of file pns_shove.h.

Member Typedef Documentation

◆ HULL_SET

typedef std::vector<SHAPE_LINE_CHAIN> PNS::SHOVE::HULL_SET
private

Definition at line 94 of file pns_shove.h.

◆ LINE_PAIR

typedef std::pair<LINE, LINE> PNS::SHOVE::LINE_PAIR
private

Definition at line 96 of file pns_shove.h.

◆ LINE_PAIR_VEC

typedef std::vector<LINE_PAIR> PNS::SHOVE::LINE_PAIR_VEC
private

Definition at line 97 of file pns_shove.h.

◆ OPT_LINE

typedef OPT<LINE> PNS::SHOVE::OPT_LINE
private

Definition at line 95 of file pns_shove.h.

Member Enumeration Documentation

◆ SHOVE_STATUS

Enumerator
SH_OK 
SH_NULL 
SH_INCOMPLETE 
SH_HEAD_MODIFIED 
SH_TRY_WALK 

Definition at line 52 of file pns_shove.h.

Constructor & Destructor Documentation

◆ SHOVE()

PNS::SHOVE::SHOVE ( NODE aWorld,
ROUTER aRouter 
)

Definition at line 82 of file pns_shove.cpp.

82  :
83  ALGO_BASE( aRouter )
84 {
85  m_forceClearance = -1;
86  m_root = aWorld;
87  m_currentNode = aWorld;
88  SetDebugDecorator( aRouter->GetInterface()->GetDebugDecorator() );
89 
90  // Initialize other temporary variables:
92  m_iter = 0;
93  m_multiLineMode = false;
94 }
NODE * m_root
Definition: pns_shove.h:154
#define NULL
ALGO_BASE(ROUTER *aRouter)
Definition: pns_algo_base.h:42
VIA * m_draggedVia
Definition: pns_shove.h:161
void SetDebugDecorator(DEBUG_DECORATOR *aDecorator)
Function SetDebugDecorator.
Definition: pns_algo_base.h:72
bool m_multiLineMode
Definition: pns_shove.h:165
NODE * m_currentNode
Definition: pns_shove.h:155
int m_iter
Definition: pns_shove.h:163
int m_forceClearance
Definition: pns_shove.h:164

References PNS::ROUTER_IFACE::GetDebugDecorator(), PNS::ROUTER::GetInterface(), m_currentNode, m_draggedVia, m_forceClearance, m_iter, m_multiLineMode, m_root, NULL, and PNS::ALGO_BASE::SetDebugDecorator().

◆ ~SHOVE()

PNS::SHOVE::~SHOVE ( )

Definition at line 97 of file pns_shove.cpp.

98 {
99 }

Member Function Documentation

◆ AddLockedSpringbackNode()

bool PNS::SHOVE::AddLockedSpringbackNode ( NODE aNode)

Definition at line 1614 of file pns_shove.cpp.

1615 {
1616  SPRINGBACK_TAG sp;
1617  sp.m_node = aNode;
1618  sp.m_locked = true;
1619 
1620  m_nodeStack.push_back(sp);
1621  return true;
1622 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:150

References PNS::SHOVE::SPRINGBACK_TAG::m_locked, PNS::SHOVE::SPRINGBACK_TAG::m_node, and m_nodeStack.

◆ assembleLine()

LINE PNS::SHOVE::assembleLine ( const LINKED_ITEM aSeg,
int *  aIndex = NULL 
)
private

Definition at line 102 of file pns_shove.cpp.

103 {
104  return m_currentNode->AssembleLine( const_cast<LINKED_ITEM*>( aSeg ), aIndex, true );
105 }
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Function AssembleLine()
Definition: pns_node.cpp:893
NODE * m_currentNode
Definition: pns_shove.h:155

References PNS::NODE::AssembleLine(), and m_currentNode.

Referenced by onCollidingArc(), onCollidingSegment(), onReverseCollidingVia(), pushOrShoveVia(), and shoveIteration().

◆ checkBumpDirection()

bool PNS::SHOVE::checkBumpDirection ( const LINE aCurrent,
const LINE aShoved 
) const
private

Definition at line 111 of file pns_shove.cpp.

112 {
113  const SEG& ss = aCurrent.CSegment( 0 );
114 
115  int dist = getClearance( &aCurrent, &aShoved );
116 
117  dist += aCurrent.Width() / 2;
118  dist += aShoved.Width() / 2;
119 
120  const VECTOR2I ps = ss.A - ( ss.B - ss.A ).Resize( dist );
121 
122  return !aShoved.CLine().PointOnEdge( ps );
123 }
static const int dist[10][10]
Definition: ar_matrix.cpp:326
Definition: seg.h:39
VECTOR2I A
Definition: seg.h:47
int getClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:66
VECTOR2I B
Definition: seg.h:48

References SEG::A, SEG::B, PNS::LINE::CLine(), PNS::LINE::CSegment(), dist, getClearance(), SHAPE_LINE_CHAIN::PointOnEdge(), and PNS::LINE::Width().

Referenced by processHullSet().

◆ CurrentNode()

NODE * PNS::SHOVE::CurrentNode ( )

Definition at line 1593 of file pns_shove.cpp.

1594 {
1595  return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
1596 }
NODE * m_root
Definition: pns_shove.h:154
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:150

References m_nodeStack, and m_root.

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

◆ Dbg()

◆ ForceClearance()

void PNS::SHOVE::ForceClearance ( bool  aEnabled,
int  aClearance 
)
inline

Definition at line 75 of file pns_shove.h.

76  {
77  if( aEnabled )
78  m_forceClearance = aClearance;
79  else
80  m_forceClearance = -1;
81  }
int m_forceClearance
Definition: pns_shove.h:164

References m_forceClearance.

Referenced by PNS::DIFF_PAIR_PLACER::attemptWalk().

◆ getClearance()

int PNS::SHOVE::getClearance ( const ITEM aA,
const ITEM aB 
) const
private

Definition at line 66 of file pns_shove.cpp.

67 {
68  if( m_forceClearance >= 0 )
69  return m_forceClearance;
70 
71  return m_currentNode->GetClearance( aA, aB );
72 }
int GetClearance(const ITEM *aA, const ITEM *aB) const
Returns the expected clearance between items a and b.
Definition: pns_node.cpp:97
NODE * m_currentNode
Definition: pns_shove.h:155
int m_forceClearance
Definition: pns_shove.h:164

References PNS::NODE::GetClearance(), m_currentNode, and m_forceClearance.

Referenced by checkBumpDirection(), onCollidingVia(), ProcessSingleLine(), and walkaroundLoneVia().

◆ Logger()

virtual LOGGER* PNS::SHOVE::Logger ( )
inlineoverridevirtual

Returns the logger object, allowing to dump geometry to a file.

Reimplemented from PNS::ALGO_BASE.

Definition at line 64 of file pns_shove.h.

65  {
66  return &m_logger;
67  }
LOGGER m_logger
Definition: pns_shove.h:160

References m_logger.

◆ NewHead()

const LINE PNS::SHOVE::NewHead ( ) const

Definition at line 1599 of file pns_shove.cpp.

1600 {
1601  assert( m_newHead );
1602 
1603  return *m_newHead;
1604 }
OPT_LINE m_newHead
Definition: pns_shove.h:158

References m_newHead.

◆ onCollidingArc()

SHOVE::SHOVE_STATUS PNS::SHOVE::onCollidingArc ( LINE aCurrent,
ARC aObstacleArc 
)
private

Definition at line 384 of file pns_shove.cpp.

385 {
386  int segIndex;
387  LINE obstacleLine = assembleLine( aObstacleArc, &segIndex );
388  LINE shovedLine( obstacleLine );
389  ARC tmp( *aObstacleArc );
390 
391  if( obstacleLine.HasLockedSegments() )
392  return SH_TRY_WALK;
393 
394  SHOVE_STATUS rv = ProcessSingleLine( aCurrent, obstacleLine, shovedLine );
395 
396  const double extensionWalkThreshold = 1.0;
397 
398  double obsLen = obstacleLine.CLine().Length();
399  double shovedLen = shovedLine.CLine().Length();
400  double extensionFactor = 0.0;
401 
402  if( obsLen != 0.0f )
403  extensionFactor = shovedLen / obsLen - 1.0;
404 
405  if( extensionFactor > extensionWalkThreshold )
406  return SH_TRY_WALK;
407 
408  assert( obstacleLine.LayersOverlap( &shovedLine ) );
409 
410 #ifdef DEBUG
411  m_logger.NewGroup( "on-colliding-segment", m_iter );
412  m_logger.Log( &tmp, 0, "obstacle-segment" );
413  m_logger.Log( &aCurrent, 1, "current-line" );
414  m_logger.Log( &obstacleLine, 2, "obstacle-line" );
415  m_logger.Log( &shovedLine, 3, "shoved-line" );
416 #endif
417 
418  if( rv == SH_OK )
419  {
420  if( shovedLine.Marker() & MK_HEAD )
421  {
422  if( m_multiLineMode )
423  return SH_INCOMPLETE;
424 
425  m_newHead = shovedLine;
426  }
427 
428  int rank = aCurrent.Rank();
429  shovedLine.SetRank( rank - 1 );
430 
431  sanityCheck( &obstacleLine, &shovedLine );
432  replaceLine( obstacleLine, shovedLine );
433 
434  if( !pushLineStack( shovedLine ) )
435  rv = SH_INCOMPLETE;
436  }
437 
438  return rv;
439 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1006
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:102
SHOVE_STATUS ProcessSingleLine(LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
Definition: pns_shove.cpp:265
void NewGroup(const std::string &aName, int aIter=0)
Definition: pns_logger.cpp:55
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:75
void Log(const ITEM *aItem, int aKind=0, const std::string &aName=std::string())
Definition: pns_logger.cpp:75
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:56
bool m_multiLineMode
Definition: pns_shove.h:165
OPT_LINE m_newHead
Definition: pns_shove.h:158
LOGGER m_logger
Definition: pns_shove.h:160
int m_iter
Definition: pns_shove.h:163

References assembleLine(), PNS::LINE::CLine(), PNS::LINE::HasLockedSegments(), PNS::ITEM::LayersOverlap(), SHAPE_LINE_CHAIN::Length(), PNS::LOGGER::Log(), m_iter, m_logger, m_multiLineMode, m_newHead, PNS::LINE::Marker(), PNS::MK_HEAD, PNS::LOGGER::NewGroup(), ProcessSingleLine(), pushLineStack(), PNS::LINE::Rank(), replaceLine(), sanityCheck(), PNS::LINE::SetRank(), SH_INCOMPLETE, SH_OK, and SH_TRY_WALK.

Referenced by shoveIteration().

◆ onCollidingLine()

SHOVE::SHOVE_STATUS PNS::SHOVE::onCollidingLine ( LINE aCurrent,
LINE aObstacle 
)
private

Definition at line 445 of file pns_shove.cpp.

446 {
447  LINE shovedLine( aObstacle );
448 
449  SHOVE_STATUS rv = ProcessSingleLine( aCurrent, aObstacle, shovedLine );
450 
451  #ifdef DEBUG
452  m_logger.NewGroup( "on-colliding-line", m_iter );
453  m_logger.Log( &aObstacle, 0, "obstacle-line" );
454  m_logger.Log( &aCurrent, 1, "current-line" );
455  m_logger.Log( &shovedLine, 3, "shoved-line" );
456  #endif
457 
458  if( rv == SH_OK )
459  {
460  if( shovedLine.Marker() & MK_HEAD )
461  {
462  if( m_multiLineMode )
463  return SH_INCOMPLETE;
464 
465  m_newHead = shovedLine;
466  }
467 
468  sanityCheck( &aObstacle, &shovedLine );
469  replaceLine( aObstacle, shovedLine );
470 
471  int rank = aObstacle.Rank();
472  shovedLine.SetRank( rank - 1 );
473 
474 
475  if( !pushLineStack( shovedLine ) )
476  {
477  rv = SH_INCOMPLETE;
478  }
479  }
480 
481  return rv;
482 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1006
SHOVE_STATUS ProcessSingleLine(LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
Definition: pns_shove.cpp:265
void NewGroup(const std::string &aName, int aIter=0)
Definition: pns_logger.cpp:55
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:75
void Log(const ITEM *aItem, int aKind=0, const std::string &aName=std::string())
Definition: pns_logger.cpp:75
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:56
bool m_multiLineMode
Definition: pns_shove.h:165
OPT_LINE m_newHead
Definition: pns_shove.h:158
LOGGER m_logger
Definition: pns_shove.h:160
int m_iter
Definition: pns_shove.h:163

References PNS::LOGGER::Log(), m_iter, m_logger, m_multiLineMode, m_newHead, PNS::LINE::Marker(), PNS::MK_HEAD, PNS::LOGGER::NewGroup(), ProcessSingleLine(), pushLineStack(), PNS::LINE::Rank(), replaceLine(), sanityCheck(), PNS::LINE::SetRank(), SH_INCOMPLETE, and SH_OK.

Referenced by shoveIteration().

◆ onCollidingSegment()

SHOVE::SHOVE_STATUS PNS::SHOVE::onCollidingSegment ( LINE aCurrent,
SEGMENT aObstacleSeg 
)
private

Definition at line 323 of file pns_shove.cpp.

324 {
325  int segIndex;
326  LINE obstacleLine = assembleLine( aObstacleSeg, &segIndex );
327  LINE shovedLine( obstacleLine );
328  SEGMENT tmp( *aObstacleSeg );
329 
330  if( obstacleLine.HasLockedSegments() )
331  return SH_TRY_WALK;
332 
333  SHOVE_STATUS rv = ProcessSingleLine( aCurrent, obstacleLine, shovedLine );
334 
335  const double extensionWalkThreshold = 1.0;
336 
337  double obsLen = obstacleLine.CLine().Length();
338  double shovedLen = shovedLine.CLine().Length();
339  double extensionFactor = 0.0;
340 
341  if( obsLen != 0.0f )
342  extensionFactor = shovedLen / obsLen - 1.0;
343 
344  if( extensionFactor > extensionWalkThreshold )
345  return SH_TRY_WALK;
346 
347  assert( obstacleLine.LayersOverlap( &shovedLine ) );
348 
349 #ifdef DEBUG
350  m_logger.NewGroup( "on-colliding-segment", m_iter );
351  m_logger.Log( &tmp, 0, "obstacle-segment" );
352  m_logger.Log( &aCurrent, 1, "current-line" );
353  m_logger.Log( &obstacleLine, 2, "obstacle-line" );
354  m_logger.Log( &shovedLine, 3, "shoved-line" );
355 #endif
356 
357  if( rv == SH_OK )
358  {
359  if( shovedLine.Marker() & MK_HEAD )
360  {
361  if( m_multiLineMode )
362  return SH_INCOMPLETE;
363 
364  m_newHead = shovedLine;
365  }
366 
367  int rank = aCurrent.Rank();
368  shovedLine.SetRank( rank - 1 );
369 
370  sanityCheck( &obstacleLine, &shovedLine );
371  replaceLine( obstacleLine, shovedLine );
372 
373  if( !pushLineStack( shovedLine ) )
374  rv = SH_INCOMPLETE;
375  }
376 
377  return rv;
378 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1006
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:102
SHOVE_STATUS ProcessSingleLine(LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
Definition: pns_shove.cpp:265
void NewGroup(const std::string &aName, int aIter=0)
Definition: pns_logger.cpp:55
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:75
void Log(const ITEM *aItem, int aKind=0, const std::string &aName=std::string())
Definition: pns_logger.cpp:75
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:56
bool m_multiLineMode
Definition: pns_shove.h:165
OPT_LINE m_newHead
Definition: pns_shove.h:158
LOGGER m_logger
Definition: pns_shove.h:160
int m_iter
Definition: pns_shove.h:163

References assembleLine(), PNS::LINE::CLine(), PNS::LINE::HasLockedSegments(), PNS::ITEM::LayersOverlap(), SHAPE_LINE_CHAIN::Length(), PNS::LOGGER::Log(), m_iter, m_logger, m_multiLineMode, m_newHead, PNS::LINE::Marker(), PNS::MK_HEAD, PNS::LOGGER::NewGroup(), ProcessSingleLine(), pushLineStack(), PNS::LINE::Rank(), replaceLine(), sanityCheck(), PNS::LINE::SetRank(), SH_INCOMPLETE, SH_OK, and SH_TRY_WALK.

Referenced by shoveIteration().

◆ onCollidingSolid()

SHOVE::SHOVE_STATUS PNS::SHOVE::onCollidingSolid ( LINE aCurrent,
ITEM aObstacle 
)
private

Definition at line 488 of file pns_shove.cpp.

489 {
490  WALKAROUND walkaround( m_currentNode, Router() );
491  LINE walkaroundLine( aCurrent );
492 
493  if( aCurrent.EndsWithVia() )
494  {
495  VIA vh = aCurrent.Via();
496  VIA* via = NULL;
497  JOINT* jtStart = m_currentNode->FindJoint( vh.Pos(), &aCurrent );
498 
499  if( !jtStart )
500  return SH_INCOMPLETE;
501 
502  for( ITEM* item : jtStart->LinkList() )
503  {
504  if( item->OfKind( ITEM::VIA_T ) )
505  {
506  via = (VIA*) item;
507  break;
508  }
509  }
510 
511  if( via && m_currentNode->CheckColliding( via, aObstacle ) )
512  return onCollidingVia( aObstacle, via );
513  }
514 
515  TOPOLOGY topo( m_currentNode );
516 
517  std::set<ITEM*> cluster = topo.AssembleCluster( aObstacle, aCurrent.Layers().Start() );
518 
519 #ifdef DEBUG
520  m_logger.NewGroup( "on-colliding-solid-cluster", m_iter );
521  for( ITEM* item : cluster )
522  {
523  m_logger.Log( item, 0, "cluster-entry" );
524  }
525 #endif
526 
527  walkaround.SetSolidsOnly( false );
528  walkaround.RestrictToSet( true, cluster );
529  walkaround.SetIterationLimit( 16 ); // fixme: make configurable
530 
531  int currentRank = aCurrent.Rank();
532  int nextRank;
533 
534  bool success = false;
535 
536  for( int attempt = 0; attempt < 2; attempt++ )
537  {
538  if( attempt == 1 || Settings().JumpOverObstacles() )
539  {
540 
541  nextRank = currentRank - 1;
542  walkaround.SetSingleDirection( true );
543  }
544  else
545  {
546  nextRank = currentRank + 10000;
547  walkaround.SetSingleDirection( false );
548  }
549 
550 
551  WALKAROUND::WALKAROUND_STATUS status = walkaround.Route( aCurrent, walkaroundLine, false );
552 
553  if( status != WALKAROUND::DONE )
554  continue;
555 
556  walkaroundLine.ClearSegmentLinks();
557  walkaroundLine.Unmark();
558  walkaroundLine.Line().Simplify();
559 
560  if( walkaroundLine.HasLoops() )
561  continue;
562 
563  if( aCurrent.Marker() & MK_HEAD )
564  {
565  walkaroundLine.Mark( MK_HEAD );
566 
567  if( m_multiLineMode )
568  continue;
569 
570  m_newHead = walkaroundLine;
571  }
572 
573  sanityCheck( &aCurrent, &walkaroundLine );
574 
575  if( !m_lineStack.empty() )
576  {
577  LINE lastLine = m_lineStack.front();
578 
579  if( m_currentNode->CheckColliding( &lastLine, &walkaroundLine ) )
580  {
581  LINE dummy( lastLine );
582 
583  if( ProcessSingleLine( walkaroundLine, lastLine, dummy ) == SH_OK )
584  {
585  success = true;
586  break;
587  }
588  } else {
589  success = true;
590  break;
591  }
592  }
593  }
594 
595  if(!success)
596  return SH_INCOMPLETE;
597 
598  replaceLine( aCurrent, walkaroundLine );
599  walkaroundLine.SetRank( nextRank );
600 
601 #ifdef DEBUG
602  m_logger.NewGroup( "on-colliding-solid", m_iter );
603  m_logger.Log( aObstacle, 0, "obstacle-solid" );
604  m_logger.Log( &aCurrent, 1, "current-line" );
605  m_logger.Log( &walkaroundLine, 3, "walk-line" );
606 #endif
607 
608  popLineStack();
609 
610  if( !pushLineStack( walkaroundLine ) )
611  return SH_INCOMPLETE;
612 
613  return SH_OK;
614 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1006
ROUTER * Router() const
Returns the instance of our router
Definition: pns_algo_base.h:51
void popLineStack()
Definition: pns_shove.cpp:1025
SHOVE_STATUS ProcessSingleLine(LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
Definition: pns_shove.cpp:265
ROUTING_SETTINGS & Settings() const
Returns current router settings
void NewGroup(const std::string &aName, int aIter=0)
Definition: pns_logger.cpp:55
#define NULL
SHOVE_STATUS onCollidingVia(ITEM *aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:813
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:75
void Log(const ITEM *aItem, int aKind=0, const std::string &aName=std::string())
Definition: pns_logger.cpp:75
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:1027
static LIB_PART * dummy()
Used to draw a dummy shape when a LIB_PART is not found in library.
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:427
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:56
bool m_multiLineMode
Definition: pns_shove.h:165
OPT_LINE m_newHead
Definition: pns_shove.h:158
std::vector< LINE > m_lineStack
Definition: pns_shove.h:151
NODE * m_currentNode
Definition: pns_shove.h:155
LOGGER m_logger
Definition: pns_shove.h:160
int m_iter
Definition: pns_shove.h:163

References PNS::TOPOLOGY::AssembleCluster(), PNS::NODE::CheckColliding(), PNS::LINE::ClearSegmentLinks(), PNS::WALKAROUND::DONE, dummy(), PNS::LINE::EndsWithVia(), PNS::NODE::FindJoint(), PNS::LINE::HasLoops(), PNS::ITEM::Layers(), PNS::LINE::Line(), PNS::JOINT::LinkList(), PNS::LOGGER::Log(), m_currentNode, m_iter, m_lineStack, m_logger, m_multiLineMode, m_newHead, PNS::LINE::Mark(), PNS::LINE::Marker(), PNS::MK_HEAD, PNS::LOGGER::NewGroup(), NULL, onCollidingVia(), popLineStack(), PNS::VIA::Pos(), ProcessSingleLine(), pushLineStack(), PNS::LINE::Rank(), replaceLine(), PNS::WALKAROUND::RestrictToSet(), PNS::WALKAROUND::Route(), PNS::ALGO_BASE::Router(), sanityCheck(), PNS::WALKAROUND::SetIterationLimit(), PNS::LINE::SetRank(), PNS::WALKAROUND::SetSingleDirection(), PNS::WALKAROUND::SetSolidsOnly(), PNS::ALGO_BASE::Settings(), SH_INCOMPLETE, SH_OK, SHAPE_LINE_CHAIN::Simplify(), LAYER_RANGE::Start(), PNS::LINE::Unmark(), PNS::LINE::Via(), and PNS::ITEM::VIA_T.

Referenced by shoveIteration().

◆ onCollidingVia()

SHOVE::SHOVE_STATUS PNS::SHOVE::onCollidingVia ( ITEM aCurrent,
VIA aObstacleVia 
)
private

Definition at line 813 of file pns_shove.cpp.

814 {
815  int clearance = getClearance( aCurrent, aObstacleVia ) ;
816  LINE_PAIR_VEC draggedLines;
817  bool lineCollision = false;
818  bool viaCollision = false;
819  bool holeCollision = false;
820  LINE* currentLine = NULL;
821  VECTOR2I mtvLine; // Minimum translation vector to correct line collisions
822  VECTOR2I mtvVia; // MTV to correct via collisions
823  VECTOR2I mtvHoles; // MTV to correct hole collisions
824  VECTOR2I mtvSolid; // MTV to correct solid collisions
825  VECTOR2I mtv; // Union of relevant MTVs (will correct all collisions)
826  int rank = -1;
827 
828  if( aCurrent->OfKind( ITEM::LINE_T ) )
829  {
830 #ifdef DEBUG
831  m_logger.NewGroup( "push-via-by-line", m_iter );
832  m_logger.Log( aCurrent, 4, "current" );
833 #endif
834 
835  currentLine = (LINE*) aCurrent;
836  lineCollision = CollideShapes( aObstacleVia->Shape(), currentLine->Shape(),
837  clearance + currentLine->Width() / 2 + PNS_HULL_MARGIN,
838  true, mtvLine );
839 
840  if( currentLine->EndsWithVia() )
841  {
842  int currentNet = currentLine->Net();
843  int obstacleNet = aObstacleVia->Net();
844 
845  if( currentNet != obstacleNet && currentNet >= 0 && obstacleNet >= 0 )
846  {
847  viaCollision = CollideShapes( currentLine->Via().Shape(), aObstacleVia->Shape(),
848  clearance + PNS_HULL_MARGIN, true, mtvVia );
849  }
850 
851  // hole-to-hole is a mechanical constraint (broken drill bits), not an electrical
852  // one, so it has to be checked irrespective of matching nets.
853 
854  // temporarily removed hole-to-hole collision check due to conflicts with the springback algorithm...
855  // we need to figure out a better solution here - TW
856  holeCollision = false; //rr->CollideHoles( &currentLine->Via(), aObstacleVia, true, &mtvHoles );
857  }
858 
859  // These aren't /actually/ lengths as we don't bother to do the square-root part,
860  // but we're just comparing them to each other so it's faster this way.
861  ecoord lineMTVLength = lineCollision ? mtvLine.SquaredEuclideanNorm() : 0;
862  ecoord viaMTVLength = viaCollision ? mtvVia.SquaredEuclideanNorm() : 0;
863  ecoord holeMTVLength = holeCollision ? mtvHoles.SquaredEuclideanNorm() : 0;
864 
865  if( lineMTVLength >= viaMTVLength && lineMTVLength >= holeMTVLength )
866  mtv = mtvLine;
867  else if( viaMTVLength >= lineMTVLength && viaMTVLength >= holeMTVLength )
868  mtv = mtvVia;
869  else
870  mtv = mtvHoles;
871 
872  rank = currentLine->Rank();
873  }
874  else if( aCurrent->OfKind( ITEM::SOLID_T ) )
875  {
876  CollideShapes( aObstacleVia->Shape(), aCurrent->Shape(),
877  clearance + PNS_HULL_MARGIN, true, mtvSolid );
878  mtv = -mtvSolid;
879  rank = aCurrent->Rank() + 10000;
880  }
881 
882  return pushOrShoveVia( aObstacleVia, mtv, rank );
883 }
#define PNS_HULL_MARGIN
LINE.
Definition: pns_line.h:59
extended_type SquaredEuclideanNorm() const
Function Squared Euclidean Norm computes the squared euclidean norm of the vector,...
Definition: vector2d.h:306
SHOVE_STATUS pushOrShoveVia(VIA *aVia, const VECTOR2I &aForce, int aCurrentRank)
Definition: pns_shove.cpp:686
std::vector< LINE_PAIR > LINE_PAIR_VEC
Definition: pns_shove.h:97
void NewGroup(const std::string &aName, int aIter=0)
Definition: pns_logger.cpp:55
#define NULL
VECTOR2I::extended_type ecoord
void Log(const ITEM *aItem, int aKind=0, const std::string &aName=std::string())
Definition: pns_logger.cpp:75
bool CollideShapes(const SHAPE *aA, const SHAPE *aB, int aClearance, bool aNeedMTV, VECTOR2I &aMTV)
int getClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:66
LOGGER m_logger
Definition: pns_shove.h:160
int m_iter
Definition: pns_shove.h:163

References CollideShapes(), PNS::LINE::EndsWithVia(), getClearance(), PNS::ITEM::LINE_T, PNS::LOGGER::Log(), m_iter, m_logger, PNS::ITEM::Net(), PNS::LOGGER::NewGroup(), NULL, PNS::ITEM::OfKind(), PNS_HULL_MARGIN, pushOrShoveVia(), PNS::ITEM::Rank(), PNS::LINE::Rank(), PNS::LINE::Shape(), PNS::VIA::Shape(), PNS::ITEM::Shape(), PNS::ITEM::SOLID_T, VECTOR2< T >::SquaredEuclideanNorm(), PNS::LINE::Via(), and PNS::LINE::Width().

Referenced by onCollidingSolid(), and shoveIteration().

◆ onReverseCollidingVia()

SHOVE::SHOVE_STATUS PNS::SHOVE::onReverseCollidingVia ( LINE aCurrent,
VIA aObstacleVia 
)
private

Definition at line 889 of file pns_shove.cpp.

890 {
891  int n = 0;
892  LINE cur( aCurrent );
893  cur.ClearSegmentLinks();
894 
895  JOINT* jt = m_currentNode->FindJoint( aObstacleVia->Pos(), aObstacleVia );
896  LINE shoved( aCurrent );
897  shoved.ClearSegmentLinks();
898 
899  cur.RemoveVia();
900  unwindLineStack( &aCurrent );
901 
902  for( ITEM* item : jt->LinkList() )
903  {
904  if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->LayersOverlap( &aCurrent ) )
905  {
906  LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
907  LINE head = assembleLine( li );
908 
909  head.AppendVia( *aObstacleVia );
910 
911  SHOVE_STATUS st = ProcessSingleLine( head, cur, shoved );
912 
913  if( st != SH_OK )
914  {
915 #ifdef DEBUG
916  m_logger.NewGroup( "on-reverse-via-fail-shove", m_iter );
917  m_logger.Log( aObstacleVia, 0, "the-via" );
918  m_logger.Log( &aCurrent, 1, "current-line" );
919  m_logger.Log( &shoved, 3, "shoved-line" );
920 #endif
921 
922  return st;
923  }
924 
925  cur.SetShape( shoved.CLine() );
926  n++;
927  }
928  }
929 
930  if( !n )
931  {
932 #ifdef DEBUG
933  m_logger.NewGroup( "on-reverse-via-fail-lonevia", m_iter );
934  m_logger.Log( aObstacleVia, 0, "the-via" );
935  m_logger.Log( &aCurrent, 1, "current-line" );
936 #endif
937 
938  LINE head( aCurrent );
939  head.Line().Clear();
940  head.AppendVia( *aObstacleVia );
941  head.ClearSegmentLinks();
942 
943  SHOVE_STATUS st = ProcessSingleLine( head, aCurrent, shoved );
944 
945  if( st != SH_OK )
946  return st;
947 
948  cur.SetShape( shoved.CLine() );
949  }
950 
951  if( aCurrent.EndsWithVia() )
952  shoved.AppendVia( aCurrent.Via() );
953 
954 #ifdef DEBUG
955  m_logger.NewGroup( "on-reverse-via", m_iter );
956  m_logger.Log( aObstacleVia, 0, "the-via" );
957  m_logger.Log( &aCurrent, 1, "current-line" );
958  m_logger.Log( &shoved, 3, "shoved-line" );
959 #endif
960  int currentRank = aCurrent.Rank();
961  replaceLine( aCurrent, shoved );
962 
963  if( !pushLineStack( shoved ) )
964  return SH_INCOMPLETE;
965 
966  shoved.SetRank( currentRank );
967 
968  return SH_OK;
969 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1006
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:102
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:972
SHOVE_STATUS ProcessSingleLine(LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
Definition: pns_shove.cpp:265
void NewGroup(const std::string &aName, int aIter=0)
Definition: pns_logger.cpp:55
void Log(const ITEM *aItem, int aKind=0, const std::string &aName=std::string())
Definition: pns_logger.cpp:75
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:1027
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:56
NODE * m_currentNode
Definition: pns_shove.h:155
LOGGER m_logger
Definition: pns_shove.h:160
int m_iter
Definition: pns_shove.h:163

References PNS::LINE::AppendVia(), PNS::ITEM::ARC_T, assembleLine(), SHAPE_LINE_CHAIN::Clear(), PNS::LINE::ClearSegmentLinks(), PNS::LINE::CLine(), PNS::LINE::EndsWithVia(), PNS::NODE::FindJoint(), PNS::LINE::Line(), PNS::JOINT::LinkList(), PNS::LOGGER::Log(), m_currentNode, m_iter, m_logger, PNS::LOGGER::NewGroup(), PNS::VIA::Pos(), ProcessSingleLine(), pushLineStack(), PNS::LINE::Rank(), PNS::LINE::RemoveVia(), replaceLine(), PNS::ITEM::SEGMENT_T, PNS::LINE::SetRank(), PNS::LINE::SetShape(), SH_INCOMPLETE, SH_OK, unwindLineStack(), and PNS::LINE::Via().

Referenced by shoveIteration().

◆ popLineStack()

void PNS::SHOVE::popLineStack ( )
private

Definition at line 1025 of file pns_shove.cpp.

1026 {
1027  LINE& l = m_lineStack.back();
1028 
1029  for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end(); )
1030  {
1031  bool found = false;
1032 
1033  for( auto s : l.LinkedSegments() )
1034  {
1035  if( i->ContainsSegment( s ) )
1036  {
1037  i = m_optimizerQueue.erase( i );
1038  found = true;
1039  break;
1040  }
1041  }
1042 
1043  if( !found )
1044  i++;
1045  }
1046 
1047  m_lineStack.pop_back();
1048 }
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:152
std::vector< LINE > m_lineStack
Definition: pns_shove.h:151

References PNS::LINE::LinkedSegments(), m_lineStack, and m_optimizerQueue.

Referenced by onCollidingSolid(), and shoveIteration().

◆ processHullSet()

SHOVE::SHOVE_STATUS PNS::SHOVE::processHullSet ( LINE aCurrent,
LINE aObstacle,
LINE aShoved,
const HULL_SET hulls 
)
private

Definition at line 162 of file pns_shove.cpp.

164 {
165  const SHAPE_LINE_CHAIN& obs = aObstacle.CLine();
166 
167  int attempt;
168 
169  for( attempt = 0; attempt < 4; attempt++ )
170  {
171  bool invertTraversal = ( attempt >= 2 );
172  bool clockwise = attempt % 2;
173  int vFirst = -1, vLast = -1;
174 
175  SHAPE_LINE_CHAIN path;
176  LINE l( aObstacle );
177 
178  for( int i = 0; i < (int) aHulls.size(); i++ )
179  {
180  const SHAPE_LINE_CHAIN& hull = aHulls[invertTraversal ? aHulls.size() - 1 - i : i];
181 
182  if( ! l.Walkaround( hull, path, clockwise ) )
183  return SH_INCOMPLETE;
184 
185  path.Simplify();
186  l.SetShape( path );
187  }
188 
189  for( int i = 0; i < std::min( path.PointCount(), obs.PointCount() ); i++ )
190  {
191  if( path.CPoint( i ) != obs.CPoint( i ) )
192  {
193  vFirst = i;
194  break;
195  }
196  }
197 
198  int k = obs.PointCount() - 1;
199  for( int i = path.PointCount() - 1; i >= 0 && k >= 0; i--, k-- )
200  {
201  if( path.CPoint( i ) != obs.CPoint( k ) )
202  {
203  vLast = i;
204  break;
205  }
206  }
207 
208  if( ( vFirst < 0 || vLast < 0 ) && !path.CompareGeometry( aObstacle.CLine() ) )
209  {
210  wxLogTrace( "PNS", "attempt %d fail vfirst-last", attempt );
211  continue;
212  }
213 
214  if( path.CPoint( -1 ) != obs.CPoint( -1 ) || path.CPoint( 0 ) != obs.CPoint( 0 ) )
215  {
216  wxLogTrace( "PNS", "attempt %d fail vend-start\n", attempt );
217  continue;
218  }
219 
220  if( !checkBumpDirection( aCurrent, l ) )
221  {
222  wxLogTrace( "PNS", "attempt %d fail direction-check", attempt );
223  aShoved.SetShape( l.CLine() );
224 
225  continue;
226  }
227 
228  if( path.SelfIntersecting() )
229  {
230  wxLogTrace( "PNS", "attempt %d fail self-intersect", attempt );
231  continue;
232  }
233 
234  bool colliding = m_currentNode->CheckColliding( &l, &aCurrent, ITEM::ANY_T, m_forceClearance );
235 
236  if( ( aCurrent.Marker() & MK_HEAD ) && !colliding )
237  {
238  JOINT* jtStart = m_currentNode->FindJoint( aCurrent.CPoint( 0 ), &aCurrent );
239 
240  for( ITEM* item : jtStart->LinkList() )
241  {
242  if( m_currentNode->CheckColliding( item, &l ) )
243  colliding = true;
244  }
245  }
246 
247  if( colliding )
248  {
249  wxLogTrace( "PNS", "attempt %d fail coll-check", attempt );
250  continue;
251  }
252 
253  aShoved.SetShape( l.CLine() );
254 
255  return SH_OK;
256  }
257 
258  return SH_INCOMPLETE;
259 }
int PointCount() const
Function PointCount()
const OPT< INTERSECTION > SelfIntersecting() const
Function SelfIntersecting()
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
const VECTOR2I & CPoint(int aIndex) const
Function Point()
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:1027
bool checkBumpDirection(const LINE &aCurrent, const LINE &aShoved) const
Definition: pns_shove.cpp:111
SHAPE_LINE_CHAIN.
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:427
NODE * m_currentNode
Definition: pns_shove.h:155
int m_forceClearance
Definition: pns_shove.h:164
bool CompareGeometry(const SHAPE_LINE_CHAIN &aOther) const

References PNS::ITEM::ANY_T, checkBumpDirection(), PNS::NODE::CheckColliding(), PNS::LINE::CLine(), SHAPE_LINE_CHAIN::CompareGeometry(), PNS::LINE::CPoint(), SHAPE_LINE_CHAIN::CPoint(), PNS::NODE::FindJoint(), PNS::JOINT::LinkList(), m_currentNode, m_forceClearance, PNS::LINE::Marker(), PNS::MK_HEAD, SHAPE_LINE_CHAIN::PointCount(), SHAPE_LINE_CHAIN::SelfIntersecting(), PNS::LINE::SetShape(), SH_INCOMPLETE, SH_OK, SHAPE_LINE_CHAIN::Simplify(), and PNS::LINE::Walkaround().

Referenced by ProcessSingleLine().

◆ ProcessSingleLine()

SHOVE::SHOVE_STATUS PNS::SHOVE::ProcessSingleLine ( LINE aCurrent,
LINE aObstacle,
LINE aShoved 
)

Definition at line 265 of file pns_shove.cpp.

266 {
267  aShoved.ClearSegmentLinks();
268 
269  bool obstacleIsHead = false;
270 
271  for( auto s : aObstacle.LinkedSegments() )
272  {
273  if( s->Marker() & MK_HEAD )
274  {
275  obstacleIsHead = true;
276  break;
277  }
278  }
279 
280  SHOVE_STATUS rv;
281 
282  bool viaOnEnd = aCurrent.EndsWithVia();
283 
284  if( viaOnEnd && ( !aCurrent.LayersOverlap( &aObstacle ) || aCurrent.SegmentCount() == 0 ) )
285  {
286  rv = walkaroundLoneVia( aCurrent, aObstacle, aShoved );
287  }
288  else
289  {
290  int w = aObstacle.Width();
291  int n_segs = aCurrent.SegmentCount();
292 
293  int clearance = getClearance( &aCurrent, &aObstacle ) + 1;
294 
295  HULL_SET hulls;
296 
297  hulls.reserve( n_segs + 1 );
298 
299  for( int i = 0; i < n_segs; i++ )
300  {
301  SEGMENT seg( aCurrent, aCurrent.CSegment( i ) );
302  SHAPE_LINE_CHAIN hull = seg.Hull( clearance, w );
303 
304  hulls.push_back( hull );
305  }
306 
307  if( viaOnEnd )
308  hulls.push_back( aCurrent.Via().Hull( clearance, w ) );
309 
310  rv = processHullSet( aCurrent, aObstacle, aShoved, hulls );
311  }
312 
313  if( obstacleIsHead )
314  aShoved.Mark( aShoved.Marker() | MK_HEAD );
315 
316  return rv;
317 }
SHOVE_STATUS processHullSet(LINE &aCurrent, LINE &aObstacle, LINE &aShoved, const HULL_SET &hulls)
Definition: pns_shove.cpp:162
std::vector< SHAPE_LINE_CHAIN > HULL_SET
Definition: pns_shove.h:94
SHAPE_LINE_CHAIN.
int getClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:66
SHOVE_STATUS walkaroundLoneVia(LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
Definition: pns_shove.cpp:126

References PNS::LINE::ClearSegmentLinks(), PNS::LINE::CSegment(), PNS::LINE::EndsWithVia(), getClearance(), PNS::VIA::Hull(), PNS::ITEM::LayersOverlap(), PNS::LINE::LinkedSegments(), PNS::LINE::Mark(), PNS::LINE::Marker(), PNS::MK_HEAD, processHullSet(), PNS::LINE::SegmentCount(), PNS::LINE::Via(), walkaroundLoneVia(), and PNS::LINE::Width().

Referenced by PNS::DIFF_PAIR_PLACER::attemptWalk(), onCollidingArc(), onCollidingLine(), onCollidingSegment(), onCollidingSolid(), and onReverseCollidingVia().

◆ pushLineStack()

bool PNS::SHOVE::pushLineStack ( const LINE aL,
bool  aKeepCurrentOnTop = false 
)
private

Definition at line 1006 of file pns_shove.cpp.

1007 {
1008  if( !aL.IsLinkedChecked() && aL.SegmentCount() != 0 )
1009  return false;
1010 
1011  if( aKeepCurrentOnTop && m_lineStack.size() > 0)
1012  {
1013  m_lineStack.insert( m_lineStack.begin() + m_lineStack.size() - 1, aL );
1014  }
1015  else
1016  {
1017  m_lineStack.push_back( aL );
1018  }
1019 
1020  m_optimizerQueue.push_back( aL );
1021 
1022  return true;
1023 }
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:152
std::vector< LINE > m_lineStack
Definition: pns_shove.h:151

References PNS::LINE::IsLinkedChecked(), m_lineStack, m_optimizerQueue, and PNS::LINE::SegmentCount().

Referenced by onCollidingArc(), onCollidingLine(), onCollidingSegment(), onCollidingSolid(), onReverseCollidingVia(), pushOrShoveVia(), shoveIteration(), ShoveLines(), shoveMainLoop(), and ShoveMultiLines().

◆ pushOrShoveVia()

SHOVE::SHOVE_STATUS PNS::SHOVE::pushOrShoveVia ( VIA aVia,
const VECTOR2I aForce,
int  aCurrentRank 
)
private

Definition at line 686 of file pns_shove.cpp.

687 {
688  LINE_PAIR_VEC draggedLines;
689  VECTOR2I p0( aVia->Pos() );
690  JOINT* jt = m_currentNode->FindJoint( p0, aVia );
691  VECTOR2I p0_pushed( p0 + aForce );
692 
693  // nothing to do...
694  if ( aForce.x == 0 && aForce.y == 0 )
695  return SH_OK;
696 
697  if( !jt )
698  {
699  wxLogTrace( "PNS", "weird, can't find the center-of-via joint\n" );
700  return SH_INCOMPLETE;
701  }
702 
703  if( aVia->IsLocked() )
704  return SH_TRY_WALK;
705 
706  if( jt->IsLocked() )
707  return SH_INCOMPLETE;
708 
709  // make sure pushed via does not overlap with any existing joint
710  while( true )
711  {
712  JOINT* jt_next = m_currentNode->FindJoint( p0_pushed, aVia );
713 
714  if( !jt_next )
715  break;
716 
717  p0_pushed += aForce.Resize( 2 );
718  }
719 
720  std::unique_ptr<VIA> pushedVia = Clone( *aVia );
721  pushedVia->SetPos( p0_pushed );
722  pushedVia->Mark( aVia->Marker() );
723 
724  for( ITEM* item : jt->LinkList() )
725  {
726  if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
727  {
728  LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
729  LINE_PAIR lp;
730  int segIndex;
731 
732  lp.first = assembleLine( li, &segIndex );
733 
734  if( lp.first.HasLockedSegments() )
735  return SH_TRY_WALK;
736 
737  assert( segIndex == 0 || ( segIndex == ( lp.first.SegmentCount() - 1 ) ) );
738 
739  if( segIndex == 0 )
740  lp.first.Reverse();
741 
742  lp.second = lp.first;
743  lp.second.ClearSegmentLinks();
744  lp.second.DragCorner( p0_pushed, lp.second.CLine().Find( p0 ) );
745  lp.second.AppendVia( *pushedVia );
746  draggedLines.push_back( lp );
747  }
748  }
749 
750 #ifdef DEBUG
751  m_logger.Log( aVia, 0, "obstacle-via" );
752 #endif
753 
754  pushedVia->SetRank( aCurrentRank - 1 );
755 
756 #ifdef DEBUG
757  m_logger.Log( pushedVia.get(), 1, "pushed-via" );
758 #endif
759 
760  if( aVia->Marker() & MK_HEAD ) // push
761  {
762  m_draggedVia = pushedVia.get();
763  }
764  else
765  { // shove
766  if( jt->IsStitchingVia() )
767  pushLineStack( LINE( *pushedVia ) );
768  }
769 
770  replaceItems( aVia, std::move( pushedVia ) );
771 
772  for( LINE_PAIR lp : draggedLines )
773  {
774  if( lp.first.Marker() & MK_HEAD )
775  {
776  lp.second.Mark( MK_HEAD );
777 
778  if( m_multiLineMode )
779  return SH_INCOMPLETE;
780 
781  m_newHead = lp.second;
782  }
783 
784  unwindLineStack( &lp.first );
785 
786  if( lp.second.SegmentCount() )
787  {
788  replaceLine( lp.first, lp.second );
789  lp.second.SetRank( aCurrentRank - 1 );
790 
791  if( !pushLineStack( lp.second, true ) )
792  return SH_INCOMPLETE;
793  }
794  else
795  {
796  m_currentNode->Remove( lp.first );
797  }
798 
799 #ifdef DEBUG
800  m_logger.Log( &lp.first, 2, "fan-pre" );
801  m_logger.Log( &lp.second, 3, "fan-post" );
802 #endif
803  }
804 
805  return SH_OK;
806 }
bool IsLocked() const override
Function IsLocked.
Definition: class_track.h:126
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1006
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:102
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:972
std::pair< LINE, LINE > LINE_PAIR
Definition: pns_shove.h:96
void Remove(ARC *aArc)
Function Remove()
Definition: pns_node.cpp:796
std::vector< LINE_PAIR > LINE_PAIR_VEC
Definition: pns_shove.h:97
void Log(const ITEM *aItem, int aKind=0, const std::string &aName=std::string())
Definition: pns_logger.cpp:75
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:1027
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:271
VECTOR2< T > Resize(T aNewLength) const
Function Resize returns a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:392
VIA * m_draggedVia
Definition: pns_shove.h:161
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:56
void replaceItems(ITEM *aOld, std::unique_ptr< ITEM > aNew)
Definition: pns_shove.cpp:46
bool m_multiLineMode
Definition: pns_shove.h:165
OPT_LINE m_newHead
Definition: pns_shove.h:158
NODE * m_currentNode
Definition: pns_shove.h:155
LOGGER m_logger
Definition: pns_shove.h:160

References PNS::ITEM::ARC_T, assembleLine(), PNS::Clone(), PNS::NODE::FindJoint(), PNS::ITEM::IsLocked(), PNS::LOGGER::Log(), m_currentNode, m_draggedVia, m_logger, m_multiLineMode, m_newHead, PNS::ITEM::Marker(), PNS::MK_HEAD, PNS::VIA::Pos(), pushLineStack(), PNS::NODE::Remove(), replaceItems(), replaceLine(), VECTOR2< T >::Resize(), PNS::ITEM::SEGMENT_T, SH_INCOMPLETE, SH_OK, SH_TRY_WALK, unwindLineStack(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by onCollidingVia(), and ShoveDraggingVia().

◆ pushSpringback()

bool PNS::SHOVE::pushSpringback ( NODE aNode,
const OPT_BOX2I aAffectedArea,
VIA aDraggedVia 
)
private

Definition at line 649 of file pns_shove.cpp.

650 {
651  SPRINGBACK_TAG st;
652  OPT_BOX2I prev_area;
653 
654  if( !m_nodeStack.empty() )
655  prev_area = m_nodeStack.back().m_affectedArea;
656 
657  if( aDraggedVia )
658  {
659  st.m_draggedVia = aDraggedVia->MakeHandle();
660  }
661 
662  st.m_node = aNode;
663 
664  if( aAffectedArea )
665  {
666  if( prev_area )
667  st.m_affectedArea = prev_area->Merge( *aAffectedArea );
668  else
669  st.m_affectedArea = aAffectedArea;
670  } else
671  st.m_affectedArea = prev_area;
672 
673  st.m_seq = (m_nodeStack.empty() ? 1 : m_nodeStack.back().m_seq + 1);
674  st.m_locked = false;
675 
676  m_nodeStack.push_back( st );
677 
678  return true;
679 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:150
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:524

References PNS::SHOVE::SPRINGBACK_TAG::m_affectedArea, PNS::SHOVE::SPRINGBACK_TAG::m_draggedVia, PNS::SHOVE::SPRINGBACK_TAG::m_locked, PNS::SHOVE::SPRINGBACK_TAG::m_node, m_nodeStack, PNS::SHOVE::SPRINGBACK_TAG::m_seq, and PNS::VIA::MakeHandle().

Referenced by ShoveDraggingVia(), ShoveLines(), and ShoveMultiLines().

◆ reduceSpringback()

NODE * PNS::SHOVE::reduceSpringback ( const ITEM_SET aHeadSet,
VIA_HANDLE aDraggedVia 
)
private

Definition at line 621 of file pns_shove.cpp.

622 {
623  while( !m_nodeStack.empty() )
624  {
625  SPRINGBACK_TAG& spTag = m_nodeStack.back();
626 
627  auto obs = spTag.m_node->CheckColliding( aHeadSet );
628 
629  if( !obs && !spTag.m_locked )
630  {
631  aDraggedVia = spTag.m_draggedVia;
632  aDraggedVia.valid = true;
633 
634  delete spTag.m_node;
635  m_nodeStack.pop_back();
636  }
637  else
638  break;
639  }
640 
641  return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
642 }
NODE * m_root
Definition: pns_shove.h:154
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:150

References PNS::NODE::CheckColliding(), PNS::SHOVE::SPRINGBACK_TAG::m_draggedVia, PNS::SHOVE::SPRINGBACK_TAG::m_locked, PNS::SHOVE::SPRINGBACK_TAG::m_node, m_nodeStack, m_root, and PNS::VIA_HANDLE::valid.

Referenced by ShoveDraggingVia(), ShoveLines(), and ShoveMultiLines().

◆ replaceItems()

void PNS::SHOVE::replaceItems ( ITEM aOld,
std::unique_ptr< ITEM aNew 
)
private

Definition at line 46 of file pns_shove.cpp.

47 {
48  OPT_BOX2I changed_area = ChangedArea( aOld, aNew.get() );
49 
50  if( changed_area )
51  m_affectedArea = m_affectedArea ? m_affectedArea->Merge( *changed_area ) : *changed_area;
52 
53  m_currentNode->Replace( aOld, std::move( aNew ) );
54 }
OPT_BOX2I ChangedArea(const ITEM *aItemA, const ITEM *aItemB)
Definition: pns_utils.cpp:290
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Function Replace()
Definition: pns_node.cpp:766
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:143
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:524
NODE * m_currentNode
Definition: pns_shove.h:155

References PNS::ChangedArea(), m_affectedArea, m_currentNode, and PNS::NODE::Replace().

Referenced by pushOrShoveVia().

◆ replaceLine()

void PNS::SHOVE::replaceLine ( LINE aOld,
LINE aNew 
)
private

Definition at line 56 of file pns_shove.cpp.

57 {
58  OPT_BOX2I changed_area = ChangedArea( aOld, aNew );
59 
60  if( changed_area )
61  m_affectedArea = m_affectedArea ? m_affectedArea->Merge( *changed_area ) : *changed_area;
62 
63  m_currentNode->Replace( aOld, aNew );
64 }
OPT_BOX2I ChangedArea(const ITEM *aItemA, const ITEM *aItemB)
Definition: pns_utils.cpp:290
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Function Replace()
Definition: pns_node.cpp:766
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:143
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:524
NODE * m_currentNode
Definition: pns_shove.h:155

References PNS::ChangedArea(), m_affectedArea, m_currentNode, and PNS::NODE::Replace().

Referenced by onCollidingArc(), onCollidingLine(), onCollidingSegment(), onCollidingSolid(), onReverseCollidingVia(), and pushOrShoveVia().

◆ RewindSpringbackTo()

bool PNS::SHOVE::RewindSpringbackTo ( NODE aNode)

Definition at line 1625 of file pns_shove.cpp.

1626 {
1627  bool found = false;
1628 
1629  auto iter = m_nodeStack.begin();
1630 
1631  while( iter != m_nodeStack.end() )
1632  {
1633  if ( iter->m_node == aNode )
1634  {
1635  found = true;
1636  break;
1637  }
1638  iter++;
1639  }
1640 
1641  if( !found )
1642  return false;
1643 
1644  auto start = iter;
1645 
1646  aNode->KillChildren();
1647  m_nodeStack.erase( start, m_nodeStack.end() );
1648 
1649  return true;
1650 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:150

References PNS::NODE::KillChildren(), and m_nodeStack.

◆ Router()

◆ runOptimizer()

void PNS::SHOVE::runOptimizer ( NODE aNode)
private

Definition at line 1522 of file pns_shove.cpp.

1523 {
1524  OPTIMIZER optimizer( aNode );
1525  int optFlags = 0;
1526  int n_passes = 0;
1527 
1529 
1530  OPT_BOX2I area = totalAffectedArea();
1531 
1532  int maxWidth = 0;
1533 
1534  for( LINE& line : m_optimizerQueue )
1535  maxWidth = std::max( line.Width(), maxWidth );
1536 
1537  if( area )
1538  area->Inflate( 10 * maxWidth );
1539 
1540  switch( effort )
1541  {
1542  case OE_LOW:
1543  optFlags = OPTIMIZER::MERGE_OBTUSE;
1544  n_passes = 1;
1545  break;
1546 
1547  case OE_MEDIUM:
1548  optFlags = OPTIMIZER::MERGE_SEGMENTS;
1549 
1550  if( area )
1551  optimizer.SetRestrictArea( *area );
1552 
1553  n_passes = 2;
1554  break;
1555 
1556  case OE_FULL:
1557  optFlags = OPTIMIZER::MERGE_SEGMENTS;
1558  n_passes = 2;
1559  break;
1560 
1561  default:
1562  break;
1563  }
1564 
1565  if( Settings().SmartPads() )
1566  optFlags |= OPTIMIZER::SMART_PADS;
1567 
1568  optimizer.SetEffortLevel( optFlags );
1569  optimizer.SetCollisionMask( ITEM::ANY_T );
1570 
1571  for( int pass = 0; pass < n_passes; pass++ )
1572  {
1573  std::reverse( m_optimizerQueue.begin(), m_optimizerQueue.end() );
1574 
1575  for( LINE& line : m_optimizerQueue)
1576  {
1577  if( !( line.Marker() & MK_HEAD ) )
1578  {
1579  LINE optimized;
1580 
1581  if( optimizer.Optimize( &line, &optimized ) )
1582  {
1583  aNode->Remove( line );
1584  line.SetShape( optimized.CLine() );
1585  aNode->Add( line );
1586  }
1587  }
1588  }
1589  }
1590 }
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:152
ROUTING_SETTINGS & Settings() const
Returns current router settings
OPT_BOX2I totalAffectedArea() const
Definition: pns_shove.cpp:1228
PNS_OPTIMIZATION_EFFORT OptimizerEffort() const
Returns the optimizer effort. Bigger means cleaner traces, but slower routing.
PNS_OPTIMIZATION_EFFORT
Optimization effort
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:524

References PNS::NODE::Add(), PNS::ITEM::ANY_T, PNS::LINE::CLine(), m_optimizerQueue, PNS::OPTIMIZER::MERGE_OBTUSE, PNS::OPTIMIZER::MERGE_SEGMENTS, PNS::MK_HEAD, PNS::OE_FULL, PNS::OE_LOW, PNS::OE_MEDIUM, PNS::OPTIMIZER::Optimize(), PNS::ROUTING_SETTINGS::OptimizerEffort(), PNS::NODE::Remove(), PNS::OPTIMIZER::SetCollisionMask(), PNS::OPTIMIZER::SetEffortLevel(), PNS::OPTIMIZER::SetRestrictArea(), PNS::ALGO_BASE::Settings(), PNS::OPTIMIZER::SMART_PADS, and totalAffectedArea().

Referenced by ShoveDraggingVia(), ShoveLines(), and ShoveMultiLines().

◆ sanityCheck()

void PNS::SHOVE::sanityCheck ( LINE aOld,
LINE aNew 
)
private

Definition at line 75 of file pns_shove.cpp.

76 {
77  assert( aOld->CPoint( 0 ) == aNew->CPoint( 0 ) );
78  assert( aOld->CPoint( -1 ) == aNew->CPoint( -1 ) );
79 }

References PNS::LINE::CPoint().

Referenced by onCollidingArc(), onCollidingLine(), onCollidingSegment(), and onCollidingSolid().

◆ SetDebugDecorator()

void PNS::ALGO_BASE::SetDebugDecorator ( DEBUG_DECORATOR aDecorator)
inlineinherited

Function SetDebugDecorator.

Assign a debug decorator allowing this algo to draw extra graphics for visual debugging

Definition at line 72 of file pns_algo_base.h.

73  {
74  m_debugDecorator = aDecorator;
75  }
DEBUG_DECORATOR * m_debugDecorator
Definition: pns_algo_base.h:83

References PNS::ALGO_BASE::m_debugDecorator.

Referenced by PNS::DRAGGER::dragWalkaround(), PNS::LINE_PLACER::rhShoveOnly(), PNS::LINE_PLACER::rhWalkOnly(), and SHOVE().

◆ SetInitialLine()

void PNS::SHOVE::SetInitialLine ( LINE aInitial)

Definition at line 1607 of file pns_shove.cpp.

1608 {
1609  m_root = m_root->Branch();
1610  m_root->Remove( aInitial );
1611 }
NODE * m_root
Definition: pns_shove.h:154
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:106
void Remove(ARC *aArc)
Function Remove()
Definition: pns_node.cpp:796

References PNS::NODE::Branch(), m_root, and PNS::NODE::Remove().

◆ SetLogger()

void PNS::ALGO_BASE::SetLogger ( LOGGER aLogger)
inlineinherited

Definition at line 62 of file pns_algo_base.h.

63  {
64  m_logger = aLogger;
65  }
LOGGER * m_logger
Definition: pns_algo_base.h:85

References PNS::ALGO_BASE::m_logger.

Referenced by PNS::DRAGGER::dragWalkaround(), PNS::LINE_PLACER::rhShoveOnly(), and PNS::LINE_PLACER::rhWalkOnly().

◆ Settings()

◆ ShoveDraggingVia()

SHOVE::SHOVE_STATUS PNS::SHOVE::ShoveDraggingVia ( const VIA_HANDLE  aOldVia,
const VECTOR2I aWhere,
VIA_HANDLE aNewVia 
)

Definition at line 1450 of file pns_shove.cpp.

1451 {
1452  SHOVE_STATUS st = SH_OK;
1453 
1454  m_lineStack.clear();
1455  m_optimizerQueue.clear();
1456  m_newHead = OPT_LINE();
1457  m_draggedVia = NULL;
1458 
1459  auto viaToDrag = findViaByHandle( m_currentNode, aOldVia );
1460 
1461  if( !viaToDrag )
1462  {
1463  return SH_INCOMPLETE;
1464  }
1465 
1466  // Pop NODEs containing previous shoves which are no longer necessary
1467  ITEM_SET headSet;
1468 
1469  VIA headVia ( *viaToDrag );
1470  headVia.SetPos( aWhere );
1471  headSet.Add( headVia );
1472  VIA_HANDLE prevViaHandle;
1473  NODE* parent = reduceSpringback( headSet, prevViaHandle );
1474 
1475  if( prevViaHandle.valid )
1476  {
1477  aNewVia = prevViaHandle;
1478  viaToDrag = findViaByHandle( parent, prevViaHandle );
1479  }
1480 
1481  // Create a new NODE to store this version of the world
1482  //
1483  m_currentNode = parent->Branch();
1485 
1486  viaToDrag->Mark( MK_HEAD );
1487  viaToDrag->SetRank( 100000 );
1488 
1489  // Push the via to its new location
1490  //
1491  st = pushOrShoveVia( viaToDrag, ( aWhere - viaToDrag->Pos()), 0 );
1492 
1493  // Shove any colliding objects out of the way
1494  //
1495  if( st == SH_OK )
1496  st = shoveMainLoop();
1497 
1498  if( st == SH_OK )
1500 
1501  if( st == SH_OK || st == SH_HEAD_MODIFIED )
1502  {
1503  wxLogTrace( "PNS","setNewV %p", m_draggedVia );
1504 
1505  if (!m_draggedVia)
1506  m_draggedVia = viaToDrag;
1507 
1508  aNewVia = m_draggedVia->MakeHandle();
1509 
1511  }
1512  else
1513  {
1514  delete m_currentNode;
1515  m_currentNode = parent;
1516  }
1517 
1518  return st;
1519 }
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION)
Definition: pns_node.cpp:1316
OPT< LINE > OPT_LINE
Definition: pns_shove.h:95
const VIA_HANDLE MakeHandle() const
Definition: pns_via.cpp:116
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:152
SHOVE_STATUS pushOrShoveVia(VIA *aVia, const VECTOR2I &aForce, int aCurrentRank)
Definition: pns_shove.cpp:686
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:106
NODE * reduceSpringback(const ITEM_SET &aHeadSet, VIA_HANDLE &aDraggedVia)
Definition: pns_shove.cpp:621
#define NULL
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1522
static VIA * findViaByHandle(NODE *aNode, const VIA_HANDLE &handle)
Definition: pns_shove.cpp:1431
bool pushSpringback(NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
Definition: pns_shove.cpp:649
std::unordered_set< SCH_ITEM * > ITEM_SET
Definition: sch_item.h:138
VIA * m_draggedVia
Definition: pns_shove.h:161
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:143
SHOVE_STATUS shoveMainLoop()
Definition: pns_shove.cpp:1188
OPT_LINE m_newHead
Definition: pns_shove.h:158
std::vector< LINE > m_lineStack
Definition: pns_shove.h:151
NODE * m_currentNode
Definition: pns_shove.h:155

References PNS::ITEM_SET::Add(), PNS::NODE::Branch(), PNS::NODE::ClearRanks(), PNS::findViaByHandle(), m_affectedArea, m_currentNode, m_draggedVia, m_lineStack, m_newHead, m_optimizerQueue, PNS::VIA::MakeHandle(), PNS::MK_HEAD, NULL, pushOrShoveVia(), pushSpringback(), reduceSpringback(), runOptimizer(), PNS::VIA::SetPos(), SH_HEAD_MODIFIED, SH_INCOMPLETE, SH_OK, shoveMainLoop(), and PNS::VIA_HANDLE::valid.

◆ shoveIteration()

SHOVE::SHOVE_STATUS PNS::SHOVE::shoveIteration ( int  aIter)
private

Definition at line 1054 of file pns_shove.cpp.

1055 {
1056  LINE currentLine = m_lineStack.back();
1057  NODE::OPT_OBSTACLE nearest;
1058  SHOVE_STATUS st = SH_NULL;
1059 
1060  for( ITEM::PnsKind search_order : { ITEM::SOLID_T, ITEM::VIA_T, ITEM::SEGMENT_T } )
1061  {
1062  nearest = m_currentNode->NearestObstacle( &currentLine, search_order );
1063 
1064  if( nearest )
1065  break;
1066  }
1067 
1068  if( !nearest )
1069  {
1070  m_lineStack.pop_back();
1071  return SH_OK;
1072  }
1073 
1074  ITEM* ni = nearest->m_item;
1075 
1076  unwindLineStack( ni );
1077 
1078  if( !ni->OfKind( ITEM::SOLID_T ) && ni->Rank() >= 0 && ni->Rank() > currentLine.Rank() )
1079  {
1080  // Collision with a higher-ranking object (ie: one that we've already shoved)
1081  //
1082  switch( ni->Kind() )
1083  {
1084  case ITEM::VIA_T:
1085  {
1086  wxLogTrace( "PNS", "iter %d: reverse-collide-via", aIter );
1087 
1088  if( currentLine.EndsWithVia()
1089  && m_currentNode->CheckColliding( &currentLine.Via(), (VIA*) ni ) )
1090  {
1091  st = SH_INCOMPLETE;
1092  }
1093  else
1094  {
1095  st = onReverseCollidingVia( currentLine, (VIA*) ni );
1096  }
1097 
1098  break;
1099  }
1100 
1101  case ITEM::SEGMENT_T:
1102  {
1103  wxLogTrace( "PNS", "iter %d: reverse-collide-segment ", aIter );
1104  LINE revLine = assembleLine( static_cast<SEGMENT*>( ni ) );
1105 
1106  popLineStack();
1107  st = onCollidingLine( revLine, currentLine );
1108  if( !pushLineStack( revLine ) )
1109  return SH_INCOMPLETE;
1110 
1111  break;
1112  }
1113 
1114  case ITEM::ARC_T:
1115  {
1116  //TODO(snh): Handle Arc shove separate from track
1117  wxLogTrace( "PNS", "iter %d: reverse-collide-arc ", aIter );
1118  LINE revLine = assembleLine( static_cast<ARC*>( ni ) );
1119 
1120  popLineStack();
1121  st = onCollidingLine( revLine, currentLine );
1122  if( !pushLineStack( revLine ) )
1123  return SH_INCOMPLETE;
1124 
1125  break;
1126  }
1127 
1128  default:
1129  assert( false );
1130  }
1131  }
1132  else
1133  {
1134  // Collision with a lower-ranking object or a solid
1135  //
1136  switch( ni->Kind() )
1137  {
1138  case ITEM::SEGMENT_T:
1139  wxLogTrace( "PNS", "iter %d: collide-segment ", aIter );
1140 
1141  st = onCollidingSegment( currentLine, (SEGMENT*) ni );
1142 
1143  if( st == SH_TRY_WALK )
1144  st = onCollidingSolid( currentLine, ni );
1145 
1146  break;
1147 
1148  //TODO(snh): Customize Arc collide
1149  case ITEM::ARC_T:
1150  wxLogTrace( "PNS", "iter %d: collide-arc ", aIter );
1151 
1152  st = onCollidingArc( currentLine, static_cast<ARC*>( ni ) );
1153 
1154  if( st == SH_TRY_WALK )
1155  st = onCollidingSolid( currentLine, ni );
1156 
1157  break;
1158 
1159  case ITEM::VIA_T:
1160  wxLogTrace( "PNS", "iter %d: shove-via ", aIter );
1161  st = onCollidingVia( &currentLine, (VIA*) ni );
1162 
1163  if( st == SH_TRY_WALK )
1164  st = onCollidingSolid( currentLine, ni );
1165 
1166  break;
1167 
1168  case ITEM::SOLID_T:
1169  wxLogTrace( "PNS", "iter %d: walk-solid ", aIter );
1170  st = onCollidingSolid( currentLine, (SOLID*) ni );
1171  break;
1172 
1173  default:
1174  break;
1175  }
1176  }
1177 
1178  return st;
1179 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1006
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:102
void popLineStack()
Definition: pns_shove.cpp:1025
SHOVE_STATUS onCollidingSolid(LINE &aCurrent, ITEM *aObstacle)
Definition: pns_shove.cpp:488
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:972
OPT_OBSTACLE NearestObstacle(const LINE *aItem, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=NULL)
Function NearestObstacle()
Definition: pns_node.cpp:304
SHOVE_STATUS onCollidingArc(LINE &aCurrent, ARC *aObstacleArc)
Definition: pns_shove.cpp:384
SHOVE_STATUS onCollidingLine(LINE &aCurrent, LINE &aObstacle)
Definition: pns_shove.cpp:445
SHOVE_STATUS onReverseCollidingVia(LINE &aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:889
SHOVE_STATUS onCollidingVia(ITEM *aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:813
SHOVE_STATUS onCollidingSegment(LINE &aCurrent, SEGMENT *aObstacleSeg)
Definition: pns_shove.cpp:323
PnsKind
Supported item types
Definition: pns_item.h:59
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:427
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:148
std::vector< LINE > m_lineStack
Definition: pns_shove.h:151
NODE * m_currentNode
Definition: pns_shove.h:155

References PNS::ITEM::ARC_T, assembleLine(), PNS::NODE::CheckColliding(), PNS::LINE::EndsWithVia(), PNS::ITEM::Kind(), m_currentNode, m_lineStack, PNS::NODE::NearestObstacle(), PNS::ITEM::OfKind(), onCollidingArc(), onCollidingLine(), onCollidingSegment(), onCollidingSolid(), onCollidingVia(), onReverseCollidingVia(), popLineStack(), pushLineStack(), PNS::ITEM::Rank(), PNS::LINE::Rank(), PNS::ITEM::SEGMENT_T, SH_INCOMPLETE, SH_NULL, SH_OK, SH_TRY_WALK, PNS::ITEM::SOLID_T, unwindLineStack(), PNS::LINE::Via(), and PNS::ITEM::VIA_T.

Referenced by shoveMainLoop().

◆ ShoveLines()

SHOVE::SHOVE_STATUS PNS::SHOVE::ShoveLines ( const LINE aCurrentHead)

Definition at line 1244 of file pns_shove.cpp.

1245 {
1246  SHOVE_STATUS st = SH_OK;
1247 
1248  m_multiLineMode = false;
1249 
1250  // empty head? nothing to shove...
1251 
1252  if( !aCurrentHead.SegmentCount() && !aCurrentHead.EndsWithVia() )
1253  return SH_INCOMPLETE;
1254 
1255  LINE head( aCurrentHead );
1256  head.ClearSegmentLinks();
1257 
1258  m_lineStack.clear();
1259  m_optimizerQueue.clear();
1260  m_newHead = OPT_LINE();
1261  m_logger.Clear();
1262 
1263  // Pop NODEs containing previous shoves which are no longer necessary
1264  //
1265  ITEM_SET headSet;
1266  headSet.Add( aCurrentHead );
1267 
1268  VIA_HANDLE dummyVia;
1269 
1270  NODE* parent = reduceSpringback( headSet, dummyVia );
1271 
1272  // Create a new NODE to store this version of the world
1273  //
1274  m_currentNode = parent->Branch();
1276  m_currentNode->Add( head );
1277 
1278  m_currentNode->LockJoint( head.CPoint(0), &head, true );
1279 
1280  if( !head.EndsWithVia() )
1281  m_currentNode->LockJoint( head.CPoint( -1 ), &head, true );
1282 
1283  head.Mark( MK_HEAD );
1284  head.SetRank( 100000 );
1285 
1286  m_logger.NewGroup( "initial", 0 );
1287  m_logger.Log( &head, 0, "head" );
1288 
1289  if( head.EndsWithVia() )
1290  {
1291  std::unique_ptr< VIA >headVia = Clone( head.Via() );
1292  headVia->Mark( MK_HEAD );
1293  headVia->SetRank( 100000 );
1294  m_logger.Log( headVia.get(), 0, "head-via" );
1295  m_currentNode->Add( std::move( headVia ) );
1296  }
1297 
1298  if( !pushLineStack( head ) )
1299  {
1300  delete m_currentNode;
1301  m_currentNode = parent;
1302 
1303  return SH_INCOMPLETE;
1304  }
1305 
1306  st = shoveMainLoop();
1307 
1308  if( st == SH_OK )
1309  {
1311 
1312  if( m_newHead )
1314  else
1315  st = m_currentNode->CheckColliding( &head ) ? SH_INCOMPLETE : SH_OK;
1316  }
1317 
1319 
1320  wxLogTrace( "PNS", "Shove status : %s after %d iterations",
1321  ( ( st == SH_OK || st == SH_HEAD_MODIFIED ) ? "OK" : "FAILURE"), m_iter );
1322 
1323  if( st == SH_OK || st == SH_HEAD_MODIFIED )
1324  {
1326  }
1327  else
1328  {
1329  delete m_currentNode;
1330 
1331  m_currentNode = parent;
1332  m_newHead = OPT_LINE();
1333  }
1334 
1335  if(m_newHead)
1336  m_newHead->Unmark();
1337 
1338  if( m_newHead && head.EndsWithVia() )
1339  {
1340  VIA v = head.Via();
1341  v.SetPos( m_newHead->CPoint( -1 ) );
1342  m_newHead->AppendVia(v);
1343  }
1344 
1345  return st;
1346 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1006
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION)
Definition: pns_node.cpp:1316
OPT< LINE > OPT_LINE
Definition: pns_shove.h:95
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:152
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:106
NODE * reduceSpringback(const ITEM_SET &aHeadSet, VIA_HANDLE &aDraggedVia)
Definition: pns_shove.cpp:621
void NewGroup(const std::string &aName, int aIter=0)
Definition: pns_logger.cpp:55
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1522
bool pushSpringback(NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
Definition: pns_shove.cpp:649
void Log(const ITEM *aItem, int aKind=0, const std::string &aName=std::string())
Definition: pns_logger.cpp:75
std::unordered_set< SCH_ITEM * > ITEM_SET
Definition: sch_item.h:138
void Clear()
Definition: pns_logger.cpp:48
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:271
void RemoveByMarker(int aMarker)
Definition: pns_node.cpp:1326
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:143
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:427
SHOVE_STATUS shoveMainLoop()
Definition: pns_shove.cpp:1188
bool m_multiLineMode
Definition: pns_shove.h:165
OPT_LINE m_newHead
Definition: pns_shove.h:158
std::vector< LINE > m_lineStack
Definition: pns_shove.h:151
NODE * m_currentNode
Definition: pns_shove.h:155
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:620
LOGGER m_logger
Definition: pns_shove.h:160
int m_iter
Definition: pns_shove.h:163
void LockJoint(const VECTOR2I &aPos, const ITEM *aItem, bool aLock)
Definition: pns_node.cpp:1057

References PNS::ITEM_SET::Add(), PNS::NODE::Add(), PNS::NODE::Branch(), PNS::NODE::CheckColliding(), PNS::LOGGER::Clear(), PNS::NODE::ClearRanks(), PNS::LINE::ClearSegmentLinks(), PNS::Clone(), PNS::LINE::CPoint(), PNS::LINE::EndsWithVia(), PNS::NODE::LockJoint(), PNS::LOGGER::Log(), m_affectedArea, m_currentNode, m_iter, m_lineStack, m_logger, m_multiLineMode, m_newHead, m_optimizerQueue, PNS::LINE::Mark(), PNS::MK_HEAD, PNS::LOGGER::NewGroup(), pushLineStack(), pushSpringback(), reduceSpringback(), PNS::NODE::RemoveByMarker(), runOptimizer(), PNS::LINE::SegmentCount(), PNS::VIA::SetPos(), PNS::LINE::SetRank(), SH_HEAD_MODIFIED, SH_INCOMPLETE, SH_OK, shoveMainLoop(), and PNS::LINE::Via().

◆ shoveMainLoop()

SHOVE::SHOVE_STATUS PNS::SHOVE::shoveMainLoop ( )
private

Definition at line 1188 of file pns_shove.cpp.

1189 {
1190  SHOVE_STATUS st = SH_OK;
1191 
1193 
1194  wxLogTrace( "PNS", "ShoveStart [root: %d jts, current: %d jts]", m_root->JointCount(),
1196 
1197  int iterLimit = Settings().ShoveIterationLimit();
1198  TIME_LIMIT timeLimit = Settings().ShoveTimeLimit();
1199 
1200  m_iter = 0;
1201 
1202  timeLimit.Restart();
1203 
1204  if( m_lineStack.empty() && m_draggedVia )
1205  {
1206  // If we're shoving a free via then push a proxy LINE (with the via on the end) onto
1207  // the stack.
1209  }
1210 
1211  while( !m_lineStack.empty() )
1212  {
1213  st = shoveIteration( m_iter );
1214 
1215  m_iter++;
1216 
1217  if( st == SH_INCOMPLETE || timeLimit.Expired() || m_iter >= iterLimit )
1218  {
1219  st = SH_INCOMPLETE;
1220  break;
1221  }
1222  }
1223 
1224  return st;
1225 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1006
int JointCount() const
Returns the number of joints
Definition: pns_node.h:182
NODE * m_root
Definition: pns_shove.h:154
ROUTING_SETTINGS & Settings() const
Returns current router settings
SHOVE_STATUS shoveIteration(int aIter)
Definition: pns_shove.cpp:1054
VIA * m_draggedVia
Definition: pns_shove.h:161
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:143
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:524
std::vector< LINE > m_lineStack
Definition: pns_shove.h:151
NODE * m_currentNode
Definition: pns_shove.h:155
int m_iter
Definition: pns_shove.h:163
TIME_LIMIT ShoveTimeLimit() const

References PNS::TIME_LIMIT::Expired(), PNS::NODE::JointCount(), m_affectedArea, m_currentNode, m_draggedVia, m_iter, m_lineStack, m_root, pushLineStack(), PNS::TIME_LIMIT::Restart(), PNS::ALGO_BASE::Settings(), SH_INCOMPLETE, SH_OK, shoveIteration(), PNS::ROUTING_SETTINGS::ShoveIterationLimit(), and PNS::ROUTING_SETTINGS::ShoveTimeLimit().

Referenced by ShoveDraggingVia(), ShoveLines(), and ShoveMultiLines().

◆ ShoveMultiLines()

SHOVE::SHOVE_STATUS PNS::SHOVE::ShoveMultiLines ( const ITEM_SET aHeadSet)

Definition at line 1349 of file pns_shove.cpp.

1350 {
1351  SHOVE_STATUS st = SH_OK;
1352 
1353  m_multiLineMode = true;
1354 
1355  ITEM_SET headSet;
1356 
1357  for( const ITEM* item : aHeadSet.CItems() )
1358  {
1359  const LINE* headOrig = static_cast<const LINE*>( item );
1360 
1361  // empty head? nothing to shove...
1362  if( !headOrig->SegmentCount() )
1363  return SH_INCOMPLETE;
1364 
1365  headSet.Add( *headOrig );
1366  }
1367 
1368  m_lineStack.clear();
1369  m_optimizerQueue.clear();
1370  m_logger.Clear();
1371 
1372  VIA_HANDLE dummyVia;
1373 
1374  NODE* parent = reduceSpringback( headSet, dummyVia );
1375 
1376  m_currentNode = parent->Branch();
1378  int n = 0;
1379 
1380  for( const ITEM* item : aHeadSet.CItems() )
1381  {
1382  const LINE* headOrig = static_cast<const LINE*>( item );
1383  LINE head( *headOrig );
1384  head.ClearSegmentLinks();
1385 
1386  m_currentNode->Add( head );
1387 
1388  head.Mark( MK_HEAD );
1389  head.SetRank( 100000 );
1390  n++;
1391 
1392  if( !pushLineStack( head ) )
1393  return SH_INCOMPLETE;
1394 
1395  if( head.EndsWithVia() )
1396  {
1397  std::unique_ptr< VIA > headVia = Clone( head.Via() );
1398  headVia->Mark( MK_HEAD );
1399  headVia->SetRank( 100000 );
1400  m_logger.Log( headVia.get(), 0, "head-via" );
1401  m_currentNode->Add( std::move( headVia ) );
1402  }
1403  }
1404 
1405  m_logger.NewGroup( "initial", 0 );
1406  //m_logger.Log( head, 0, "head" );
1407 
1408  st = shoveMainLoop();
1409 
1410  if( st == SH_OK )
1412 
1414 
1415  wxLogTrace( "PNS", "Shove status : %s after %d iterations",
1416  ( st == SH_OK ? "OK" : "FAILURE"), m_iter );
1417 
1418  if( st == SH_OK )
1419  {
1421  }
1422  else
1423  {
1424  delete m_currentNode;
1425  m_currentNode = parent;
1426  }
1427 
1428  return st;
1429 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1006
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION)
Definition: pns_node.cpp:1316
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:152
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:106
NODE * reduceSpringback(const ITEM_SET &aHeadSet, VIA_HANDLE &aDraggedVia)
Definition: pns_shove.cpp:621
void NewGroup(const std::string &aName, int aIter=0)
Definition: pns_logger.cpp:55
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1522
bool pushSpringback(NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
Definition: pns_shove.cpp:649
void Log(const ITEM *aItem, int aKind=0, const std::string &aName=std::string())
Definition: pns_logger.cpp:75
std::unordered_set< SCH_ITEM * > ITEM_SET
Definition: sch_item.h:138
void Clear()
Definition: pns_logger.cpp:48
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:271
void RemoveByMarker(int aMarker)
Definition: pns_node.cpp:1326
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:143
SHOVE_STATUS shoveMainLoop()
Definition: pns_shove.cpp:1188
bool m_multiLineMode
Definition: pns_shove.h:165
std::vector< LINE > m_lineStack
Definition: pns_shove.h:151
NODE * m_currentNode
Definition: pns_shove.h:155
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:620
LOGGER m_logger
Definition: pns_shove.h:160
int m_iter
Definition: pns_shove.h:163

References PNS::ITEM_SET::Add(), PNS::NODE::Add(), PNS::NODE::Branch(), PNS::ITEM_SET::CItems(), PNS::LOGGER::Clear(), PNS::NODE::ClearRanks(), PNS::LINE::ClearSegmentLinks(), PNS::Clone(), PNS::LINE::EndsWithVia(), PNS::LOGGER::Log(), m_affectedArea, m_currentNode, m_iter, m_lineStack, m_logger, m_multiLineMode, m_optimizerQueue, PNS::LINE::Mark(), PNS::MK_HEAD, PNS::LOGGER::NewGroup(), pushLineStack(), pushSpringback(), reduceSpringback(), PNS::NODE::RemoveByMarker(), runOptimizer(), PNS::LINE::SegmentCount(), PNS::LINE::SetRank(), SH_INCOMPLETE, SH_OK, shoveMainLoop(), and PNS::LINE::Via().

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

◆ totalAffectedArea()

OPT_BOX2I PNS::SHOVE::totalAffectedArea ( ) const
private

Definition at line 1228 of file pns_shove.cpp.

1229 {
1230  OPT_BOX2I area;
1231 
1232  if( !m_nodeStack.empty() )
1233  area = m_nodeStack.back().m_affectedArea;
1234 
1235  if( area && m_affectedArea)
1236  area->Merge( *m_affectedArea );
1237  else if( !area )
1238  area = m_affectedArea;
1239 
1240  return area;
1241 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:150
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:143
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:524

References m_affectedArea, and m_nodeStack.

Referenced by runOptimizer().

◆ UnlockSpringbackNode()

void PNS::SHOVE::UnlockSpringbackNode ( NODE aNode)

Definition at line 1653 of file pns_shove.cpp.

1654 {
1655  auto iter = m_nodeStack.begin();
1656 
1657  while( iter != m_nodeStack.end() )
1658  {
1659  if ( iter->m_node == aNode )
1660  {
1661  iter->m_locked = false;
1662  break;
1663  }
1664  iter++;
1665  }
1666 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:150

References m_nodeStack.

◆ unwindLineStack() [1/2]

void PNS::SHOVE::unwindLineStack ( LINKED_ITEM aSeg)
private

Definition at line 972 of file pns_shove.cpp.

973 {
974  for( std::vector<LINE>::iterator i = m_lineStack.begin(); i != m_lineStack.end() ; )
975  {
976  if( i->ContainsSegment( aSeg ) )
977  i = m_lineStack.erase( i );
978  else
979  i++;
980  }
981 
982  for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end() ; )
983  {
984  if( i->ContainsSegment( aSeg ) )
985  i = m_optimizerQueue.erase( i );
986  else
987  i++;
988  }
989 }
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:152
std::vector< LINE > m_lineStack
Definition: pns_shove.h:151

References m_lineStack, and m_optimizerQueue.

Referenced by onReverseCollidingVia(), pushOrShoveVia(), shoveIteration(), and unwindLineStack().

◆ unwindLineStack() [2/2]

void PNS::SHOVE::unwindLineStack ( ITEM aItem)
private

Definition at line 992 of file pns_shove.cpp.

993 {
994  if( aItem->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
995  unwindLineStack( static_cast<LINKED_ITEM*>( aItem ) );
996  else if( aItem->OfKind( ITEM::LINE_T ) )
997  {
998  LINE* l = static_cast<LINE*>( aItem );
999 
1000  for( auto seg : l->LinkedSegments() )
1001  unwindLineStack( seg );
1002  }
1003 }
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:972

References PNS::ITEM::ARC_T, PNS::ITEM::LINE_T, PNS::LINE::LinkedSegments(), PNS::ITEM::OfKind(), PNS::ITEM::SEGMENT_T, and unwindLineStack().

◆ walkaroundLoneVia()

SHOVE::SHOVE_STATUS PNS::SHOVE::walkaroundLoneVia ( LINE aCurrent,
LINE aObstacle,
LINE aShoved 
)
private

Definition at line 126 of file pns_shove.cpp.

127 {
128  int clearance = getClearance( &aCurrent, &aObstacle );
129  const SHAPE_LINE_CHAIN hull = aCurrent.Via().Hull( clearance, aObstacle.Width() );
130  SHAPE_LINE_CHAIN path_cw;
131  SHAPE_LINE_CHAIN path_ccw;
132 
133  if( ! aObstacle.Walkaround( hull, path_cw, true ) )
134  return SH_INCOMPLETE;
135 
136  if( ! aObstacle.Walkaround( hull, path_ccw, false ) )
137  return SH_INCOMPLETE;
138 
139  const SHAPE_LINE_CHAIN& shortest = path_ccw.Length() < path_cw.Length() ? path_ccw : path_cw;
140 
141  if( shortest.PointCount() < 2 )
142  return SH_INCOMPLETE;
143 
144  if( aObstacle.CPoint( -1 ) != shortest.CPoint( -1 ) )
145  return SH_INCOMPLETE;
146 
147  if( aObstacle.CPoint( 0 ) != shortest.CPoint( 0 ) )
148  return SH_INCOMPLETE;
149 
150  aShoved.SetShape( shortest );
151 
152  if( m_currentNode->CheckColliding( &aShoved, &aCurrent ) )
153  return SH_INCOMPLETE;
154 
155  return SH_OK;
156 }
long long int Length() const
Function Length()
int PointCount() const
Function PointCount()
const VECTOR2I & CPoint(int aIndex) const
Function Point()
SHAPE_LINE_CHAIN.
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:427
int getClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:66
NODE * m_currentNode
Definition: pns_shove.h:155

References PNS::NODE::CheckColliding(), PNS::LINE::CPoint(), SHAPE_LINE_CHAIN::CPoint(), getClearance(), PNS::VIA::Hull(), SHAPE_LINE_CHAIN::Length(), m_currentNode, SHAPE_LINE_CHAIN::PointCount(), PNS::LINE::SetShape(), SH_INCOMPLETE, SH_OK, PNS::LINE::Via(), PNS::LINE::Walkaround(), and PNS::LINE::Width().

Referenced by ProcessSingleLine().

Member Data Documentation

◆ m_affectedArea

OPT_BOX2I PNS::SHOVE::m_affectedArea
private

◆ m_currentNode

◆ m_debugDecorator

DEBUG_DECORATOR* PNS::ALGO_BASE::m_debugDecorator
protectedinherited

Definition at line 83 of file pns_algo_base.h.

Referenced by PNS::ALGO_BASE::Dbg(), and PNS::ALGO_BASE::SetDebugDecorator().

◆ m_draggedVia

VIA* PNS::SHOVE::m_draggedVia
private

Definition at line 161 of file pns_shove.h.

Referenced by pushOrShoveVia(), SHOVE(), ShoveDraggingVia(), and shoveMainLoop().

◆ m_forceClearance

int PNS::SHOVE::m_forceClearance
private

Definition at line 164 of file pns_shove.h.

Referenced by ForceClearance(), getClearance(), processHullSet(), and SHOVE().

◆ m_iter

◆ m_lineStack

std::vector<LINE> PNS::SHOVE::m_lineStack
private

◆ m_logger

◆ m_multiLineMode

bool PNS::SHOVE::m_multiLineMode
private

◆ m_newHead

◆ m_nodeStack

std::vector<SPRINGBACK_TAG> PNS::SHOVE::m_nodeStack
private

◆ m_optimizerQueue

std::vector<LINE> PNS::SHOVE::m_optimizerQueue
private

◆ m_restrictSpringbackTagId

int PNS::SHOVE::m_restrictSpringbackTagId
private

Definition at line 156 of file pns_shove.h.

◆ m_root

NODE* PNS::SHOVE::m_root
private

Definition at line 154 of file pns_shove.h.

Referenced by CurrentNode(), reduceSpringback(), SetInitialLine(), SHOVE(), and shoveMainLoop().

◆ m_router

ROUTER* PNS::ALGO_BASE::m_router
protectedinherited

Definition at line 84 of file pns_algo_base.h.

Referenced by PNS::ALGO_BASE::Router(), and PNS::ALGO_BASE::Settings().


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