KiCad PCB EDA Suite
PNS::SHOVE Class Reference

The actual Push and Shove algorithm. 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
 
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 ShoveObstacleLine (const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
 
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
 Return current router settings. More...
 
ROUTING_SETTINGSSettings () const
 Return the logger object, allowing to dump geometry to a file. More...
 
void SetLogger (LOGGER *aLogger)
 
void SetDebugDecorator (DEBUG_DECORATOR *aDecorator)
 Assign a debug decorator allowing this algo to draw extra graphics for visual debugging. More...
 
DEBUG_DECORATORDbg () const
 
const BOX2IVisibleViewArea () 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 shoveLineToHullSet (const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine, const HULL_SET &aHulls)
 
NODEreduceSpringback (const ITEM_SET &aHeadSet, VIA_HANDLE &aDraggedVia)
 
bool pushSpringback (NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
 
SHOVE_STATUS shoveLineFromLoneVia (const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
 
bool checkShoveDirection (const LINE &aCurLine, const LINE &aObstacleLine, const LINE &aShovedLine) 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=nullptr)
 
void replaceItems (ITEM *aOld, std::unique_ptr< ITEM > aNew)
 
void replaceLine (LINE &aOld, LINE &aNew, bool aIncludeInChangedArea=true, NODE *aNode=nullptr)
 
LINEfindRootLine (LINE *aLine)
 
SHOVE_STATUS shoveIteration (int aIter)
 
SHOVE_STATUS shoveMainLoop ()
 
int getClearance (const ITEM *aA, const ITEM *aB) const
 
int getHoleClearance (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
 
std::unordered_map< const LINKED_ITEM *, LINE * > m_rootLineHistory
 
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

The actual Push and Shove algorithm.

Definition at line 45 of file pns_shove.h.

Member Typedef Documentation

◆ HULL_SET

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

Definition at line 93 of file pns_shove.h.

◆ LINE_PAIR

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

Definition at line 95 of file pns_shove.h.

◆ LINE_PAIR_VEC

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

Definition at line 96 of file pns_shove.h.

◆ OPT_LINE

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

Definition at line 94 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 49 of file pns_shove.h.

Constructor & Destructor Documentation

◆ SHOVE()

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

Definition at line 159 of file pns_shove.cpp.

159  :
160  ALGO_BASE( aRouter )
161 {
162  m_forceClearance = -1;
163  m_root = aWorld;
164  m_currentNode = aWorld;
165  SetDebugDecorator( aRouter->GetInterface()->GetDebugDecorator() );
166 
167  // Initialize other temporary variables:
168  m_draggedVia = nullptr;
169  m_iter = 0;
170  m_multiLineMode = false;
172 }
int m_restrictSpringbackTagId
Definition: pns_shove.h:172
NODE * m_root
Definition: pns_shove.h:170
ALGO_BASE(ROUTER *aRouter)
Definition: pns_algo_base.h:45
VIA * m_draggedVia
Definition: pns_shove.h:177
void SetDebugDecorator(DEBUG_DECORATOR *aDecorator)
Assign a debug decorator allowing this algo to draw extra graphics for visual debugging.
Definition: pns_algo_base.h:73
bool m_multiLineMode
Definition: pns_shove.h:181
NODE * m_currentNode
Definition: pns_shove.h:171
int m_iter
Definition: pns_shove.h:179
int m_forceClearance
Definition: pns_shove.h:180

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

◆ ~SHOVE()

PNS::SHOVE::~SHOVE ( )

Definition at line 175 of file pns_shove.cpp.

176 {
177  std::unordered_set<LINE*> alreadyDeleted;
178 
179  for( auto it : m_rootLineHistory )
180  {
181  auto it2 = alreadyDeleted.find( it.second );
182 
183  if( it2 == alreadyDeleted.end() )
184  {
185  alreadyDeleted.insert( it.second );
186  delete it.second;
187  }
188  }
189 }
std::unordered_map< const LINKED_ITEM *, LINE * > m_rootLineHistory
Definition: pns_shove.h:168

References m_rootLineHistory.

Member Function Documentation

◆ AddLockedSpringbackNode()

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

Definition at line 1808 of file pns_shove.cpp.

1809 {
1810  SPRINGBACK_TAG sp;
1811  sp.m_node = aNode;
1812  sp.m_locked = true;
1813 
1814  m_nodeStack.push_back(sp);
1815  return true;
1816 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:165

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 = nullptr 
)
private

Definition at line 192 of file pns_shove.cpp.

193 {
194  return m_currentNode->AssembleLine( const_cast<LINKED_ITEM*>( aSeg ), aIndex, true );
195 }
NODE * m_currentNode
Definition: pns_shove.h:171
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:946

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

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

◆ checkShoveDirection()

bool PNS::SHOVE::checkShoveDirection ( const LINE aCurLine,
const LINE aObstacleLine,
const LINE aShovedLine 
) const
private

Definition at line 206 of file pns_shove.cpp.

208 {
209  SHAPE_LINE_CHAIN::POINT_INSIDE_TRACKER checker( aCurLine.CPoint( 0) );
210  checker.AddPolyline( aObstacleLine.CLine() );
211  checker.AddPolyline( aShovedLine.CLine().Reverse() );
212 
213  bool inside = checker.IsInside();
214 
215  return !inside;
216 }
void AddPolyline(const SHAPE_LINE_CHAIN &aPolyline)
A dynamic state checking if a point lies within polygon with a dynamically built outline ( with each ...

References SHAPE_LINE_CHAIN::POINT_INSIDE_TRACKER::AddPolyline(), PNS::LINE::CLine(), PNS::LINE::CPoint(), and SHAPE_LINE_CHAIN::Reverse().

Referenced by shoveLineToHullSet().

◆ CurrentNode()

NODE * PNS::SHOVE::CurrentNode ( )

Definition at line 1787 of file pns_shove.cpp.

1788 {
1789  return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
1790 }
NODE * m_root
Definition: pns_shove.h:170
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:165

References m_nodeStack, and m_root.

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

◆ Dbg()

◆ findRootLine()

LINE * PNS::SHOVE::findRootLine ( LINE aLine)
private

Definition at line 1686 of file pns_shove.cpp.

1687 {
1688  for( auto link : aLine->Links() )
1689  {
1690  if( auto seg = dyn_cast<SEGMENT*>( link ) )
1691  {
1692  auto it = m_rootLineHistory.find( seg );
1693 
1694  if( it != m_rootLineHistory.end() )
1695  return it->second;
1696  }
1697  }
1698 
1699  return nullptr;
1700 }
std::unordered_map< const LINKED_ITEM *, LINE * > m_rootLineHistory
Definition: pns_shove.h:168

References PNS::LINK_HOLDER::Links(), and m_rootLineHistory.

Referenced by runOptimizer().

◆ ForceClearance()

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

Definition at line 74 of file pns_shove.h.

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

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 134 of file pns_shove.cpp.

135 {
136  if( m_forceClearance >= 0 )
137  return m_forceClearance;
138 
139  return m_currentNode->GetClearance( aA, aB );
140 }
int GetClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_node.cpp:101
NODE * m_currentNode
Definition: pns_shove.h:171
int m_forceClearance
Definition: pns_shove.h:180

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

Referenced by onCollidingVia(), shoveLineFromLoneVia(), and ShoveObstacleLine().

◆ getHoleClearance()

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

Definition at line 143 of file pns_shove.cpp.

144 {
145  if( m_forceClearance >= 0 )
146  return m_forceClearance;
147 
148  return m_currentNode->GetHoleClearance( aA, aB );
149 }
int GetHoleClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_node.cpp:113
NODE * m_currentNode
Definition: pns_shove.h:171
int m_forceClearance
Definition: pns_shove.h:180

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

Referenced by shoveLineFromLoneVia(), and ShoveObstacleLine().

◆ Logger()

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

Reimplemented from PNS::ALGO_BASE.

Definition at line 61 of file pns_shove.h.

62  {
63  return &m_logger;
64  }
LOGGER m_logger
Definition: pns_shove.h:176

References m_logger.

◆ NewHead()

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

Definition at line 1793 of file pns_shove.cpp.

1794 {
1795  assert( m_newHead );
1796 
1797  return *m_newHead;
1798 }
OPT_LINE m_newHead
Definition: pns_shove.h:174

References m_newHead.

◆ onCollidingArc()

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

Definition at line 545 of file pns_shove.cpp.

546 {
547  int segIndex;
548  LINE obstacleLine = assembleLine( aObstacleArc, &segIndex );
549  LINE shovedLine( obstacleLine );
550  ARC tmp( *aObstacleArc );
551 
552  if( obstacleLine.HasLockedSegments() )
553  return SH_TRY_WALK;
554 
555  SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, obstacleLine, shovedLine );
556 
557  const double extensionWalkThreshold = 1.0;
558 
559  double obsLen = obstacleLine.CLine().Length();
560  double shovedLen = shovedLine.CLine().Length();
561  double extensionFactor = 0.0;
562 
563  if( obsLen != 0.0f )
564  extensionFactor = shovedLen / obsLen - 1.0;
565 
566  if( extensionFactor > extensionWalkThreshold )
567  return SH_TRY_WALK;
568 
569  assert( obstacleLine.LayersOverlap( &shovedLine ) );
570 
571  if ( Dbg() )
572  {
573  Dbg()->BeginGroup( wxString::Format( "on-colliding-arc-iter-%d", m_iter ).ToStdString() );
574  Dbg()->AddLine( tmp.CLine(), WHITE, 10000, "obstacle-segment" );
575  Dbg()->AddLine( aCurrent.CLine(), RED, 10000, "current-line" );
576  Dbg()->AddLine( obstacleLine.CLine(), GREEN, 10000, "obstacle-line" );
577  Dbg()->AddLine( shovedLine.CLine(), BLUE, 10000, "shoved-line" );
578  Dbg()->EndGroup();
579  }
580 
581  if( rv == SH_OK )
582  {
583  if( shovedLine.Marker() & MK_HEAD )
584  {
585  if( m_multiLineMode )
586  return SH_INCOMPLETE;
587 
588  m_newHead = shovedLine;
589  }
590 
591  int rank = aCurrent.Rank();
592  shovedLine.SetRank( rank - 1 );
593 
594  sanityCheck( &obstacleLine, &shovedLine );
595  replaceLine( obstacleLine, shovedLine );
596 
597  if( !pushLineStack( shovedLine ) )
598  rv = SH_INCOMPLETE;
599  }
600 
601  return rv;
602 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1147
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, const KIGFX::COLOR4D &aColor, int aWidth, const std::string aName, const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
virtual void EndGroup(const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
SHOVE_STATUS ShoveObstacleLine(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
Definition: pns_shove.cpp:393
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:152
Definition: color4d.h:57
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
Definition: color4d.h:59
void replaceLine(LINE &aOld, LINE &aNew, bool aIncludeInChangedArea=true, NODE *aNode=nullptr)
Definition: pns_shove.cpp:62
Definition: color4d.h:48
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
Definition: ptree.cpp:200
virtual void BeginGroup(const std::string name, const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
Definition: color4d.h:56
bool m_multiLineMode
Definition: pns_shove.h:181
OPT_LINE m_newHead
Definition: pns_shove.h:174
int m_iter
Definition: pns_shove.h:179
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=nullptr)
Definition: pns_shove.cpp:192

References PNS::DEBUG_DECORATOR::AddLine(), assembleLine(), PNS::DEBUG_DECORATOR::BeginGroup(), BLUE, PNS::ARC::CLine(), PNS::LINE::CLine(), PNS::ALGO_BASE::Dbg(), PNS::DEBUG_DECORATOR::EndGroup(), Format(), GREEN, PNS::LINE::HasLockedSegments(), PNS::ITEM::LayersOverlap(), SHAPE_LINE_CHAIN::Length(), m_iter, m_multiLineMode, m_newHead, PNS::LINE::Marker(), PNS::MK_HEAD, pushLineStack(), PNS::LINE::Rank(), RED, replaceLine(), sanityCheck(), PNS::LINE::SetRank(), SH_INCOMPLETE, SH_OK, SH_TRY_WALK, ShoveObstacleLine(), and WHITE.

Referenced by shoveIteration().

◆ onCollidingLine()

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

Definition at line 608 of file pns_shove.cpp.

609 {
610  LINE shovedLine( aObstacle );
611 
612  SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, aObstacle, shovedLine );
613 
614  Dbg()->BeginGroup( "on-colliding-line" );
615  Dbg()->AddLine( aObstacle.CLine(), RED, 100000, "obstacle-line" );
616  Dbg()->AddLine( aCurrent.CLine(), GREEN, 150000, "current-line" );
617  Dbg()->AddLine( shovedLine.CLine(), BLUE, 200000, "shoved-line" );
618 
619  if( rv == SH_OK )
620  {
621  if( shovedLine.Marker() & MK_HEAD )
622  {
623  if( m_multiLineMode )
624  return SH_INCOMPLETE;
625 
626  m_newHead = shovedLine;
627  }
628 
629  sanityCheck( &aObstacle, &shovedLine );
630  replaceLine( aObstacle, shovedLine );
631 
632  int rank = aObstacle.Rank();
633  shovedLine.SetRank( rank - 1 );
634 
635 
636  if( !pushLineStack( shovedLine ) )
637  {
638  rv = SH_INCOMPLETE;
639  }
640  }
641 
642  return rv;
643 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1147
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, const KIGFX::COLOR4D &aColor, int aWidth, const std::string aName, const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
SHOVE_STATUS ShoveObstacleLine(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
Definition: pns_shove.cpp:393
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:152
Definition: color4d.h:57
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
Definition: color4d.h:59
void replaceLine(LINE &aOld, LINE &aNew, bool aIncludeInChangedArea=true, NODE *aNode=nullptr)
Definition: pns_shove.cpp:62
virtual void BeginGroup(const std::string name, const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
Definition: color4d.h:56
bool m_multiLineMode
Definition: pns_shove.h:181
OPT_LINE m_newHead
Definition: pns_shove.h:174

References PNS::DEBUG_DECORATOR::AddLine(), PNS::DEBUG_DECORATOR::BeginGroup(), BLUE, PNS::LINE::CLine(), PNS::ALGO_BASE::Dbg(), GREEN, m_multiLineMode, m_newHead, PNS::LINE::Marker(), PNS::MK_HEAD, pushLineStack(), PNS::LINE::Rank(), RED, replaceLine(), sanityCheck(), PNS::LINE::SetRank(), SH_INCOMPLETE, SH_OK, and ShoveObstacleLine().

Referenced by shoveIteration().

◆ onCollidingSegment()

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

Definition at line 475 of file pns_shove.cpp.

476 {
477  int segIndex;
478  LINE obstacleLine = assembleLine( aObstacleSeg, &segIndex );
479  LINE shovedLine( obstacleLine );
480  SEGMENT tmp( *aObstacleSeg );
481 
482  if( obstacleLine.HasLockedSegments() )
483  return SH_TRY_WALK;
484 
485  SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, obstacleLine, shovedLine );
486 
487  const double extensionWalkThreshold = 1.0;
488 
489  double obsLen = obstacleLine.CLine().Length();
490  double shovedLen = shovedLine.CLine().Length();
491  double extensionFactor = 0.0;
492 
493  if( obsLen != 0.0f )
494  extensionFactor = shovedLen / obsLen - 1.0;
495 
496  if( extensionFactor > extensionWalkThreshold )
497  return SH_TRY_WALK;
498 
499  assert( obstacleLine.LayersOverlap( &shovedLine ) );
500 
501  if( Dbg() )
502  {
503  Dbg()->BeginGroup( wxString::Format( "on-colliding-segment-iter-%d",
504  m_iter ).ToStdString() );
505  Dbg()->AddSegment( tmp.Seg(), WHITE, "obstacle-segment" );
506  Dbg()->AddLine( aCurrent.CLine(), RED, 10000, "current-line" );
507  Dbg()->AddLine( obstacleLine.CLine(), GREEN, 10000, "obstacle-line" );
508  Dbg()->AddLine( shovedLine.CLine(), BLUE, 10000, "shoved-line" );
509 
510  if( rv == SH_OK )
511  Dbg()->Message( "Shove success" );
512  else
513  Dbg()->Message( "Shove FAIL" );
514 
515  Dbg()->EndGroup();
516  }
517 
518  if( rv == SH_OK )
519  {
520  if( shovedLine.Marker() & MK_HEAD )
521  {
522  if( m_multiLineMode )
523  return SH_INCOMPLETE;
524 
525  m_newHead = shovedLine;
526  }
527 
528  int rank = aCurrent.Rank();
529  shovedLine.SetRank( rank - 1 );
530 
531  sanityCheck( &obstacleLine, &shovedLine );
532  replaceLine( obstacleLine, shovedLine );
533 
534  if( !pushLineStack( shovedLine ) )
535  rv = SH_INCOMPLETE;
536  }
537 
538  return rv;
539 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1147
virtual void Message(const wxString msg, const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, const KIGFX::COLOR4D &aColor, int aWidth, const std::string aName, const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
usual segment : line with rounded ends
virtual void EndGroup(const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
SHOVE_STATUS ShoveObstacleLine(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
Definition: pns_shove.cpp:393
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:152
Definition: color4d.h:57
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
Definition: color4d.h:59
void replaceLine(LINE &aOld, LINE &aNew, bool aIncludeInChangedArea=true, NODE *aNode=nullptr)
Definition: pns_shove.cpp:62
virtual void AddSegment(SEG aS, const KIGFX::COLOR4D &aColor, const std::string aName, const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
Definition: color4d.h:48
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
Definition: ptree.cpp:200
virtual void BeginGroup(const std::string name, const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
Definition: color4d.h:56
bool m_multiLineMode
Definition: pns_shove.h:181
OPT_LINE m_newHead
Definition: pns_shove.h:174
int m_iter
Definition: pns_shove.h:179
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=nullptr)
Definition: pns_shove.cpp:192

References PNS::DEBUG_DECORATOR::AddLine(), PNS::DEBUG_DECORATOR::AddSegment(), assembleLine(), PNS::DEBUG_DECORATOR::BeginGroup(), BLUE, PNS::LINE::CLine(), PNS::ALGO_BASE::Dbg(), PNS::DEBUG_DECORATOR::EndGroup(), Format(), GREEN, PNS::LINE::HasLockedSegments(), PNS::ITEM::LayersOverlap(), SHAPE_LINE_CHAIN::Length(), m_iter, m_multiLineMode, m_newHead, PNS::LINE::Marker(), PNS::DEBUG_DECORATOR::Message(), PNS::MK_HEAD, pushLineStack(), PNS::LINE::Rank(), RED, replaceLine(), sanityCheck(), PNS::SEGMENT::Seg(), PNS::LINE::SetRank(), SH_INCOMPLETE, SH_OK, SH_TRY_WALK, ShoveObstacleLine(), and WHITE.

Referenced by shoveIteration().

◆ onCollidingSolid()

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

Definition at line 649 of file pns_shove.cpp.

650 {
651  WALKAROUND walkaround( m_currentNode, Router() );
652  LINE walkaroundLine( aCurrent );
653 
654  if( aCurrent.EndsWithVia() )
655  {
656  VIA vh = aCurrent.Via();
657  VIA* via = nullptr;
658  JOINT* jtStart = m_currentNode->FindJoint( vh.Pos(), &aCurrent );
659 
660  if( !jtStart )
661  return SH_INCOMPLETE;
662 
663  for( ITEM* item : jtStart->LinkList() )
664  {
665  if( item->OfKind( ITEM::VIA_T ) )
666  {
667  via = (VIA*) item;
668  break;
669  }
670  }
671 
672  if( via && via->Collide( aObstacle, m_currentNode ) )
673  return onCollidingVia( aObstacle, via );
674  }
675 
676  TOPOLOGY topo( m_currentNode );
677 
678  std::set<ITEM*> cluster = topo.AssembleCluster( aObstacle, aCurrent.Layers().Start() );
679 
680  walkaround.SetSolidsOnly( false );
681  walkaround.RestrictToSet( true, cluster );
682  walkaround.SetIterationLimit( 16 ); // fixme: make configurable
683 
684  int currentRank = aCurrent.Rank();
685  int nextRank;
686 
687  bool success = false;
688 
689  for( int attempt = 0; attempt < 2; attempt++ )
690  {
691  if( attempt == 1 || Settings().JumpOverObstacles() )
692  {
693 
694  nextRank = currentRank - 1;
695  walkaround.SetSingleDirection( true );
696  }
697  else
698  {
699  nextRank = currentRank + 10000;
700  walkaround.SetSingleDirection( false );
701  }
702 
703 
704  WALKAROUND::WALKAROUND_STATUS status = walkaround.Route( aCurrent, walkaroundLine, false );
705 
706  if( status != WALKAROUND::DONE )
707  continue;
708 
709  walkaroundLine.ClearLinks();
710  walkaroundLine.Unmark();
711  walkaroundLine.Line().Simplify();
712 
713  if( walkaroundLine.HasLoops() )
714  continue;
715 
716  if( aCurrent.Marker() & MK_HEAD )
717  {
718  walkaroundLine.Mark( MK_HEAD );
719 
720  if( m_multiLineMode )
721  continue;
722 
723  m_newHead = walkaroundLine;
724  }
725 
726  sanityCheck( &aCurrent, &walkaroundLine );
727 
728  if( !m_lineStack.empty() )
729  {
730  LINE lastLine = m_lineStack.front();
731 
732  if( lastLine.Collide( &walkaroundLine, m_currentNode ) )
733  {
734  LINE dummy( lastLine );
735 
736  if( ShoveObstacleLine( walkaroundLine, lastLine, dummy ) == SH_OK )
737  {
738  success = true;
739  break;
740  }
741  }
742  else
743  {
744  success = true;
745  break;
746  }
747  }
748  }
749 
750  if(!success)
751  return SH_INCOMPLETE;
752 
753  replaceLine( aCurrent, walkaroundLine );
754  walkaroundLine.SetRank( nextRank );
755 
756  if( Dbg() )
757  {
758  Dbg()->BeginGroup( "on-colliding-solid" );
759  Dbg()->AddLine( aCurrent.CLine(), RED, 10000, "current-line" );
760  Dbg()->AddLine( walkaroundLine.CLine(), BLUE, 10000, "walk-line" );
761  Dbg()->EndGroup();
762  }
763 
764  popLineStack();
765 
766  if( !pushLineStack( walkaroundLine ) )
767  return SH_INCOMPLETE;
768 
769  return SH_OK;
770 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1147
ROUTER * Router() const
Return current router settings.
Definition: pns_algo_base.h:54
void popLineStack()
Definition: pns_shove.cpp:1167
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, const KIGFX::COLOR4D &aColor, int aWidth, const std::string aName, const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
virtual void EndGroup(const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
SHOVE_STATUS ShoveObstacleLine(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
Definition: pns_shove.cpp:393
static LIB_SYMBOL * dummy()
Used to draw a dummy shape when a LIB_SYMBOL is not found in library.
Definition: sch_symbol.cpp:71
ROUTING_SETTINGS & Settings() const
Return the logger object, allowing to dump geometry to a file.
Normal via.
Definition: router_tool.cpp:70
SHOVE_STATUS onCollidingVia(ITEM *aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:970
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:152
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
Definition: color4d.h:59
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
Definition: pns_node.cpp:1134
void replaceLine(LINE &aOld, LINE &aNew, bool aIncludeInChangedArea=true, NODE *aNode=nullptr)
Definition: pns_shove.cpp:62
virtual void BeginGroup(const std::string name, const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
Definition: color4d.h:56
bool m_multiLineMode
Definition: pns_shove.h:181
OPT_LINE m_newHead
Definition: pns_shove.h:174
std::vector< LINE > m_lineStack
Definition: pns_shove.h:166
NODE * m_currentNode
Definition: pns_shove.h:171

References PNS::DEBUG_DECORATOR::AddLine(), PNS::TOPOLOGY::AssembleCluster(), PNS::DEBUG_DECORATOR::BeginGroup(), BLUE, PNS::LINK_HOLDER::ClearLinks(), PNS::LINE::CLine(), PNS::ITEM::Collide(), PNS::ALGO_BASE::Dbg(), PNS::WALKAROUND::DONE, dummy(), PNS::DEBUG_DECORATOR::EndGroup(), PNS::LINE::EndsWithVia(), PNS::NODE::FindJoint(), PNS::LINE::HasLoops(), PNS::ITEM::Layers(), PNS::LINE::Line(), PNS::JOINT::LinkList(), m_currentNode, m_lineStack, m_multiLineMode, m_newHead, PNS::LINE::Mark(), PNS::LINE::Marker(), PNS::MK_HEAD, onCollidingVia(), popLineStack(), PNS::VIA::Pos(), pushLineStack(), PNS::LINE::Rank(), RED, 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, ShoveObstacleLine(), SHAPE_LINE_CHAIN::Simplify(), LAYER_RANGE::Start(), PNS::LINE::Unmark(), PNS::LINE::Via(), via, and PNS::ITEM::VIA_T.

Referenced by shoveIteration().

◆ onCollidingVia()

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

Definition at line 970 of file pns_shove.cpp.

971 {
972  int clearance = getClearance( aCurrent, aObstacleVia );
973  VECTOR2I mtv;
974  int rank = -1;
975 
976  bool lineCollision = false;
977  bool viaCollision = false;
978  VECTOR2I mtvLine, mtvVia;
979 
980  PNS_DBG( Dbg(), BeginGroup, "push-via-by-line" );
981 
982  if( aCurrent->OfKind( ITEM::LINE_T ) )
983  {
984  LINE* currentLine = (LINE*) aCurrent;
985 
986 #if 0
987  m_logger.NewGroup( "push-via-by-line", m_iter );
988  m_logger.Log( currentLine, 4, "current" );
989 #endif
990 
991  lineCollision = aObstacleVia->Shape()->Collide( currentLine->Shape(),
992  clearance + currentLine->Width() / 2,
993  &mtvLine );
994 
995  // Check the via if present. Via takes priority.
996  if( currentLine->EndsWithVia() )
997  {
998  const VIA& currentVia = currentLine->Via();
999  int viaClearance = getClearance( &currentVia, aObstacleVia );
1000 
1001  viaCollision = aObstacleVia->Shape()->Collide( currentVia.Shape(), viaClearance,
1002  &mtvVia );
1003  }
1004  }
1005  else if( aCurrent->OfKind( ITEM::SOLID_T ) )
1006  {
1007  // TODO: is this possible at all? We don't shove solids.
1008  return SH_INCOMPLETE;
1009  }
1010 
1011  // fixme: we may have a sign issue in Collide(CIRCLE, LINE_CHAIN)
1012  if( viaCollision )
1013  mtv = mtvVia;
1014  else if ( lineCollision )
1015  mtv = -mtvLine;
1016  else
1017  mtv = VECTOR2I(0, 0);
1018 
1019  SHOVE::SHOVE_STATUS st = pushOrShoveVia( aObstacleVia, -mtv, rank );
1020 
1021  PNS_DBGN( Dbg(), EndGroup );
1022 
1023  return st;
1024 }
#define PNS_DBGN(dbg, method)
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
SHOVE_STATUS pushOrShoveVia(VIA *aVia, const VECTOR2I &aForce, int aCurrentRank)
Definition: pns_shove.cpp:847
Normal via.
Definition: router_tool.cpp:70
#define PNS_DBG(dbg, method,...)
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
int getClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:134
void Log(EVENT_TYPE evt, VECTOR2I pos, const ITEM *item=nullptr)
Definition: pns_logger.cpp:64
LOGGER m_logger
Definition: pns_shove.h:176
int m_iter
Definition: pns_shove.h:179

References SHAPE::Collide(), PNS::ALGO_BASE::Dbg(), PNS::LINE::EndsWithVia(), getClearance(), PNS::ITEM::LINE_T, PNS::LOGGER::Log(), m_iter, m_logger, PNS::ITEM::OfKind(), PNS_DBG, PNS_DBGN, pushOrShoveVia(), SH_INCOMPLETE, PNS::VIA::Shape(), PNS::LINE::Shape(), PNS::ITEM::SOLID_T, 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 1030 of file pns_shove.cpp.

1031 {
1032  int n = 0;
1033  LINE cur( aCurrent );
1034  cur.ClearLinks();
1035 
1036  JOINT* jt = m_currentNode->FindJoint( aObstacleVia->Pos(), aObstacleVia );
1037  LINE shoved( aCurrent );
1038  shoved.ClearLinks();
1039 
1040  cur.RemoveVia();
1041  unwindLineStack( &aCurrent );
1042 
1043  for( ITEM* item : jt->LinkList() )
1044  {
1045  if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->LayersOverlap( &aCurrent ) )
1046  {
1047  LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
1048  LINE head = assembleLine( li );
1049 
1050  head.AppendVia( *aObstacleVia );
1051 
1052  SHOVE_STATUS st = ShoveObstacleLine( head, cur, shoved );
1053 
1054  if( st != SH_OK )
1055  {
1056 #if 0
1057  m_logger.NewGroup( "on-reverse-via-fail-shove", m_iter );
1058  m_logger.Log( aObstacleVia, 0, "the-via" );
1059  m_logger.Log( &aCurrent, 1, "current-line" );
1060  m_logger.Log( &shoved, 3, "shoved-line" );
1061 #endif
1062 
1063  return st;
1064  }
1065 
1066  cur.SetShape( shoved.CLine() );
1067  n++;
1068  }
1069  }
1070 
1071  if( !n )
1072  {
1073 #if 0
1074  m_logger.NewGroup( "on-reverse-via-fail-lonevia", m_iter );
1075  m_logger.Log( aObstacleVia, 0, "the-via" );
1076  m_logger.Log( &aCurrent, 1, "current-line" );
1077 #endif
1078 
1079  LINE head( aCurrent );
1080  head.Line().Clear();
1081  head.AppendVia( *aObstacleVia );
1082  head.ClearLinks();
1083 
1084  SHOVE_STATUS st = ShoveObstacleLine( head, aCurrent, shoved );
1085 
1086  if( st != SH_OK )
1087  return st;
1088 
1089  cur.SetShape( shoved.CLine() );
1090  }
1091 
1092  if( aCurrent.EndsWithVia() )
1093  shoved.AppendVia( aCurrent.Via() );
1094 
1095 #if 0
1096  m_logger.NewGroup( "on-reverse-via", m_iter );
1097  m_logger.Log( aObstacleVia, 0, "the-via" );
1098  m_logger.Log( &aCurrent, 1, "current-line" );
1099  m_logger.Log( &shoved, 3, "shoved-line" );
1100 #endif
1101  int currentRank = aCurrent.Rank();
1102  replaceLine( aCurrent, shoved );
1103 
1104  if( !pushLineStack( shoved ) )
1105  return SH_INCOMPLETE;
1106 
1107  shoved.SetRank( currentRank );
1108 
1109  return SH_OK;
1110 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1147
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:1113
SHOVE_STATUS ShoveObstacleLine(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
Definition: pns_shove.cpp:393
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
Definition: pns_node.cpp:1134
void replaceLine(LINE &aOld, LINE &aNew, bool aIncludeInChangedArea=true, NODE *aNode=nullptr)
Definition: pns_shove.cpp:62
NODE * m_currentNode
Definition: pns_shove.h:171
void Log(EVENT_TYPE evt, VECTOR2I pos, const ITEM *item=nullptr)
Definition: pns_logger.cpp:64
LOGGER m_logger
Definition: pns_shove.h:176
int m_iter
Definition: pns_shove.h:179
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=nullptr)
Definition: pns_shove.cpp:192

References PNS::LINE::AppendVia(), PNS::ITEM::ARC_T, assembleLine(), SHAPE_LINE_CHAIN::Clear(), PNS::LINK_HOLDER::ClearLinks(), 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::VIA::Pos(), pushLineStack(), PNS::LINE::Rank(), PNS::LINE::RemoveVia(), replaceLine(), PNS::ITEM::SEGMENT_T, PNS::LINE::SetRank(), PNS::LINE::SetShape(), SH_INCOMPLETE, SH_OK, ShoveObstacleLine(), unwindLineStack(), and PNS::LINE::Via().

Referenced by shoveIteration().

◆ popLineStack()

void PNS::SHOVE::popLineStack ( )
private

Definition at line 1167 of file pns_shove.cpp.

1168 {
1169  LINE& l = m_lineStack.back();
1170 
1171  for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end(); )
1172  {
1173  bool found = false;
1174 
1175  for( LINKED_ITEM* s : l.Links() )
1176  {
1177  if( i->ContainsLink( s ) )
1178  {
1179  i = m_optimizerQueue.erase( i );
1180  found = true;
1181  break;
1182  }
1183  }
1184 
1185  if( !found )
1186  i++;
1187  }
1188 
1189  m_lineStack.pop_back();
1190 }
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:167
std::vector< LINE > m_lineStack
Definition: pns_shove.h:166

References PNS::LINK_HOLDER::Links(), m_lineStack, and m_optimizerQueue.

Referenced by onCollidingSolid(), and shoveIteration().

◆ pushLineStack()

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

Definition at line 1147 of file pns_shove.cpp.

1148 {
1149  if( !aL.IsLinkedChecked() && aL.SegmentCount() != 0 )
1150  return false;
1151 
1152  if( aKeepCurrentOnTop && m_lineStack.size() > 0)
1153  {
1154  m_lineStack.insert( m_lineStack.begin() + m_lineStack.size() - 1, aL );
1155  }
1156  else
1157  {
1158  m_lineStack.push_back( aL );
1159  }
1160 
1161  m_optimizerQueue.push_back( aL );
1162 
1163  return true;
1164 }
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:167
std::vector< LINE > m_lineStack
Definition: pns_shove.h:166

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 847 of file pns_shove.cpp.

848 {
849  LINE_PAIR_VEC draggedLines;
850  VECTOR2I p0( aVia->Pos() );
851  JOINT* jt = m_currentNode->FindJoint( p0, aVia );
852  VECTOR2I p0_pushed( p0 + aForce );
853 
854  PNS_DBG( Dbg(), Message, wxString::Format( "via force [%d %d]\n", aForce.x, aForce.y ) );
855 
856  // nothing to do...
857  if ( aForce.x == 0 && aForce.y == 0 )
858  return SH_OK;
859 
860  if( !jt )
861  {
862  PNS_DBG( Dbg(), Message,
863  wxString::Format( "weird, can't find the center-of-via joint\n" ) );
864  return SH_INCOMPLETE;
865  }
866 
867  if( aVia->IsLocked() )
868  return SH_TRY_WALK;
869 
870  if( jt->IsLocked() )
871  return SH_INCOMPLETE;
872 
873  // make sure pushed via does not overlap with any existing joint
874  while( true )
875  {
876  JOINT* jt_next = m_currentNode->FindJoint( p0_pushed, aVia );
877 
878  if( !jt_next )
879  break;
880 
881  p0_pushed += aForce.Resize( 2 );
882  }
883 
884  std::unique_ptr<VIA> pushedVia = Clone( *aVia );
885  pushedVia->SetPos( p0_pushed );
886  pushedVia->Mark( aVia->Marker() );
887 
888  for( ITEM* item : jt->LinkList() )
889  {
890  if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
891  {
892  LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
893  LINE_PAIR lp;
894  int segIndex;
895 
896  lp.first = assembleLine( li, &segIndex );
897 
898  if( lp.first.HasLockedSegments() )
899  return SH_TRY_WALK;
900 
901  assert( segIndex == 0 || ( segIndex == ( lp.first.SegmentCount() - 1 ) ) );
902 
903  if( segIndex == 0 )
904  lp.first.Reverse();
905 
906  lp.second = lp.first;
907  lp.second.ClearLinks();
908  lp.second.DragCorner( p0_pushed, lp.second.CLine().Find( p0 ) );
909  lp.second.AppendVia( *pushedVia );
910  draggedLines.push_back( lp );
911  }
912  }
913 
914  pushedVia->SetRank( aCurrentRank - 1 );
915 
916  if( aVia->Marker() & MK_HEAD ) // push
917  {
918  m_draggedVia = pushedVia.get();
919  }
920  else
921  { // shove
922  if( jt->IsStitchingVia() )
923  pushLineStack( LINE( *pushedVia ) );
924  }
925 
926  PNS_DBG( Dbg(), AddPoint, aVia->Pos(), LIGHTGREEN, 100000, "via-pre" );
927  PNS_DBG( Dbg(), AddPoint, pushedVia->Pos(), LIGHTRED, 100000, "via-post" );
928 
929  replaceItems( aVia, std::move( pushedVia ) );
930 
931  for( LINE_PAIR lp : draggedLines )
932  {
933  if( lp.first.Marker() & MK_HEAD )
934  {
935  lp.second.Mark( MK_HEAD );
936 
937  if( m_multiLineMode )
938  return SH_INCOMPLETE;
939 
940  m_newHead = lp.second;
941  }
942 
943  unwindLineStack( &lp.first );
944 
945  if( lp.second.SegmentCount() )
946  {
947  replaceLine( lp.first, lp.second );
948  lp.second.SetRank( aCurrentRank - 1 );
949 
950  if( !pushLineStack( lp.second, true ) )
951  return SH_INCOMPLETE;
952  }
953  else
954  {
955  m_currentNode->Remove( lp.first );
956  }
957 
958  PNS_DBG( Dbg(), AddLine, lp.first.CLine(), LIGHTGREEN, 10000, "fan-pre" );
959  PNS_DBG( Dbg(), AddLine, lp.second.CLine(), LIGHTRED, 10000, "fan-post" );
960  }
961 
962  return SH_OK;
963 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1147
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:1113
std::pair< LINE, LINE > LINE_PAIR
Definition: pns_shove.h:95
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:836
std::vector< LINE_PAIR > LINE_PAIR_VEC
Definition: pns_shove.h:96
#define PNS_DBG(dbg, method,...)
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
Definition: pns_node.cpp:1134
void replaceLine(LINE &aOld, LINE &aNew, bool aIncludeInChangedArea=true, NODE *aNode=nullptr)
Definition: pns_shove.cpp:62
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
Definition: ptree.cpp:200
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:404
VIA * m_draggedVia
Definition: pns_shove.h:177
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:265
void replaceItems(ITEM *aOld, std::unique_ptr< ITEM > aNew)
Definition: pns_shove.cpp:51
bool m_multiLineMode
Definition: pns_shove.h:181
OPT_LINE m_newHead
Definition: pns_shove.h:174
NODE * m_currentNode
Definition: pns_shove.h:171
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=nullptr)
Definition: pns_shove.cpp:192

References PNS::ITEM::ARC_T, assembleLine(), PNS::Clone(), PNS::ALGO_BASE::Dbg(), PNS::NODE::FindJoint(), Format(), PNS::ITEM::IsLocked(), LIGHTGREEN, LIGHTRED, m_currentNode, m_draggedVia, m_multiLineMode, m_newHead, PNS::ITEM::Marker(), PNS::MK_HEAD, PNS_DBG, 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 807 of file pns_shove.cpp.

808 {
809  SPRINGBACK_TAG st;
810  OPT_BOX2I prev_area;
811 
812  if( !m_nodeStack.empty() )
813  prev_area = m_nodeStack.back().m_affectedArea;
814 
815  if( aDraggedVia )
816  {
817  st.m_draggedVia = aDraggedVia->MakeHandle();
818  }
819 
820  st.m_node = aNode;
821 
822  if( aAffectedArea )
823  {
824  if( prev_area )
825  st.m_affectedArea = prev_area->Merge( *aAffectedArea );
826  else
827  st.m_affectedArea = aAffectedArea;
828  }
829  else
830  {
831  st.m_affectedArea = prev_area;
832  }
833 
834  st.m_seq = ( m_nodeStack.empty() ? 1 : m_nodeStack.back().m_seq + 1 );
835  st.m_locked = false;
836 
837  m_nodeStack.push_back( st );
838 
839  return true;
840 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:165
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:509

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 777 of file pns_shove.cpp.

778 {
779  while( !m_nodeStack.empty() )
780  {
781  SPRINGBACK_TAG& spTag = m_nodeStack.back();
782 
783  OPT<OBSTACLE> obs = spTag.m_node->CheckColliding( aHeadSet );
784 
785  if( !obs && !spTag.m_locked )
786  {
787  aDraggedVia = spTag.m_draggedVia;
788  aDraggedVia.valid = true;
789 
790  delete spTag.m_node;
791  m_nodeStack.pop_back();
792  }
793  else
794  {
795  break;
796  }
797  }
798 
799  return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
800 }
NODE * m_root
Definition: pns_shove.h:170
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:165
boost::optional< T > OPT
Definition: optional.h:7

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 51 of file pns_shove.cpp.

52 {
53  OPT_BOX2I changed_area = ChangedArea( aOld, aNew.get() );
54 
55  if( changed_area )
56  m_affectedArea = m_affectedArea ? m_affectedArea->Merge( *changed_area ) : *changed_area;
57 
58  m_currentNode->Replace( aOld, std::move( aNew ) );
59 }
OPT_BOX2I ChangedArea(const ITEM *aItemA, const ITEM *aItemB)
Definition: pns_utils.cpp:249
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Replace an item with another one.
Definition: pns_node.cpp:801
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:155
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:509
NODE * m_currentNode
Definition: pns_shove.h:171

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

Referenced by pushOrShoveVia().

◆ replaceLine()

void PNS::SHOVE::replaceLine ( LINE aOld,
LINE aNew,
bool  aIncludeInChangedArea = true,
NODE aNode = nullptr 
)
private

Definition at line 62 of file pns_shove.cpp.

63 {
64  if( aIncludeInChangedArea )
65  {
66  OPT_BOX2I changed_area = ChangedArea( aOld, aNew );
67 
68  if( changed_area )
69  {
70  if( Dbg() )
71  {
72  Dbg()->AddBox( *changed_area, BLUE, "shove-changed-area" );
73  }
74 
76  m_affectedArea ? m_affectedArea->Merge( *changed_area ) : *changed_area;
77  }
78  }
79 
80  bool foundPredecessor = false;
81  LINE* rootLine = nullptr;
82 
83  // Keep track of the 'root lines', i.e. the unmodified (pre-shove) versions
84  // of the affected tracks in a map. The optimizer can then query the pre-shove shape
85  // for each shoved line and perform additional constraint checks (i.e. prevent overzealous
86  // optimizations)
87 
88  // Check if the shoved line already has an ancestor (e.g. line from a previous shove
89  // iteration/cursor movement)
90  for( auto link : aOld.Links() )
91  {
92  auto oldLineIter = m_rootLineHistory.find( link );
93 
94  if( oldLineIter != m_rootLineHistory.end() )
95  {
96  rootLine = oldLineIter->second;
97  foundPredecessor = true;
98  break;
99  }
100  }
101 
102  // If found, use it, otherwise, create new entry in the map (we have a genuine new 'root' line)
103  if( !foundPredecessor )
104  {
105  for( auto link : aOld.Links() )
106  {
107  if( ! rootLine )
108  {
109  rootLine = aOld.Clone();
110  }
111 
112  m_rootLineHistory[link] = rootLine;
113  }
114  }
115 
116  // Now update the NODE (calling Replace invalidates the Links() in a LINE)
117  if( aNode )
118  {
119  aNode->Replace( aOld, aNew );
120  }
121  else
122  {
123  m_currentNode->Replace( aOld, aNew );
124  }
125 
126  // point the Links() of the new line to its oldest ancestor
127  for( auto link : aNew.Links() )
128  {
129  m_rootLineHistory[ link ] = rootLine;
130  }
131 }
virtual void AddBox(BOX2I aB, const KIGFX::COLOR4D &aColor, const std::string aName, const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
OPT_BOX2I ChangedArea(const ITEM *aItemA, const ITEM *aItemB)
Definition: pns_utils.cpp:249
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
std::unordered_map< const LINKED_ITEM *, LINE * > m_rootLineHistory
Definition: pns_shove.h:168
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Replace an item with another one.
Definition: pns_node.cpp:801
Definition: color4d.h:56
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:155
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:509
NODE * m_currentNode
Definition: pns_shove.h:171

References PNS::DEBUG_DECORATOR::AddBox(), BLUE, PNS::ChangedArea(), PNS::LINE::Clone(), PNS::ALGO_BASE::Dbg(), PNS::LINK_HOLDER::Links(), m_affectedArea, m_currentNode, m_rootLineHistory, and PNS::NODE::Replace().

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

◆ RewindSpringbackTo()

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

Definition at line 1819 of file pns_shove.cpp.

1820 {
1821  bool found = false;
1822 
1823  auto iter = m_nodeStack.begin();
1824 
1825  while( iter != m_nodeStack.end() )
1826  {
1827  if ( iter->m_node == aNode )
1828  {
1829  found = true;
1830  break;
1831  }
1832 
1833  iter++;
1834  }
1835 
1836  if( !found )
1837  return false;
1838 
1839  auto start = iter;
1840 
1841  aNode->KillChildren();
1842  m_nodeStack.erase( start, m_nodeStack.end() );
1843 
1844  return true;
1845 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:165

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

◆ Router()

◆ runOptimizer()

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

Definition at line 1703 of file pns_shove.cpp.

1704 {
1705  OPTIMIZER optimizer( aNode );
1706  int optFlags = 0;
1707  int n_passes = 0;
1708 
1710 
1711  OPT_BOX2I area = totalAffectedArea();
1712 
1713  int maxWidth = 0;
1714 
1715  for( LINE& line : m_optimizerQueue )
1716  maxWidth = std::max( line.Width(), maxWidth );
1717 
1718  if( area )
1719  {
1720  area->Inflate( maxWidth );
1721  area = area->Intersect( VisibleViewArea() );
1722  }
1723 
1724  switch( effort )
1725  {
1726  case OE_LOW:
1727  optFlags |= OPTIMIZER::MERGE_OBTUSE;
1728  n_passes = 1;
1729  break;
1730 
1731  case OE_MEDIUM:
1732  optFlags |= OPTIMIZER::MERGE_SEGMENTS;
1733 
1734  n_passes = 2;
1735  break;
1736 
1737  case OE_FULL:
1738  optFlags = OPTIMIZER::MERGE_SEGMENTS;
1739  n_passes = 2;
1740  break;
1741 
1742  default:
1743  break;
1744  }
1745 
1746  optFlags |= OPTIMIZER::LIMIT_CORNER_COUNT;
1747 
1748  if( area )
1749  {
1750  if( Dbg() )
1751  {
1752  Dbg()->AddBox( *area, BLUE, "opt-area" );
1753  }
1754 
1755  optFlags |= OPTIMIZER::RESTRICT_AREA;
1756  optimizer.SetRestrictArea( *area, false );
1757  }
1758 
1759  if( Settings().SmartPads() )
1760  optFlags |= OPTIMIZER::SMART_PADS;
1761 
1762  optimizer.SetEffortLevel( optFlags );
1763  optimizer.SetCollisionMask( ITEM::ANY_T );
1764 
1765  for( int pass = 0; pass < n_passes; pass++ )
1766  {
1767  std::reverse( m_optimizerQueue.begin(), m_optimizerQueue.end() );
1768 
1769  for( LINE& line : m_optimizerQueue)
1770  {
1771  if( !( line.Marker() & MK_HEAD ) )
1772  {
1773  LINE optimized;
1774  LINE* root = findRootLine( &line );
1775 
1776  if( optimizer.Optimize( &line, &optimized, root ) )
1777  {
1778  replaceLine( line, optimized, false, aNode );
1779  line = optimized; // keep links in the lines in the queue up to date
1780  }
1781  }
1782  }
1783  }
1784 }
LINE * findRootLine(LINE *aLine)
Definition: pns_shove.cpp:1686
virtual void AddBox(BOX2I aB, const KIGFX::COLOR4D &aColor, const std::string aName, const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:167
ROUTING_SETTINGS & Settings() const
Return the logger object, allowing to dump geometry to a file.
OPT_BOX2I totalAffectedArea() const
Definition: pns_shove.cpp:1386
PNS_OPTIMIZATION_EFFORT OptimizerEffort() const
Set the optimizer effort. Bigger means cleaner traces, but slower routing.
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
Reduce corner cost iteratively.
Definition: pns_optimizer.h:99
void replaceLine(LINE &aOld, LINE &aNew, bool aIncludeInChangedArea=true, NODE *aNode=nullptr)
Definition: pns_shove.cpp:62
const BOX2I & VisibleViewArea() const
Definition: color4d.h:56
Reduce corner cost by merging obtuse segments.
Do not attempt to optimize if the resulting line's corner count is outside the predefined range.
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:509
Reroute pad exits.

References PNS::DEBUG_DECORATOR::AddBox(), PNS::ITEM::ANY_T, BLUE, PNS::ALGO_BASE::Dbg(), findRootLine(), PNS::OPTIMIZER::LIMIT_CORNER_COUNT, 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(), replaceLine(), PNS::OPTIMIZER::RESTRICT_AREA, PNS::OPTIMIZER::SetCollisionMask(), PNS::OPTIMIZER::SetEffortLevel(), PNS::OPTIMIZER::SetRestrictArea(), PNS::ALGO_BASE::Settings(), PNS::OPTIMIZER::SMART_PADS, totalAffectedArea(), and PNS::ALGO_BASE::VisibleViewArea().

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

◆ sanityCheck()

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

Definition at line 152 of file pns_shove.cpp.

153 {
154  assert( aOld->CPoint( 0 ) == aNew->CPoint( 0 ) );
155  assert( aOld->CPoint( -1 ) == aNew->CPoint( -1 ) );
156 }

References PNS::LINE::CPoint().

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

◆ SetDebugDecorator()

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

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

Definition at line 73 of file pns_algo_base.h.

74  {
75  m_debugDecorator = aDecorator;
76  }
DEBUG_DECORATOR * m_debugDecorator
Definition: pns_algo_base.h:86

References PNS::ALGO_BASE::m_debugDecorator.

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

◆ SetInitialLine()

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

Definition at line 1801 of file pns_shove.cpp.

1802 {
1803  m_root = m_root->Branch();
1804  m_root->Remove( aInitial );
1805 }
NODE * m_root
Definition: pns_shove.h:170
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:137
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:836

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

◆ SetLogger()

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

Definition at line 65 of file pns_algo_base.h.

66  {
67  m_logger = aLogger;
68  }
LOGGER * m_logger
Definition: pns_algo_base.h:88

References PNS::ALGO_BASE::m_logger.

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

◆ Settings()

◆ ShoveDraggingVia()

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

Definition at line 1618 of file pns_shove.cpp.

1620 {
1621  SHOVE_STATUS st = SH_OK;
1622 
1623  m_lineStack.clear();
1624  m_optimizerQueue.clear();
1625  m_newHead = OPT_LINE();
1626  m_draggedVia = nullptr;
1627 
1628  VIA* viaToDrag = findViaByHandle( m_currentNode, aOldVia );
1629 
1630  if( !viaToDrag )
1631  return SH_INCOMPLETE;
1632 
1633  // Pop NODEs containing previous shoves which are no longer necessary
1634  ITEM_SET headSet;
1635 
1636  VIA headVia ( *viaToDrag );
1637  headVia.SetPos( aWhere );
1638  headSet.Add( headVia );
1639  VIA_HANDLE prevViaHandle;
1640  NODE* parent = reduceSpringback( headSet, prevViaHandle );
1641 
1642  if( prevViaHandle.valid )
1643  {
1644  aNewVia = prevViaHandle;
1645  viaToDrag = findViaByHandle( parent, prevViaHandle );
1646  }
1647 
1648  // Create a new NODE to store this version of the world
1649  m_currentNode = parent->Branch();
1651 
1652  viaToDrag->Mark( MK_HEAD );
1653  viaToDrag->SetRank( 100000 );
1654 
1655  // Push the via to its new location
1656  st = pushOrShoveVia( viaToDrag, ( aWhere - viaToDrag->Pos() ), 0 );
1657 
1658  // Shove any colliding objects out of the way
1659  if( st == SH_OK )
1660  st = shoveMainLoop();
1661 
1662  if( st == SH_OK )
1664 
1665  if( st == SH_OK || st == SH_HEAD_MODIFIED )
1666  {
1667  wxLogTrace( "PNS","setNewV %p", m_draggedVia );
1668 
1669  if (!m_draggedVia)
1670  m_draggedVia = viaToDrag;
1671 
1672  aNewVia = m_draggedVia->MakeHandle();
1673 
1675  }
1676  else
1677  {
1678  delete m_currentNode;
1679  m_currentNode = parent;
1680  }
1681 
1682  return st;
1683 }
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION|MK_HOLE)
Definition: pns_node.cpp:1434
const VIA_HANDLE MakeHandle() const
Definition: pns_via.cpp:122
OPT< LINE > OPT_LINE
Definition: pns_shove.h:94
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:167
SHOVE_STATUS pushOrShoveVia(VIA *aVia, const VECTOR2I &aForce, int aCurrentRank)
Definition: pns_shove.cpp:847
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:137
NODE * reduceSpringback(const ITEM_SET &aHeadSet, VIA_HANDLE &aDraggedVia)
Definition: pns_shove.cpp:777
Normal via.
Definition: router_tool.cpp:70
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1703
static VIA * findViaByHandle(NODE *aNode, const VIA_HANDLE &handle)
Definition: pns_shove.cpp:1598
bool pushSpringback(NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
Definition: pns_shove.cpp:807
VIA * m_draggedVia
Definition: pns_shove.h:177
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:155
SHOVE_STATUS shoveMainLoop()
Definition: pns_shove.cpp:1342
OPT_LINE m_newHead
Definition: pns_shove.h:174
std::vector< LINE > m_lineStack
Definition: pns_shove.h:166
NODE * m_currentNode
Definition: pns_shove.h:171

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::ITEM::Mark(), PNS::MK_HEAD, PNS::VIA::Pos(), pushOrShoveVia(), pushSpringback(), reduceSpringback(), runOptimizer(), PNS::VIA::SetPos(), PNS::ITEM::SetRank(), 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 1196 of file pns_shove.cpp.

1197 {
1198  LINE currentLine = m_lineStack.back();
1199  NODE::OPT_OBSTACLE nearest;
1200  SHOVE_STATUS st = SH_NULL;
1201 
1202 #ifdef DEBUG
1203  Dbg()->SetIteration( aIter );
1204 #endif
1205 
1206  for( ITEM::PnsKind search_order : { ITEM::SOLID_T, ITEM::VIA_T, ITEM::SEGMENT_T } )
1207  {
1208  nearest = m_currentNode->NearestObstacle( &currentLine, search_order );
1209 
1210  if( nearest )
1211  PNS_DBG( Dbg(), Message,
1212  wxString::Format( "nearest %p %s", nearest->m_item,
1213  nearest->m_item->KindStr() ) );
1214 
1215  if( nearest )
1216  break;
1217  }
1218 
1219  if( !nearest )
1220  {
1221  m_lineStack.pop_back();
1222  PNS_DBG( Dbg(), Message, "no-nearest-item ");
1223  return SH_OK;
1224  }
1225 
1226  ITEM* ni = nearest->m_item;
1227 
1228  unwindLineStack( ni );
1229 
1230  if( !ni->OfKind( ITEM::SOLID_T ) && ni->Rank() >= 0 && ni->Rank() > currentLine.Rank() )
1231  {
1232  // Collision with a higher-ranking object (ie: one that we've already shoved)
1233  //
1234  switch( ni->Kind() )
1235  {
1236  case ITEM::VIA_T:
1237  {
1238  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: reverse-collide-via", aIter ) );
1239 
1240  if( currentLine.EndsWithVia() )
1241  {
1242  st = SH_INCOMPLETE;
1243  }
1244  else
1245  {
1246  st = onReverseCollidingVia( currentLine, (VIA*) ni );
1247  }
1248 
1249  break;
1250  }
1251 
1252  case ITEM::SEGMENT_T:
1253  {
1254  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: reverse-collide-segment ",
1255  aIter ) );
1256  LINE revLine = assembleLine( static_cast<SEGMENT*>( ni ) );
1257 
1258  popLineStack();
1259  st = onCollidingLine( revLine, currentLine );
1260 
1261  if( !pushLineStack( revLine ) )
1262  return SH_INCOMPLETE;
1263 
1264  break;
1265  }
1266 
1267  case ITEM::ARC_T:
1268  {
1269  //TODO(snh): Handle Arc shove separate from track
1270  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: reverse-collide-arc ", aIter ) );
1271  LINE revLine = assembleLine( static_cast<ARC*>( ni ) );
1272 
1273  popLineStack();
1274  st = onCollidingLine( revLine, currentLine );
1275 
1276  if( !pushLineStack( revLine ) )
1277  return SH_INCOMPLETE;
1278 
1279  break;
1280  }
1281 
1282  default:
1283  assert( false );
1284  }
1285  }
1286  else
1287  {
1288  // Collision with a lower-ranking object or a solid
1289  //
1290  switch( ni->Kind() )
1291  {
1292  case ITEM::SEGMENT_T:
1293  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: collide-segment ", aIter ) );
1294 
1295  st = onCollidingSegment( currentLine, (SEGMENT*) ni );
1296 
1297  if( st == SH_TRY_WALK )
1298  st = onCollidingSolid( currentLine, ni );
1299 
1300  break;
1301 
1302  //TODO(snh): Customize Arc collide
1303  case ITEM::ARC_T:
1304  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: collide-arc ", aIter ) );
1305 
1306  st = onCollidingArc( currentLine, static_cast<ARC*>( ni ) );
1307 
1308  if( st == SH_TRY_WALK )
1309  st = onCollidingSolid( currentLine, ni );
1310 
1311  break;
1312 
1313  case ITEM::VIA_T:
1314  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: shove-via ", aIter ) );
1315  st = onCollidingVia( &currentLine, (VIA*) ni );
1316 
1317  if( st == SH_TRY_WALK )
1318  st = onCollidingSolid( currentLine, ni );
1319 
1320  break;
1321 
1322  case ITEM::SOLID_T:
1323  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: walk-solid ", aIter ) );
1324  st = onCollidingSolid( currentLine, (SOLID*) ni );
1325  break;
1326 
1327  default:
1328  break;
1329  }
1330  }
1331 
1332  return st;
1333 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1147
virtual void SetIteration(int iter)
void popLineStack()
Definition: pns_shove.cpp:1167
SHOVE_STATUS onCollidingSolid(LINE &aCurrent, ITEM *aObstacle)
Definition: pns_shove.cpp:649
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:1113
SHOVE_STATUS onCollidingArc(LINE &aCurrent, ARC *aObstacleArc)
Definition: pns_shove.cpp:545
SHOVE_STATUS onCollidingLine(LINE &aCurrent, LINE &aObstacle)
Definition: pns_shove.cpp:608
SHOVE_STATUS onReverseCollidingVia(LINE &aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:1030
SHOVE_STATUS onCollidingVia(ITEM *aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:970
#define PNS_DBG(dbg, method,...)
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
SHOVE_STATUS onCollidingSegment(LINE &aCurrent, SEGMENT *aObstacleSeg)
Definition: pns_shove.cpp:475
OPT_OBSTACLE NearestObstacle(const LINE *aLine, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=nullptr)
Follow the line in search of an obstacle that is nearest to the starting to the line's starting point...
Definition: pns_node.cpp:296
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
Definition: ptree.cpp:200
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:147
std::vector< LINE > m_lineStack
Definition: pns_shove.h:166
NODE * m_currentNode
Definition: pns_shove.h:171
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=nullptr)
Definition: pns_shove.cpp:192

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

Referenced by shoveMainLoop().

◆ shoveLineFromLoneVia()

SHOVE::SHOVE_STATUS PNS::SHOVE::shoveLineFromLoneVia ( const LINE aCurLine,
const LINE aObstacleLine,
LINE aResultLine 
)
private

Definition at line 226 of file pns_shove.cpp.

228 {
229  // Build a hull for aCurLine's via and re-walk aObstacleLine around it.
230 
231  int obstacleLineWidth = aObstacleLine.Width();
232  int clearance = getClearance( &aCurLine, &aObstacleLine );
233  int holeClearance = getHoleClearance( &aCurLine.Via(), &aObstacleLine );
234 
235  if( holeClearance + aCurLine.Via().Drill() / 2 > clearance + aCurLine.Via().Diameter() / 2 )
236  clearance = holeClearance + aCurLine.Via().Drill() / 2 - aCurLine.Via().Diameter() / 2;
237 
238  SHAPE_LINE_CHAIN hull = aCurLine.Via().Hull( clearance, obstacleLineWidth, aCurLine.Layer() );
239  SHAPE_LINE_CHAIN path_cw;
240  SHAPE_LINE_CHAIN path_ccw;
241 
242  if( ! aObstacleLine.Walkaround( hull, path_cw, true ) )
243  return SH_INCOMPLETE;
244 
245  if( ! aObstacleLine.Walkaround( hull, path_ccw, false ) )
246  return SH_INCOMPLETE;
247 
248  const SHAPE_LINE_CHAIN& shortest = path_ccw.Length() < path_cw.Length() ? path_ccw : path_cw;
249 
250  if( shortest.PointCount() < 2 )
251  return SH_INCOMPLETE;
252 
253  if( aObstacleLine.CPoint( -1 ) != shortest.CPoint( -1 ) )
254  return SH_INCOMPLETE;
255 
256  if( aObstacleLine.CPoint( 0 ) != shortest.CPoint( 0 ) )
257  return SH_INCOMPLETE;
258 
259  aResultLine.SetShape( shortest );
260 
261  if( aResultLine.Collide( &aCurLine, m_currentNode ) )
262  return SH_INCOMPLETE;
263 
264  return SH_OK;
265 }
long long int Length() const
Return length of the line chain in Euclidean metric.
int PointCount() const
Return the number of points (vertices) in this line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
Represent a polyline (an zero-thickness chain of connected line segments).
int getClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:134
int getHoleClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:143
NODE * m_currentNode
Definition: pns_shove.h:171

References PNS::ITEM::Collide(), PNS::LINE::CPoint(), SHAPE_LINE_CHAIN::CPoint(), PNS::VIA::Diameter(), PNS::VIA::Drill(), getClearance(), getHoleClearance(), PNS::VIA::Hull(), PNS::ITEM::Layer(), 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 ShoveObstacleLine().

◆ ShoveLines()

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

Definition at line 1402 of file pns_shove.cpp.

1403 {
1404  SHOVE_STATUS st = SH_OK;
1405 
1406  m_multiLineMode = false;
1407 
1408  if( Dbg() )
1409  {
1410  Dbg()->Message( wxString::Format( "Shove start, lc = %d", aCurrentHead.SegmentCount() ) );
1411  }
1412 
1413  // empty head? nothing to shove...
1414  if( !aCurrentHead.SegmentCount() && !aCurrentHead.EndsWithVia() )
1415  return SH_INCOMPLETE;
1416 
1417  LINE head( aCurrentHead );
1418  head.ClearLinks();
1419 
1420  m_lineStack.clear();
1421  m_optimizerQueue.clear();
1422  m_newHead = OPT_LINE();
1423 
1424 #if 0
1425  m_logger.Clear();
1426 #endif
1427 
1428  // Pop NODEs containing previous shoves which are no longer necessary
1429  //
1430  ITEM_SET headSet;
1431  headSet.Add( aCurrentHead );
1432 
1433  VIA_HANDLE dummyVia;
1434 
1435  NODE* parent = reduceSpringback( headSet, dummyVia );
1436 
1437  // Create a new NODE to store this version of the world
1438  m_currentNode = parent->Branch();
1440  m_currentNode->Add( head );
1441 
1442  m_currentNode->LockJoint( head.CPoint(0), &head, true );
1443 
1444  if( !head.EndsWithVia() )
1445  m_currentNode->LockJoint( head.CPoint( -1 ), &head, true );
1446 
1447  head.Mark( MK_HEAD );
1448  head.SetRank( 100000 );
1449 
1450  if( Dbg() )
1451  {
1452  Dbg()->BeginGroup( "initial" );
1453  Dbg()->AddLine(head.CLine(), CYAN, head.Width(), "head" );
1454  Dbg()->EndGroup();
1455  }
1456 
1457  if( head.EndsWithVia() )
1458  {
1459  std::unique_ptr< VIA >headVia = Clone( head.Via() );
1460  headVia->Mark( MK_HEAD );
1461  headVia->SetRank( 100000 );
1462  m_currentNode->Add( std::move( headVia ) );
1463  }
1464 
1465  if( !pushLineStack( head ) )
1466  {
1467  delete m_currentNode;
1468  m_currentNode = parent;
1469 
1470  return SH_INCOMPLETE;
1471  }
1472 
1473  st = shoveMainLoop();
1474 
1475  if( st == SH_OK )
1476  {
1478 
1479  if( m_newHead )
1481  else
1482  st = m_currentNode->CheckColliding( &head ) ? SH_INCOMPLETE : SH_OK;
1483  }
1484 
1486 
1487  PNS_DBG( Dbg(), Message, wxString::Format( "Shove status : %s after %d iterations",
1488  ( ( st == SH_OK || st == SH_HEAD_MODIFIED ) ? "OK" : "FAILURE"), m_iter ) );
1489 
1490  if( st == SH_OK || st == SH_HEAD_MODIFIED )
1491  {
1493  }
1494  else
1495  {
1496  delete m_currentNode;
1497 
1498  m_currentNode = parent;
1499  m_newHead = OPT_LINE();
1500  }
1501 
1502  if(m_newHead)
1503  m_newHead->Unmark();
1504 
1505  if( m_newHead && head.EndsWithVia() )
1506  {
1507  VIA v = head.Via();
1508  v.SetPos( m_newHead->CPoint( -1 ) );
1509  m_newHead->AppendVia(v);
1510  }
1511 
1512  return st;
1513 }
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION|MK_HOLE)
Definition: pns_node.cpp:1434
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1147
virtual void Message(const wxString msg, const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
OPT< LINE > OPT_LINE
Definition: pns_shove.h:94
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:167
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, const KIGFX::COLOR4D &aColor, int aWidth, const std::string aName, const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
virtual void EndGroup(const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:137
NODE * reduceSpringback(const ITEM_SET &aHeadSet, VIA_HANDLE &aDraggedVia)
Definition: pns_shove.cpp:777
Normal via.
Definition: router_tool.cpp:70
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1703
#define PNS_DBG(dbg, method,...)
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
Definition: color4d.h:58
bool pushSpringback(NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
Definition: pns_shove.cpp:807
void Clear()
Definition: pns_logger.cpp:40
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
Definition: ptree.cpp:200
void RemoveByMarker(int aMarker)
Definition: pns_node.cpp:1444
virtual void BeginGroup(const std::string name, const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:155
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:265
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Check if the item collides with anything else in the world, and if found, returns the obstacle.
Definition: pns_node.cpp:450
SHOVE_STATUS shoveMainLoop()
Definition: pns_shove.cpp:1342
bool m_multiLineMode
Definition: pns_shove.h:181
OPT_LINE m_newHead
Definition: pns_shove.h:174
std::vector< LINE > m_lineStack
Definition: pns_shove.h:166
NODE * m_currentNode
Definition: pns_shove.h:171
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:638
LOGGER m_logger
Definition: pns_shove.h:176
int m_iter
Definition: pns_shove.h:179
void LockJoint(const VECTOR2I &aPos, const ITEM *aItem, bool aLock)
Definition: pns_node.cpp:1164

References PNS::ITEM_SET::Add(), PNS::NODE::Add(), PNS::DEBUG_DECORATOR::AddLine(), PNS::DEBUG_DECORATOR::BeginGroup(), PNS::NODE::Branch(), PNS::NODE::CheckColliding(), PNS::LOGGER::Clear(), PNS::LINK_HOLDER::ClearLinks(), PNS::NODE::ClearRanks(), PNS::LINE::CLine(), PNS::Clone(), PNS::LINE::CPoint(), CYAN, PNS::ALGO_BASE::Dbg(), PNS::DEBUG_DECORATOR::EndGroup(), PNS::LINE::EndsWithVia(), Format(), PNS::NODE::LockJoint(), m_affectedArea, m_currentNode, m_iter, m_lineStack, m_logger, m_multiLineMode, m_newHead, m_optimizerQueue, PNS::LINE::Mark(), PNS::DEBUG_DECORATOR::Message(), PNS::MK_HEAD, PNS_DBG, pushLineStack(), pushSpringback(), reduceSpringback(), PNS::NODE::RemoveByMarker(), runOptimizer(), PNS::LINE::SegmentCount(), PNS::VIA::SetPos(), PNS::LINE::SetRank(), SH_HEAD_MODIFIED, SH_INCOMPLETE, SH_OK, shoveMainLoop(), PNS::LINE::Via(), and PNS::LINE::Width().

◆ shoveLineToHullSet()

SHOVE::SHOVE_STATUS PNS::SHOVE::shoveLineToHullSet ( const LINE aCurLine,
const LINE aObstacleLine,
LINE aResultLine,
const HULL_SET aHulls 
)
private

Definition at line 271 of file pns_shove.cpp.

273 {
274  const SHAPE_LINE_CHAIN& obs = aObstacleLine.CLine();
275 
276  int attempt;
277 
278  for( attempt = 0; attempt < 4; attempt++ )
279  {
280  bool invertTraversal = ( attempt >= 2 );
281  bool clockwise = attempt % 2;
282  int vFirst = -1, vLast = -1;
283 
284  LINE l( aObstacleLine );
285  SHAPE_LINE_CHAIN path( l.CLine() );
286 
287  for( int i = 0; i < (int) aHulls.size(); i++ )
288  {
289  const SHAPE_LINE_CHAIN& hull = aHulls[invertTraversal ? aHulls.size() - 1 - i : i];
290 
291  PNS_DBG( Dbg(), AddLine, hull, YELLOW, 10000, "hull" );
292  PNS_DBG( Dbg(), AddLine, path, WHITE, l.Width(), "path" );
293  PNS_DBG( Dbg(), AddLine, obs, LIGHTGRAY, aObstacleLine.Width(), "obs" );
294 
295  if( !l.Walkaround( hull, path, clockwise ) )
296  {
297  PNS_DBG( Dbg(), Message, wxString::Format( "Fail-Walk %s %s %d\n",
298  hull.Format().c_str(),
299  l.CLine().Format().c_str(),
300  clockwise? 1 : 0) );
301  return SH_INCOMPLETE;
302  }
303 
304  path.Simplify();
305  l.SetShape( path );
306  }
307 
308  for( int i = 0; i < std::min( path.PointCount(), obs.PointCount() ); i++ )
309  {
310  if( path.CPoint( i ) != obs.CPoint( i ) )
311  {
312  vFirst = i;
313  break;
314  }
315  }
316 
317  int k = obs.PointCount() - 1;
318 
319  for( int i = path.PointCount() - 1; i >= 0 && k >= 0; i--, k-- )
320  {
321  if( path.CPoint( i ) != obs.CPoint( k ) )
322  {
323  vLast = i;
324  break;
325  }
326  }
327 
328  if( ( vFirst < 0 || vLast < 0 ) && !path.CompareGeometry( aObstacleLine.CLine() ) )
329  {
330  PNS_DBG( Dbg(), Message, wxString::Format( "attempt %d fail vfirst-last", attempt ) );
331  continue;
332  }
333 
334  if( path.CPoint( -1 ) != obs.CPoint( -1 ) || path.CPoint( 0 ) != obs.CPoint( 0 ) )
335  {
336  PNS_DBG( Dbg(), Message, wxString::Format( "attempt %d fail vend-start\n", attempt ) );
337  continue;
338  }
339 
340  if( !checkShoveDirection( aCurLine, aObstacleLine, l ) )
341  {
342  PNS_DBG( Dbg(), Message, wxString::Format( "attempt %d fail direction-check",
343  attempt ) );
344  aResultLine.SetShape( l.CLine() );
345  continue;
346  }
347 
348  if( path.SelfIntersecting() )
349  {
350  PNS_DBG( Dbg(), Message, wxString::Format( "attempt %d fail self-intersect",
351  attempt ) );
352  continue;
353  }
354 
355  bool colliding = l.Collide( &aCurLine, m_currentNode );
356 
357 #ifdef DEBUG
358  char str[128];
359  sprintf( str, "att-%d-shoved", attempt );
360  Dbg()->AddLine( l.CLine(), BLUE, 20000, str );
361 #endif
362 
363  if(( aCurLine.Marker() & MK_HEAD ) && !colliding )
364  {
365  JOINT* jtStart = m_currentNode->FindJoint( aCurLine.CPoint( 0 ), &aCurLine );
366 
367  for( ITEM* item : jtStart->LinkList() )
368  {
369  if( item->Collide( &l, m_currentNode ) )
370  colliding = true;
371  }
372  }
373 
374  if( colliding )
375  {
376  PNS_DBG( Dbg(), Message, wxString::Format( "attempt %d fail coll-check", attempt ) );
377  continue;
378  }
379 
380  aResultLine.SetShape( l.CLine() );
381 
382  return SH_OK;
383  }
384 
385  return SH_INCOMPLETE;
386 }
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, const KIGFX::COLOR4D &aColor, int aWidth, const std::string aName, const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
int PointCount() const
Return the number of points (vertices) in this line chain.
Definition: color4d.h:67
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
#define PNS_DBG(dbg, method,...)
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
const std::string Format() const override
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
Definition: pns_node.cpp:1134
Definition: color4d.h:48
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
Definition: ptree.cpp:200
Definition: color4d.h:56
Represent a polyline (an zero-thickness chain of connected line segments).
bool checkShoveDirection(const LINE &aCurLine, const LINE &aObstacleLine, const LINE &aShovedLine) const
Definition: pns_shove.cpp:206
NODE * m_currentNode
Definition: pns_shove.h:171

References PNS::DEBUG_DECORATOR::AddLine(), BLUE, checkShoveDirection(), PNS::LINE::CLine(), PNS::ITEM::Collide(), PNS::LINE::CPoint(), SHAPE_LINE_CHAIN::CPoint(), PNS::ALGO_BASE::Dbg(), PNS::NODE::FindJoint(), Format(), SHAPE_LINE_CHAIN::Format(), LIGHTGRAY, PNS::JOINT::LinkList(), m_currentNode, PNS::LINE::Marker(), PNS::MK_HEAD, path, PNS_DBG, SHAPE_LINE_CHAIN::PointCount(), PNS::LINE::SetShape(), SH_INCOMPLETE, SH_OK, PNS::LINE::Walkaround(), WHITE, PNS::LINE::Width(), and YELLOW.

Referenced by ShoveObstacleLine().

◆ shoveMainLoop()

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

Definition at line 1342 of file pns_shove.cpp.

1343 {
1344  SHOVE_STATUS st = SH_OK;
1345 
1347 
1348  PNS_DBG( Dbg(), Message, wxString::Format( "ShoveStart [root: %d jts, current: %d jts]",
1349  m_root->JointCount(),
1350  m_currentNode->JointCount() ) );
1351 
1352  int iterLimit = Settings().ShoveIterationLimit();
1353  TIME_LIMIT timeLimit = Settings().ShoveTimeLimit();
1354 
1355  m_iter = 0;
1356 
1357  timeLimit.Restart();
1358 
1359  if( m_lineStack.empty() && m_draggedVia )
1360  {
1361  // If we're shoving a free via then push a proxy LINE (with the via on the end) onto
1362  // the stack.
1364  }
1365 
1366  while( !m_lineStack.empty() )
1367  {
1368  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: node %p stack %d ", m_iter,
1369  m_currentNode, (int) m_lineStack.size() ) );
1370 
1371  st = shoveIteration( m_iter );
1372 
1373  m_iter++;
1374 
1375  if( st == SH_INCOMPLETE || timeLimit.Expired() || m_iter >= iterLimit )
1376  {
1377  st = SH_INCOMPLETE;
1378  break;
1379  }
1380  }
1381 
1382  return st;
1383 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1147
int JointCount() const
Return the number of nodes in the inheritance chain (wrs to the root node).
Definition: pns_node.h:183
NODE * m_root
Definition: pns_shove.h:170
ROUTING_SETTINGS & Settings() const
Return the logger object, allowing to dump geometry to a file.
SHOVE_STATUS shoveIteration(int aIter)
Definition: pns_shove.cpp:1196
#define PNS_DBG(dbg, method,...)
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
Definition: ptree.cpp:200
VIA * m_draggedVia
Definition: pns_shove.h:177
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:155
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:509
std::vector< LINE > m_lineStack
Definition: pns_shove.h:166
NODE * m_currentNode
Definition: pns_shove.h:171
int m_iter
Definition: pns_shove.h:179
TIME_LIMIT ShoveTimeLimit() const

References PNS::ALGO_BASE::Dbg(), PNS::TIME_LIMIT::Expired(), Format(), PNS::NODE::JointCount(), m_affectedArea, m_currentNode, m_draggedVia, m_iter, m_lineStack, m_root, PNS_DBG, 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 1516 of file pns_shove.cpp.

1517 {
1518  SHOVE_STATUS st = SH_OK;
1519 
1520  m_multiLineMode = true;
1521 
1522  ITEM_SET headSet;
1523 
1524  for( const ITEM* item : aHeadSet.CItems() )
1525  {
1526  const LINE* headOrig = static_cast<const LINE*>( item );
1527 
1528  // empty head? nothing to shove...
1529  if( !headOrig->SegmentCount() )
1530  return SH_INCOMPLETE;
1531 
1532  headSet.Add( *headOrig );
1533  }
1534 
1535  m_lineStack.clear();
1536  m_optimizerQueue.clear();
1537 
1538 #if 0
1539  m_logger.Clear();
1540 #endif
1541 
1542  VIA_HANDLE dummyVia;
1543 
1544  NODE* parent = reduceSpringback( headSet, dummyVia );
1545 
1546  m_currentNode = parent->Branch();
1548  int n = 0;
1549 
1550  for( const ITEM* item : aHeadSet.CItems() )
1551  {
1552  const LINE* headOrig = static_cast<const LINE*>( item );
1553  LINE head( *headOrig );
1554  head.ClearLinks();
1555 
1556  m_currentNode->Add( head );
1557 
1558  head.Mark( MK_HEAD );
1559  head.SetRank( 100000 );
1560  n++;
1561 
1562  if( !pushLineStack( head ) )
1563  return SH_INCOMPLETE;
1564 
1565  if( head.EndsWithVia() )
1566  {
1567  std::unique_ptr< VIA > headVia = Clone( head.Via() );
1568  headVia->Mark( MK_HEAD );
1569  headVia->SetRank( 100000 );
1570  m_currentNode->Add( std::move( headVia ) );
1571  }
1572  }
1573 
1574  st = shoveMainLoop();
1575 
1576  if( st == SH_OK )
1578 
1580 
1581  PNS_DBG( Dbg(), Message, wxString::Format( "Shove status : %s after %d iterations",
1582  ( st == SH_OK ? "OK" : "FAILURE"), m_iter ) );
1583 
1584  if( st == SH_OK )
1585  {
1587  }
1588  else
1589  {
1590  delete m_currentNode;
1591  m_currentNode = parent;
1592  }
1593 
1594  return st;
1595 }
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION|MK_HOLE)
Definition: pns_node.cpp:1434
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1147
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:167
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:137
NODE * reduceSpringback(const ITEM_SET &aHeadSet, VIA_HANDLE &aDraggedVia)
Definition: pns_shove.cpp:777
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1703
#define PNS_DBG(dbg, method,...)
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
bool pushSpringback(NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
Definition: pns_shove.cpp:807
void Clear()
Definition: pns_logger.cpp:40
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
Definition: ptree.cpp:200
void RemoveByMarker(int aMarker)
Definition: pns_node.cpp:1444
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:155
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:265
SHOVE_STATUS shoveMainLoop()
Definition: pns_shove.cpp:1342
bool m_multiLineMode
Definition: pns_shove.h:181
std::vector< LINE > m_lineStack
Definition: pns_shove.h:166
NODE * m_currentNode
Definition: pns_shove.h:171
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:638
LOGGER m_logger
Definition: pns_shove.h:176
int m_iter
Definition: pns_shove.h:179

References PNS::ITEM_SET::Add(), PNS::NODE::Add(), PNS::NODE::Branch(), PNS::ITEM_SET::CItems(), PNS::LOGGER::Clear(), PNS::LINK_HOLDER::ClearLinks(), PNS::NODE::ClearRanks(), PNS::Clone(), PNS::ALGO_BASE::Dbg(), PNS::LINE::EndsWithVia(), Format(), m_affectedArea, m_currentNode, m_iter, m_lineStack, m_logger, m_multiLineMode, m_optimizerQueue, PNS::LINE::Mark(), PNS::MK_HEAD, PNS_DBG, 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().

◆ ShoveObstacleLine()

SHOVE::SHOVE_STATUS PNS::SHOVE::ShoveObstacleLine ( const LINE aCurLine,
const LINE aObstacleLine,
LINE aResultLine 
)

Definition at line 393 of file pns_shove.cpp.

395 {
396  aResultLine.ClearLinks();
397 
398  bool obstacleIsHead = false;
399 
400  for( LINKED_ITEM* s : aObstacleLine.Links() )
401  {
402  if( s->Marker() & MK_HEAD )
403  {
404  obstacleIsHead = true;
405  break;
406  }
407  }
408 
409  SHOVE_STATUS rv;
410  bool viaOnEnd = aCurLine.EndsWithVia();
411 
412  if( viaOnEnd && ( !aCurLine.LayersOverlap( &aObstacleLine ) || aCurLine.SegmentCount() == 0 ) )
413  {
414  // Shove aObstacleLine to the hull of aCurLine's via.
415 
416  rv = shoveLineFromLoneVia( aCurLine, aObstacleLine, aResultLine );
417  }
418  else
419  {
420  // Build a set of hulls around the segments of aCurLine. Hulls are at the clearance
421  // distance + aObstacleLine's linewidth so that when re-walking aObstacleLine along the
422  // hull it will be at the appropriate clearance.
423 
424  int obstacleLineWidth = aObstacleLine.Width();
425  int clearance = getClearance( &aCurLine, &aObstacleLine ) + 1;
426  int currentLineSegmentCount = aCurLine.SegmentCount();
427  HULL_SET hulls;
428 
429  hulls.reserve( currentLineSegmentCount + 1 );
430 
431 #ifdef DEBUG
432  Dbg()->Message( wxString::Format( "shove process-single: cur net %d obs %d cl %d",
433  aCurLine.Net(), aObstacleLine.Net(), clearance ) );
434 #endif
435 
436  for( int i = 0; i < currentLineSegmentCount; i++ )
437  {
438  SEGMENT seg( aCurLine, aCurLine.CSegment( i ) );
439  SHAPE_LINE_CHAIN hull = seg.Hull( clearance, obstacleLineWidth, aObstacleLine.Layer() );
440 
441  hulls.push_back( hull );
442  }
443 
444  if( viaOnEnd )
445  {
446  const VIA& via = aCurLine.Via();
447  int viaClearance = getClearance( &via, &aObstacleLine );
448  int holeClearance = getHoleClearance( &via, &aObstacleLine );
449 
450  if( holeClearance + via.Drill() / 2 > viaClearance + via.Diameter() / 2 )
451  viaClearance = holeClearance + via.Drill() / 2 - via.Diameter() / 2;
452 
453  hulls.push_back( aCurLine.Via().Hull( viaClearance, obstacleLineWidth ) );
454  }
455 
456 #ifdef DEBUG
457  char str[128];
458  sprintf( str, "current-cl-%d", clearance );
459  Dbg()->AddLine( aCurLine.CLine(), BLUE, 20000, str );
460 #endif
461 
462  rv = shoveLineToHullSet( aCurLine, aObstacleLine, aResultLine, hulls );
463  }
464 
465  if( obstacleIsHead )
466  aResultLine.Mark( aResultLine.Marker() | MK_HEAD );
467 
468  return rv;
469 }
virtual void Message(const wxString msg, const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
SHOVE_STATUS shoveLineToHullSet(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine, const HULL_SET &aHulls)
Definition: pns_shove.cpp:271
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, const KIGFX::COLOR4D &aColor, int aWidth, const std::string aName, const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
usual segment : line with rounded ends
std::vector< SHAPE_LINE_CHAIN > HULL_SET
Definition: pns_shove.h:93
Normal via.
Definition: router_tool.cpp:70
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
Definition: ptree.cpp:200
Definition: color4d.h:56
Represent a polyline (an zero-thickness chain of connected line segments).
int getClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:134
int getHoleClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:143
SHOVE_STATUS shoveLineFromLoneVia(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
Definition: pns_shove.cpp:226

References PNS::DEBUG_DECORATOR::AddLine(), BLUE, PNS::LINK_HOLDER::ClearLinks(), PNS::LINE::CLine(), PNS::LINE::CSegment(), PNS::ALGO_BASE::Dbg(), PNS::LINE::EndsWithVia(), Format(), getClearance(), getHoleClearance(), PNS::VIA::Hull(), PNS::ITEM::Layer(), PNS::ITEM::LayersOverlap(), PNS::LINK_HOLDER::Links(), PNS::LINE::Mark(), PNS::LINE::Marker(), PNS::DEBUG_DECORATOR::Message(), PNS::MK_HEAD, PNS::ITEM::Net(), PNS::LINE::SegmentCount(), shoveLineFromLoneVia(), shoveLineToHullSet(), PNS::LINE::Via(), via, and PNS::LINE::Width().

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

◆ totalAffectedArea()

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

Definition at line 1386 of file pns_shove.cpp.

1387 {
1388  OPT_BOX2I area;
1389 
1390  if( !m_nodeStack.empty() )
1391  area = m_nodeStack.back().m_affectedArea;
1392 
1393  if( area && m_affectedArea)
1394  area->Merge( *m_affectedArea );
1395  else if( !area )
1396  area = m_affectedArea;
1397 
1398  return area;
1399 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:165
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:155
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:509

References m_affectedArea, and m_nodeStack.

Referenced by runOptimizer().

◆ UnlockSpringbackNode()

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

Definition at line 1848 of file pns_shove.cpp.

1849 {
1850  auto iter = m_nodeStack.begin();
1851 
1852  while( iter != m_nodeStack.end() )
1853  {
1854  if ( iter->m_node == aNode )
1855  {
1856  iter->m_locked = false;
1857  break;
1858  }
1859 
1860  iter++;
1861  }
1862 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:165

References m_nodeStack.

◆ unwindLineStack() [1/2]

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

Definition at line 1113 of file pns_shove.cpp.

1114 {
1115  for( std::vector<LINE>::iterator i = m_lineStack.begin(); i != m_lineStack.end() ; )
1116  {
1117  if( i->ContainsLink( aSeg ) )
1118  i = m_lineStack.erase( i );
1119  else
1120  i++;
1121  }
1122 
1123  for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end() ; )
1124  {
1125  if( i->ContainsLink( aSeg ) )
1126  i = m_optimizerQueue.erase( i );
1127  else
1128  i++;
1129  }
1130 }
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:167
std::vector< LINE > m_lineStack
Definition: pns_shove.h:166

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 1133 of file pns_shove.cpp.

1134 {
1135  if( aItem->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
1136  unwindLineStack( static_cast<LINKED_ITEM*>( aItem ) );
1137  else if( aItem->OfKind( ITEM::LINE_T ) )
1138  {
1139  LINE* l = static_cast<LINE*>( aItem );
1140 
1141  for( LINKED_ITEM* seg : l->Links() )
1142  unwindLineStack( seg );
1143  }
1144 }
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:1113

References PNS::ITEM::ARC_T, PNS::ITEM::LINE_T, PNS::LINK_HOLDER::Links(), PNS::ITEM::OfKind(), PNS::ITEM::SEGMENT_T, and unwindLineStack().

◆ VisibleViewArea()

const BOX2I & PNS::ALGO_BASE::VisibleViewArea ( ) const
inherited

Definition at line 40 of file pns_algo_base.cpp.

41 {
42  return m_router->VisibleViewArea();
43 }
ROUTER * m_router
Definition: pns_algo_base.h:87
const BOX2I & VisibleViewArea() const
Definition: pns_router.h:210

References PNS::ALGO_BASE::m_router, and PNS::ROUTER::VisibleViewArea().

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

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 86 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 177 of file pns_shove.h.

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

◆ m_forceClearance

int PNS::SHOVE::m_forceClearance
private

Definition at line 180 of file pns_shove.h.

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

◆ m_iter

int PNS::SHOVE::m_iter
private

◆ m_lineStack

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

◆ m_logger

LOGGER PNS::SHOVE::m_logger
private

◆ 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 172 of file pns_shove.h.

Referenced by SHOVE().

◆ m_root

NODE* PNS::SHOVE::m_root
private

Definition at line 170 of file pns_shove.h.

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

◆ m_rootLineHistory

std::unordered_map<const LINKED_ITEM*, LINE*> PNS::SHOVE::m_rootLineHistory
private

Definition at line 168 of file pns_shove.h.

Referenced by findRootLine(), replaceLine(), and ~SHOVE().

◆ m_router


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