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, 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 ) {};
NODE * m_world
Definition: pns_topology.h:98

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

519{
520 std::set<ITEM*> visited;
521 std::deque<ITEM*> pending;
522
523 pending.push_back( aStart );
524
525 while( !pending.empty() )
526 {
527 NODE::OBSTACLES obstacles;
528 ITEM* top = pending.front();
529
530 pending.pop_front();
531
532 visited.insert( top );
533
534 m_world->QueryColliding( top, obstacles, ITEM::ANY_T, -1, false, 0 ); // only query touching objects
535
536 for( OBSTACLE& obs : obstacles )
537 {
538 bool trackOnTrack = ( obs.m_item->Net() != top->Net() ) && obs.m_item->OfKind( ITEM::SEGMENT_T ) && top->OfKind( ITEM::SEGMENT_T );
539
540 if( trackOnTrack )
541 continue;
542
543 if( visited.find( obs.m_item ) == visited.end() &&
544 obs.m_item->Layers().Overlaps( aLayer ) && !( obs.m_item->Marker() & MK_HEAD ) )
545 {
546 visited.insert( obs.m_item );
547 pending.push_back( obs.m_item );
548 }
549 }
550 }
551
552 return visited;
553}
@ 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:271
std::vector< OBSTACLE > OBSTACLES
Definition: pns_node.h:162
@ 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 444 of file pns_topology.cpp.

445{
446 int refNet = aStart->Net();
447 int coupledNet = m_world->GetRuleResolver()->DpCoupledNet( refNet );
448
449 if( coupledNet < 0 )
450 return false;
451
452 std::set<ITEM*> coupledItems;
453
454 m_world->AllItemsInNet( coupledNet, coupledItems );
455
456 SEGMENT* coupledSeg = nullptr, *refSeg;
457 int minDist = std::numeric_limits<int>::max();
458
459 if( ( refSeg = dyn_cast<SEGMENT*>( aStart ) ) != nullptr )
460 {
461 for( ITEM* item : coupledItems )
462 {
463 if( SEGMENT* s = dyn_cast<SEGMENT*>( item ) )
464 {
465 if( s->Layers().Start() == refSeg->Layers().Start() &&
466 s->Width() == refSeg->Width() )
467 {
468 int dist = s->Seg().Distance( refSeg->Seg() );
469 bool isParallel = refSeg->Seg().ApproxParallel( s->Seg(), DP_PARALLELITY_THRESHOLD );
470 SEG p_clip, n_clip;
471
472 bool isCoupled = commonParallelProjection( refSeg->Seg(), s->Seg(), p_clip,
473 n_clip );
474
475 if( isParallel && isCoupled && dist < minDist )
476 {
477 minDist = dist;
478 coupledSeg = s;
479 }
480 }
481 }
482 }
483 }
484 else
485 {
486 return false;
487 }
488
489 if( !coupledSeg )
490 return false;
491
492 LINE lp = m_world->AssembleLine( refSeg );
493 LINE ln = m_world->AssembleLine( coupledSeg );
494
495 if( m_world->GetRuleResolver()->DpNetPolarity( refNet ) < 0 )
496 {
497 std::swap( lp, ln );
498 }
499
500 int gap = -1;
501
502 if( refSeg->Seg().ApproxParallel( coupledSeg->Seg(), DP_PARALLELITY_THRESHOLD ) )
503 {
504 // Segments are parallel -> compute pair gap
505 const VECTOR2I refDir = refSeg->Anchor( 1 ) - refSeg->Anchor( 0 );
506 const VECTOR2I displacement = refSeg->Anchor( 1 ) - coupledSeg->Anchor( 1 );
507 gap = (int) std::abs( refDir.Cross( displacement ) / refDir.EuclideanNorm() ) - lp.Width();
508 }
509
510 aPair = DIFF_PAIR( lp, ln );
511 aPair.SetWidth( lp.Width() );
512 aPair.SetLayers( lp.Layers() );
513 aPair.SetGap( gap );
514
515 return true;
516}
void AllItemsInNet(int aNet, std::set< ITEM * > &aItems, int aKindMask=-1)
Definition: pns_node.cpp:1457
RULE_RESOLVER * GetRuleResolver() const
Return the number of joints.
Definition: pns_node.h:191
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:983
virtual int DpNetPolarity(int aNet)=0
virtual int DpCoupledNet(int aNet)=0
const int DP_PARALLELITY_THRESHOLD
Definition: pns_topology.h:93
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:291
extended_type Cross(const VECTOR2< T > &aVector) const
Compute cross product of self with aVector.
Definition: vector2d.h:476
bool commonParallelProjection(SEG p, SEG n, SEG &pClip, SEG &nClip)
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition: eda_angle.h:412

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

252{
253 ITEM_SET path;
254 std::set<ITEM*> visited;
255 LINKED_ITEM* seg = nullptr;
256
257 if( aStart->Kind() == ITEM::VIA_T )
258 {
259 VIA* via = static_cast<VIA*>( aStart );
260 JOINT* jt = m_world->FindJoint( via->Pos(), via );
261
262 if( !jt->IsNonFanoutVia() )
263 return ITEM_SET();
264
265 for( const ITEM_SET::ENTRY& entry : jt->Links().Items() )
266 {
267 if( entry.item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
268 {
269 seg = static_cast<LINKED_ITEM*>( entry.item );
270 break;
271 }
272 }
273 }
274 else if( aStart->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
275 {
276 seg = static_cast<LINKED_ITEM*>( aStart );
277 }
278
279 if( !seg )
280 return ITEM_SET();
281
282 // Assemble a line following through locked segments
283 // TODO: consider if we want to allow tuning lines with different widths in the future
284 LINE l = m_world->AssembleLine( seg, nullptr, false, true );
285
286 path.Add( l );
287
288 JOINT* jointA = nullptr;
289 JOINT* jointB = nullptr;
290
291 followTrivialPath( &l, false, path, visited, &jointA );
292 followTrivialPath( &l, true, path, visited, &jointB );
293
294 if( aTerminalJoints )
295 {
296 wxASSERT( jointA && jointB );
297 *aTerminalJoints = std::make_pair( jointA, jointB );
298 }
299
300 return path;
301}
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:1181
bool followTrivialPath(LINE *aLine, bool aLeft, ITEM_SET &aSet, std::set< ITEM * > &aVisited, JOINT **aTerminalJoint=nullptr)
@ VIA
Normal via.
Definition: router_tool.cpp:76

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

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

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

436{
437 return ITEM_SET();
438}

◆ ConnectedItems() [2/2]

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

Definition at line 429 of file pns_topology.cpp.

430{
431 return ITEM_SET();
432}

◆ 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}
std::set< JOINT * > JOINT_SET
Definition: pns_topology.h:42
CITER next(CITER it)
Definition: ptree.cpp:126

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}

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 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}
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
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 anchor, PNS::ITEM::Anchor(), SHAPE_LINE_CHAIN::Append(), PNS::NODE::Branch(), SHAPE_LINE_CHAIN::Clear(), PNS::LINE::CPoint(), PNS::LINE::EndsWithVia(), PNS::JOINT::LinkCount(), m_world, NearestUnconnectedItem(), 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}
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 LeadingRatLine().

◆ 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:656
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:873

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 93 of file pns_topology.h.

Referenced by AssembleDiffPair().

◆ m_world


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