KiCad PCB EDA Suite
PNS::LINE_PLACER Class Reference

Single track placement algorithm. More...

#include <pns_line_placer.h>

Inheritance diagram for PNS::LINE_PLACER:
PNS::PLACEMENT_ALGO PNS::ALGO_BASE

Public Member Functions

 LINE_PLACER (ROUTER *aRouter)
 
 ~LINE_PLACER ()
 
bool Start (const VECTOR2I &aP, ITEM *aStartItem) override
 Start routing a single track at point aP, taking item aStartItem as anchor (unless NULL). More...
 
bool Move (const VECTOR2I &aP, ITEM *aEndItem) override
 Move the end of the currently routed trace to the point aP, taking aEndItem as anchor (if not NULL). More...
 
bool FixRoute (const VECTOR2I &aP, ITEM *aEndItem, bool aForceFinish) override
 Commit the currently routed track to the parent node taking aP as the final end point and aEndItem as the final anchor (if provided). More...
 
bool UnfixRoute () override
 
bool CommitPlacement () override
 
bool AbortPlacement () override
 
bool HasPlacedAnything () const override
 
bool ToggleVia (bool aEnabled) override
 Enable/disable a via at the end of currently routed trace. More...
 
bool SetLayer (int aLayer) override
 Set the current routing layer. More...
 
const LINEHead () const
 Return the "head" of the line being placed, that is the volatile part that has not been "fixed" yet. More...
 
const LINETail () const
 Return the "tail" of the line being placed, the part which has already wrapped around and shoved some obstacles. More...
 
const LINE Trace () const
 Return the complete routed line. More...
 
const ITEM_SET Traces () override
 Return the complete routed line, as a single-member ITEM_SET. More...
 
const VECTOR2ICurrentEnd () const override
 Return the current end of the line being placed. More...
 
const std::vector< int > CurrentNets () const override
 Return the net code of currently routed track. More...
 
int CurrentLayer () const override
 Return the layer of currently routed track. More...
 
NODECurrentNode (bool aLoopsRemoved=false) const override
 Return the most recent world state. More...
 
void FlipPosture () override
 Toggle the current posture (straight/diagonal) of the trace head. More...
 
void UpdateSizes (const SIZES_SETTINGS &aSizes) override
 Perform on-the-fly update of the width, via diameter & drill size from a settings class. More...
 
void SetOrthoMode (bool aOrthoMode) override
 Function SetOrthoMode() More...
 
bool IsPlacingVia () const override
 Function IsPlacingVia() More...
 
void GetModifiedNets (std::vector< int > &aNets) const override
 Function GetModifiedNets. More...
 
bool SplitAdjacentSegments (NODE *aNode, ITEM *aSeg, const VECTOR2I &aP)
 Check if point aP lies on segment aSeg. More...
 
ROUTERRouter () const
 Return current router settings. More...
 
ROUTING_SETTINGSSettings () const
 Return the logger object, allowing to dump geometry to a file. More...
 
virtual LOGGERLogger ()
 
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
 
LOGGERm_logger
 

Private Member Functions

bool route (const VECTOR2I &aP)
 Re-route the current track to point aP. More...
 
void updateLeadingRatLine ()
 Draw the "leading" rats nest line, which connects the end of currently routed track and the nearest yet unrouted item. More...
 
void setWorld (NODE *aWorld)
 Set the board to route. More...
 
void initPlacement ()
 Initialize placement of a new line with given parameters. More...
 
void setInitialDirection (const DIRECTION_45 &aDirection)
 Set preferred direction of the very first track segment to be laid. More...
 
void removeLoops (NODE *aNode, LINE &aLatest)
 Searches aNode for traces concurrent to aLatest and removes them. More...
 
void simplifyNewLine (NODE *aNode, LINKED_ITEM *aLatest)
 Assemble a line starting from segment or arc aLatest, removes collinear segments and redundant vertices. More...
 
bool handleSelfIntersections ()
 Check if the head of the track intersects its tail. More...
 
bool handlePullback ()
 Deal with pull-back: reduces the tail if head trace is moved backwards wrs to the current tail direction. More...
 
bool mergeHead ()
 Moves "established" segments from the head to the tail if certain conditions are met. More...
 
bool reduceTail (const VECTOR2I &aEnd)
 Attempt to reduce the number of segments in the tail by trying to replace a certain number of latest tail segments with a direct trace leading to aEnd that does not collide with anything. More...
 
bool optimizeTailHeadTransition ()
 Try to reduce the corner count of the most recent part of tail/head by merging obtuse/collinear segments. More...
 
bool routeHead (const VECTOR2I &aP, LINE &aNewHead)
 Compute the head trace between the current start point (m_p_start) and point aP, starting with direction defined in m_direction. More...
 
void routeStep (const VECTOR2I &aP)
 Perform a single routing algorithm step, for the end point aP. More...
 
bool rhWalkOnly (const VECTOR2I &aP, LINE &aNewHead)
 Route step shove mode. More...
 
bool rhShoveOnly (const VECTOR2I &aP, LINE &aNewHead)
 Route step mark obstacles mode. More...
 
bool rhMarkObstacles (const VECTOR2I &aP, LINE &aNewHead)
 
const VIA makeVia (const VECTOR2I &aP)
 
bool buildInitialLine (const VECTOR2I &aP, LINE &aHead, bool aForceNoVia=false)
 

Private Attributes

DIRECTION_45 m_direction
 current routing direction More...
 
DIRECTION_45 m_initial_direction
 routing direction for new traces More...
 
LINE m_head
 the volatile part of the track from the previously analyzed point to the current routing destination More...
 
LINE m_last_head
 Most recent successful (non-colliding) head. More...
 
LINE m_tail
 routing "tail": part of the track that has been already fixed due to collisions with obstacles More...
 
NODEm_world
 pointer to world to search colliding items More...
 
VECTOR2I m_p_start
 current routing start (end of tail, beginning of head) More...
 
std::unique_ptr< SHOVEm_shove
 The shove engine. More...
 
NODEm_currentNode
 Current world state. More...
 
NODEm_lastNode
 Postprocessed world state (including marked collisions & removed loops) More...
 
SIZES_SETTINGS m_sizes
 
bool m_placingVia
 
int m_currentNet
 
int m_currentLayer
 
VECTOR2I m_currentEnd
 
VECTOR2I m_currentStart
 
LINE m_currentTrace
 
PNS_MODE m_currentMode
 
ITEMm_startItem
 
bool m_idle
 
bool m_chainedPlacement
 
bool m_orthoMode
 
bool m_placementCorrect
 
FIXED_TAIL m_fixedTail
 
MOUSE_TRAIL_TRACER m_mouseTrailTracer
 

Detailed Description

Single track placement algorithm.

Interactively routes a track. Applies shove and walkaround algorithms when needed.

Definition at line 84 of file pns_line_placer.h.

Constructor & Destructor Documentation

◆ LINE_PLACER()

PNS::LINE_PLACER::LINE_PLACER ( ROUTER aRouter)

Definition at line 40 of file pns_line_placer.cpp.

40  :
41  PLACEMENT_ALGO( aRouter )
42 {
44  m_world = nullptr;
45  m_shove = nullptr;
46  m_currentNode = nullptr;
47  m_idle = true;
48 
49  // Init temporary variables (do not leave uninitialized members)
50  m_lastNode = nullptr;
51  m_placingVia = false;
52  m_currentNet = 0;
53  m_currentLayer = 0;
55  m_startItem = nullptr;
56  m_chainedPlacement = false;
57  m_orthoMode = false;
58  m_placementCorrect = false;
59 }
NODE * m_lastNode
Postprocessed world state (including marked collisions & removed loops)
NODE * m_world
pointer to world to search colliding items
DIRECTION_45 m_initial_direction
routing direction for new traces
std::unique_ptr< SHOVE > m_shove
The shove engine.
NODE * m_currentNode
Current world state.
Ignore collisions, mark obstacles.
PLACEMENT_ALGO(ROUTER *aRouter)

References m_chainedPlacement, m_currentLayer, m_currentMode, m_currentNet, m_currentNode, m_idle, m_initial_direction, m_lastNode, m_orthoMode, m_placementCorrect, m_placingVia, m_shove, m_startItem, m_world, DIRECTION_45::N, and PNS::RM_MarkObstacles.

◆ ~LINE_PLACER()

PNS::LINE_PLACER::~LINE_PLACER ( )

Definition at line 62 of file pns_line_placer.cpp.

63 {
64 }

Member Function Documentation

◆ AbortPlacement()

bool PNS::LINE_PLACER::AbortPlacement ( )
overridevirtual

Reimplemented from PNS::PLACEMENT_ALGO.

Definition at line 1723 of file pns_line_placer.cpp.

1724 {
1725  m_world->KillChildren();
1726  return true;
1727 }
NODE * m_world
pointer to world to search colliding items
void KillChildren()
Definition: pns_node.cpp:1369

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

◆ buildInitialLine()

bool PNS::LINE_PLACER::buildInitialLine ( const VECTOR2I aP,
LINE aHead,
bool  aForceNoVia = false 
)
private

Definition at line 1645 of file pns_line_placer.cpp.

1646 {
1647  SHAPE_LINE_CHAIN l;
1648  DIRECTION_45 guessedDir = m_mouseTrailTracer.GetPosture( aP );
1649 
1650  wxLogTrace( "PNS", "buildInitialLine: m_direction %s, guessedDir %s, tail points %d",
1651  m_direction.Format(), guessedDir.Format(), m_tail.PointCount() );
1652 
1653  // Rounded corners don't make sense when routing orthogonally (single track at a time)
1654  bool fillet = !m_orthoMode && Settings().GetCornerMode() == CORNER_MODE::ROUNDED_45;
1655 
1656  if( m_p_start == aP )
1657  {
1658  l.Clear();
1659  }
1660  else
1661  {
1662  if( Settings().GetFreeAngleMode() && Settings().Mode() == RM_MarkObstacles )
1663  {
1664  l = SHAPE_LINE_CHAIN( { m_p_start, aP } );
1665  }
1666  else
1667  {
1668  if( !m_tail.PointCount() )
1669  l = guessedDir.BuildInitialTrace( m_p_start, aP, false, fillet );
1670  else
1671  l = m_direction.BuildInitialTrace( m_p_start, aP, false, fillet );
1672  }
1673 
1674  if( l.SegmentCount() > 1 && m_orthoMode )
1675  {
1676  VECTOR2I newLast = l.CSegment( 0 ).LineProject( l.CPoint( -1 ) );
1677 
1678  l.Remove( -1, -1 );
1679  l.SetPoint( 1, newLast );
1680  }
1681  }
1682 
1683  aHead.SetLayer( m_currentLayer );
1684  aHead.SetShape( l );
1685 
1686  if( !m_placingVia || aForceNoVia )
1687  return true;
1688 
1689  VIA v( makeVia( aP ) );
1690  v.SetNet( aHead.Net() );
1691 
1693  {
1694  aHead.AppendVia( v );
1695  return true;
1696  }
1697 
1698  VECTOR2I force;
1699  VECTOR2I lead = aP - m_p_start;
1700 
1701  bool solidsOnly = ( m_currentMode != RM_Walkaround );
1702 
1703  if( v.PushoutForce( m_currentNode, lead, force, solidsOnly, 40 ) )
1704  {
1705  SHAPE_LINE_CHAIN line = guessedDir.BuildInitialTrace( m_p_start, aP + force, false,
1706  fillet );
1707  aHead = LINE( aHead, line );
1708 
1709  v.SetPos( v.Pos() + force );
1710  return true;
1711  }
1712 
1713  return false; // via placement unsuccessful
1714 }
void SetPoint(int aIndex, const VECTOR2I &aPos)
Accessor Function to move a point to a specific location.
const std::string Format() const
Format the direction in a human readable word.
Definition: direction45.h:117
H/V/45 with filleted corners.
int PointCount() const
Definition: pns_line.h:140
ROUTING_SETTINGS & Settings() const
Return the logger object, allowing to dump geometry to a file.
const VECTOR2I & CPoint(int aIndex) const
Function Point()
VECTOR2I LineProject(const VECTOR2I &aP) const
Compute the perpendicular projection point of aP on a line passing through ends of the segment.
Definition: seg.cpp:268
Normal via.
Definition: router_tool.cpp:70
LINE m_tail
routing "tail": part of the track that has been already fixed due to collisions with obstacles
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:36
DIRECTION_45 m_direction
current routing direction
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false, bool aFillet=false) const
Build a 2-segment line chain between points aP0 and aP1 and following 45-degree routing regime.
MOUSE_TRAIL_TRACER m_mouseTrailTracer
void Remove(int aStartIndex, int aEndIndex)
Function Remove()
int SegmentCount() const
Function SegmentCount()
NODE * m_currentNode
Current world state.
Ignore collisions, mark obstacles.
CORNER_MODE GetCornerMode() const
const SEG CSegment(int aIndex) const
Function CSegment()
SHAPE_LINE_CHAIN.
Only walk around.
DIRECTION_45 GetPosture(const VECTOR2I &aP)
void Clear()
Function Clear() Removes all points from the line chain.
VECTOR2I m_p_start
current routing start (end of tail, beginning of head)
const VIA makeVia(const VECTOR2I &aP)

References PNS::LINE::AppendVia(), DIRECTION_45::BuildInitialTrace(), SHAPE_LINE_CHAIN::Clear(), SHAPE_LINE_CHAIN::CPoint(), SHAPE_LINE_CHAIN::CSegment(), DIRECTION_45::Format(), PNS::ROUTING_SETTINGS::GetCornerMode(), PNS::MOUSE_TRAIL_TRACER::GetPosture(), SEG::LineProject(), m_currentLayer, m_currentMode, m_currentNode, m_direction, m_mouseTrailTracer, m_orthoMode, m_p_start, m_placingVia, m_tail, makeVia(), PNS::ITEM::Net(), PNS::LINE::PointCount(), PNS::VIA::Pos(), PNS::VIA::PushoutForce(), SHAPE_LINE_CHAIN::Remove(), PNS::RM_MarkObstacles, PNS::RM_Walkaround, PNS::ROUNDED_45, SHAPE_LINE_CHAIN::SegmentCount(), PNS::ITEM::SetLayer(), PNS::ITEM::SetNet(), SHAPE_LINE_CHAIN::SetPoint(), PNS::VIA::SetPos(), PNS::LINE::SetShape(), and PNS::ALGO_BASE::Settings().

Referenced by rhMarkObstacles(), rhShoveOnly(), and rhWalkOnly().

◆ CommitPlacement()

bool PNS::LINE_PLACER::CommitPlacement ( )
overridevirtual

Reimplemented from PNS::PLACEMENT_ALGO.

Definition at line 1463 of file pns_line_placer.cpp.

1464 {
1465  if( m_lastNode )
1467 
1468  m_lastNode = nullptr;
1469  m_currentNode = nullptr;
1470  return true;
1471 }
ROUTER * Router() const
Return current router settings.
Definition: pns_algo_base.h:54
NODE * m_lastNode
Postprocessed world state (including marked collisions & removed loops)
void CommitRouting()
Definition: pns_router.cpp:694
NODE * m_currentNode
Current world state.

References PNS::ROUTER::CommitRouting(), m_currentNode, m_lastNode, and PNS::ALGO_BASE::Router().

◆ CurrentEnd()

const VECTOR2I& PNS::LINE_PLACER::CurrentEnd ( ) const
inlineoverridevirtual

Return the current end of the line being placed.

It may not be equal to the cursor position due to collisions.

Implements PNS::PLACEMENT_ALGO.

Definition at line 155 of file pns_line_placer.h.

156  {
157  return m_currentEnd;
158  }

References m_currentEnd.

◆ CurrentLayer()

int PNS::LINE_PLACER::CurrentLayer ( ) const
inlineoverridevirtual

Return the layer of currently routed track.

Implements PNS::PLACEMENT_ALGO.

Definition at line 171 of file pns_line_placer.h.

172  {
173  return m_currentLayer;
174  }

References m_currentLayer.

◆ CurrentNets()

const std::vector<int> PNS::LINE_PLACER::CurrentNets ( ) const
inlineoverridevirtual

Return the net code of currently routed track.

Implements PNS::PLACEMENT_ALGO.

Definition at line 163 of file pns_line_placer.h.

164  {
165  return std::vector<int>( 1, m_currentNet );
166  }

References m_currentNet.

◆ CurrentNode()

NODE * PNS::LINE_PLACER::CurrentNode ( bool  aLoopsRemoved = false) const
overridevirtual

Return the most recent world state.

Implements PNS::PLACEMENT_ALGO.

Definition at line 1031 of file pns_line_placer.cpp.

1032 {
1033  if( aLoopsRemoved && m_lastNode )
1034  return m_lastNode;
1035 
1036  return m_currentNode;
1037 }
NODE * m_lastNode
Postprocessed world state (including marked collisions & removed loops)
NODE * m_currentNode
Current world state.

References m_currentNode, and m_lastNode.

◆ Dbg()

◆ FixRoute()

bool PNS::LINE_PLACER::FixRoute ( const VECTOR2I aP,
ITEM aEndItem,
bool  aForceFinish 
)
overridevirtual

Commit the currently routed track to the parent node taking aP as the final end point and aEndItem as the final anchor (if provided).

Returns
true if route has been committed. May return false if the routing result is violating design rules. In such cases, the track is only committed if CanViolateDRC() is on.

<

Todo:
Determine what to do if m_lastNode is a null pointer. I'm guessing return false but someone with more knowledge of the code will need to determine that..

Implements PNS::PLACEMENT_ALGO.

Definition at line 1242 of file pns_line_placer.cpp.

1243 {
1244  bool fixAll = Settings().GetFixAllSegments();
1245  bool realEnd = false;
1246 
1247  LINE pl = Trace();
1248 
1250  {
1251  // Mark Obstacles is sort of a half-manual, half-automated mode in which the
1252  // user has more responsibility and authority.
1253 
1254  if( aEndItem )
1255  {
1256  // The user has indicated a connection should be made. If either the trace or
1257  // endItem is net-less, then allow the connection by adopting the net of the other.
1258  if( m_currentNet <= 0 )
1259  {
1260  m_currentNet = aEndItem->Net();
1261  pl.SetNet( m_currentNet );
1262  }
1263  else if (aEndItem->Net() <= 0 )
1264  {
1265  aEndItem->SetNet( m_currentNet );
1266  }
1267  }
1268 
1269  // Collisions still prevent fixing unless "Allow DRC violations" is checked
1270  if( !Settings().AllowDRCViolations() && m_world->CheckColliding( &pl ) )
1271  return false;
1272  }
1273 
1274  const SHAPE_LINE_CHAIN& l = pl.CLine();
1275 
1276  if( !l.SegmentCount() )
1277  {
1278  if( m_lastNode )
1279  {
1280  // Do a final optimization to the stored state
1281  NODE::ITEM_VECTOR removed, added;
1282  m_lastNode->GetUpdatedItems( removed, added );
1283 
1284  if( !added.empty() && added.back()->Kind() == ITEM::SEGMENT_T )
1285  simplifyNewLine( m_lastNode, static_cast<SEGMENT*>( added.back() ) );
1286  }
1287 
1288  // Nothing to commit if we have an empty line
1289  if( !pl.EndsWithVia() )
1290  return false;
1291 
1294  if( m_lastNode )
1295  m_lastNode->Add( Clone( pl.Via() ) );
1296 
1297  m_currentNode = nullptr;
1298 
1299  m_idle = true;
1300  m_placementCorrect = true;
1301  return true;
1302  }
1303 
1304  VECTOR2I p_pre_last = l.CPoint( -1 );
1305  const VECTOR2I p_last = l.CPoint( -1 );
1306 
1307  if( l.PointCount() > 2 )
1308  p_pre_last = l.CPoint( -2 );
1309 
1310  if( aEndItem && m_currentNet >= 0 && m_currentNet == aEndItem->Net() )
1311  realEnd = true;
1312 
1313  if( aForceFinish )
1314  realEnd = true;
1315 
1316  // TODO: Rollback doesn't work properly if fix-all isn't enabled and we are placing arcs,
1317  // so if we are, act as though we are in fix-all mode.
1318  if( !fixAll && l.ArcCount() )
1319  fixAll = true;
1320 
1321  // TODO: lastDirSeg will be calculated incorrectly if we end on an arc
1322  SEG lastDirSeg = ( !fixAll && l.SegmentCount() > 1 ) ? l.CSegment( -2 ) : l.CSegment( -1 );
1323  DIRECTION_45 d_last( lastDirSeg );
1324 
1325  int lastV;
1326 
1327  if( realEnd || m_placingVia || fixAll )
1328  lastV = l.SegmentCount();
1329  else
1330  lastV = std::max( 1, l.SegmentCount() - 1 );
1331 
1332  ARC arc;
1333  SEGMENT seg;
1334  LINKED_ITEM* lastItem = nullptr;
1335  int lastArc = -1;
1336 
1337  for( int i = 0; i < lastV; i++ )
1338  {
1339  ssize_t arcIndex = l.ArcIndex( i );
1340 
1341  if( arcIndex < 0 || ( lastArc >= 0 && i == lastV - 1 && l.CShapes()[lastV] == -1 ) )
1342  {
1343  seg = SEGMENT( pl.CSegment( i ), m_currentNet );
1344  seg.SetWidth( pl.Width() );
1345  seg.SetLayer( m_currentLayer );
1346 
1347  std::unique_ptr<SEGMENT> sp = std::make_unique<SEGMENT>( seg );
1348  lastItem = sp.get();
1349 
1350  if( !m_lastNode->Add( std::move( sp ) ) )
1351  lastItem = nullptr;
1352  }
1353  else
1354  {
1355  if( arcIndex == lastArc )
1356  continue;
1357 
1358  arc = ARC( l.Arc( arcIndex ), m_currentNet );
1359  arc.SetWidth( pl.Width() );
1360  arc.SetLayer( m_currentLayer );
1361 
1362  std::unique_ptr<ARC> ap = std::make_unique<ARC>( arc );
1363  lastItem = ap.get();
1364 
1365  m_lastNode->Add( std::move( ap ) );
1366  lastArc = arcIndex;
1367  }
1368  }
1369 
1370  if( pl.EndsWithVia() )
1371  m_lastNode->Add( Clone( pl.Via() ) );
1372 
1373  if( realEnd && lastItem )
1374  simplifyNewLine( m_lastNode, lastItem );
1375 
1376  if( !realEnd )
1377  {
1378  setInitialDirection( d_last );
1379  m_currentStart = ( m_placingVia || fixAll ) ? p_last : p_pre_last;
1380 
1382 
1383  m_startItem = nullptr;
1384  m_placingVia = false;
1385  m_chainedPlacement = !pl.EndsWithVia();
1386 
1389 
1390  m_head.Line().Clear();
1391  m_tail.Line().Clear();
1392  m_head.RemoveVia();
1393  m_tail.RemoveVia();
1396 
1397  if( m_shove )
1398  m_shove->AddLockedSpringbackNode( m_currentNode );
1399 
1400  DIRECTION_45 lastSegDir = pl.EndsWithVia() ? DIRECTION_45::UNDEFINED : d_last;
1401 
1406 
1407  m_placementCorrect = true;
1408  }
1409  else
1410  {
1411  m_placementCorrect = true;
1412  m_idle = true;
1413  }
1414 
1415  return realEnd;
1416 }
const SHAPE_ARC & Arc(size_t aArc) const
NODE * m_lastNode
Postprocessed world state (including marked collisions & removed loops)
NODE * m_world
pointer to world to search colliding items
void simplifyNewLine(NODE *aNode, LINKED_ITEM *aLatest)
Assemble a line starting from segment or arc aLatest, removes collinear segments and redundant vertic...
LINE m_head
the volatile part of the track from the previously analyzed point to the current routing destination
void RemoveVia()
Definition: pns_line.h:194
const LINE Trace() const
Return the complete routed line.
size_t ArcCount() const
int PointCount() const
Function PointCount()
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:127
const std::vector< ssize_t > & CShapes() const
ssize_t ArcIndex(size_t aSegment) const
ROUTING_SETTINGS & Settings() const
Return the logger object, allowing to dump geometry to a file.
const VECTOR2I & CPoint(int aIndex) const
Function Point()
DIRECTION_45 m_initial_direction
routing direction for new traces
LINE m_tail
routing "tail": part of the track that has been already fixed due to collisions with obstacles
void setInitialDirection(const DIRECTION_45 &aDirection)
Set preferred direction of the very first track segment to be laid.
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:36
std::unique_ptr< SHOVE > m_shove
The shove engine.
DIRECTION_45 m_direction
current routing direction
void AddTrailPoint(const VECTOR2I &aP)
MOUSE_TRAIL_TRACER m_mouseTrailTracer
FIXED_TAIL m_fixedTail
int SegmentCount() const
Function SegmentCount()
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:136
Definition: seg.h:40
NODE * m_currentNode
Current world state.
Ignore collisions, mark obstacles.
void AddStage(VECTOR2I aStart, int aLayer, bool placingVias, DIRECTION_45 direction, NODE *aNode)
const SEG CSegment(int aIndex) const
Function CSegment()
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:265
SHAPE_LINE_CHAIN.
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:433
void SetDefaultDirections(DIRECTION_45 aInitDirection, DIRECTION_45 aLastSegDir)
usual segment : line with rounded ends
int Width() const
Return true if the line is geometrically identical as line aOther.
Definition: pns_line.h:156
void GetUpdatedItems(ITEM_VECTOR &aRemoved, ITEM_VECTOR &aAdded)
Return the list of items removed and added in this branch with respect to the root branch.
Definition: pns_node.cpp:1302
void Clear()
Function Clear() Removes all points from the line chain.
VECTOR2I m_p_start
current routing start (end of tail, beginning of head)
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:621
std::vector< ITEM * > ITEM_VECTOR
Definition: pns_node.h:148

References PNS::NODE::Add(), PNS::FIXED_TAIL::AddStage(), PNS::MOUSE_TRAIL_TRACER::AddTrailPoint(), SHAPE_LINE_CHAIN::Arc(), SHAPE_LINE_CHAIN::ArcCount(), SHAPE_LINE_CHAIN::ArcIndex(), PNS::NODE::Branch(), PNS::NODE::CheckColliding(), PNS::MOUSE_TRAIL_TRACER::Clear(), SHAPE_LINE_CHAIN::Clear(), PNS::LINE::CLine(), PNS::Clone(), SHAPE_LINE_CHAIN::CPoint(), PNS::LINE::CSegment(), SHAPE_LINE_CHAIN::CSegment(), SHAPE_LINE_CHAIN::CShapes(), PNS::LINE::EndsWithVia(), PNS::ROUTING_SETTINGS::GetFixAllSegments(), PNS::NODE::GetUpdatedItems(), PNS::LINE::Line(), m_chainedPlacement, m_currentLayer, m_currentMode, m_currentNet, m_currentNode, m_currentStart, m_direction, m_fixedTail, m_head, m_idle, m_initial_direction, m_lastNode, m_mouseTrailTracer, m_p_start, m_placementCorrect, m_placingVia, m_shove, m_startItem, m_tail, m_world, PNS::ITEM::Net(), SHAPE_LINE_CHAIN::PointCount(), PNS::LINE::RemoveVia(), PNS::RM_MarkObstacles, PNS::ITEM::SEGMENT_T, SHAPE_LINE_CHAIN::SegmentCount(), PNS::MOUSE_TRAIL_TRACER::SetDefaultDirections(), setInitialDirection(), PNS::ITEM::SetLayer(), PNS::ITEM::SetNet(), PNS::ALGO_BASE::Settings(), PNS::MOUSE_TRAIL_TRACER::SetTolerance(), PNS::SEGMENT::SetWidth(), PNS::ARC::SetWidth(), simplifyNewLine(), Trace(), DIRECTION_45::UNDEFINED, PNS::LINE::Via(), and PNS::LINE::Width().

◆ FlipPosture()

void PNS::LINE_PLACER::FlipPosture ( )
overridevirtual

Toggle the current posture (straight/diagonal) of the trace head.

Reimplemented from PNS::PLACEMENT_ALGO.

Definition at line 1025 of file pns_line_placer.cpp.

1026 {
1028 }
MOUSE_TRAIL_TRACER m_mouseTrailTracer

References PNS::MOUSE_TRAIL_TRACER::FlipPosture(), and m_mouseTrailTracer.

◆ GetModifiedNets()

void PNS::LINE_PLACER::GetModifiedNets ( std::vector< int > &  aNets) const
overridevirtual

Function GetModifiedNets.

Returns the net codes of all currently routed trace(s)

Reimplemented from PNS::PLACEMENT_ALGO.

Definition at line 1717 of file pns_line_placer.cpp.

1718 {
1719  aNets.push_back( m_currentNet );
1720 }

References m_currentNet.

◆ handlePullback()

bool PNS::LINE_PLACER::handlePullback ( )
private

Deal with pull-back: reduces the tail if head trace is moved backwards wrs to the current tail direction.

Returns
true if the line has been changed.

Definition at line 174 of file pns_line_placer.cpp.

175 {
176  SHAPE_LINE_CHAIN& head = m_head.Line();
177  SHAPE_LINE_CHAIN& tail = m_tail.Line();
178 
179  if( head.PointCount() < 2 )
180  return false;
181 
182  int n = tail.PointCount();
183 
184  if( n == 0 )
185  {
186  return false;
187  }
188  else if( n == 1 )
189  {
190  m_p_start = tail.CPoint( 0 );
191  tail.Clear();
192  return true;
193  }
194 
195  DIRECTION_45 first_head, last_tail;
196 
197  const std::vector<ssize_t>& headShapes = head.CShapes();
198  const std::vector<ssize_t>& tailShapes = tail.CShapes();
199 
200  wxASSERT( tail.PointCount() >= 2 );
201 
202  if( headShapes[0] == -1 )
203  first_head = DIRECTION_45( head.CSegment( 0 ) );
204  else
205  first_head = DIRECTION_45( head.CArcs()[ headShapes[0] ] );
206 
207  int lastSegIdx = tail.PointCount() - 2;
208 
209  if( tailShapes[lastSegIdx] == -1 )
210  last_tail = DIRECTION_45( tail.CSegment( lastSegIdx ) );
211  else
212  last_tail = DIRECTION_45( tail.CArcs()[tailShapes[lastSegIdx]] );
213 
214  DIRECTION_45::AngleType angle = first_head.Angle( last_tail );
215 
216  // case 1: we have a defined routing direction, and the currently computed
217  // head goes in different one.
218  bool pullback_1 = false; // (m_direction != DIRECTION_45::UNDEFINED && m_direction != first_head);
219 
220  // case 2: regardless of the current routing direction, if the tail/head
221  // extremities form an acute or right angle, reduce the tail by one segment
222  // (and hope that further iterations) will result with a cleaner trace
223  bool pullback_2 = ( angle == DIRECTION_45::ANG_RIGHT || angle == DIRECTION_45::ANG_ACUTE );
224 
225  if( pullback_1 || pullback_2 )
226  {
227  lastSegIdx = tail.PrevShape( -1 );
228 
229  if( tailShapes[lastSegIdx] == -1 )
230  {
231  const SEG& seg = tail.CSegment( lastSegIdx );
232  m_direction = DIRECTION_45( seg );
233  m_p_start = seg.A;
234  }
235  else
236  {
237  const SHAPE_ARC& arc = tail.CArcs()[tailShapes[lastSegIdx]];
238  m_direction = DIRECTION_45( arc );
239  m_p_start = arc.GetP0();
240  }
241 
242  wxLogTrace( "PNS", "Placer: pullback triggered [%d] [%s %s]",
243  n, last_tail.Format().c_str(), first_head.Format().c_str() );
244 
245  // erase the last point in the tail, hoping that the next iteration will
246  // result with a head trace that starts with a segment following our
247  // current direction.
248  if( n < 2 )
249  tail.Clear(); // don't leave a single-point tail
250  else
251  tail.RemoveShape( -1 );
252 
253  if( !tail.SegmentCount() )
255 
256  return true;
257  }
258 
259  return false;
260 }
int PrevShape(int aPointIndex) const
void RemoveShape(int aPointIndex)
Removes the shape at the given index from the line chain.
const std::string Format() const
Format the direction in a human readable word.
Definition: direction45.h:117
LINE m_head
the volatile part of the track from the previously analyzed point to the current routing destination
const std::vector< SHAPE_ARC > & CArcs() const
int PointCount() const
Function PointCount()
const std::vector< ssize_t > & CShapes() const
AngleType Angle(const DIRECTION_45 &aOther) const
Return the type of angle between directions (this) and aOther.
Definition: direction45.h:169
const VECTOR2I & CPoint(int aIndex) const
Function Point()
DIRECTION_45 m_initial_direction
routing direction for new traces
LINE m_tail
routing "tail": part of the track that has been already fixed due to collisions with obstacles
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:36
DIRECTION_45 m_direction
current routing direction
const VECTOR2I & GetP0() const
Definition: shape_arc.h:95
int SegmentCount() const
Function SegmentCount()
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:136
Definition: seg.h:40
AngleType
Represent kind of angle formed by vectors heading in two DIRECTION_45s.
Definition: direction45.h:65
const SEG CSegment(int aIndex) const
Function CSegment()
SHAPE_LINE_CHAIN.
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
VECTOR2I A
Definition: seg.h:48
void Clear()
Function Clear() Removes all points from the line chain.
VECTOR2I m_p_start
current routing start (end of tail, beginning of head)

References SEG::A, DIRECTION_45::ANG_ACUTE, DIRECTION_45::ANG_RIGHT, PNS::angle(), DIRECTION_45::Angle(), SHAPE_LINE_CHAIN::CArcs(), SHAPE_LINE_CHAIN::Clear(), SHAPE_LINE_CHAIN::CPoint(), SHAPE_LINE_CHAIN::CSegment(), SHAPE_LINE_CHAIN::CShapes(), DIRECTION_45::Format(), SHAPE_ARC::GetP0(), PNS::LINE::Line(), m_direction, m_head, m_initial_direction, m_p_start, m_tail, SHAPE_LINE_CHAIN::PointCount(), SHAPE_LINE_CHAIN::PrevShape(), SHAPE_LINE_CHAIN::RemoveShape(), and SHAPE_LINE_CHAIN::SegmentCount().

Referenced by routeStep().

◆ handleSelfIntersections()

bool PNS::LINE_PLACER::handleSelfIntersections ( )
private

Check if the head of the track intersects its tail.

If so, cuts the tail up to the intersecting segment and fixes the head direction to match the last segment before the cut.

Returns
true if the line has been changed.

Definition at line 102 of file pns_line_placer.cpp.

103 {
105  SHAPE_LINE_CHAIN& head = m_head.Line();
106  SHAPE_LINE_CHAIN& tail = m_tail.Line();
107 
108  // if there is no tail, there is nothing to intersect with
109  if( tail.PointCount() < 2 )
110  return false;
111 
112  if( head.PointCount() < 2 )
113  return false;
114 
115  // completely new head trace? chop off the tail
116  if( tail.CPoint(0) == head.CPoint(0) )
117  {
118  m_p_start = tail.CPoint( 0 );
120  tail.Clear();
121  return true;
122  }
123 
124  tail.Intersect( head, ips );
125 
126  // no intesection points - nothing to reduce
127  if( ips.empty() )
128  return false;
129 
130  int n = INT_MAX;
131  VECTOR2I ipoint;
132 
133  // if there is more than one intersection, find the one that is
134  // closest to the beginning of the tail.
135  for( const SHAPE_LINE_CHAIN::INTERSECTION& i : ips )
136  {
137  if( i.index_our < n )
138  {
139  n = i.index_our;
140  ipoint = i.p;
141  }
142  }
143 
144  // ignore the point where head and tail meet
145  if( ipoint == head.CPoint( 0 ) || ipoint == tail.CPoint( -1 ) )
146  return false;
147 
148  // Intersection point is on the first or the second segment: just start routing
149  // from the beginning
150  if( n < 2 )
151  {
152  m_p_start = tail.CPoint( 0 );
154  tail.Clear();
155  head.Clear();
156 
157  return true;
158  }
159  else
160  {
161  // Clip till the last tail segment before intersection.
162  // Set the direction to the one of this segment.
163  const SEG last = tail.CSegment( n - 1 );
164  m_p_start = last.A;
165  m_direction = DIRECTION_45( last );
166  tail.Remove( n, -1 );
167  return true;
168  }
169 
170  return false;
171 }
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
std::vector< INTERSECTION > INTERSECTIONS
LINE m_head
the volatile part of the track from the previously analyzed point to the current routing destination
int PointCount() const
Function PointCount()
const VECTOR2I & CPoint(int aIndex) const
Function Point()
DIRECTION_45 m_initial_direction
routing direction for new traces
LINE m_tail
routing "tail": part of the track that has been already fixed due to collisions with obstacles
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:36
DIRECTION_45 m_direction
current routing direction
void Remove(int aStartIndex, int aEndIndex)
Function Remove()
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:136
Definition: seg.h:40
const SEG CSegment(int aIndex) const
Function CSegment()
SHAPE_LINE_CHAIN.
VECTOR2I A
Definition: seg.h:48
void Clear()
Function Clear() Removes all points from the line chain.
VECTOR2I m_p_start
current routing start (end of tail, beginning of head)

References SEG::A, SHAPE_LINE_CHAIN::Clear(), SHAPE_LINE_CHAIN::CPoint(), SHAPE_LINE_CHAIN::CSegment(), SHAPE_LINE_CHAIN::Intersect(), PNS::LINE::Line(), m_direction, m_head, m_initial_direction, m_p_start, m_tail, SHAPE_LINE_CHAIN::PointCount(), and SHAPE_LINE_CHAIN::Remove().

Referenced by routeStep().

◆ HasPlacedAnything()

bool PNS::LINE_PLACER::HasPlacedAnything ( ) const
overridevirtual

Reimplemented from PNS::PLACEMENT_ALGO.

Definition at line 1457 of file pns_line_placer.cpp.

1458 {
1459  return m_placementCorrect || m_fixedTail.StageCount() > 1;
1460 }
FIXED_TAIL m_fixedTail
int StageCount() const

References m_fixedTail, m_placementCorrect, and PNS::FIXED_TAIL::StageCount().

◆ Head()

const LINE& PNS::LINE_PLACER::Head ( ) const
inline

Return the "head" of the line being placed, that is the volatile part that has not been "fixed" yet.

Definition at line 133 of file pns_line_placer.h.

133 { return m_head; }
LINE m_head
the volatile part of the track from the previously analyzed point to the current routing destination

References m_head.

◆ initPlacement()

void PNS::LINE_PLACER::initPlacement ( )
private

Initialize placement of a new line with given parameters.

Definition at line 1155 of file pns_line_placer.cpp.

1156 {
1157  m_idle = false;
1158 
1159  m_head.Line().Clear();
1160  m_tail.Line().Clear();
1167  m_head.RemoveVia();
1168  m_tail.RemoveVia();
1169 
1172 
1173  NODE* world = Router()->GetWorld();
1174 
1175  world->KillChildren();
1176  NODE* rootNode = world->Branch();
1177 
1179 
1180  setWorld( rootNode );
1181 
1182  wxLogTrace( "PNS", "world %p, intitial-direction %s layer %d",
1183  m_world,
1184  m_direction.Format().c_str(),
1185  m_currentLayer );
1186 
1187  m_lastNode = nullptr;
1189  m_currentMode = Settings().Mode();
1190 
1191  m_shove.reset();
1192 
1194  m_shove = std::make_unique<SHOVE>( m_world->Branch(), Router() );
1195 }
ROUTER * Router() const
Return current router settings.
Definition: pns_algo_base.h:54
NODE * m_lastNode
Postprocessed world state (including marked collisions & removed loops)
NODE * m_world
pointer to world to search colliding items
void SetLayer(int aLayer)
Definition: pns_item.h:155
const std::string Format() const
Format the direction in a human readable word.
Definition: direction45.h:117
LINE m_head
the volatile part of the track from the previously analyzed point to the current routing destination
void RemoveVia()
Definition: pns_line.h:194
SIZES_SETTINGS m_sizes
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:127
void SetWidth(int aWidth)
Return line width.
Definition: pns_line.h:149
void SetNet(int aNet)
Definition: pns_item.h:149
ROUTING_SETTINGS & Settings() const
Return the logger object, allowing to dump geometry to a file.
DIRECTION_45 m_initial_direction
routing direction for new traces
void KillChildren()
Definition: pns_node.cpp:1369
LINE m_tail
routing "tail": part of the track that has been already fixed due to collisions with obstacles
bool SplitAdjacentSegments(NODE *aNode, ITEM *aSeg, const VECTOR2I &aP)
Check if point aP lies on segment aSeg.
std::unique_ptr< SHOVE > m_shove
The shove engine.
DIRECTION_45 m_direction
current routing direction
PNS_MODE Mode() const
Set the routing mode.
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:136
Guess what's better, try to make least mess on the PCB.
NODE * m_currentNode
Current world state.
void setWorld(NODE *aWorld)
Set the board to route.
void Clear()
Function Clear() Removes all points from the line chain.
VECTOR2I m_p_start
current routing start (end of tail, beginning of head)
NODE * GetWorld() const
Definition: pns_router.h:153

References PNS::NODE::Branch(), SHAPE_LINE_CHAIN::Clear(), DIRECTION_45::Format(), PNS::ROUTER::GetWorld(), PNS::NODE::KillChildren(), PNS::LINE::Line(), m_currentLayer, m_currentMode, m_currentNet, m_currentNode, m_currentStart, m_direction, m_head, m_idle, m_initial_direction, m_lastNode, m_p_start, m_shove, m_sizes, m_startItem, m_tail, m_world, PNS::ROUTING_SETTINGS::Mode(), PNS::LINE::RemoveVia(), PNS::RM_Shove, PNS::RM_Smart, PNS::ALGO_BASE::Router(), PNS::ITEM::SetLayer(), PNS::ITEM::SetNet(), PNS::ALGO_BASE::Settings(), PNS::LINE::SetWidth(), setWorld(), SplitAdjacentSegments(), and PNS::SIZES_SETTINGS::TrackWidth().

Referenced by Start().

◆ IsPlacingVia()

bool PNS::LINE_PLACER::IsPlacingVia ( ) const
inlineoverridevirtual

Function IsPlacingVia()

Returns true if the placer is placing a via (or more vias).

Reimplemented from PNS::PLACEMENT_ALGO.

Definition at line 196 of file pns_line_placer.h.

196 { return m_placingVia; }

References m_placingVia.

◆ Logger()

LOGGER * PNS::ALGO_BASE::Logger ( )
virtualinherited

Reimplemented in PNS::SHOVE.

Definition at line 34 of file pns_algo_base.cpp.

35 {
36  return NULL;
37 }
#define NULL

References NULL.

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

◆ makeVia()

◆ mergeHead()

bool PNS::LINE_PLACER::mergeHead ( )
private

Moves "established" segments from the head to the tail if certain conditions are met.

Returns
true, if the line has been changed.

Definition at line 328 of file pns_line_placer.cpp.

329 {
330  SHAPE_LINE_CHAIN& head = m_head.Line();
331  SHAPE_LINE_CHAIN& tail = m_tail.Line();
332 
333  const int ForbiddenAngles = DIRECTION_45::ANG_ACUTE
336 
337  head.Simplify();
338  tail.Simplify();
339 
340  int n_head = head.ShapeCount();
341  int n_tail = tail.ShapeCount();
342 
343  if( n_head < 3 )
344  {
345  wxLogTrace( "PNS", "Merge failed: not enough head segs." );
346  return false;
347  }
348 
349  if( n_tail && head.CPoint( 0 ) != tail.CPoint( -1 ) )
350  {
351  wxLogTrace( "PNS", "Merge failed: head and tail discontinuous." );
352  return false;
353  }
354 
355  if( m_head.CountCorners( ForbiddenAngles ) != 0 )
356  return false;
357 
358  DIRECTION_45 dir_tail, dir_head;
359 
360  const std::vector<ssize_t>& headShapes = head.CShapes();
361  const std::vector<ssize_t>& tailShapes = tail.CShapes();
362 
363  if( headShapes[0] == -1 )
364  dir_head = DIRECTION_45( head.CSegment( 0 ) );
365  else
366  dir_head = DIRECTION_45( head.CArcs()[ headShapes[0] ] );
367 
368  if( n_tail )
369  {
370  wxASSERT( tail.PointCount() >= 2 );
371  int lastSegIdx = tail.PointCount() - 2;
372 
373  if( tailShapes[lastSegIdx] == -1 )
374  dir_tail = DIRECTION_45( tail.CSegment( -1 ) );
375  else
376  dir_tail = DIRECTION_45( tail.CArcs()[ tailShapes[lastSegIdx] ] );
377 
378  if( dir_head.Angle( dir_tail ) & ForbiddenAngles )
379  return false;
380  }
381 
382  tail.Append( head );
383 
384  tail.Simplify();
385 
386  SEG last = tail.CSegment( -1 );
387  m_p_start = last.B;
388 
389  int lastSegIdx = tail.PointCount() - 2;
390 
391  if( tailShapes[lastSegIdx] == -1 )
392  m_direction = DIRECTION_45( tail.CSegment( -1 ) );
393  else
394  m_direction = DIRECTION_45( tail.CArcs()[ tailShapes[lastSegIdx] ] );
395 
396  head.Remove( 0, -1 );
397 
398  wxLogTrace( "PNS", "Placer: merge %d, new direction: %s", n_head,
399  m_direction.Format().c_str() );
400 
401  head.Simplify();
402  tail.Simplify();
403 
404  return true;
405 }
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Function Simplify()
const std::string Format() const
Format the direction in a human readable word.
Definition: direction45.h:117
LINE m_head
the volatile part of the track from the previously analyzed point to the current routing destination
const std::vector< SHAPE_ARC > & CArcs() const
int PointCount() const
Function PointCount()
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
const std::vector< ssize_t > & CShapes() const
AngleType Angle(const DIRECTION_45 &aOther) const
Return the type of angle between directions (this) and aOther.
Definition: direction45.h:169
const VECTOR2I & CPoint(int aIndex) const
Function Point()
LINE m_tail
routing "tail": part of the track that has been already fixed due to collisions with obstacles
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:36
DIRECTION_45 m_direction
current routing direction
int ShapeCount() const
Returns the number of shapes (line segments or arcs) in this line chain.
void Remove(int aStartIndex, int aEndIndex)
Function Remove()
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:136
Definition: seg.h:40
const SEG CSegment(int aIndex) const
Function CSegment()
SHAPE_LINE_CHAIN.
VECTOR2I m_p_start
current routing start (end of tail, beginning of head)
int CountCorners(int aAngles) const
Definition: pns_line.cpp:135
VECTOR2I B
Definition: seg.h:49

References DIRECTION_45::ANG_ACUTE, DIRECTION_45::ANG_HALF_FULL, DIRECTION_45::ANG_UNDEFINED, DIRECTION_45::Angle(), SHAPE_LINE_CHAIN::Append(), SEG::B, SHAPE_LINE_CHAIN::CArcs(), PNS::LINE::CountCorners(), SHAPE_LINE_CHAIN::CPoint(), SHAPE_LINE_CHAIN::CSegment(), SHAPE_LINE_CHAIN::CShapes(), DIRECTION_45::Format(), PNS::LINE::Line(), m_direction, m_head, m_p_start, m_tail, SHAPE_LINE_CHAIN::PointCount(), SHAPE_LINE_CHAIN::Remove(), SHAPE_LINE_CHAIN::ShapeCount(), and SHAPE_LINE_CHAIN::Simplify().

Referenced by routeStep().

◆ Move()

bool PNS::LINE_PLACER::Move ( const VECTOR2I aP,
ITEM aEndItem 
)
overridevirtual

Move the end of the currently routed trace to the point aP, taking aEndItem as anchor (if not NULL).

Implements PNS::PLACEMENT_ALGO.

Definition at line 1198 of file pns_line_placer.cpp.

1199 {
1200  LINE current;
1201  VECTOR2I p = aP;
1202  int eiDepth = -1;
1203 
1204  if( aEndItem && aEndItem->Owner() )
1205  eiDepth = static_cast<NODE*>( aEndItem->Owner() )->Depth();
1206 
1207  if( m_lastNode )
1208  {
1209  delete m_lastNode;
1210  m_lastNode = nullptr;
1211  }
1212 
1213  bool reachesEnd = route( p );
1214 
1215  current = Trace();
1216 
1217  if( !current.PointCount() )
1219  else
1220  m_currentEnd = current.CLine().CPoint( -1 );
1221 
1222  NODE* latestNode = m_currentNode;
1223  m_lastNode = latestNode->Branch();
1224 
1225  if( reachesEnd
1226  && eiDepth >= 0
1227  && aEndItem && latestNode->Depth() > eiDepth
1228  && current.SegmentCount() )
1229  {
1230  SplitAdjacentSegments( m_lastNode, aEndItem, current.CPoint( -1 ) );
1231 
1232  if( Settings().RemoveLoops() )
1233  removeLoops( m_lastNode, current );
1234  }
1235 
1238  return true;
1239 }
NODE * m_lastNode
Postprocessed world state (including marked collisions & removed loops)
void removeLoops(NODE *aNode, LINE &aLatest)
Searches aNode for traces concurrent to aLatest and removes them.
const LINE Trace() const
Return the complete routed line.
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:127
bool RemoveLoops() const
Enable/disable loop (redundant track) removal.
ROUTING_SETTINGS & Settings() const
Return the logger object, allowing to dump geometry to a file.
bool SplitAdjacentSegments(NODE *aNode, ITEM *aSeg, const VECTOR2I &aP)
Check if point aP lies on segment aSeg.
void AddTrailPoint(const VECTOR2I &aP)
void updateLeadingRatLine()
Draw the "leading" rats nest line, which connects the end of currently routed track and the nearest y...
MOUSE_TRAIL_TRACER m_mouseTrailTracer
bool route(const VECTOR2I &aP)
Re-route the current track to point aP.
NODE * m_currentNode
Current world state.
VECTOR2I m_p_start
current routing start (end of tail, beginning of head)

References PNS::MOUSE_TRAIL_TRACER::AddTrailPoint(), PNS::NODE::Branch(), PNS::LINE::CLine(), PNS::LINE::CPoint(), SHAPE_LINE_CHAIN::CPoint(), PNS::NODE::Depth(), m_currentEnd, m_currentNode, m_lastNode, m_mouseTrailTracer, m_p_start, PNS::ITEM::Owner(), PNS::LINE::PointCount(), PNS::ROUTING_SETTINGS::RemoveLoops(), removeLoops(), route(), PNS::LINE::SegmentCount(), PNS::ALGO_BASE::Settings(), SplitAdjacentSegments(), Trace(), and updateLeadingRatLine().

Referenced by SetLayer().

◆ optimizeTailHeadTransition()

bool PNS::LINE_PLACER::optimizeTailHeadTransition ( )
private

Try to reduce the corner count of the most recent part of tail/head by merging obtuse/collinear segments.

Returns
true if the line has been changed.

Definition at line 829 of file pns_line_placer.cpp.

830 {
831  LINE linetmp = Trace();
832 
833  PNS_DBG( Dbg(), Message, "optimize HT" );
834 
836  {
837  if( linetmp.SegmentCount() < 1 )
838  return false;
839 
840  m_head = linetmp;
841  m_p_start = linetmp.CLine().CPoint( 0 );
842  m_direction = DIRECTION_45( linetmp.CSegment( 0 ) );
843  m_tail.Line().Clear();
844 
845  PNS_DBG( Dbg(), Message, wxString::Format( "Placer: optimize fanout-cleanup" ) );
846 
847 
848  return true;
849  }
850 
851  SHAPE_LINE_CHAIN& head = m_head.Line();
852  SHAPE_LINE_CHAIN& tail = m_tail.Line();
853 
854  int tailLookbackSegments = 3;
855 
856  //if(m_currentMode() == RM_Walkaround)
857  // tailLookbackSegments = 10000;
858 
859  int threshold = std::min( tail.PointCount(), tailLookbackSegments + 1 );
860 
861  if( tail.ShapeCount() < 3 )
862  return false;
863 
864  // assemble TailLookbackSegments tail segments with the current head
865  SHAPE_LINE_CHAIN opt_line = tail.Slice( -threshold, -1 );
866 
867  int end = std::min(2, head.PointCount() - 1 );
868 
869  opt_line.Append( head.Slice( 0, end ) );
870 
871  LINE new_head( m_tail, opt_line );
872 
873  // and see if it could be made simpler by merging obtuse/collnear segments.
874  // If so, replace the (threshold) last tail points and the head with
875  // the optimized line
876 
877 
878  PNS_DBG( Dbg(), AddLine, new_head.CLine(), LIGHTCYAN, 10000, "ht-newline" );
879 
881  {
882  LINE tmp( m_tail, opt_line );
883 
884  PNS_DBG( Dbg(), Message, wxString::Format( "Placer: optimize tail-head [%d]", threshold ) );
885 
886  head.Clear();
887  tail.Replace( -threshold, -1, new_head.CLine() );
888  tail.Simplify();
889 
890  m_p_start = new_head.CLine().CPoint( -1 );
891  m_direction = DIRECTION_45( new_head.CSegment( -1 ) );
892 
893  return true;
894  }
895 
896  return false;
897 }
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Function Simplify()
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Function Slice()
Simplify pad-pad and pad-via connections if possible.
LINE m_head
the volatile part of the track from the previously analyzed point to the current routing destination
const LINE Trace() const
Return the complete routed line.
int PointCount() const
Function PointCount()
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
LINE m_tail
routing "tail": part of the track that has been already fixed due to collisions with obstacles
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:36
DIRECTION_45 m_direction
current routing direction
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I aV=VECTOR2I(0, 0))
#define PNS_DBG(dbg, method,...)
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
int ShapeCount() const
Returns the number of shapes (line segments or arcs) in this line chain.
Reduce corner cost iteratively.
Definition: pns_optimizer.h:99
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:136
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
NODE * m_currentNode
Current world state.
SHAPE_LINE_CHAIN.
void Clear()
Function Clear() Removes all points from the line chain.
VECTOR2I m_p_start
current routing start (end of tail, beginning of head)
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Function Replace()

References SHAPE_LINE_CHAIN::Append(), SHAPE_LINE_CHAIN::Clear(), PNS::LINE::CLine(), SHAPE_LINE_CHAIN::CPoint(), PNS::LINE::CSegment(), PNS::ALGO_BASE::Dbg(), PNS::OPTIMIZER::FANOUT_CLEANUP, Format(), LIGHTCYAN, PNS::LINE::Line(), m_currentNode, m_direction, m_head, m_p_start, m_tail, PNS::OPTIMIZER::MERGE_SEGMENTS, PNS::OPTIMIZER::Optimize(), PNS_DBG, SHAPE_LINE_CHAIN::PointCount(), SHAPE_LINE_CHAIN::Replace(), PNS::LINE::SegmentCount(), SHAPE_LINE_CHAIN::ShapeCount(), SHAPE_LINE_CHAIN::Simplify(), SHAPE_LINE_CHAIN::Slice(), and Trace().

Referenced by routeStep().

◆ reduceTail()

bool PNS::LINE_PLACER::reduceTail ( const VECTOR2I aEnd)
private

Attempt to reduce the number of segments in the tail by trying to replace a certain number of latest tail segments with a direct trace leading to aEnd that does not collide with anything.

Parameters
aEndis the current routing destination point.
Returns
true if the line has been changed.

Definition at line 263 of file pns_line_placer.cpp.

264 {
265  SHAPE_LINE_CHAIN& head = m_head.Line();
266  SHAPE_LINE_CHAIN& tail = m_tail.Line();
267 
268  int n = tail.SegmentCount();
269 
270  if( head.SegmentCount() < 1 )
271  return false;
272 
273  // Don't attempt this for too short tails
274  if( n < 2 )
275  return false;
276 
277  // Start from the segment farthest from the end of the tail
278  // int start_index = std::max(n - 1 - ReductionDepth, 0);
279 
280  DIRECTION_45 new_direction;
281  VECTOR2I new_start;
282  int reduce_index = -1;
283 
284  for( int i = tail.SegmentCount() - 1; i >= 0; i-- )
285  {
286  const SEG s = tail.CSegment( i );
287  DIRECTION_45 dir( s );
288 
289  // calculate a replacement route and check if it matches
290  // the direction of the segment to be replaced
291  SHAPE_LINE_CHAIN replacement = dir.BuildInitialTrace( s.A, aEnd );
292 
293  if( replacement.SegmentCount() < 1 )
294  continue;
295 
296  LINE tmp( m_tail, replacement );
297 
299  break;
300 
301  if( DIRECTION_45( replacement.CSegment( 0 ) ) == dir )
302  {
303  new_start = s.A;
304  new_direction = dir;
305  reduce_index = i;
306  }
307  }
308 
309  if( reduce_index >= 0 )
310  {
311  wxLogTrace( "PNS", "Placer: reducing tail: %d", reduce_index );
312  SHAPE_LINE_CHAIN reducedLine = new_direction.BuildInitialTrace( new_start, aEnd );
313 
314  m_p_start = new_start;
315  m_direction = new_direction;
316  tail.Remove( reduce_index + 1, -1 );
317  head.Clear();
318  return true;
319  }
320 
321  if( !tail.SegmentCount() )
323 
324  return false;
325 }
LINE m_head
the volatile part of the track from the previously analyzed point to the current routing destination
DIRECTION_45 m_initial_direction
routing direction for new traces
LINE m_tail
routing "tail": part of the track that has been already fixed due to collisions with obstacles
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:36
DIRECTION_45 m_direction
current routing direction
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false, bool aFillet=false) const
Build a 2-segment line chain between points aP0 and aP1 and following 45-degree routing regime.
void Remove(int aStartIndex, int aEndIndex)
Function Remove()
int SegmentCount() const
Function SegmentCount()
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:136
Definition: seg.h:40
NODE * m_currentNode
Current world state.
const SEG CSegment(int aIndex) const
Function CSegment()
SHAPE_LINE_CHAIN.
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:433
VECTOR2I A
Definition: seg.h:48
void Clear()
Function Clear() Removes all points from the line chain.
VECTOR2I m_p_start
current routing start (end of tail, beginning of head)

References SEG::A, PNS::ITEM::ANY_T, DIRECTION_45::BuildInitialTrace(), PNS::NODE::CheckColliding(), SHAPE_LINE_CHAIN::Clear(), SHAPE_LINE_CHAIN::CSegment(), PNS::LINE::Line(), m_currentNode, m_direction, m_head, m_initial_direction, m_p_start, m_tail, SHAPE_LINE_CHAIN::Remove(), and SHAPE_LINE_CHAIN::SegmentCount().

Referenced by routeStep().

◆ removeLoops()

void PNS::LINE_PLACER::removeLoops ( NODE aNode,
LINE aLatest 
)
private

Searches aNode for traces concurrent to aLatest and removes them.

Updated topology is stored in aNode.

Definition at line 1474 of file pns_line_placer.cpp.

1475 {
1476  if( !aLatest.SegmentCount() )
1477  return;
1478 
1479  if( aLatest.CLine().CPoint( 0 ) == aLatest.CLine().CPoint( -1 ) )
1480  return;
1481 
1482  std::set<LINKED_ITEM *> toErase;
1483  aNode->Add( aLatest, true );
1484 
1485  for( int s = 0; s < aLatest.LinkCount(); s++ )
1486  {
1487  LINKED_ITEM* seg = aLatest.GetLink(s);
1488  LINE ourLine = aNode->AssembleLine( seg );
1489  JOINT a, b;
1490  std::vector<LINE> lines;
1491 
1492  aNode->FindLineEnds( ourLine, a, b );
1493 
1494  if( a == b )
1495  aNode->FindLineEnds( aLatest, a, b );
1496 
1497  aNode->FindLinesBetweenJoints( a, b, lines );
1498 
1499  int removedCount = 0;
1500  int total = 0;
1501 
1502  for( LINE& line : lines )
1503  {
1504  total++;
1505 
1506  if( !( line.ContainsLink( seg ) ) && line.SegmentCount() )
1507  {
1508  for( LINKED_ITEM* ss : line.Links() )
1509  toErase.insert( ss );
1510 
1511  removedCount++;
1512  }
1513  }
1514 
1515  wxLogTrace( "PNS", "total segs removed: %d/%d", removedCount, total );
1516  }
1517 
1518  for( LINKED_ITEM* s : toErase )
1519  aNode->Remove( s );
1520 
1521  aNode->Remove( aLatest );
1522 }

References PNS::NODE::Add(), PNS::NODE::AssembleLine(), PNS::LINE::CLine(), SHAPE_LINE_CHAIN::CPoint(), PNS::NODE::FindLineEnds(), PNS::NODE::FindLinesBetweenJoints(), PNS::LINK_HOLDER::GetLink(), PNS::LINK_HOLDER::LinkCount(), PNS::NODE::Remove(), and PNS::LINE::SegmentCount().

Referenced by Move().

◆ rhMarkObstacles()

bool PNS::LINE_PLACER::rhMarkObstacles ( const VECTOR2I aP,
LINE aNewHead 
)
private

Definition at line 682 of file pns_line_placer.cpp.

683 {
684  buildInitialLine( aP, m_head );
685  m_head.SetBlockingObstacle( nullptr );
686 
687  // Note: Something like the below could be used to implement a "stop at first obstacle" mode,
688  // but we don't have one right now and there isn't a lot of demand for one. If we do end up
689  // doing that, put it in a new routing mode as "highlight collisions" mode should not have
690  // collision handling other than highlighting.
691 #if 0
692  if( !Settings().AllowDRCViolations() )
693  {
695 
696  if( obs && obs->m_distFirst != INT_MAX )
697  {
698  buildInitialLine( obs->m_ipFirst, m_head );
699  m_head.SetBlockingObstacle( obs->m_item );
700  }
701  }
702 #endif
703 
704  aNewHead = m_head;
705 
706  return true;
707 }
OPT_OBSTACLE NearestObstacle(const LINE *aLine, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=NULL)
Follow the line in search of an obstacle that is nearest to the starting to the line's starting point...
Definition: pns_node.cpp:281
LINE m_head
the volatile part of the track from the previously analyzed point to the current routing destination
ROUTING_SETTINGS & Settings() const
Return the logger object, allowing to dump geometry to a file.
NODE * m_currentNode
Current world state.
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:147
bool buildInitialLine(const VECTOR2I &aP, LINE &aHead, bool aForceNoVia=false)
void SetBlockingObstacle(ITEM *aObstacle)
Definition: pns_line.h:205

References buildInitialLine(), m_currentNode, m_head, PNS::NODE::NearestObstacle(), PNS::LINE::SetBlockingObstacle(), and PNS::ALGO_BASE::Settings().

Referenced by routeHead().

◆ rhShoveOnly()

bool PNS::LINE_PLACER::rhShoveOnly ( const VECTOR2I aP,
LINE aNewHead 
)
private

Route step mark obstacles mode.

Definition at line 710 of file pns_line_placer.cpp.

711 {
712  LINE initTrack( m_head );
713  LINE walkSolids, l2;
714 
715  bool viaOk = buildInitialLine( aP, initTrack );
716 
717  m_currentNode = m_shove->CurrentNode();
718 
719  m_shove->SetLogger( Logger() );
720  m_shove->SetDebugDecorator( Dbg() );
721 
722  OPTIMIZER optimizer( m_currentNode );
723 
724  WALKAROUND walkaround( m_currentNode, Router() );
725 
726  walkaround.SetSolidsOnly( true );
727  walkaround.SetIterationLimit( 10 );
728  walkaround.SetDebugDecorator( Dbg() );
729  walkaround.SetLogger( Logger() );
730  WALKAROUND::WALKAROUND_STATUS stat_solids = walkaround.Route( initTrack, walkSolids );
731 
732  optimizer.SetEffortLevel( OPTIMIZER::MERGE_SEGMENTS );
733  optimizer.SetCollisionMask( ITEM::SOLID_T );
734  optimizer.Optimize( &walkSolids );
735 
736  if( stat_solids == WALKAROUND::DONE )
737  l2 = walkSolids;
738  else
739  l2 = initTrack.ClipToNearestObstacle( m_shove->CurrentNode() );
740 
741  LINE l( m_tail );
742  l.Line().Append( l2.CLine() );
743  l.Line().Simplify();
744 
745  if( l.PointCount() == 0 || l2.PointCount() == 0 )
746  {
747  aNewHead = m_head;
748  return false;
749  }
750 
751  if( m_placingVia && viaOk )
752  {
753  VIA v1( makeVia( l.CPoint( -1 ) ) );
754  VIA v2( makeVia( l2.CPoint( -1 ) ) );
755 
756  l.AppendVia( v1 );
757  l2.AppendVia( v2 );
758  }
759 
760  l.Line().Simplify();
761 
762  // in certain, uncommon cases there may be loops in the head+tail, In such case, we don't
763  // shove to avoid screwing up the database.
764  if( l.HasLoops() )
765  {
766  aNewHead = m_head;
767  return false;
768  }
769 
770  SHOVE::SHOVE_STATUS status = m_shove->ShoveLines( l );
771 
772  m_currentNode = m_shove->CurrentNode();
773 
774  if( status == SHOVE::SH_OK || status == SHOVE::SH_HEAD_MODIFIED )
775  {
776  if( status == SHOVE::SH_HEAD_MODIFIED )
777  l2 = m_shove->NewHead();
778 
779  optimizer.SetWorld( m_currentNode );
780 
781  int effortLevel = OPTIMIZER::MERGE_OBTUSE;
782 
783  if( Settings().SmartPads() && !m_mouseTrailTracer.IsManuallyForced() )
784  effortLevel = OPTIMIZER::SMART_PADS;
785 
786  optimizer.SetEffortLevel( effortLevel );
787 
788  optimizer.SetCollisionMask( ITEM::ANY_T );
789  optimizer.Optimize( &l2 );
790 
791  aNewHead = l2;
792 
793  return true;
794  }
795  else
796  {
797  walkaround.SetWorld( m_currentNode );
798  walkaround.SetSolidsOnly( false );
799  walkaround.SetIterationLimit( 10 );
800  walkaround.SetApproachCursor( true, aP );
801  walkaround.Route( initTrack, l2 );
802  aNewHead = l2.ClipToNearestObstacle( m_shove->CurrentNode() );
803 
804  return false;
805  }
806 
807  return false;
808 }
ROUTER * Router() const
Return current router settings.
Definition: pns_algo_base.h:54
VECTOR2I v2(1, 0)
Test suite for KiCad math code.
virtual LOGGER * Logger()
LINE m_head
the volatile part of the track from the previously analyzed point to the current routing destination
ROUTING_SETTINGS & Settings() const
Return the logger object, allowing to dump geometry to a file.
Normal via.
Definition: router_tool.cpp:70
LINE m_tail
routing "tail": part of the track that has been already fixed due to collisions with obstacles
std::unique_ptr< SHOVE > m_shove
The shove engine.
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
MOUSE_TRAIL_TRACER m_mouseTrailTracer
Reduce corner cost iteratively.
Definition: pns_optimizer.h:99
NODE * m_currentNode
Current world state.
Reduce corner cost by merging obtuse segments.
const VIA makeVia(const VECTOR2I &aP)
Reroute pad exits.
bool buildInitialLine(const VECTOR2I &aP, LINE &aHead, bool aForceNoVia=false)

References PNS::ITEM::ANY_T, SHAPE_LINE_CHAIN::Append(), PNS::LINE::AppendVia(), buildInitialLine(), PNS::LINE::CLine(), PNS::LINE::ClipToNearestObstacle(), PNS::LINE::CPoint(), PNS::ALGO_BASE::Dbg(), PNS::WALKAROUND::DONE, PNS::LINE::HasLoops(), PNS::MOUSE_TRAIL_TRACER::IsManuallyForced(), PNS::LINE::Line(), PNS::ALGO_BASE::Logger(), m_currentNode, m_head, m_mouseTrailTracer, m_placingVia, m_shove, m_tail, makeVia(), PNS::OPTIMIZER::MERGE_OBTUSE, PNS::OPTIMIZER::MERGE_SEGMENTS, PNS::OPTIMIZER::Optimize(), PNS::LINE::PointCount(), PNS::WALKAROUND::Route(), PNS::ALGO_BASE::Router(), PNS::WALKAROUND::SetApproachCursor(), PNS::OPTIMIZER::SetCollisionMask(), PNS::ALGO_BASE::SetDebugDecorator(), PNS::OPTIMIZER::SetEffortLevel(), PNS::WALKAROUND::SetIterationLimit(), PNS::ALGO_BASE::SetLogger(), PNS::WALKAROUND::SetSolidsOnly(), PNS::ALGO_BASE::Settings(), PNS::WALKAROUND::SetWorld(), PNS::OPTIMIZER::SetWorld(), PNS::SHOVE::SH_HEAD_MODIFIED, PNS::SHOVE::SH_OK, SHAPE_LINE_CHAIN::Simplify(), PNS::OPTIMIZER::SMART_PADS, PNS::ITEM::SOLID_T, and v2.

Referenced by routeHead().

◆ rhWalkOnly()

bool PNS::LINE_PLACER::rhWalkOnly ( const VECTOR2I aP,
LINE aNewHead 
)
private

Route step shove mode.

Definition at line 533 of file pns_line_placer.cpp.

534 {
535  LINE initTrack( m_head );
536  LINE walkFull( m_head );
537 
538  initTrack.RemoveVia();
539  walkFull.RemoveVia();
540 
541  int effort = 0;
542  bool viaOk = false;
543 
544  VECTOR2I walkP = aP;
545 
546  WALKAROUND walkaround( m_currentNode, Router() );
547 
548  walkaround.SetSolidsOnly( false );
549  walkaround.SetDebugDecorator( Dbg() );
550  walkaround.SetLogger( Logger() );
551  walkaround.SetIterationLimit( Settings().WalkaroundIterationLimit() );
552 
553  char name[50];
554  int round = 0;
555 
556  do {
557  snprintf( name, sizeof( name ), "walk-round-%d", round );
558  PNS_DBG( Dbg(), BeginGroup, name );
559 
560  viaOk = buildInitialLine( walkP, initTrack, round == 0 );
561 
562  double initialLength = initTrack.CLine().Length();
563  double hugThresholdLength = initialLength * Settings().WalkaroundHugLengthThreshold();
564 
565  WALKAROUND::RESULT wr = walkaround.Route( initTrack );
566 
567  SHAPE_LINE_CHAIN l_cw = wr.lineCw.CLine();
568  SHAPE_LINE_CHAIN l_ccw = wr.lineCcw.CLine();
569 
570  if( wr.statusCcw == WALKAROUND::DONE || wr.statusCw == WALKAROUND::DONE )
571  {
572  int len_cw = wr.statusCw == WALKAROUND::DONE ? l_cw.Length() : INT_MAX;
573  int len_ccw = wr.statusCcw == WALKAROUND::DONE ? l_ccw.Length() : INT_MAX;
574 
575  PNS_DBG( Dbg(), AddLine, wr.lineCw.CLine(), CYAN, 10000, "wf-result-cw" );
576  PNS_DBG( Dbg(), AddLine, wr.lineCcw.CLine(), BLUE, 20000, "wf-result-ccw" );
577 
578  int bestLength = len_cw < len_ccw ? len_cw : len_ccw;
579 
580  if( bestLength > hugThresholdLength )
581  {
582  wr.statusCw = WALKAROUND::ALMOST_DONE;
583  wr.statusCcw = WALKAROUND::ALMOST_DONE;
584  }
585 
586  SHAPE_LINE_CHAIN& bestLine = len_cw < len_ccw ? l_cw : l_ccw;
587  walkFull.SetShape( bestLine );
588  }
589 
590  if( wr.statusCcw == WALKAROUND::ALMOST_DONE || wr.statusCw == WALKAROUND::ALMOST_DONE )
591  {
592  bool valid_cw = false, valid_ccw = false;
593  VECTOR2I p_cw, p_ccw;
594  int dist_ccw, dist_cw;
595 
596  if( wr.statusCcw == WALKAROUND::ALMOST_DONE )
597  {
598  valid_ccw = cursorDistMinimum( l_ccw, aP, hugThresholdLength, dist_ccw, p_ccw );
599  if( valid_ccw )
600  {
601  int idx_ccw = l_ccw.Split( p_ccw );
602  l_ccw = l_ccw.Slice( 0, idx_ccw );
603  PNS_DBG( Dbg(), AddPoint, p_ccw, BLUE, 500000, "hug-target-ccw" );
604  PNS_DBG( Dbg(), AddLine, l_ccw, MAGENTA, 200000, "wh-result-ccw" );
605  }
606  }
607  if( wr.statusCw == WALKAROUND::ALMOST_DONE )
608  {
609  valid_cw = cursorDistMinimum( l_cw, aP, hugThresholdLength, dist_cw, p_cw );
610  if( valid_cw )
611  {
612  int idx_cw = l_cw.Split( p_cw );
613  l_cw = l_cw.Slice( 0, idx_cw );
614  PNS_DBG( Dbg(), AddPoint, p_cw, YELLOW, 500000, "hug-target-cw" );
615  PNS_DBG( Dbg(), AddLine, l_cw, BLUE, 200000, "wh-result-cw" );
616  }
617  }
618 
619  if( dist_cw < dist_ccw && valid_cw )
620  {
621  walkFull.SetShape( l_cw );
622  walkP = p_cw;
623  }
624  else if ( valid_ccw )
625  {
626  walkFull.SetShape( l_ccw );
627  walkP = p_ccw;
628  }
629  else
630  {
631  PNS_DBGN( Dbg(), EndGroup );
632  return false;
633  }
634  }
635  else if ( wr.statusCcw == WALKAROUND::STUCK || wr.statusCw == WALKAROUND::STUCK )
636  {
637  PNS_DBGN( Dbg(), EndGroup );
638  return false;
639  }
640 
641  PNS_DBGN( Dbg(), EndGroup );
642 
643  round++;
644  } while( round < 2 && m_placingVia );
645 
646  PNS_DBG( Dbg(), AddLine, walkFull.CLine(), GREEN, 200000, "walk-full" );
647 
648  switch( Settings().OptimizerEffort() )
649  {
650  case OE_LOW:
651  effort = 0;
652  break;
653 
654  case OE_MEDIUM:
655  case OE_FULL:
656  effort = OPTIMIZER::MERGE_SEGMENTS;
657  break;
658  }
659 
661  effort |= OPTIMIZER::SMART_PADS;
662 
663  if( m_placingVia && viaOk )
664  {
665  walkFull.AppendVia( makeVia( walkFull.CPoint( -1 ) ) );
666  }
667 
668  OPTIMIZER::Optimize( &walkFull, effort, m_currentNode );
669 
670 
671  if( m_currentNode->CheckColliding( &walkFull ) )
672  {
673  return false;
674  }
675 
676  aNewHead = walkFull;
677 
678  return true;
679 }
#define PNS_DBGN(dbg, method)
bool SmartPads() const
Enable/disable Smart Pads (optimized connections).
ROUTER * Router() const
Return current router settings.
Definition: pns_algo_base.h:54
long long int Length() const
Function Length()
int Split(const VECTOR2I &aP)
Function Split()
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Function Slice()
virtual LOGGER * Logger()
LINE m_head
the volatile part of the track from the previously analyzed point to the current routing destination
ROUTING_SETTINGS & Settings() const
Return the logger object, allowing to dump geometry to a file.
Definition: color4d.h:67
static bool cursorDistMinimum(const SHAPE_LINE_CHAIN &aL, const VECTOR2I &aCursor, double lengthThreshold, int &theDist, VECTOR2I &aNearest)
PNS_OPTIMIZATION_EFFORT OptimizerEffort() const
Set the optimizer effort. Bigger means cleaner traces, but slower routing.
Definition: color4d.h:57
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I aV=VECTOR2I(0, 0))
#define PNS_DBG(dbg, method,...)
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
Definition: color4d.h:58
MOUSE_TRAIL_TRACER m_mouseTrailTracer
Reduce corner cost iteratively.
Definition: pns_optimizer.h:99
NODE * m_currentNode
Current world state.
Definition: color4d.h:56
const char * name
Definition: DXF_plotter.cpp:59
SHAPE_LINE_CHAIN.
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:433
double WalkaroundHugLengthThreshold() const
const VIA makeVia(const VECTOR2I &aP)
Reroute pad exits.
bool buildInitialLine(const VECTOR2I &aP, LINE &aHead, bool aForceNoVia=false)

References PNS::WALKAROUND::ALMOST_DONE, PNS::LINE::AppendVia(), BLUE, buildInitialLine(), PNS::NODE::CheckColliding(), PNS::LINE::CLine(), PNS::LINE::CPoint(), PNS::cursorDistMinimum(), CYAN, PNS::ALGO_BASE::Dbg(), PNS::WALKAROUND::DONE, GREEN, PNS::MOUSE_TRAIL_TRACER::IsManuallyForced(), SHAPE_LINE_CHAIN::Length(), PNS::WALKAROUND::RESULT::lineCcw, PNS::WALKAROUND::RESULT::lineCw, PNS::ALGO_BASE::Logger(), m_currentNode, m_head, m_mouseTrailTracer, m_placingVia, MAGENTA, makeVia(), PNS::OPTIMIZER::MERGE_SEGMENTS, name, PNS::OE_FULL, PNS::OE_LOW, PNS::OE_MEDIUM, PNS::OPTIMIZER::Optimize(), PNS::ROUTING_SETTINGS::OptimizerEffort(), PNS_DBG, PNS_DBGN, PNS::LINE::RemoveVia(), PNS::WALKAROUND::Route(), PNS::ALGO_BASE::Router(), PNS::ALGO_BASE::SetDebugDecorator(), PNS::WALKAROUND::SetIterationLimit(), PNS::ALGO_BASE::SetLogger(), PNS::LINE::SetShape(), PNS::WALKAROUND::SetSolidsOnly(), PNS::ALGO_BASE::Settings(), SHAPE_LINE_CHAIN::Slice(), PNS::OPTIMIZER::SMART_PADS, PNS::ROUTING_SETTINGS::SmartPads(), SHAPE_LINE_CHAIN::Split(), PNS::WALKAROUND::RESULT::statusCcw, PNS::WALKAROUND::RESULT::statusCw, PNS::WALKAROUND::STUCK, PNS::ROUTING_SETTINGS::WalkaroundHugLengthThreshold(), and YELLOW.

Referenced by routeHead().

◆ route()

bool PNS::LINE_PLACER::route ( const VECTOR2I aP)
private

Re-route the current track to point aP.

Returns true, when routing has completed successfully (i.e. the trace end has reached point aP), and false if the trace was stuck somewhere on the way. May call routeStep() repetitively due to mouse smoothing.

Parameters
aPending point of current route.
Returns
true, if the routing is complete.

Definition at line 996 of file pns_line_placer.cpp.

997 {
998  routeStep( aP );
999 
1000  if (!m_head.PointCount() )
1001  return false;
1002 
1003  return m_head.CPoint(-1) == aP;
1004 }
void routeStep(const VECTOR2I &aP)
Perform a single routing algorithm step, for the end point aP.
LINE m_head
the volatile part of the track from the previously analyzed point to the current routing destination
int PointCount() const
Definition: pns_line.h:140
const VECTOR2I & CPoint(int aIdx) const
Definition: pns_line.h:145

References PNS::LINE::CPoint(), m_head, PNS::LINE::PointCount(), and routeStep().

Referenced by Move().

◆ routeHead()

bool PNS::LINE_PLACER::routeHead ( const VECTOR2I aP,
LINE aNewHead 
)
private

Compute the head trace between the current start point (m_p_start) and point aP, starting with direction defined in m_direction.

The trace walks around all colliding solid or non-movable items. Movable segments are ignored, as they'll be handled later by the shove algorithm.

Definition at line 811 of file pns_line_placer.cpp.

812 {
813  switch( m_currentMode )
814  {
815  case RM_MarkObstacles:
816  return rhMarkObstacles( aP, aNewHead );
817  case RM_Walkaround:
818  return rhWalkOnly( aP, aNewHead );
819  case RM_Shove:
820  return rhShoveOnly( aP, aNewHead );
821  default:
822  break;
823  }
824 
825  return false;
826 }
bool rhWalkOnly(const VECTOR2I &aP, LINE &aNewHead)
Route step shove mode.
bool rhMarkObstacles(const VECTOR2I &aP, LINE &aNewHead)
bool rhShoveOnly(const VECTOR2I &aP, LINE &aNewHead)
Route step mark obstacles mode.
Ignore collisions, mark obstacles.
Only walk around.

References m_currentMode, rhMarkObstacles(), rhShoveOnly(), rhWalkOnly(), PNS::RM_MarkObstacles, PNS::RM_Shove, and PNS::RM_Walkaround.

Referenced by routeStep().

◆ Router()

◆ routeStep()

void PNS::LINE_PLACER::routeStep ( const VECTOR2I aP)
private

Perform a single routing algorithm step, for the end point aP.

Parameters
aPis the ending point of current route.
Returns
true if the line has been changed.Route step walk around mode.

Definition at line 900 of file pns_line_placer.cpp.

901 {
902  bool fail = false;
903  bool go_back = false;
904 
905  int i, n_iter = 1;
906 
907  LINE new_head;
908 
909  wxLogTrace( "PNS", "routeStep: direction: %s head: %d, tail: %d shapes",
910  m_direction.Format().c_str(),
911  m_head.ShapeCount(),
912  m_tail.ShapeCount() );
913 
914  PNS_DBG( Dbg(), BeginGroup, "route-step" );
915 
916  PNS_DBG( Dbg(), AddLine, m_tail.CLine(), WHITE, 10000, "tail-init" );
917  PNS_DBG( Dbg(), AddLine, m_head.CLine(), GREEN, 10000, "head-init" );
918 
919  for( i = 0; i < n_iter; i++ )
920  {
921  if( !go_back && Settings().FollowMouse() )
922  reduceTail( aP );
923 
924  PNS_DBG( Dbg(), AddLine, m_tail.CLine(), WHITE, 10000, "tail-after-reduce" );
925  PNS_DBG( Dbg(), AddLine, m_head.CLine(), GREEN, 10000, "head-after-reduce" );
926 
927  go_back = false;
928 
929  if( !routeHead( aP, new_head ) )
930  fail = true;
931 
932  if( !new_head.Is45Degree() )
933  fail = true;
934 
935  if( fail )
936  break;
937 
938  m_head = new_head;
939 
940  PNS_DBG( Dbg(), AddLine, m_head.CLine(), LIGHTGREEN, 100000, "head-new" );
941 
943  {
944  n_iter++;
945  go_back = true;
946  }
947 
948  PNS_DBG( Dbg(), AddLine, m_tail.CLine(), WHITE, 10000, "tail-after-si" );
949  PNS_DBG( Dbg(), AddLine, m_head.CLine(), GREEN, 10000, "head-after-si" );
950 
951  if( !go_back && handlePullback() )
952  {
953  n_iter++;
954  go_back = true;
955  }
956 
957  PNS_DBG( Dbg(), AddLine, m_tail.CLine(), WHITE, 100000, "tail-after-pb" );
958  PNS_DBG( Dbg(), AddLine, m_head.CLine(), GREEN, 100000, "head-after-pb" );
959  }
960 
961  if( fail )
962  {
963  if( m_last_head.PointCount() > 0 )
964  {
966  }
967  else
968  {
969  m_head.RemoveVia();
970  m_head.Clear();
971  }
972  }
973  else
974  {
976  }
977 
978  if( !fail && Settings().FollowMouse() )
979  {
980  PNS_DBG( Dbg(), AddLine, m_tail.CLine(), WHITE, 10000, "tail-pre-merge" );
981  PNS_DBG( Dbg(), AddLine, m_head.CLine(), GREEN, 10000, "head-pre-merge" );
982 
984  {
985  mergeHead();
986  }
987 
988  PNS_DBG( Dbg(), AddLine, m_tail.CLine(), WHITE, 100000, "tail-post-merge" );
989  PNS_DBG( Dbg(), AddLine, m_head.CLine(), GREEN, 100000, "head-post-merge" );
990  }
991 
992  PNS_DBGN( Dbg(), EndGroup );
993 }
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:137
#define PNS_DBGN(dbg, method)
LINE m_last_head
Most recent successful (non-colliding) head.
const std::string Format() const
Format the direction in a human readable word.
Definition: direction45.h:117
LINE m_head
the volatile part of the track from the previously analyzed point to the current routing destination
void RemoveVia()
Definition: pns_line.h:194
bool reduceTail(const VECTOR2I &aEnd)
Attempt to reduce the number of segments in the tail by trying to replace a certain number of latest ...
int PointCount() const
Definition: pns_line.h:140
bool handlePullback()
Deal with pull-back: reduces the tail if head trace is moved backwards wrs to the current tail direct...
bool FollowMouse() const
Return true if smoothing segments during dragging is enabled.
ROUTING_SETTINGS & Settings() const
Return the logger object, allowing to dump geometry to a file.
LINE m_tail
routing "tail": part of the track that has been already fixed due to collisions with obstacles
DIRECTION_45 m_direction
current routing direction
Definition: color4d.h:57
#define PNS_DBG(dbg, method,...)
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
bool routeHead(const VECTOR2I &aP, LINE &aNewHead)
Compute the head trace between the current start point (m_p_start) and point aP, starting with direct...
bool handleSelfIntersections()
Check if the head of the track intersects its tail.
Definition: color4d.h:48
int ShapeCount() const
Return the aIdx-th point of the line.
Definition: pns_line.h:142
bool optimizeTailHeadTransition()
Try to reduce the corner count of the most recent part of tail/head by merging obtuse/collinear segme...
bool mergeHead()
Moves "established" segments from the head to the tail if certain conditions are met.
void Clear()
Definition: pns_line.cpp:1256

References PNS::LINE::Clear(), PNS::LINE::CLine(), PNS::ALGO_BASE::Dbg(), PNS::ROUTING_SETTINGS::FollowMouse(), DIRECTION_45::Format(), GREEN, handlePullback(), handleSelfIntersections(), PNS::LINE::Is45Degree(), LIGHTGREEN, m_direction, m_head, m_last_head, m_tail, mergeHead(), optimizeTailHeadTransition(), PNS_DBG, PNS_DBGN, PNS::LINE::PointCount(), reduceTail(), PNS::LINE::RemoveVia(), routeHead(), PNS::ALGO_BASE::Settings(), PNS::LINE::ShapeCount(), and WHITE.

Referenced by route().

◆ 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 rhShoveOnly(), rhWalkOnly(), PNS::SHOVE::SHOVE(), and PNS::DRAGGER::tryWalkaround().

◆ setInitialDirection()

void PNS::LINE_PLACER::setInitialDirection ( const DIRECTION_45 aDirection)
private

Set preferred direction of the very first track segment to be laid.

Used by posture switching mechanism.

Definition at line 93 of file pns_line_placer.cpp.

94 {
95  m_initial_direction = aDirection;
96 
97  if( m_tail.SegmentCount() == 0 )
98  m_direction = aDirection;
99 }
int SegmentCount() const
Definition: pns_line.h:139
DIRECTION_45 m_initial_direction
routing direction for new traces
LINE m_tail
routing "tail": part of the track that has been already fixed due to collisions with obstacles
DIRECTION_45 m_direction
current routing direction

References m_direction, m_initial_direction, m_tail, and PNS::LINE::SegmentCount().

Referenced by FixRoute(), and Start().

◆ SetLayer()

bool PNS::LINE_PLACER::SetLayer ( int  aLayer)
overridevirtual

Set the current routing layer.

Reimplemented from PNS::PLACEMENT_ALGO.

Definition at line 1068 of file pns_line_placer.cpp.

1069 {
1070  if( m_idle )
1071  {
1072  m_currentLayer = aLayer;
1073  return true;
1074  }
1075  else if( m_chainedPlacement )
1076  {
1077  return false;
1078  }
1079  else if( !m_startItem
1080  || ( m_startItem->OfKind( ITEM::VIA_T ) && m_startItem->Layers().Overlaps( aLayer ) )
1081  || ( m_startItem->OfKind( ITEM::SOLID_T ) && m_startItem->Layers().Overlaps( aLayer ) ) )
1082  {
1083  m_currentLayer = aLayer;
1084  m_head.Line().Clear();
1085  m_tail.Line().Clear();
1088  Move( m_currentEnd, nullptr );
1089  return true;
1090  }
1091 
1092  return false;
1093 }
bool Move(const VECTOR2I &aP, ITEM *aEndItem) override
Move the end of the currently routed trace to the point aP, taking aEndItem as anchor (if not NULL).
void SetLayer(int aLayer)
Definition: pns_item.h:155
LINE m_head
the volatile part of the track from the previously analyzed point to the current routing destination
bool Overlaps(const LAYER_RANGE &aOther) const
Definition: pns_layerset.h:67
LINE m_tail
routing "tail": part of the track that has been already fixed due to collisions with obstacles
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:136
bool OfKind(int aKindMask) const
Return true if the item's type matches the mask aKindMask.
Definition: pns_item.h:136
void Clear()
Function Clear() Removes all points from the line chain.
const LAYER_RANGE & Layers() const
Definition: pns_item.h:152

References SHAPE_LINE_CHAIN::Clear(), PNS::ITEM::Layers(), PNS::LINE::Line(), m_chainedPlacement, m_currentEnd, m_currentLayer, m_head, m_idle, m_startItem, m_tail, Move(), PNS::ITEM::OfKind(), LAYER_RANGE::Overlaps(), PNS::ITEM::SetLayer(), PNS::ITEM::SOLID_T, and PNS::ITEM::VIA_T.

◆ 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 rhShoveOnly(), rhWalkOnly(), and PNS::DRAGGER::tryWalkaround().

◆ SetOrthoMode()

void PNS::LINE_PLACER::SetOrthoMode ( bool  aOrthoMode)
overridevirtual

Function SetOrthoMode()

Forces the router to place a straight 90/45 degree trace (with the end as near to the cursor as possible) instead of a standard 135 degree two-segment bend.

Reimplemented from PNS::PLACEMENT_ALGO.

Definition at line 1639 of file pns_line_placer.cpp.

1640 {
1641  m_orthoMode = aOrthoMode;
1642 }

References m_orthoMode.

◆ Settings()

◆ setWorld()

void PNS::LINE_PLACER::setWorld ( NODE aWorld)
private

Set the board to route.

Definition at line 67 of file pns_line_placer.cpp.

68 {
69  m_world = aWorld;
70 }
NODE * m_world
pointer to world to search colliding items

References m_world.

Referenced by initPlacement().

◆ simplifyNewLine()

void PNS::LINE_PLACER::simplifyNewLine ( NODE aNode,
LINKED_ITEM aLatest 
)
private

Assemble a line starting from segment or arc aLatest, removes collinear segments and redundant vertices.

If a simplification has been found, replaces the old line with the simplified one in aNode.

Definition at line 1525 of file pns_line_placer.cpp.

1526 {
1527  wxASSERT( aLatest->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) );
1528 
1529  // Before we assemble the final line and run the optimizer, do a separate pass to clean up
1530  // colinear segments that exist on non-line-corner joints, as these will prevent proper assembly
1531  // of the line and won't get cleaned up by the optimizer.
1532  NODE::ITEM_VECTOR removed, added;
1533  aNode->GetUpdatedItems( removed, added );
1534 
1535  std::set<ITEM*> cleanup;
1536 
1537  auto processJoint =
1538  [&]( JOINT* aJoint, ITEM* aItem )
1539  {
1540  if( !aJoint || aJoint->IsLineCorner() )
1541  return;
1542 
1543  SEG refSeg = static_cast<SEGMENT*>( aItem )->Seg();
1544 
1545  NODE::ITEM_VECTOR toRemove;
1546 
1547  for( ITEM* neighbor : aJoint->Links() )
1548  {
1549  if( neighbor == aItem || !neighbor->LayersOverlap( aItem ) )
1550  continue;
1551 
1552  const SEG& testSeg = static_cast<SEGMENT*>( neighbor )->Seg();
1553 
1554  if( refSeg.Contains( testSeg ) )
1555  {
1556  JOINT* nA = aNode->FindJoint( neighbor->Anchor( 0 ), neighbor );
1557  JOINT* nB = aNode->FindJoint( neighbor->Anchor( 1 ), neighbor );
1558 
1559  if( ( nA == aJoint && nB->LinkCount() == 1 ) ||
1560  ( nB == aJoint && nA->LinkCount() == 1 ) )
1561  {
1562  cleanup.insert( neighbor );
1563  }
1564  }
1565  }
1566  };
1567 
1568  for( ITEM* item : added )
1569  {
1570  if( !item->OfKind( ITEM::SEGMENT_T ) || cleanup.count( item ) )
1571  continue;
1572 
1573  JOINT* jA = aNode->FindJoint( item->Anchor( 0 ), item );
1574  JOINT* jB = aNode->FindJoint( item->Anchor( 1 ), item );
1575 
1576  processJoint( jA, item );
1577  processJoint( jB, item );
1578  }
1579 
1580  for( ITEM* seg : cleanup )
1581  aNode->Remove( seg );
1582 
1583  // And now we can proceed with assembling the final line and optimizing it.
1584 
1585  LINE l = aNode->AssembleLine( aLatest );
1586 
1587  bool optimized = OPTIMIZER::Optimize( &l, OPTIMIZER::MERGE_COLINEAR, aNode );
1588 
1589  SHAPE_LINE_CHAIN simplified( l.CLine() );
1590 
1591  simplified.Simplify();
1592 
1593  if( optimized || simplified.PointCount() != l.PointCount() )
1594  {
1595  aNode->Remove( l );
1596  l.SetShape( simplified );
1597  aNode->Add( l );
1598  }
1599 }
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Function Simplify()
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I aV=VECTOR2I(0, 0))
void Remove(int aStartIndex, int aEndIndex)
Function Remove()
Definition: seg.h:40
SHAPE_LINE_CHAIN.
Merge co-linear segments.
std::vector< ITEM * > ITEM_VECTOR
Definition: pns_node.h:148
bool Contains(const SEG &aSeg) const
Definition: seg.h:331

References PNS::NODE::Add(), PNS::ITEM::ARC_T, PNS::NODE::AssembleLine(), PNS::LINE::CLine(), SEG::Contains(), PNS::NODE::FindJoint(), PNS::NODE::GetUpdatedItems(), PNS::JOINT::IsLineCorner(), PNS::JOINT::LinkCount(), PNS::JOINT::Links(), PNS::OPTIMIZER::MERGE_COLINEAR, PNS::ITEM::OfKind(), PNS::OPTIMIZER::Optimize(), PNS::LINE::PointCount(), PNS::NODE::Remove(), PNS::ITEM::SEGMENT_T, PNS::LINE::SetShape(), and SHAPE_LINE_CHAIN::Simplify().

Referenced by FixRoute().

◆ SplitAdjacentSegments()

bool PNS::LINE_PLACER::SplitAdjacentSegments ( NODE aNode,
ITEM aSeg,
const VECTOR2I aP 
)

Check if point aP lies on segment aSeg.

If so, splits the segment in two, forming a joint at aP and stores updated topology in node aNode.

Definition at line 1040 of file pns_line_placer.cpp.

1041 {
1042  if( !aSeg )
1043  return false;
1044 
1045  if( !aSeg->OfKind( ITEM::SEGMENT_T ) )
1046  return false;
1047 
1048  JOINT* jt = aNode->FindJoint( aP, aSeg );
1049 
1050  if( jt && jt->LinkCount() >= 1 )
1051  return false;
1052 
1053  SEGMENT* s_old = static_cast<SEGMENT*>( aSeg );
1054 
1055  std::unique_ptr<SEGMENT> s_new[2] = { Clone( *s_old ), Clone( *s_old ) };
1056 
1057  s_new[0]->SetEnds( s_old->Seg().A, aP );
1058  s_new[1]->SetEnds( aP, s_old->Seg().B );
1059 
1060  aNode->Remove( s_old );
1061  aNode->Add( std::move( s_new[0] ), true );
1062  aNode->Add( std::move( s_new[1] ), true );
1063 
1064  return true;
1065 }
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:265
usual segment : line with rounded ends

References SEG::A, PNS::NODE::Add(), SEG::B, PNS::Clone(), PNS::NODE::FindJoint(), PNS::JOINT::LinkCount(), PNS::ITEM::OfKind(), PNS::NODE::Remove(), PNS::SEGMENT::Seg(), and PNS::ITEM::SEGMENT_T.

Referenced by PNS::ROUTER::BreakSegment(), initPlacement(), and Move().

◆ Start()

bool PNS::LINE_PLACER::Start ( const VECTOR2I aP,
ITEM aStartItem 
)
overridevirtual

Start routing a single track at point aP, taking item aStartItem as anchor (unless NULL).

Implements PNS::PLACEMENT_ALGO.

Definition at line 1096 of file pns_line_placer.cpp.

1097 {
1098  m_placementCorrect = false;
1099  m_currentStart = VECTOR2I( aP );
1100  m_currentEnd = VECTOR2I( aP );
1101  m_currentNet = std::max( 0, aStartItem ? aStartItem->Net() : 0 );
1102  m_startItem = aStartItem;
1103  m_placingVia = false;
1104  m_chainedPlacement = false;
1105  m_fixedTail.Clear();
1106 
1107  setInitialDirection( Settings().InitialDirection() );
1108 
1109  initPlacement();
1110 
1111  DIRECTION_45 initialDir = m_initial_direction;
1113 
1114  if( aStartItem && aStartItem->Kind() == ITEM::SEGMENT_T )
1115  {
1116  // If we land on a segment endpoint, assume the starting direction is continuing along
1117  // the same direction as the endpoint. If we started in the middle, don't set a
1118  // direction so that the posture solver is not biased.
1119  SEG seg = static_cast<SEGMENT*>( aStartItem )->Seg();
1120 
1121  if( aP == seg.A )
1122  lastSegDir = DIRECTION_45( seg.Reversed() );
1123  else if( aP == seg.B )
1124  lastSegDir = DIRECTION_45( seg );
1125  }
1126  else if( aStartItem && aStartItem->Kind() == ITEM::SOLID_T &&
1127  static_cast<SOLID*>( aStartItem )->Parent()->Type() == PCB_PAD_T )
1128  {
1129  double angle = static_cast<SOLID*>( aStartItem )->GetOrientation() / 10.0;
1130  angle = ( angle + 22.5 ) / 45.0;
1131  initialDir = DIRECTION_45( static_cast<DIRECTION_45::Directions>( int( angle ) ) );
1132  }
1133 
1134  wxLogTrace( "PNS", "Posture: init %s, last seg %s", initialDir.Format(), lastSegDir.Format() );
1135 
1140  m_mouseTrailTracer.SetMouseDisabled( !Settings().GetAutoPosture() );
1141 
1142  NODE *n;
1143 
1144  if ( m_shove )
1145  n = m_shove->CurrentNode();
1146  else
1147  n = m_currentNode;
1148 
1150 
1151  return true;
1152 }
const std::string Format() const
Format the direction in a human readable word.
Definition: direction45.h:117
LINE m_head
the volatile part of the track from the previously analyzed point to the current routing destination
class PAD, a pad in a footprint
Definition: typeinfo.h:89
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
ROUTING_SETTINGS & Settings() const
Return the logger object, allowing to dump geometry to a file.
DIRECTION_45 m_initial_direction
routing direction for new traces
void setInitialDirection(const DIRECTION_45 &aDirection)
Set preferred direction of the very first track segment to be laid.
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:36
std::unique_ptr< SHOVE > m_shove
The shove engine.
DIRECTION_45 m_direction
current routing direction
void initPlacement()
Initialize placement of a new line with given parameters.
void AddTrailPoint(const VECTOR2I &aP)
MOUSE_TRAIL_TRACER m_mouseTrailTracer
FIXED_TAIL m_fixedTail
SEG Reversed() const
Returns the center point of the line.
Definition: seg.h:380
Definition: seg.h:40
NODE * m_currentNode
Current world state.
void AddStage(VECTOR2I aStart, int aLayer, bool placingVias, DIRECTION_45 direction, NODE *aNode)
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
void SetDefaultDirections(DIRECTION_45 aInitDirection, DIRECTION_45 aLastSegDir)
VECTOR2I A
Definition: seg.h:48
int Width() const
Return true if the line is geometrically identical as line aOther.
Definition: pns_line.h:156
void SetMouseDisabled(bool aDisabled=true)
Disables the mouse-trail portion of the posture solver; leaving only the manual posture switch and th...
VECTOR2I B
Definition: seg.h:49

References SEG::A, PNS::FIXED_TAIL::AddStage(), PNS::MOUSE_TRAIL_TRACER::AddTrailPoint(), PNS::angle(), SEG::B, PNS::MOUSE_TRAIL_TRACER::Clear(), PNS::FIXED_TAIL::Clear(), DIRECTION_45::Format(), initPlacement(), PNS::ITEM::Kind(), m_chainedPlacement, m_currentEnd, m_currentLayer, m_currentNet, m_currentNode, m_currentStart, m_direction, m_fixedTail, m_head, m_initial_direction, m_mouseTrailTracer, m_placementCorrect, m_placingVia, m_shove, m_startItem, PNS::ITEM::Net(), PCB_PAD_T, SEG::Reversed(), PNS::ITEM::SEGMENT_T, PNS::MOUSE_TRAIL_TRACER::SetDefaultDirections(), setInitialDirection(), PNS::MOUSE_TRAIL_TRACER::SetMouseDisabled(), PNS::ALGO_BASE::Settings(), PNS::MOUSE_TRAIL_TRACER::SetTolerance(), PNS::ITEM::SOLID_T, DIRECTION_45::UNDEFINED, and PNS::LINE::Width().

◆ Tail()

const LINE& PNS::LINE_PLACER::Tail ( ) const
inline

Return the "tail" of the line being placed, the part which has already wrapped around and shoved some obstacles.

Definition at line 139 of file pns_line_placer.h.

139 { return m_tail; }
LINE m_tail
routing "tail": part of the track that has been already fixed due to collisions with obstacles

References m_tail.

◆ ToggleVia()

bool PNS::LINE_PLACER::ToggleVia ( bool  aEnabled)
overridevirtual

Enable/disable a via at the end of currently routed trace.

Reimplemented from PNS::PLACEMENT_ALGO.

Definition at line 82 of file pns_line_placer.cpp.

83 {
84  m_placingVia = aEnabled;
85 
86  if( !aEnabled )
87  m_head.RemoveVia();
88 
89  return true;
90 }
LINE m_head
the volatile part of the track from the previously analyzed point to the current routing destination
void RemoveVia()
Definition: pns_line.h:194

References m_head, m_placingVia, and PNS::LINE::RemoveVia().

◆ Trace()

const LINE PNS::LINE_PLACER::Trace ( ) const

Return the complete routed line.

Definition at line 1007 of file pns_line_placer.cpp.

1008 {
1009  LINE tmp( m_head );
1010 
1011  tmp.SetShape( m_tail.CLine() );
1012  tmp.Line().Append( m_head.CLine() );
1013  tmp.Line().Simplify();
1014  return tmp;
1015 }
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:137
LINE m_head
the volatile part of the track from the previously analyzed point to the current routing destination
LINE m_tail
routing "tail": part of the track that has been already fixed due to collisions with obstacles

References SHAPE_LINE_CHAIN::Append(), PNS::LINE::CLine(), PNS::LINE::Line(), m_head, m_tail, PNS::LINE::SetShape(), and SHAPE_LINE_CHAIN::Simplify().

Referenced by FixRoute(), Move(), optimizeTailHeadTransition(), Traces(), and updateLeadingRatLine().

◆ Traces()

const ITEM_SET PNS::LINE_PLACER::Traces ( )
overridevirtual

Return the complete routed line, as a single-member ITEM_SET.

Implements PNS::PLACEMENT_ALGO.

Definition at line 1018 of file pns_line_placer.cpp.

1019 {
1020  m_currentTrace = Trace();
1021  return ITEM_SET( &m_currentTrace );
1022 }
const LINE Trace() const
Return the complete routed line.

References m_currentTrace, and Trace().

◆ UnfixRoute()

bool PNS::LINE_PLACER::UnfixRoute ( )
overridevirtual

Reimplemented from PNS::PLACEMENT_ALGO.

Definition at line 1419 of file pns_line_placer.cpp.

1420 {
1421  FIXED_TAIL::STAGE st;
1422 
1423  if ( !m_fixedTail.PopStage( st ) )
1424  return false;
1425 
1426  m_head.Line().Clear();
1427  m_tail.Line().Clear();
1428  m_startItem = nullptr;
1429  m_p_start = st.pts[0].p;
1430  m_direction = st.pts[0].direction;
1431  m_placingVia = st.pts[0].placingVias;
1432  m_currentNode = st.commit;
1433  m_currentLayer = st.pts[0].layer;
1436  m_head.RemoveVia();
1437  m_tail.RemoveVia();
1438 
1442 
1443  if( m_shove )
1444  {
1445  m_shove->RewindSpringbackTo( m_currentNode );
1446  m_shove->UnlockSpringbackNode( m_currentNode );
1447  m_currentNode = m_shove->CurrentNode();
1449  }
1450 
1452 
1453  return true;
1454 }
NODE * m_lastNode
Postprocessed world state (including marked collisions & removed loops)
void SetLayer(int aLayer)
Definition: pns_item.h:155
LINE m_head
the volatile part of the track from the previously analyzed point to the current routing destination
void RemoveVia()
Definition: pns_line.h:194
bool PopStage(STAGE &aStage)
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:127
DIRECTION_45 m_initial_direction
routing direction for new traces
void KillChildren()
Definition: pns_node.cpp:1369
LINE m_tail
routing "tail": part of the track that has been already fixed due to collisions with obstacles
std::unique_ptr< SHOVE > m_shove
The shove engine.
DIRECTION_45 m_direction
current routing direction
void AddTrailPoint(const VECTOR2I &aP)
MOUSE_TRAIL_TRACER m_mouseTrailTracer
FIXED_TAIL m_fixedTail
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:136
NODE * m_currentNode
Current world state.
void SetDefaultDirections(DIRECTION_45 aInitDirection, DIRECTION_45 aLastSegDir)
void Clear()
Function Clear() Removes all points from the line chain.
VECTOR2I m_p_start
current routing start (end of tail, beginning of head)

References PNS::MOUSE_TRAIL_TRACER::AddTrailPoint(), PNS::NODE::Branch(), PNS::MOUSE_TRAIL_TRACER::Clear(), SHAPE_LINE_CHAIN::Clear(), PNS::FIXED_TAIL::STAGE::commit, PNS::NODE::KillChildren(), PNS::LINE::Line(), m_currentLayer, m_currentNode, m_direction, m_fixedTail, m_head, m_initial_direction, m_lastNode, m_mouseTrailTracer, m_p_start, m_placingVia, m_shove, m_startItem, m_tail, PNS::FIXED_TAIL::PopStage(), PNS::FIXED_TAIL::STAGE::pts, PNS::LINE::RemoveVia(), PNS::MOUSE_TRAIL_TRACER::SetDefaultDirections(), and PNS::ITEM::SetLayer().

◆ updateLeadingRatLine()

void PNS::LINE_PLACER::updateLeadingRatLine ( )
private

Draw the "leading" rats nest line, which connects the end of currently routed track and the nearest yet unrouted item.

If the routing for current net is complete, draws nothing.

Definition at line 1628 of file pns_line_placer.cpp.

1629 {
1630  LINE current = Trace();
1631  SHAPE_LINE_CHAIN ratLine;
1632  TOPOLOGY topo( m_lastNode );
1633 
1634  if( topo.LeadingRatLine( &current, ratLine ) )
1635  m_router->GetInterface()->DisplayRatline( ratLine, 5 );
1636 }
NODE * m_lastNode
Postprocessed world state (including marked collisions & removed loops)
const LINE Trace() const
Return the complete routed line.
virtual void DisplayRatline(const SHAPE_LINE_CHAIN &aRatline, int aColor=-1)=0
ROUTER * m_router
Definition: pns_algo_base.h:87
SHAPE_LINE_CHAIN.
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:210

References PNS::ROUTER_IFACE::DisplayRatline(), PNS::ROUTER::GetInterface(), PNS::TOPOLOGY::LeadingRatLine(), m_lastNode, PNS::ALGO_BASE::m_router, and Trace().

Referenced by Move().

◆ UpdateSizes()

void PNS::LINE_PLACER::UpdateSizes ( const SIZES_SETTINGS aSizes)
overridevirtual

Perform on-the-fly update of the width, via diameter & drill size from a settings class.

Performs on-the-fly update of the width, via diameter & drill size from a settings class. Used to dynamically change these parameters as the track is routed.

Reimplemented from PNS::PLACEMENT_ALGO.

Definition at line 1602 of file pns_line_placer.cpp.

1603 {
1604  m_sizes = aSizes;
1605 
1606  if( !m_idle )
1607  {
1608  // If the track width was originally determined from the rules resolver ("use netclass
1609  // width") or continuing from an existing track, we don't want to change the width unless
1610  // the user is moving to an explicitly-specified value.
1611  // NOTE: This doesn't quite correctly handle the case of moving *from* an explicit value
1612  // *to* the "use netclass width" value, but that is more complicated to handle.
1614  {
1617  }
1618 
1619  if( m_head.EndsWithVia() )
1620  {
1623  }
1624  }
1625 }
void SetViaDiameter(int aDiameter)
Definition: pns_line.h:198
LINE m_head
the volatile part of the track from the previously analyzed point to the current routing destination
SIZES_SETTINGS m_sizes
bool EndsWithVia() const
Definition: pns_line.h:191
void SetWidth(int aWidth)
Return line width.
Definition: pns_line.h:149
LINE m_tail
routing "tail": part of the track that has been already fixed due to collisions with obstacles
bool TrackWidthIsExplicit() const
void SetViaDrill(int aDrill)
Definition: pns_line.h:199

References PNS::LINE::EndsWithVia(), m_head, m_idle, m_sizes, m_tail, PNS::LINE::SetViaDiameter(), PNS::LINE::SetViaDrill(), PNS::LINE::SetWidth(), PNS::SIZES_SETTINGS::TrackWidth(), PNS::SIZES_SETTINGS::TrackWidthIsExplicit(), PNS::SIZES_SETTINGS::ViaDiameter(), and PNS::SIZES_SETTINGS::ViaDrill().

◆ VisibleViewArea()

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

Definition at line 39 of file pns_algo_base.cpp.

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

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

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

Member Data Documentation

◆ m_chainedPlacement

bool PNS::LINE_PLACER::m_chainedPlacement
private

Definition at line 360 of file pns_line_placer.h.

Referenced by FixRoute(), LINE_PLACER(), SetLayer(), and Start().

◆ m_currentEnd

VECTOR2I PNS::LINE_PLACER::m_currentEnd
private

Definition at line 352 of file pns_line_placer.h.

Referenced by CurrentEnd(), Move(), SetLayer(), and Start().

◆ m_currentLayer

int PNS::LINE_PLACER::m_currentLayer
private

◆ m_currentMode

PNS_MODE PNS::LINE_PLACER::m_currentMode
private

Definition at line 356 of file pns_line_placer.h.

Referenced by buildInitialLine(), FixRoute(), initPlacement(), LINE_PLACER(), and routeHead().

◆ m_currentNet

int PNS::LINE_PLACER::m_currentNet
private

◆ m_currentNode

◆ m_currentStart

VECTOR2I PNS::LINE_PLACER::m_currentStart
private

Definition at line 353 of file pns_line_placer.h.

Referenced by FixRoute(), initPlacement(), and Start().

◆ m_currentTrace

LINE PNS::LINE_PLACER::m_currentTrace
private

Definition at line 354 of file pns_line_placer.h.

Referenced by Traces().

◆ 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_direction

◆ m_fixedTail

FIXED_TAIL PNS::LINE_PLACER::m_fixedTail
private

Definition at line 364 of file pns_line_placer.h.

Referenced by FixRoute(), HasPlacedAnything(), Start(), and UnfixRoute().

◆ m_head

LINE PNS::LINE_PLACER::m_head
private

the volatile part of the track from the previously analyzed point to the current routing destination

Definition at line 328 of file pns_line_placer.h.

Referenced by FixRoute(), handlePullback(), handleSelfIntersections(), Head(), initPlacement(), mergeHead(), optimizeTailHeadTransition(), reduceTail(), rhMarkObstacles(), rhShoveOnly(), rhWalkOnly(), route(), routeStep(), SetLayer(), Start(), ToggleVia(), Trace(), UnfixRoute(), and UpdateSizes().

◆ m_idle

bool PNS::LINE_PLACER::m_idle
private

Definition at line 359 of file pns_line_placer.h.

Referenced by FixRoute(), initPlacement(), LINE_PLACER(), SetLayer(), and UpdateSizes().

◆ m_initial_direction

DIRECTION_45 PNS::LINE_PLACER::m_initial_direction
private

◆ m_last_head

LINE PNS::LINE_PLACER::m_last_head
private

Most recent successful (non-colliding) head.

Definition at line 331 of file pns_line_placer.h.

Referenced by routeStep().

◆ m_lastNode

NODE* PNS::LINE_PLACER::m_lastNode
private

Postprocessed world state (including marked collisions & removed loops)

Definition at line 342 of file pns_line_placer.h.

Referenced by CommitPlacement(), CurrentNode(), FixRoute(), initPlacement(), LINE_PLACER(), Move(), UnfixRoute(), and updateLeadingRatLine().

◆ m_logger

LOGGER* PNS::ALGO_BASE::m_logger
protectedinherited

Definition at line 88 of file pns_algo_base.h.

Referenced by PNS::ALGO_BASE::SetLogger().

◆ m_mouseTrailTracer

MOUSE_TRAIL_TRACER PNS::LINE_PLACER::m_mouseTrailTracer
private

◆ m_orthoMode

bool PNS::LINE_PLACER::m_orthoMode
private

Definition at line 361 of file pns_line_placer.h.

Referenced by buildInitialLine(), LINE_PLACER(), and SetOrthoMode().

◆ m_p_start

VECTOR2I PNS::LINE_PLACER::m_p_start
private

current routing start (end of tail, beginning of head)

Definition at line 337 of file pns_line_placer.h.

Referenced by buildInitialLine(), FixRoute(), handlePullback(), handleSelfIntersections(), initPlacement(), mergeHead(), Move(), optimizeTailHeadTransition(), reduceTail(), and UnfixRoute().

◆ m_placementCorrect

bool PNS::LINE_PLACER::m_placementCorrect
private

Definition at line 362 of file pns_line_placer.h.

Referenced by FixRoute(), HasPlacedAnything(), LINE_PLACER(), and Start().

◆ m_placingVia

bool PNS::LINE_PLACER::m_placingVia
private

◆ m_router

◆ m_shove

std::unique_ptr<SHOVE> PNS::LINE_PLACER::m_shove
private

The shove engine.

Definition at line 339 of file pns_line_placer.h.

Referenced by FixRoute(), initPlacement(), LINE_PLACER(), rhShoveOnly(), Start(), and UnfixRoute().

◆ m_sizes

SIZES_SETTINGS PNS::LINE_PLACER::m_sizes
private

Definition at line 345 of file pns_line_placer.h.

Referenced by initPlacement(), makeVia(), and UpdateSizes().

◆ m_startItem

ITEM* PNS::LINE_PLACER::m_startItem
private

Definition at line 357 of file pns_line_placer.h.

Referenced by FixRoute(), initPlacement(), LINE_PLACER(), SetLayer(), Start(), and UnfixRoute().

◆ m_tail

LINE PNS::LINE_PLACER::m_tail
private

routing "tail": part of the track that has been already fixed due to collisions with obstacles

Definition at line 333 of file pns_line_placer.h.

Referenced by buildInitialLine(), FixRoute(), handlePullback(), handleSelfIntersections(), initPlacement(), mergeHead(), optimizeTailHeadTransition(), reduceTail(), rhShoveOnly(), routeStep(), setInitialDirection(), SetLayer(), Tail(), Trace(), UnfixRoute(), and UpdateSizes().

◆ m_world

NODE* PNS::LINE_PLACER::m_world
private

pointer to world to search colliding items

Definition at line 336 of file pns_line_placer.h.

Referenced by AbortPlacement(), FixRoute(), initPlacement(), LINE_PLACER(), and setWorld().


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