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 NearestUnconnectedAnchorPoint (const LINE *aTrack, VECTOR2I &aPoint, LAYER_RANGE &aLayers)
 
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, bool aFollowLockedSegments=false)
 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

const int DP_PARALLELITY_THRESHOLD = 5
 
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 ) {};

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

534{
535 std::set<ITEM*> visited;
536 std::deque<ITEM*> pending;
537
538 pending.push_back( aStart );
539
540 while( !pending.empty() )
541 {
542 NODE::OBSTACLES obstacles;
543 ITEM* top = pending.front();
544
545 pending.pop_front();
546
547 visited.insert( top );
548
549 m_world->QueryColliding( top, obstacles, ITEM::ANY_T, -1, false, 0 ); // only query touching objects
550
551 for( OBSTACLE& obs : obstacles )
552 {
553 bool trackOnTrack = ( obs.m_item->Net() != top->Net() ) && obs.m_item->OfKind( ITEM::SEGMENT_T ) && top->OfKind( ITEM::SEGMENT_T );
554
555 if( trackOnTrack )
556 continue;
557
558 if( visited.find( obs.m_item ) == visited.end() &&
559 obs.m_item->Layers().Overlaps( aLayer ) && !( obs.m_item->Marker() & MK_HEAD ) )
560 {
561 visited.insert( obs.m_item );
562 pending.push_back( obs.m_item );
563 }
564 }
565 }
566
567 return visited;
568}
@ SEGMENT_T
Definition: pns_item.h:66
int QueryColliding(const ITEM *aItem, OBSTACLES &aObstacles, int aKindMask=ITEM::ANY_T, int aLimitCount=-1, bool aDifferentNetsOnly=true, int aOverrideClearance=-1)
Find items colliding (closer than clearance) with the item aItem.
Definition: pns_node.cpp:272
std::vector< OBSTACLE > OBSTACLES
Definition: pns_node.h:168
@ MK_HEAD
Definition: pns_item.h:41

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

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

◆ AssembleDiffPair() [1/2]

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

Definition at line 459 of file pns_topology.cpp.

460{
461 int refNet = aStart->Net();
462 int coupledNet = m_world->GetRuleResolver()->DpCoupledNet( refNet );
463
464 if( coupledNet < 0 )
465 return false;
466
467 std::set<ITEM*> coupledItems;
468
469 m_world->AllItemsInNet( coupledNet, coupledItems );
470
471 SEGMENT* coupledSeg = nullptr, *refSeg;
472 int minDist = std::numeric_limits<int>::max();
473
474 if( ( refSeg = dyn_cast<SEGMENT*>( aStart ) ) != nullptr )
475 {
476 for( ITEM* item : coupledItems )
477 {
478 if( SEGMENT* s = dyn_cast<SEGMENT*>( item ) )
479 {
480 if( s->Layers().Start() == refSeg->Layers().Start() &&
481 s->Width() == refSeg->Width() )
482 {
483 int dist = s->Seg().Distance( refSeg->Seg() );
484 bool isParallel = refSeg->Seg().ApproxParallel( s->Seg(), DP_PARALLELITY_THRESHOLD );
485 SEG p_clip, n_clip;
486
487 bool isCoupled = commonParallelProjection( refSeg->Seg(), s->Seg(), p_clip,
488 n_clip );
489
490 if( isParallel && isCoupled && dist < minDist )
491 {
492 minDist = dist;
493 coupledSeg = s;
494 }
495 }
496 }
497 }
498 }
499 else
500 {
501 return false;
502 }
503
504 if( !coupledSeg )
505 return false;
506
507 LINE lp = m_world->AssembleLine( refSeg );
508 LINE ln = m_world->AssembleLine( coupledSeg );
509
510 if( m_world->GetRuleResolver()->DpNetPolarity( refNet ) < 0 )
511 {
512 std::swap( lp, ln );
513 }
514
515 int gap = -1;
516
517 if( refSeg->Seg().ApproxParallel( coupledSeg->Seg(), DP_PARALLELITY_THRESHOLD ) )
518 {
519 // Segments are parallel -> compute pair gap
520 const VECTOR2I refDir = refSeg->Anchor( 1 ) - refSeg->Anchor( 0 );
521 const VECTOR2I displacement = refSeg->Anchor( 1 ) - coupledSeg->Anchor( 1 );
522 gap = (int) std::abs( refDir.Cross( displacement ) / refDir.EuclideanNorm() ) - lp.Width();
523 }
524
525 aPair = DIFF_PAIR( lp, ln );
526 aPair.SetWidth( lp.Width() );
527 aPair.SetLayers( lp.Layers() );
528 aPair.SetGap( gap );
529
530 return true;
531}
void AllItemsInNet(int aNet, std::set< ITEM * > &aItems, int aKindMask=-1)
Definition: pns_node.cpp:1476
RULE_RESOLVER * GetRuleResolver() const
Return the number of joints.
Definition: pns_node.h:197
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false, bool aFollowLockedSegments=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:1003
virtual int DpNetPolarity(int aNet)=0
virtual int DpCoupledNet(int aNet)=0
const int DP_PARALLELITY_THRESHOLD
Definition: pns_topology.h:96
Definition: seg.h:42
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition: vector2d.h:265
extended_type Cross(const VECTOR2< T > &aVector) const
Compute cross product of self with aVector.
Definition: vector2d.h:459
bool commonParallelProjection(SEG p, SEG n, SEG &pClip, SEG &nClip)
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition: eda_angle.h:418

References std::abs(), PNS::NODE::AllItemsInNet(), PNS::SEGMENT::Anchor(), PNS::NODE::AssembleLine(), PNS::commonParallelProjection(), VECTOR2< T >::Cross(), DP_PARALLELITY_THRESHOLD, 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().

◆ AssembleDiffPair() [2/2]

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

◆ AssembleTrivialPath()

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

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.
aFollowLockedSegmentsif true will assemble a path including locked segments
Returns
a set of items in the path.

Definition at line 265 of file pns_topology.cpp.

268{
269 ITEM_SET path;
270 std::set<ITEM*> visited;
271 LINKED_ITEM* seg = nullptr;
272
273 if( aStart->Kind() == ITEM::VIA_T )
274 {
275 VIA* via = static_cast<VIA*>( aStart );
276 JOINT* jt = m_world->FindJoint( via->Pos(), via );
277
278 if( !jt->IsNonFanoutVia() )
279 return ITEM_SET();
280
281 for( const ITEM_SET::ENTRY& entry : jt->Links().Items() )
282 {
283 if( entry.item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
284 {
285 seg = static_cast<LINKED_ITEM*>( entry.item );
286 break;
287 }
288 }
289 }
290 else if( aStart->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
291 {
292 seg = static_cast<LINKED_ITEM*>( aStart );
293 }
294
295 if( !seg )
296 return ITEM_SET();
297
298 // Assemble a line following through locked segments
299 // TODO: consider if we want to allow tuning lines with different widths in the future
300 LINE l = m_world->AssembleLine( seg, nullptr, false, true );
301
302 path.Add( l );
303
304 JOINT* jointA = nullptr;
305 JOINT* jointB = nullptr;
306
307 followTrivialPath( &l, false, path, visited, &jointB );
308 followTrivialPath( &l, true, path, visited, &jointA );
309
310 if( aTerminalJoints )
311 {
312 wxASSERT( jointA && jointB );
313 *aTerminalJoints = std::make_pair( jointA, jointB );
314 }
315
316 return path;
317}
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:1201
bool followTrivialPath(LINE *aLine, bool aLeft, ITEM_SET &aSet, std::set< ITEM * > &aVisited, JOINT **aTerminalJoint=nullptr)
@ VIA
Normal via.
Definition: router_tool.cpp:90

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

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

References SEG::A, AssembleTrivialPath(), SEG::B, PNS::LINE::CLine(), 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::DP_MEANDER_PLACER::Start(), PNS::MEANDER_PLACER::Start(), and PNS::MEANDER_SKEW_PLACER::Start().

◆ ConnectedItems() [1/2]

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

Definition at line 450 of file pns_topology.cpp.

451{
452 return ITEM_SET();
453}

◆ ConnectedItems() [2/2]

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

Definition at line 444 of file pns_topology.cpp.

445{
446 return ITEM_SET();
447}

◆ 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 | ITEM::ARC_T ) )
78 {
79 JOINT* a = m_world->FindJoint( item->Anchor( 0 ), item );;
80 JOINT* b = m_world->FindJoint( item->Anchor( 1 ), item );;
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}
std::set< JOINT * > JOINT_SET
Definition: pns_topology.h:42
CITER next(CITER it)
Definition: ptree.cpp:126

References PNS::ITEM::ARC_T, PNS::NODE::FindJoint(), PNS::JOINT::LinkList(), m_world, next(), 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 197 of file pns_topology.cpp.

199{
200 assert( aLine->IsLinked() );
201
202 VECTOR2I anchor = aLeft ? aLine->CPoint( 0 ) : aLine->CPoint( -1 );
203 LINKED_ITEM* last = aLeft ? aLine->Links().front() : aLine->Links().back();
204 JOINT* jt = m_world->FindJoint( anchor, aLine );
205
206 assert( jt != nullptr );
207
208 aVisited.insert( last );
209
210 if( jt->IsNonFanoutVia() || jt->IsTraceWidthChange() )
211 {
212 ITEM* via = nullptr;
213 SEGMENT* next_seg = nullptr;
214
215 for( ITEM* link : jt->Links().Items() )
216 {
217 if( link->OfKind( ITEM::VIA_T ) )
218 via = link;
219 else if( aVisited.find( link ) == aVisited.end() )
220 next_seg = static_cast<SEGMENT*>( link );
221 }
222
223 if( !next_seg )
224 {
225 if( aTerminalJoint )
226 *aTerminalJoint = jt;
227
228 return false;
229 }
230
231 LINE l = m_world->AssembleLine( next_seg );
232
233 VECTOR2I nextAnchor = ( aLeft ? l.CLine().CPoint( -1 ) : l.CLine().CPoint( 0 ) );
234
235 if( nextAnchor != anchor )
236 {
237 l.Reverse();
238 }
239
240 if( aLeft )
241 {
242 if( via )
243 aSet.Prepend( via );
244
245 aSet.Prepend( l );
246 }
247 else
248 {
249 if( via )
250 aSet.Add( via );
251
252 aSet.Add( l );
253 }
254
255 return followTrivialPath( &l, aLeft, aSet, aVisited, aTerminalJoint );
256 }
257
258 if( aTerminalJoint )
259 *aTerminalJoint = jt;
260
261 return false;
262}

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

Referenced by AssembleTrivialPath(), and followTrivialPath().

◆ LeadingRatLine()

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

Definition at line 138 of file pns_topology.cpp.

139{
140 VECTOR2I end;
141 // Ratline doesn't care about the layer
142 LAYER_RANGE layers;
143
144 if( !NearestUnconnectedAnchorPoint( aTrack, end, layers ) )
145 return false;
146
147 aRatLine.Clear();
148 aRatLine.Append( aTrack->CPoint( -1 ) );
149 aRatLine.Append( end );
150 return true;
151}
Represent a contiguous set of PCB layers.
Definition: pns_layerset.h:32
bool NearestUnconnectedAnchorPoint(const LINE *aTrack, VECTOR2I &aPoint, LAYER_RANGE &aLayers)
void Clear()
Remove all points from the line chain.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.

References SHAPE_LINE_CHAIN::Append(), SHAPE_LINE_CHAIN::Clear(), PNS::LINE::CPoint(), and NearestUnconnectedAnchorPoint().

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

◆ NearestUnconnectedAnchorPoint()

bool PNS::TOPOLOGY::NearestUnconnectedAnchorPoint ( const LINE aTrack,
VECTOR2I aPoint,
LAYER_RANGE aLayers 
)

Definition at line 96 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 aLayers = jt->Layers();
118 }
119 else
120 {
121 int anchor;
122
123 TOPOLOGY topo( tmpNode.get() );
124 ITEM* it = topo.NearestUnconnectedItem( jt, &anchor );
125
126 if( !it )
127 return false;
128
129 end = it->Anchor( anchor );
130 aLayers = it->Layers();
131 }
132
133 aPoint = end;
134 return true;
135}
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:139
TOPOLOGY(NODE *aNode)
Definition: pns_topology.h:44

References anchor, PNS::ITEM::Anchor(), PNS::NODE::Branch(), PNS::LINE::CPoint(), PNS::LINE::EndsWithVia(), PNS::ITEM::Layers(), PNS::JOINT::LinkCount(), m_world, NearestUnconnectedItem(), PNS::JOINT::Net(), PNS::LINE::PointCount(), and PNS::JOINT::Pos().

Referenced by PNS::ROUTER::getNearestRatnestAnchor(), and LeadingRatLine().

◆ NearestUnconnectedItem()

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

Definition at line 154 of file pns_topology.cpp.

155{
156 std::set<ITEM*> disconnected;
157
158 m_world->AllItemsInNet( aStart->Net(), disconnected );
159
160 for( const JOINT* jt : ConnectedJoints( aStart ) )
161 {
162 for( ITEM* link : jt->LinkList() )
163 {
164 if( disconnected.find( link ) != disconnected.end() )
165 disconnected.erase( link );
166 }
167 }
168
169 int best_dist = INT_MAX;
170 ITEM* best = nullptr;
171
172 for( ITEM* item : disconnected )
173 {
174 if( item->OfKind( aKindMask ) )
175 {
176 for( int i = 0; i < item->AnchorCount(); i++ )
177 {
178 VECTOR2I p = item->Anchor( i );
179 int d = ( p - aStart->Pos() ).EuclideanNorm();
180
181 if( d < best_dist )
182 {
183 best_dist = d;
184 best = item;
185
186 if( aAnchor )
187 *aAnchor = i;
188 }
189 }
190 }
191 }
192
193 return best;
194}
const JOINT_SET ConnectedJoints(JOINT *aStart)
double EuclideanNorm(const VECTOR2I &vector)
Definition: trigo.h:129

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

Referenced by PNS::ROUTER::getNearestRatnestAnchor(), and NearestUnconnectedAnchorPoint().

◆ 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}
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:667
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:893

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

◆ DP_PARALLELITY_THRESHOLD

const int PNS::TOPOLOGY::DP_PARALLELITY_THRESHOLD = 5
private

Definition at line 96 of file pns_topology.h.

Referenced by AssembleDiffPair().

◆ m_world


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