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=NULL, 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)
 
const DIFF_PAIR AssembleDiffPair (SEGMENT *aStart)
 
int DpCoupledNet (int aNet)
 
int DpNetPolarity (int aNet)
 
const LINE DpCoupledLine (LINE *aLine)
 
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)
 

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:71

◆ ~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 361 of file pns_topology.cpp.

362 {
363  std::set<ITEM*> visited;
364  std::deque<ITEM*> pending;
365 
366  pending.push_back( aStart );
367 
368  while( !pending.empty() )
369  {
370  NODE::OBSTACLES obstacles;
371  ITEM* top = pending.front();
372 
373  pending.pop_front();
374 
375  visited.insert( top );
376 
377  m_world->QueryColliding( top, obstacles, ITEM::ANY_T, -1, false );
378 
379  for( OBSTACLE& obs : obstacles )
380  {
381  if( visited.find( obs.m_item ) == visited.end() && obs.m_item->Layers().Overlaps( aLayer ) && !( obs.m_item->Marker() & MK_HEAD ) )
382  {
383  visited.insert( obs.m_item );
384  pending.push_back( obs.m_item );
385  }
386  }
387  }
388 
389  return visited;
390 }
NODE * m_world
Definition: pns_topology.h:71
std::vector< OBSTACLE > OBSTACLES
Definition: pns_node.h:150
int QueryColliding(const ITEM *aItem, OBSTACLES &aObstacles, int aKindMask=ITEM::ANY_T, int aLimitCount=-1, bool aDifferentNetsOnly=true, int aForceClearance=-1)
Function QueryColliding()
Definition: pns_node.cpp:278

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 289 of file pns_topology.cpp.

290 {
291  int refNet = aStart->Net();
292  int coupledNet = m_world->GetRuleResolver()->DpCoupledNet( refNet );
293 
294  if( coupledNet < 0 )
295  return false;
296 
297  std::set<ITEM*> coupledItems;
298 
299  m_world->AllItemsInNet( coupledNet, coupledItems );
300 
301  SEGMENT* coupledSeg = NULL, *refSeg;
302  int minDist = std::numeric_limits<int>::max();
303 
304  if( ( refSeg = dyn_cast<SEGMENT*>( aStart ) ) != NULL )
305  {
306  for( ITEM* item : coupledItems )
307  {
308  if( SEGMENT* s = dyn_cast<SEGMENT*>( item ) )
309  {
310  if( s->Layers().Start() == refSeg->Layers().Start() && s->Width() == refSeg->Width() )
311  {
312  int dist = s->Seg().Distance( refSeg->Seg() );
313  bool isParallel = refSeg->Seg().ApproxParallel( s->Seg() );
314  SEG p_clip, n_clip;
315 
316  bool isCoupled = commonParallelProjection( refSeg->Seg(), s->Seg(), p_clip, n_clip );
317 
318  if( isParallel && isCoupled && dist < minDist )
319  {
320  minDist = dist;
321  coupledSeg = s;
322  }
323  }
324  }
325  }
326  }
327  else
328  {
329  return false;
330  }
331 
332  if( !coupledSeg )
333  return false;
334 
335  LINE lp = m_world->AssembleLine( refSeg );
336  LINE ln = m_world->AssembleLine( coupledSeg );
337 
338  if( m_world->GetRuleResolver()->DpNetPolarity( refNet ) < 0 )
339  {
340  std::swap( lp, ln );
341  }
342 
343  int gap = -1;
344 
345  if( refSeg->Seg().ApproxParallel( coupledSeg->Seg() ) )
346  {
347  // Segments are parallel -> compute pair gap
348  const VECTOR2I refDir = refSeg->Anchor( 1 ) - refSeg->Anchor( 0 );
349  const VECTOR2I displacement = refSeg->Anchor( 1 ) - coupledSeg->Anchor( 1 );
350  gap = (int) std::abs( refDir.Cross( displacement ) / refDir.EuclideanNorm() ) - lp.Width();
351  }
352 
353  aPair = DIFF_PAIR( lp, ln );
354  aPair.SetWidth( lp.Width() );
355  aPair.SetLayers( lp.Layers() );
356  aPair.SetGap( gap );
357 
358  return true;
359 }
extended_type Cross(const VECTOR2< T > &aVector) const
Function Cross() computes cross product of self with aVector.
Definition: vector2d.h:484
static const int dist[10][10]
Definition: ar_matrix.cpp:326
virtual int DpCoupledNet(int aNet)=0
void AllItemsInNet(int aNet, std::set< ITEM * > &aItems)
Definition: pns_node.cpp:1294
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Function AssembleLine()
Definition: pns_node.cpp:893
#define NULL
NODE * m_world
Definition: pns_topology.h:71
RULE_RESOLVER * GetRuleResolver() const
Definition: pns_node.h:176
Definition: seg.h:39
bool commonParallelProjection(SEG p, SEG n, SEG &pClip, SEG &nClip)
virtual int DpNetPolarity(int aNet)=0
T EuclideanNorm() const
Destructor.
Definition: vector2d.h:299

References PNS::NODE::AllItemsInNet(), PNS::SEGMENT::Anchor(), PNS::NODE::AssembleLine(), PNS::commonParallelProjection(), VECTOR2< T >::Cross(), dist, PNS::RULE_RESOLVER::DpCoupledNet(), PNS::RULE_RESOLVER::DpNetPolarity(), VECTOR2< T >::EuclideanNorm(), PNS::NODE::GetRuleResolver(), PNS::ITEM::Layers(), m_world, PNS::ITEM::Net(), NULL, 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)

Definition at line 239 of file pns_topology.cpp.

240 {
241  ITEM_SET path;
242  std::set<ITEM*> visited;
243  SEGMENT* seg;
244  VIA* via;
245 
246  seg = dyn_cast<SEGMENT*> (aStart);
247 
248  if(!seg && (via = dyn_cast<VIA*>( aStart ) ) )
249  {
250  JOINT *jt = m_world->FindJoint( via->Pos(), via );
251 
252  if( !jt->IsNonFanoutVia() )
253  return ITEM_SET();
254 
255  for( const auto& entry : jt->Links().Items() )
256  if( ( seg = dyn_cast<SEGMENT*>( entry.item ) ) )
257  break;
258  }
259 
260  if( !seg )
261  return ITEM_SET();
262 
263  LINE l = m_world->AssembleLine( seg );
264 
265  path.Add( l );
266 
267  followTrivialPath( &l, false, path, visited );
268  followTrivialPath( &l, true, path, visited );
269 
270  return path;
271 }
bool followTrivialPath(LINE *aLine, bool aLeft, ITEM_SET &aSet, std::set< ITEM * > &aVisited)
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Function AssembleLine()
Definition: pns_node.cpp:893
NODE * m_world
Definition: pns_topology.h:71
std::unordered_set< SCH_ITEM * > ITEM_SET
Definition: sch_item.h:138
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:1027

References PNS::ITEM_SET::Add(), PNS::NODE::AssembleLine(), PNS::NODE::FindJoint(), followTrivialPath(), PNS::JOINT::IsNonFanoutVia(), PNS::ITEM_SET::Items(), PNS::JOINT::Links(), m_world, and PNS::VIA::Pos().

Referenced by PNS::TOOL_BASE::deleteTraces(), 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 274 of file pns_topology.cpp.

275 {
276  return ITEM_SET();
277 }
std::unordered_set< SCH_ITEM * > ITEM_SET
Definition: sch_item.h:138

◆ ConnectedItems() [2/2]

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

Definition at line 280 of file pns_topology.cpp.

281 {
282  return ITEM_SET();
283 }
std::unordered_set< SCH_ITEM * > ITEM_SET
Definition: sch_item.h:138

◆ ConnectedJoints()

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

Definition at line 61 of file pns_topology.cpp.

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

◆ DpCoupledLine()

const LINE PNS::TOPOLOGY::DpCoupledLine ( LINE aLine)

◆ DpCoupledNet()

int PNS::TOPOLOGY::DpCoupledNet ( int  aNet)

◆ DpNetPolarity()

int PNS::TOPOLOGY::DpNetPolarity ( int  aNet)

◆ followTrivialPath()

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

Definition at line 179 of file pns_topology.cpp.

180 {
181  assert( aLine->IsLinked() );
182 
183  VECTOR2I anchor = aLeft ? aLine->CPoint( 0 ) : aLine->CPoint( -1 );
184  LINKED_ITEM* last =
185  aLeft ? aLine->LinkedSegments().front() : aLine->LinkedSegments().back();
186  JOINT* jt = m_world->FindJoint( anchor, aLine );
187 
188  assert( jt != NULL );
189 
190  aVisited.insert( last );
191 
192  if( jt->IsNonFanoutVia() || jt->IsTraceWidthChange() )
193  {
194  ITEM* via = NULL;
195  SEGMENT* next_seg = NULL;
196 
197  for( ITEM* link : jt->Links().Items() )
198  {
199  if( link->OfKind( ITEM::VIA_T ) )
200  via = link;
201  else if( aVisited.find( link ) == aVisited.end() )
202  next_seg = static_cast<SEGMENT*>( link );
203  }
204 
205  if( !next_seg )
206  return false;
207 
208  LINE l = m_world->AssembleLine( next_seg );
209 
210  VECTOR2I nextAnchor = ( aLeft ? l.CLine().CPoint( -1 ) : l.CLine().CPoint( 0 ) );
211 
212  if( nextAnchor != anchor )
213  {
214  l.Reverse();
215  }
216 
217  if( aLeft )
218  {
219  if( via )
220  aSet.Prepend( via );
221 
222  aSet.Prepend( l );
223  }
224  else
225  {
226  if( via )
227  aSet.Add( via );
228 
229  aSet.Add( l );
230  }
231 
232  return followTrivialPath( &l, aLeft, aSet, aVisited );
233  }
234 
235  return false;
236 }
bool followTrivialPath(LINE *aLine, bool aLeft, ITEM_SET &aSet, std::set< ITEM * > &aVisited)
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Function AssembleLine()
Definition: pns_node.cpp:893
#define NULL
NODE * m_world
Definition: pns_topology.h:71
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:1027

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

Referenced by AssembleTrivialPath().

◆ LeadingRatLine()

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

Definition at line 96 of file pns_topology.cpp.

97 {
98  LINE track( *aTrack );
99  VECTOR2I end;
100 
101  if( !track.PointCount() )
102  return false;
103 
104  std::unique_ptr<NODE> tmpNode( m_world->Branch() );
105  tmpNode->Add( track );
106 
107  JOINT* jt = tmpNode->FindJoint( track.CPoint( -1 ), &track );
108 
109  if( !jt )
110  return false;
111 
112  if( ( !track.EndsWithVia() && jt->LinkCount() >= 2 ) || ( track.EndsWithVia() && jt->LinkCount() >= 3 ) ) // we got something connected
113  {
114  end = jt->Pos();
115  }
116  else
117  {
118  int anchor;
119 
120  TOPOLOGY topo( tmpNode.get() );
121  ITEM* it = topo.NearestUnconnectedItem( jt, &anchor );
122 
123  if( !it )
124  return false;
125 
126  end = it->Anchor( anchor );
127  }
128 
129  aRatLine.Clear();
130  aRatLine.Append( track.CPoint( -1 ) );
131  aRatLine.Append( end );
132  return true;
133 }
TOPOLOGY(NODE *aNode)
Definition: pns_topology.h:44
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:106
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
NODE * m_world
Definition: pns_topology.h:71
void Clear()
Function Clear() Removes all points from the line chain.

References SHAPE_LINE_CHAIN::Append(), PNS::NODE::Branch(), SHAPE_LINE_CHAIN::Clear(), PNS::LINE::CPoint(), PNS::LINE::EndsWithVia(), PNS::JOINT::LinkCount(), m_world, 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 = NULL,
int  aKindMask = ITEM::ANY_T 
)

Definition at line 136 of file pns_topology.cpp.

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

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

◆ ShortestConnectionLength()

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

◆ SimplifyLine()

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

Definition at line 37 of file pns_topology.cpp.

38 {
39  if( !aLine->IsLinked() || !aLine->SegmentCount() )
40  return false;
41 
42  LINKED_ITEM* root = aLine->GetLink( 0 );
43  LINE l = m_world->AssembleLine( root );
44  SHAPE_LINE_CHAIN simplified( l.CLine() );
45 
46  simplified.Simplify();
47 
48  if( simplified.PointCount() != l.PointCount() )
49  {
50  m_world->Remove( l );
51  LINE lnew( l );
52  lnew.SetShape( simplified );
53  m_world->Add( lnew );
54  return true;
55  }
56 
57  return false;
58 }
void Remove(ARC *aArc)
Function Remove()
Definition: pns_node.cpp:796
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Function AssembleLine()
Definition: pns_node.cpp:893
NODE * m_world
Definition: pns_topology.h:71
SHAPE_LINE_CHAIN.
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:620

References PNS::NODE::Add(), PNS::NODE::AssembleLine(), PNS::LINE::CLine(), PNS::LINE::GetLink(), PNS::LINE::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: