KiCad PCB EDA Suite
RN_NET Class Reference

Describe ratsnest for a single net. More...

#include <ratsnest_data.h>

Classes

class  TRIANGULATOR_STATE
 

Public Member Functions

 RN_NET ()
 
bool IsDirty () const
 Return state of the 'dirty' flag, indicating that ratsnest for a given net is invalid and requires an update. More...
 
void UpdateNet ()
 Recompute ratsnest for a net. More...
 
void Clear ()
 
void AddCluster (std::shared_ptr< CN_CLUSTER > aCluster)
 
unsigned int GetNodeCount () const
 
const std::vector< CN_EDGE > & GetEdges () const
 
std::vector< CN_EDGE > & GetEdges ()
 
bool NearestBicoloredPair (RN_NET *aOtherNet, VECTOR2I &aPos1, VECTOR2I &aPos2) const
 

Protected Member Functions

void compute ()
 < Recompute ratsnest from scratch. More...
 
void kruskalMST (const std::vector< CN_EDGE > &aEdges)
 Find optimal ends of RNEdges. More...
 
void optimizeRNEdges ()
 

Protected Attributes

std::multiset< std::shared_ptr< CN_ANCHOR >, CN_PTR_CMPm_nodes
 < Vector of nodes More...
 
std::vector< CN_EDGEm_boardEdges
 Vector of edges that makes ratsnest for a given net. More...
 
std::vector< CN_EDGEm_rnEdges
 Flag indicating necessity of recalculation of ratsnest for a net. More...
 
bool m_dirty
 
std::shared_ptr< TRIANGULATOR_STATEm_triangulator
 

Detailed Description

Describe ratsnest for a single net.

Definition at line 62 of file ratsnest_data.h.

Constructor & Destructor Documentation

◆ RN_NET()

RN_NET::RN_NET ( )

Definition at line 262 of file ratsnest_data.cpp.

262 : m_dirty( true )
263{
264 m_triangulator.reset( new TRIANGULATOR_STATE );
265}
std::shared_ptr< TRIANGULATOR_STATE > m_triangulator
bool m_dirty

References m_triangulator.

Member Function Documentation

◆ AddCluster()

void RN_NET::AddCluster ( std::shared_ptr< CN_CLUSTER aCluster)

Definition at line 473 of file ratsnest_data.cpp.

474{
475 std::shared_ptr<CN_ANCHOR> firstAnchor;
476
477 for( CN_ITEM* item : *aCluster )
478 {
479 std::vector<std::shared_ptr<CN_ANCHOR>>& anchors = item->Anchors();
480 unsigned int nAnchors = dynamic_cast<CN_ZONE_LAYER*>( item ) ? 1 : anchors.size();
481
482 if( nAnchors > anchors.size() )
483 nAnchors = anchors.size();
484
485 for( unsigned int i = 0; i < nAnchors; i++ )
486 {
487 anchors[i]->SetCluster( aCluster );
488 m_nodes.insert( anchors[i] );
489
490 if( firstAnchor )
491 {
492 if( firstAnchor != anchors[i] )
493 m_boardEdges.emplace_back( firstAnchor, anchors[i], 0 );
494 }
495 else
496 {
497 firstAnchor = anchors[i];
498 }
499 }
500 }
501}
CN_ITEM represents a BOARD_CONNETED_ITEM in the connectivity system (ie: a pad, track/arc/via,...
std::multiset< std::shared_ptr< CN_ANCHOR >, CN_PTR_CMP > m_nodes
< Vector of nodes
std::vector< CN_EDGE > m_boardEdges
Vector of edges that makes ratsnest for a given net.

References m_boardEdges, and m_nodes.

Referenced by CONNECTIVITY_DATA::addRatsnestCluster().

◆ Clear()

void RN_NET::Clear ( )

Definition at line 463 of file ratsnest_data.cpp.

464{
465 m_rnEdges.clear();
466 m_boardEdges.clear();
467 m_nodes.clear();
468
469 m_dirty = true;
470}
std::vector< CN_EDGE > m_rnEdges
Flag indicating necessity of recalculation of ratsnest for a net.

References m_boardEdges, m_dirty, m_nodes, and m_rnEdges.

◆ compute()

void RN_NET::compute ( )
protected

< Recompute ratsnest from scratch.

Compute the minimum spanning tree using Kruskal's algorithm

Definition at line 268 of file ratsnest_data.cpp.

269{
270 // Special cases do not need complicated algorithms (actually, it does not work well with
271 // the Delaunay triangulator)
272 if( m_nodes.size() <= 2 )
273 {
274 m_rnEdges.clear();
275
276 // Check if the only possible connection exists
277 if( m_boardEdges.size() == 0 && m_nodes.size() == 2 )
278 {
279 // There can be only one possible connection, but it is missing
280 auto it = m_nodes.begin();
281 const std::shared_ptr<CN_ANCHOR>& source = *it++;
282 const std::shared_ptr<CN_ANCHOR>& target = *it;
283
284 source->SetTag( 0 );
285 target->SetTag( 1 );
286 m_rnEdges.emplace_back( source, target );
287 }
288 else
289 {
290 // Set tags to m_nodes as connected
291 for( const std::shared_ptr<CN_ANCHOR>& node : m_nodes )
292 node->SetTag( 0 );
293 }
294
295 return;
296 }
297
298
299 m_triangulator->Clear();
300
301 for( const std::shared_ptr<CN_ANCHOR>& n : m_nodes )
302 m_triangulator->AddNode( n );
303
304 std::vector<CN_EDGE> triangEdges;
305 triangEdges.reserve( m_nodes.size() + m_boardEdges.size() );
306
307#ifdef PROFILE
308 PROF_TIMER cnt( "triangulate" );
309#endif
310 m_triangulator->Triangulate( triangEdges );
311#ifdef PROFILE
312 cnt.Show();
313#endif
314
315 for( const CN_EDGE& e : m_boardEdges )
316 triangEdges.emplace_back( e );
317
318 std::sort( triangEdges.begin(), triangEdges.end() );
319
320// Get the minimal spanning tree
321#ifdef PROFILE
322 PROF_TIMER cnt2( "mst" );
323#endif
324 kruskalMST( triangEdges );
325#ifdef PROFILE
326 cnt2.Show();
327#endif
328}
CN_EDGE represents a point-to-point connection, whether realized or unrealized (ie: tracks etc.
A small class to help profiling.
Definition: profile.h:47
void kruskalMST(const std::vector< CN_EDGE > &aEdges)
Find optimal ends of RNEdges.

References kruskalMST(), m_boardEdges, m_nodes, m_rnEdges, m_triangulator, and PROF_TIMER::Show().

Referenced by UpdateNet().

◆ GetEdges() [1/2]

std::vector< CN_EDGE > & RN_NET::GetEdges ( )
inline

Definition at line 86 of file ratsnest_data.h.

86{ return m_rnEdges; }

References m_rnEdges.

◆ GetEdges() [2/2]

◆ GetNodeCount()

unsigned int RN_NET::GetNodeCount ( ) const
inline

Definition at line 83 of file ratsnest_data.h.

83{ return m_nodes.size(); }

References m_nodes.

Referenced by CONNECTIVITY_DATA::ComputeLocalRatsnest().

◆ IsDirty()

bool RN_NET::IsDirty ( ) const
inline

Return state of the 'dirty' flag, indicating that ratsnest for a given net is invalid and requires an update.

Returns
True if ratsnest requires recomputation, false otherwise.

Definition at line 73 of file ratsnest_data.h.

73{ return m_dirty; }

References m_dirty.

◆ kruskalMST()

void RN_NET::kruskalMST ( const std::vector< CN_EDGE > &  aEdges)
protected

Find optimal ends of RNEdges.

The MST will have found the closest anchors, but when zones are involved we might have points closer than the anchors.

Definition at line 110 of file ratsnest_data.cpp.

111{
112 disjoint_set dset( m_nodes.size() );
113
114 m_rnEdges.clear();
115
116 int i = 0;
117
118 for( const std::shared_ptr<CN_ANCHOR>& node : m_nodes )
119 node->SetTag( i++ );
120
121 for( const CN_EDGE& tmp : aEdges )
122 {
123 const std::shared_ptr<const CN_ANCHOR>& source = tmp.GetSourceNode();
124 const std::shared_ptr<const CN_ANCHOR>& target = tmp.GetTargetNode();
125
126 if( dset.unite( source->GetTag(), target->GetTag() ) )
127 {
128 if( tmp.GetWeight() > 0 )
129 m_rnEdges.push_back( tmp );
130 }
131 }
132}

References m_nodes, m_rnEdges, and disjoint_set::unite().

Referenced by compute().

◆ NearestBicoloredPair()

bool RN_NET::NearestBicoloredPair ( RN_NET aOtherNet,
VECTOR2I aPos1,
VECTOR2I aPos2 
) const

Sweep-line algorithm to cut the number of comparisons to find the closest point

Step 1: The outer loop needs to be the subset (selected nodes) as it is a linear search

Step 2: O( log n ) search to identify a close element ordered by x The fwd_it iterator will move forward through the elements while the rev_it iterator will move backward through the same set

As soon as the x distance (primary sort) is larger than the smallest distance, stop checking further elements

Step 3: using the same starting point, check points backwards for closer points

Definition at line 504 of file ratsnest_data.cpp.

505{
506 bool rv = false;
507
509
510 auto verify =
511 [&]( const std::shared_ptr<CN_ANCHOR>& aTestNode1,
512 const std::shared_ptr<CN_ANCHOR>& aTestNode2 )
513 {
514 VECTOR2I diff = aTestNode1->Pos() - aTestNode2->Pos();
515 SEG::ecoord dist_sq = diff.SquaredEuclideanNorm();
516
517 if( dist_sq < distMax_sq )
518 {
519 rv = true;
520 distMax_sq = dist_sq;
521 aPos1 = aTestNode1->Pos();
522 aPos2 = aTestNode2->Pos();
523 }
524 };
525
526 std::multiset<std::shared_ptr<CN_ANCHOR>, CN_PTR_CMP> nodes_b;
527
528 std::copy_if( m_nodes.begin(), m_nodes.end(), std::inserter( nodes_b, nodes_b.end() ),
529 []( const std::shared_ptr<CN_ANCHOR> &aVal )
530 { return !aVal->GetNoLine(); } );
531
535 for( const std::shared_ptr<CN_ANCHOR>& nodeA : aOtherNet->m_nodes )
536 {
537
538 if( nodeA->GetNoLine() )
539 continue;
540
544 auto fwd_it = nodes_b.lower_bound( nodeA );
545 auto rev_it = std::make_reverse_iterator( fwd_it );
546
547 for( ; fwd_it != nodes_b.end(); ++fwd_it )
548 {
549 const std::shared_ptr<CN_ANCHOR>& nodeB = *fwd_it;
550
551 SEG::ecoord distX_sq = SEG::Square( nodeA->Pos().x - nodeB->Pos().x );
552
555 if( distX_sq > distMax_sq )
556 break;
557
558 verify( nodeA, nodeB );
559 }
560
562 for( ; rev_it != nodes_b.rend(); ++rev_it )
563 {
564 const std::shared_ptr<CN_ANCHOR>& nodeB = *rev_it;
565
566 SEG::ecoord distX_sq = SEG::Square( nodeA->Pos().x - nodeB->Pos().x );
567
568 if( distX_sq > distMax_sq )
569 break;
570
571 verify( nodeA, nodeB );
572 }
573 }
574
575 return rv;
576}
VECTOR2I::extended_type ecoord
Definition: seg.h:44
static SEG::ecoord Square(int a)
Definition: seg.h:123
extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
Definition: vector2d.h:300
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:79

References VECTOR2< int >::ECOORD_MAX, m_nodes, SEG::Square(), and VECTOR2< T >::SquaredEuclideanNorm().

Referenced by CONNECTIVITY_DATA::ComputeLocalRatsnest().

◆ optimizeRNEdges()

void RN_NET::optimizeRNEdges ( )
protected

Definition at line 331 of file ratsnest_data.cpp.

332{
333 auto optimizeZoneAnchor =
334 [&]( const VECTOR2I& aPos, const LSET& aLayerSet,
335 const std::shared_ptr<const CN_ANCHOR>& aAnchor,
336 std::function<void( std::shared_ptr<const CN_ANCHOR> )> setOptimizedTo )
337 {
338 SEG::ecoord closest_dist_sq = ( aAnchor->Pos() - aPos ).SquaredEuclideanNorm();
339 VECTOR2I closest_pt;
340 CN_ITEM* closest_item = nullptr;
341
342 for( CN_ITEM* item : aAnchor->Item()->ConnectedItems() )
343 {
344 CN_ZONE_LAYER* zoneLayer = dynamic_cast<CN_ZONE_LAYER*>( item );
345
346 if( zoneLayer && aLayerSet.test( zoneLayer->Layer() ) )
347 {
348 const std::vector<VECTOR2I>& pts = zoneLayer->GetOutline().CPoints();
349
350 for( VECTOR2I pt : pts )
351 {
352 SEG::ecoord dist_sq = ( pt - aPos ).SquaredEuclideanNorm();
353
354 if( dist_sq < closest_dist_sq )
355 {
356 closest_pt = pt;
357 closest_item = zoneLayer;
358 closest_dist_sq = dist_sq;
359 }
360 }
361 }
362 }
363
364 if( closest_item )
365 setOptimizedTo( std::make_shared<CN_ANCHOR>( closest_pt, closest_item ) );
366 };
367
368 auto optimizeZoneToZoneAnchors =
369 [&]( const std::shared_ptr<const CN_ANCHOR>& a,
370 const std::shared_ptr<const CN_ANCHOR>& b,
371 std::function<void(const std::shared_ptr<const CN_ANCHOR>&)> setOptimizedATo,
372 std::function<void(const std::shared_ptr<const CN_ANCHOR>&)> setOptimizedBTo )
373 {
374 for( CN_ITEM* itemA : a->Item()->ConnectedItems() )
375 {
376 CN_ZONE_LAYER* zoneLayerA = dynamic_cast<CN_ZONE_LAYER*>( itemA );
377
378 if( !zoneLayerA )
379 continue;
380
381 for( CN_ITEM* itemB : b->Item()->ConnectedItems() )
382 {
383 CN_ZONE_LAYER* zoneLayerB = dynamic_cast<CN_ZONE_LAYER*>( itemB );
384
385 if( zoneLayerB && zoneLayerB->Layer() == zoneLayerA->Layer() )
386 {
387 // Process the first matching layer. We don't really care if it's
388 // the "best" layer or not, as anything will be better than the
389 // original anchors (which are connected to the zone and so certainly
390 // don't look like they should have ratsnest lines coming off them).
391
392 VECTOR2I startA = zoneLayerA->GetOutline().GetPoint( 0 );
393 VECTOR2I startB = zoneLayerB->GetOutline().GetPoint( 0 );
394 const SHAPE* shapeA = &zoneLayerA->GetOutline();
395 const SHAPE* shapeB = &zoneLayerB->GetOutline();
396 int startDist = ( startA - startB ).EuclideanNorm();
397
398 VECTOR2I ptA;
399 shapeA->Collide( shapeB, startDist + 10, nullptr, &ptA );
400 setOptimizedATo( std::make_shared<CN_ANCHOR>( ptA, zoneLayerA ) );
401
402 VECTOR2I ptB;
403 shapeB->Collide( shapeA, startDist + 10, nullptr, &ptB );
404 setOptimizedBTo( std::make_shared<CN_ANCHOR>( ptB, zoneLayerB ) );
405 }
406 }
407 }
408 };
409
410 for( CN_EDGE& edge : m_rnEdges )
411 {
412 const std::shared_ptr<const CN_ANCHOR>& source = edge.GetSourceNode();
413 const std::shared_ptr<const CN_ANCHOR>& target = edge.GetTargetNode();
414
415 if( source->ConnectedItemsCount() == 0 )
416 {
417 optimizeZoneAnchor( source->Pos(), source->Parent()->GetLayerSet(), target,
418 [&]( std::shared_ptr<const CN_ANCHOR> optimized )
419 {
420 edge.SetTargetNode( optimized );
421 } );
422 }
423 else if( target->ConnectedItemsCount() == 0 )
424 {
425 optimizeZoneAnchor( target->Pos(), target->Parent()->GetLayerSet(), source,
426 [&]( std::shared_ptr<const CN_ANCHOR> optimized )
427 {
428 edge.SetSourceNode( optimized );
429 } );
430 }
431 else
432 {
433 optimizeZoneToZoneAnchors( source, target,
434 [&]( std::shared_ptr<const CN_ANCHOR> optimized )
435 {
436 edge.SetSourceNode( optimized );
437 },
438 [&]( std::shared_ptr<const CN_ANCHOR> optimized )
439 {
440 edge.SetTargetNode( optimized );
441 } );
442 }
443 }
444}
virtual int Layer() const
Return the item's layer, for single-layered items only.
const std::vector< CN_ITEM * > & ConnectedItems() const
const SHAPE_LINE_CHAIN & GetOutline() const
LSET is a set of PCB_LAYER_IDs.
Definition: layer_ids.h:530
virtual const VECTOR2I GetPoint(int aIndex) const override
const std::vector< VECTOR2I > & CPoints() const
An abstract shape on 2D plane.
Definition: shape.h:123
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const
Check if the boundary of shape (this) lies closer to the point aP than aClearance,...
Definition: shape.h:178
double EuclideanNorm(const VECTOR2I &vector)
Definition: trigo.h:129

References SHAPE::Collide(), CN_ITEM::ConnectedItems(), SHAPE_LINE_CHAIN::CPoints(), EuclideanNorm(), CN_ZONE_LAYER::GetOutline(), SHAPE_LINE_CHAIN::GetPoint(), CN_ITEM::Layer(), and m_rnEdges.

Referenced by UpdateNet().

◆ UpdateNet()

void RN_NET::UpdateNet ( )

Recompute ratsnest for a net.

Definition at line 447 of file ratsnest_data.cpp.

448{
449 compute();
450
451#ifdef PROFILE
452 PROF_TIMER cnt( "optimize" );
453#endif
455#ifdef PROFILE
456 cnt.Show();
457#endif
458
459 m_dirty = false;
460}
void optimizeRNEdges()
void compute()
< Recompute ratsnest from scratch.

References compute(), m_dirty, optimizeRNEdges(), and PROF_TIMER::Show().

Member Data Documentation

◆ m_boardEdges

std::vector<CN_EDGE> RN_NET::m_boardEdges
protected

Vector of edges that makes ratsnest for a given net.

Definition at line 106 of file ratsnest_data.h.

Referenced by AddCluster(), Clear(), and compute().

◆ m_dirty

bool RN_NET::m_dirty
protected

Definition at line 112 of file ratsnest_data.h.

Referenced by Clear(), IsDirty(), and UpdateNet().

◆ m_nodes

std::multiset<std::shared_ptr<CN_ANCHOR>, CN_PTR_CMP> RN_NET::m_nodes
protected

< Vector of nodes

Vector of edges that make pre-defined connections

Definition at line 103 of file ratsnest_data.h.

Referenced by AddCluster(), Clear(), compute(), GetNodeCount(), kruskalMST(), and NearestBicoloredPair().

◆ m_rnEdges

std::vector<CN_EDGE> RN_NET::m_rnEdges
protected

Flag indicating necessity of recalculation of ratsnest for a net.

Definition at line 109 of file ratsnest_data.h.

Referenced by Clear(), compute(), GetEdges(), kruskalMST(), and optimizeRNEdges().

◆ m_triangulator

std::shared_ptr<TRIANGULATOR_STATE> RN_NET::m_triangulator
protected

Definition at line 116 of file ratsnest_data.h.

Referenced by compute(), and RN_NET().


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