KiCad PCB EDA Suite
PNS::TOPOLOGY Class Reference

#include <pns_topology.h>

Public Types

typedef std::set< JOINT * > JOINT_SET
 

Public Member Functions

 TOPOLOGY (NODE *aNode)
 
 ~TOPOLOGY ()
 
bool SimplifyLine (LINE *aLine)
 
ITEMNearestUnconnectedItem (JOINT *aStart, int *aAnchor=nullptr, int aKindMask=ITEM::ANY_T)
 
bool LeadingRatLine (const LINE *aTrack, SHAPE_LINE_CHAIN &aRatLine)
 
const JOINT_SET ConnectedJoints (JOINT *aStart)
 
const ITEM_SET ConnectedItems (JOINT *aStart, int aKindMask=ITEM::ANY_T)
 
const ITEM_SET ConnectedItems (ITEM *aStart, int aKindMask=ITEM::ANY_T)
 
int64_t ShortestConnectionLength (ITEM *aFrom, ITEM *aTo)
 
const ITEM_SET AssembleTrivialPath (ITEM *aStart, std::pair< JOINT *, JOINT * > *aTerminalJoints=nullptr)
 Assemble a trivial path between two joints given a starting item. More...
 
const ITEM_SET AssembleTuningPath (ITEM *aStart, SOLID **aStartPad=nullptr, SOLID **aEndPad=nullptr)
 Like AssembleTrivialPath, but follows the track length algorithm, which discards segments that are fully inside pads, and truncates segments that cross into a pad (adding a straight- line segment from the intersection to the pad anchor). More...
 
const DIFF_PAIR AssembleDiffPair (SEGMENT *aStart)
 
bool AssembleDiffPair (ITEM *aStart, DIFF_PAIR &aPair)
 
const std::set< ITEM * > AssembleCluster (ITEM *aStart, int aLayer)
 

Private Member Functions

bool followTrivialPath (LINE *aLine, bool aLeft, ITEM_SET &aSet, std::set< ITEM * > &aVisited, JOINT **aTerminalJoint=nullptr)
 

Private Attributes

NODEm_world
 

Detailed Description

Definition at line 39 of file pns_topology.h.

Member Typedef Documentation

◆ JOINT_SET

typedef std::set<JOINT*> PNS::TOPOLOGY::JOINT_SET

Definition at line 42 of file pns_topology.h.

Constructor & Destructor Documentation

◆ TOPOLOGY()

PNS::TOPOLOGY::TOPOLOGY ( NODE aNode)
inline

Definition at line 44 of file pns_topology.h.

44  :
45  m_world( aNode ) {};
NODE * m_world
Definition: pns_topology.h:94

◆ ~TOPOLOGY()

PNS::TOPOLOGY::~TOPOLOGY ( )
inline

Definition at line 47 of file pns_topology.h.

47 {};

Member Function Documentation

◆ AssembleCluster()

const std::set< ITEM * > PNS::TOPOLOGY::AssembleCluster ( ITEM aStart,
int  aLayer 
)

Definition at line 515 of file pns_topology.cpp.

516 {
517  std::set<ITEM*> visited;
518  std::deque<ITEM*> pending;
519 
520  pending.push_back( aStart );
521 
522  while( !pending.empty() )
523  {
524  NODE::OBSTACLES obstacles;
525  ITEM* top = pending.front();
526 
527  pending.pop_front();
528 
529  visited.insert( top );
530 
531  m_world->QueryColliding( top, obstacles, ITEM::ANY_T, -1, false );
532 
533  for( OBSTACLE& obs : obstacles )
534  {
535  if( visited.find( obs.m_item ) == visited.end() &&
536  obs.m_item->Layers().Overlaps( aLayer ) && !( obs.m_item->Marker() & MK_HEAD ) )
537  {
538  visited.insert( obs.m_item );
539  pending.push_back( obs.m_item );
540  }
541  }
542  }
543 
544  return visited;
545 }
NODE * m_world
Definition: pns_topology.h:94
int QueryColliding(const ITEM *aItem, OBSTACLES &aObstacles, int aKindMask=ITEM::ANY_T, int aLimitCount=-1, bool aDifferentNetsOnly=true)
Find items colliding (closer than clearance) with the item aItem.
Definition: pns_node.cpp:266
std::vector< OBSTACLE > OBSTACLES
Definition: pns_node.h:149

References PNS::ITEM::ANY_T, m_world, PNS::MK_HEAD, and PNS::NODE::QueryColliding().

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

◆ AssembleDiffPair() [1/2]

const DIFF_PAIR PNS::TOPOLOGY::AssembleDiffPair ( SEGMENT aStart)

◆ AssembleDiffPair() [2/2]

bool PNS::TOPOLOGY::AssembleDiffPair ( ITEM aStart,
DIFF_PAIR aPair 
)

Definition at line 441 of file pns_topology.cpp.

442 {
443  int refNet = aStart->Net();
444  int coupledNet = m_world->GetRuleResolver()->DpCoupledNet( refNet );
445 
446  if( coupledNet < 0 )
447  return false;
448 
449  std::set<ITEM*> coupledItems;
450 
451  m_world->AllItemsInNet( coupledNet, coupledItems );
452 
453  SEGMENT* coupledSeg = nullptr, *refSeg;
454  int minDist = std::numeric_limits<int>::max();
455 
456  if( ( refSeg = dyn_cast<SEGMENT*>( aStart ) ) != nullptr )
457  {
458  for( ITEM* item : coupledItems )
459  {
460  if( SEGMENT* s = dyn_cast<SEGMENT*>( item ) )
461  {
462  if( s->Layers().Start() == refSeg->Layers().Start() &&
463  s->Width() == refSeg->Width() )
464  {
465  int dist = s->Seg().Distance( refSeg->Seg() );
466  bool isParallel = refSeg->Seg().ApproxParallel( s->Seg() );
467  SEG p_clip, n_clip;
468 
469  bool isCoupled = commonParallelProjection( refSeg->Seg(), s->Seg(), p_clip,
470  n_clip );
471 
472  if( isParallel && isCoupled && dist < minDist )
473  {
474  minDist = dist;
475  coupledSeg = s;
476  }
477  }
478  }
479  }
480  }
481  else
482  {
483  return false;
484  }
485 
486  if( !coupledSeg )
487  return false;
488 
489  LINE lp = m_world->AssembleLine( refSeg );
490  LINE ln = m_world->AssembleLine( coupledSeg );
491 
492  if( m_world->GetRuleResolver()->DpNetPolarity( refNet ) < 0 )
493  {
494  std::swap( lp, ln );
495  }
496 
497  int gap = -1;
498 
499  if( refSeg->Seg().ApproxParallel( coupledSeg->Seg() ) )
500  {
501  // Segments are parallel -> compute pair gap
502  const VECTOR2I refDir = refSeg->Anchor( 1 ) - refSeg->Anchor( 0 );
503  const VECTOR2I displacement = refSeg->Anchor( 1 ) - coupledSeg->Anchor( 1 );
504  gap = (int) std::abs( refDir.Cross( displacement ) / refDir.EuclideanNorm() ) - lp.Width();
505  }
506 
507  aPair = DIFF_PAIR( lp, ln );
508  aPair.SetWidth( lp.Width() );
509  aPair.SetLayers( lp.Layers() );
510  aPair.SetGap( gap );
511 
512  return true;
513 }
extended_type Cross(const VECTOR2< T > &aVector) const
Compute cross product of self with aVector.
Definition: vector2d.h:513
virtual int DpCoupledNet(int aNet)=0
NODE * m_world
Definition: pns_topology.h:94
RULE_RESOLVER * GetRuleResolver() const
Return the number of joints.
Definition: pns_node.h:177
Definition: seg.h:40
bool commonParallelProjection(SEG p, SEG n, SEG &pClip, SEG &nClip)
void AllItemsInNet(int aNet, std::set< ITEM * > &aItems, int aKindMask=-1)
Definition: pns_node.cpp:1411
virtual int DpNetPolarity(int aNet)=0
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition: vector2d.h:293
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:946

References PNS::NODE::AllItemsInNet(), PNS::SEGMENT::Anchor(), PNS::NODE::AssembleLine(), PNS::commonParallelProjection(), VECTOR2< T >::Cross(), PNS::RULE_RESOLVER::DpCoupledNet(), PNS::RULE_RESOLVER::DpNetPolarity(), VECTOR2< T >::EuclideanNorm(), PNS::NODE::GetRuleResolver(), PNS::ITEM::Layers(), m_world, PNS::ITEM::Net(), PNS::SEGMENT::Seg(), PNS::DIFF_PAIR::SetGap(), PNS::ITEM::SetLayers(), PNS::DIFF_PAIR::SetWidth(), and PNS::LINE::Width().

◆ AssembleTrivialPath()

const ITEM_SET PNS::TOPOLOGY::AssembleTrivialPath ( ITEM aStart,
std::pair< JOINT *, JOINT * > *  aTerminalJoints = nullptr 
)

Assemble a trivial path between two joints given a starting item.

Parameters
aStartis the item to assemble from.
aTerminalJointswill be filled with the start and end points of the assembled path.
Returns
a set of items in the path.

Definition at line 249 of file pns_topology.cpp.

251 {
252  ITEM_SET path;
253  std::set<ITEM*> visited;
254  LINKED_ITEM* seg = nullptr;
255 
256  if( aStart->Kind() == ITEM::VIA_T )
257  {
258  VIA* via = static_cast<VIA*>( aStart );
259  JOINT* jt = m_world->FindJoint( via->Pos(), via );
260 
261  if( !jt->IsNonFanoutVia() )
262  return ITEM_SET();
263 
264  for( const ITEM_SET::ENTRY& entry : jt->Links().Items() )
265  {
266  if( entry.item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
267  {
268  seg = static_cast<LINKED_ITEM*>( entry.item );
269  break;
270  }
271  }
272  }
273  else if( aStart->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
274  {
275  seg = static_cast<LINKED_ITEM*>( aStart );
276  }
277 
278  if( !seg )
279  return ITEM_SET();
280 
281  LINE l = m_world->AssembleLine( seg );
282 
283  path.Add( l );
284 
285  JOINT* jointA = nullptr;
286  JOINT* jointB = nullptr;
287 
288  followTrivialPath( &l, false, path, visited, &jointA );
289  followTrivialPath( &l, true, path, visited, &jointB );
290 
291  if( aTerminalJoints )
292  {
293  wxASSERT( jointA && jointB );
294  *aTerminalJoints = std::make_pair( jointA, jointB );
295  }
296 
297  return path;
298 }
bool followTrivialPath(LINE *aLine, bool aLeft, ITEM_SET &aSet, std::set< ITEM * > &aVisited, JOINT **aTerminalJoint=nullptr)
Normal via.
Definition: router_tool.cpp:70
NODE * m_world
Definition: pns_topology.h:94
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
Definition: pns_node.cpp:1140
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:946

References PNS::ITEM::ARC_T, PNS::NODE::AssembleLine(), PNS::NODE::FindJoint(), followTrivialPath(), PNS::JOINT::IsNonFanoutVia(), PNS::ITEM_SET::Items(), PNS::ITEM::Kind(), PNS::JOINT::Links(), m_world, PNS::ITEM::OfKind(), path, PNS::ITEM::SEGMENT_T, via, and PNS::ITEM::VIA_T.

Referenced by AssembleTuningPath(), and PNS::MEANDER_SKEW_PLACER::Start().

◆ AssembleTuningPath()

const ITEM_SET PNS::TOPOLOGY::AssembleTuningPath ( ITEM aStart,
SOLID **  aStartPad = nullptr,
SOLID **  aEndPad = nullptr 
)

Like AssembleTrivialPath, but follows the track length algorithm, which discards segments that are fully inside pads, and truncates segments that cross into a pad (adding a straight- line segment from the intersection to the pad anchor).

Note
When changing this, sync with BOARD::GetTrackLength()
Parameters
aStartis the item to assemble a path from.
aStartPadwill be filled with the starting pad of the path, if found.
aEndPadwill be filled with the ending pad of the path, if found.
Returns
an item set containing all the items in the path.

Definition at line 301 of file pns_topology.cpp.

302 {
303  std::pair<JOINT*, JOINT*> joints;
304  ITEM_SET initialPath = AssembleTrivialPath( aStart, &joints );
305 
306  PAD* padA = nullptr;
307  PAD* padB = nullptr;
308 
309  auto getPadFromJoint =
310  []( JOINT* aJoint, PAD** aTargetPad, SOLID** aTargetSolid )
311  {
312  for( ITEM* item : aJoint->LinkList() )
313  {
314  if( item->OfKind( ITEM::SOLID_T ) )
315  {
316  BOARD_ITEM* bi = static_cast<SOLID*>( item )->Parent();
317 
318  if( bi->Type() == PCB_PAD_T )
319  {
320  *aTargetPad = static_cast<PAD*>( bi );
321 
322  if( aTargetSolid )
323  *aTargetSolid = static_cast<SOLID*>( item );
324  }
325 
326  break;
327  }
328  }
329  };
330 
331  if( joints.first )
332  getPadFromJoint( joints.first, &padA, aStartPad );
333 
334  if( joints.second )
335  getPadFromJoint( joints.second, &padB, aEndPad );
336 
337  if( !padA && !padB )
338  return initialPath;
339 
340  auto clipLineToPad =
341  []( SHAPE_LINE_CHAIN& aLine, PAD* aPad, bool aForward = true )
342  {
343  const std::shared_ptr<SHAPE_POLY_SET>& shape = aPad->GetEffectivePolygon();
344 
345  int start = aForward ? 0 : aLine.PointCount() - 1;
346  int delta = aForward ? 1 : -1;
347 
348  // Skip the "first" (or last) vertex, we already know it's contained in the pad
349  int clip = start;
350 
351  for( int vertex = start + delta;
352  aForward ? vertex < aLine.PointCount() : vertex >= 0;
353  vertex += delta )
354  {
355  SEG seg( aLine.GetPoint( vertex ), aLine.GetPoint( vertex - delta ) );
356 
357  bool containsA = shape->Contains( seg.A );
358  bool containsB = shape->Contains( seg.B );
359 
360  if( containsA && containsB )
361  {
362  // Whole segment is inside: clip out this segment
363  clip = vertex;
364  }
365  else if( containsB &&
366  ( aForward ? vertex < aLine.PointCount() - 1 : vertex > 0 ) )
367  {
368  // Only one point inside: Find the intersection
369  VECTOR2I loc;
370 
371  if( shape->Collide( seg, 0, nullptr, &loc ) )
372  {
373  aLine.Replace( vertex - delta, vertex - delta, loc );
374  }
375  }
376  }
377 
378  if( !aForward && clip < start )
379  aLine.Remove( clip + 1, start );
380  else if( clip > start )
381  aLine.Remove( start, clip - 1 );
382 
383  // Now connect the dots
384  aLine.Insert( aForward ? 0 : aLine.PointCount(), aPad->GetPosition() );
385  };
386 
387  auto processPad =
388  [&]( JOINT* aJoint, PAD* aPad )
389  {
390  const std::shared_ptr<SHAPE_POLY_SET>& shape = aPad->GetEffectivePolygon();
391 
392  for( int idx = 0; idx < initialPath.Size(); idx++ )
393  {
394  if( initialPath[idx]->Kind() != ITEM::LINE_T )
395  continue;
396 
397  LINE* line = static_cast<LINE*>( initialPath[idx] );
398 
399  if( !aPad->FlashLayer( line->Layer() ) )
400  continue;
401 
402  const std::vector<VECTOR2I>& points = line->CLine().CPoints();
403 
404  if( points.front() != aJoint->Pos() && points.back() != aJoint->Pos() )
405  continue;
406 
407  SHAPE_LINE_CHAIN& slc = line->Line();
408 
409  if( shape->Contains( slc.CPoint( 0 ) ) )
410  clipLineToPad( slc, aPad, true );
411  else if( shape->Contains( slc.CPoint( -1 ) ) )
412  clipLineToPad( slc, aPad, false );
413  }
414  };
415 
416  if( padA )
417  processPad( joints.first, padA );
418 
419  if( padB )
420  processPad( joints.second, padB );
421 
422  return initialPath;
423 }
const ITEM_SET AssembleTrivialPath(ITEM *aStart, std::pair< JOINT *, JOINT * > *aTerminalJoints=nullptr)
Assemble a trivial path between two joints given a starting item.
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition: board_item.h:49
class PAD, a pad in a footprint
Definition: typeinfo.h:89
int PointCount() const
Return the number of points (vertices) in this line chain.
void Insert(size_t aVertex, const VECTOR2I &aP)
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
void Remove(int aStartIndex, int aEndIndex)
Remove the range of points [start_index, end_index] from the line chain.
virtual const VECTOR2I GetPoint(int aIndex) const override
Definition: seg.h:40
Represent a polyline (an zero-thickness chain of connected line segments).
constexpr int delta
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Replace points with indices in range [start_index, end_index] with a single point aP.
Definition: pad.h:57
KICAD_T Type() const
Returns the type of object.
Definition: eda_item.h:113
bool Contains(const SEG &aSeg) const
Definition: seg.h:331

References AssembleTrivialPath(), PNS::LINE::CLine(), SEG::Contains(), SHAPE_LINE_CHAIN::CPoint(), SHAPE_LINE_CHAIN::CPoints(), delta, SHAPE_LINE_CHAIN::GetPoint(), SHAPE_LINE_CHAIN::Insert(), PNS::ITEM::Layer(), PNS::LINE::Line(), PNS::ITEM::LINE_T, PNS::JOINT::LinkList(), PCB_PAD_T, SHAPE_LINE_CHAIN::PointCount(), PNS::JOINT::Pos(), SHAPE_LINE_CHAIN::Remove(), SHAPE_LINE_CHAIN::Replace(), PNS::ITEM_SET::Size(), PNS::ITEM::SOLID_T, and EDA_ITEM::Type().

Referenced by PNS::MEANDER_SKEW_PLACER::Start(), PNS::MEANDER_PLACER::Start(), and PNS::DP_MEANDER_PLACER::Start().

◆ ConnectedItems() [1/2]

const ITEM_SET PNS::TOPOLOGY::ConnectedItems ( JOINT aStart,
int  aKindMask = ITEM::ANY_T 
)

Definition at line 426 of file pns_topology.cpp.

427 {
428  return ITEM_SET();
429 }

◆ ConnectedItems() [2/2]

const ITEM_SET PNS::TOPOLOGY::ConnectedItems ( ITEM aStart,
int  aKindMask = ITEM::ANY_T 
)

Definition at line 432 of file pns_topology.cpp.

433 {
434  return ITEM_SET();
435 }

◆ ConnectedJoints()

const TOPOLOGY::JOINT_SET PNS::TOPOLOGY::ConnectedJoints ( JOINT aStart)

Definition at line 62 of file pns_topology.cpp.

63 {
64  std::deque<JOINT*> searchQueue;
65  JOINT_SET processed;
66 
67  searchQueue.push_back( aStart );
68  processed.insert( aStart );
69 
70  while( !searchQueue.empty() )
71  {
72  JOINT* current = searchQueue.front();
73  searchQueue.pop_front();
74 
75  for( ITEM* item : current->LinkList() )
76  {
77  if( item->OfKind( ITEM::SEGMENT_T ) )
78  {
79  SEGMENT* seg = static_cast<SEGMENT*>( item );
80  JOINT* a = m_world->FindJoint( seg->Seg().A, seg );
81  JOINT* b = m_world->FindJoint( seg->Seg().B, seg );
82  JOINT* next = ( *a == *current ) ? b : a;
83 
84  if( processed.find( next ) == processed.end() )
85  {
86  processed.insert( next );
87  searchQueue.push_back( next );
88  }
89  }
90  }
91  }
92 
93  return processed;
94 }
CITER next(CITER it)
Definition: ptree.cpp:126
NODE * m_world
Definition: pns_topology.h:94
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
Definition: pns_node.cpp:1140
std::set< JOINT * > JOINT_SET
Definition: pns_topology.h:42

References SEG::A, SEG::B, PNS::NODE::FindJoint(), PNS::JOINT::LinkList(), m_world, next(), PNS::SEGMENT::Seg(), and PNS::ITEM::SEGMENT_T.

Referenced by NearestUnconnectedItem().

◆ followTrivialPath()

bool PNS::TOPOLOGY::followTrivialPath ( LINE aLine,
bool  aLeft,
ITEM_SET aSet,
std::set< ITEM * > &  aVisited,
JOINT **  aTerminalJoint = nullptr 
)
private

Definition at line 181 of file pns_topology.cpp.

183 {
184  assert( aLine->IsLinked() );
185 
186  VECTOR2I anchor = aLeft ? aLine->CPoint( 0 ) : aLine->CPoint( -1 );
187  LINKED_ITEM* last = aLeft ? aLine->Links().front() : aLine->Links().back();
188  JOINT* jt = m_world->FindJoint( anchor, aLine );
189 
190  assert( jt != nullptr );
191 
192  aVisited.insert( last );
193 
194  if( jt->IsNonFanoutVia() || jt->IsTraceWidthChange() )
195  {
196  ITEM* via = nullptr;
197  SEGMENT* next_seg = nullptr;
198 
199  for( ITEM* link : jt->Links().Items() )
200  {
201  if( link->OfKind( ITEM::VIA_T ) )
202  via = link;
203  else if( aVisited.find( link ) == aVisited.end() )
204  next_seg = static_cast<SEGMENT*>( link );
205  }
206 
207  if( !next_seg )
208  {
209  if( aTerminalJoint )
210  *aTerminalJoint = jt;
211 
212  return false;
213  }
214 
215  LINE l = m_world->AssembleLine( next_seg );
216 
217  VECTOR2I nextAnchor = ( aLeft ? l.CLine().CPoint( -1 ) : l.CLine().CPoint( 0 ) );
218 
219  if( nextAnchor != anchor )
220  {
221  l.Reverse();
222  }
223 
224  if( aLeft )
225  {
226  if( via )
227  aSet.Prepend( via );
228 
229  aSet.Prepend( l );
230  }
231  else
232  {
233  if( via )
234  aSet.Add( via );
235 
236  aSet.Add( l );
237  }
238 
239  return followTrivialPath( &l, aLeft, aSet, aVisited, aTerminalJoint );
240  }
241 
242  if( aTerminalJoint )
243  *aTerminalJoint = jt;
244 
245  return false;
246 }
bool followTrivialPath(LINE *aLine, bool aLeft, ITEM_SET &aSet, std::set< ITEM * > &aVisited, JOINT **aTerminalJoint=nullptr)
NODE * m_world
Definition: pns_topology.h:94
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
Definition: pns_node.cpp:1140
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:946

References PNS::ITEM_SET::Add(), anchor, PNS::NODE::AssembleLine(), PNS::LINE::CLine(), PNS::LINE::CPoint(), SHAPE_LINE_CHAIN::CPoint(), PNS::NODE::FindJoint(), PNS::LINK_HOLDER::IsLinked(), PNS::JOINT::IsNonFanoutVia(), PNS::JOINT::IsTraceWidthChange(), PNS::ITEM_SET::Items(), PNS::LINK_HOLDER::Links(), PNS::JOINT::Links(), m_world, PNS::ITEM_SET::Prepend(), PNS::LINE::Reverse(), via, and PNS::ITEM::VIA_T.

Referenced by AssembleTrivialPath().

◆ LeadingRatLine()

bool PNS::TOPOLOGY::LeadingRatLine ( const LINE aTrack,
SHAPE_LINE_CHAIN aRatLine 
)

Definition at line 97 of file pns_topology.cpp.

98 {
99  LINE track( *aTrack );
100  VECTOR2I end;
101 
102  if( !track.PointCount() )
103  return false;
104 
105  std::unique_ptr<NODE> tmpNode( m_world->Branch() );
106  tmpNode->Add( track );
107 
108  JOINT* jt = tmpNode->FindJoint( track.CPoint( -1 ), &track );
109 
110  if( !jt || jt->Net() <= 0 )
111  return false;
112 
113  if( ( !track.EndsWithVia() && jt->LinkCount() >= 2 )
114  || ( track.EndsWithVia() && jt->LinkCount() >= 3 ) ) // we got something connected
115  {
116  end = jt->Pos();
117  }
118  else
119  {
120  int anchor;
121 
122  TOPOLOGY topo( tmpNode.get() );
123  ITEM* it = topo.NearestUnconnectedItem( jt, &anchor );
124 
125  if( !it )
126  return false;
127 
128  end = it->Anchor( anchor );
129  }
130 
131  aRatLine.Clear();
132  aRatLine.Append( track.CPoint( -1 ) );
133  aRatLine.Append( end );
134  return true;
135 }
TOPOLOGY(NODE *aNode)
Definition: pns_topology.h:44
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:137
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
NODE * m_world
Definition: pns_topology.h:94
void Clear()
Remove all points from the line chain.

References anchor, SHAPE_LINE_CHAIN::Append(), PNS::NODE::Branch(), SHAPE_LINE_CHAIN::Clear(), PNS::LINE::CPoint(), PNS::LINE::EndsWithVia(), PNS::JOINT::LinkCount(), m_world, PNS::JOINT::Net(), PNS::LINE::PointCount(), and PNS::JOINT::Pos().

Referenced by PNS::DIFF_PAIR_PLACER::updateLeadingRatLine(), and PNS::LINE_PLACER::updateLeadingRatLine().

◆ NearestUnconnectedItem()

ITEM * PNS::TOPOLOGY::NearestUnconnectedItem ( JOINT aStart,
int *  aAnchor = nullptr,
int  aKindMask = ITEM::ANY_T 
)

Definition at line 138 of file pns_topology.cpp.

139 {
140  std::set<ITEM*> disconnected;
141 
142  m_world->AllItemsInNet( aStart->Net(), disconnected );
143 
144  for( const JOINT* jt : ConnectedJoints( aStart ) )
145  {
146  for( ITEM* link : jt->LinkList() )
147  {
148  if( disconnected.find( link ) != disconnected.end() )
149  disconnected.erase( link );
150  }
151  }
152 
153  int best_dist = INT_MAX;
154  ITEM* best = nullptr;
155 
156  for( ITEM* item : disconnected )
157  {
158  if( item->OfKind( aKindMask ) )
159  {
160  for( int i = 0; i < item->AnchorCount(); i++ )
161  {
162  VECTOR2I p = item->Anchor( i );
163  int d = ( p - aStart->Pos() ).EuclideanNorm();
164 
165  if( d < best_dist )
166  {
167  best_dist = d;
168  best = item;
169 
170  if( aAnchor )
171  *aAnchor = i;
172  }
173  }
174  }
175  }
176 
177  return best;
178 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:146
const JOINT_SET ConnectedJoints(JOINT *aStart)
NODE * m_world
Definition: pns_topology.h:94
void AllItemsInNet(int aNet, std::set< ITEM * > &aItems, int aKindMask=-1)
Definition: pns_node.cpp:1411

References PNS::NODE::AllItemsInNet(), ConnectedJoints(), EuclideanNorm(), m_world, PNS::JOINT::Net(), and PNS::JOINT::Pos().

◆ ShortestConnectionLength()

int64_t PNS::TOPOLOGY::ShortestConnectionLength ( ITEM aFrom,
ITEM aTo 
)

◆ SimplifyLine()

bool PNS::TOPOLOGY::SimplifyLine ( LINE aLine)

Definition at line 38 of file pns_topology.cpp.

39 {
40  if( !aLine->IsLinked() || !aLine->SegmentCount() )
41  return false;
42 
43  LINKED_ITEM* root = aLine->GetLink( 0 );
44  LINE l = m_world->AssembleLine( root );
45  SHAPE_LINE_CHAIN simplified( l.CLine() );
46 
47  simplified.Simplify();
48 
49  if( simplified.PointCount() != l.PointCount() )
50  {
51  m_world->Remove( l );
52  LINE lnew( l );
53  lnew.SetShape( simplified );
54  m_world->Add( lnew );
55  return true;
56  }
57 
58  return false;
59 }
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:836
NODE * m_world
Definition: pns_topology.h:94
Represent a polyline (an zero-thickness chain of connected line segments).
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:638
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:946

References PNS::NODE::Add(), PNS::NODE::AssembleLine(), PNS::LINE::CLine(), PNS::LINK_HOLDER::GetLink(), PNS::LINK_HOLDER::IsLinked(), m_world, PNS::LINE::PointCount(), PNS::NODE::Remove(), PNS::LINE::SegmentCount(), PNS::LINE::SetShape(), and SHAPE_LINE_CHAIN::Simplify().

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

Member Data Documentation

◆ m_world


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