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 ()
 
void SetVisible (bool aEnabled)
 Set state of the visibility flag. More...
 
void MarkDirty ()
 Mark ratsnest for given net as 'dirty', i.e. More...
 
bool IsDirty () const
 Return state of the 'dirty' flag, indicating that ratsnest for a given net is invalid and requires an update. More...
 
const std::vector< CN_EDGEGetUnconnected () const
 Return pointer to a vector of edges that makes ratsnest for a given net. More...
 
void Update ()
 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
 
bool NearestBicoloredPair (const RN_NET &aOtherNet, CN_ANCHOR_PTR &aNode1, CN_ANCHOR_PTR &aNode2) const
 

Protected Member Functions

void compute ()
 < Recompute ratsnest from scratch. More...
 
void kruskalMST (const std::vector< CN_EDGE > &aEdges)
 Vector of nodes. More...
 

Protected Attributes

std::multiset< CN_ANCHOR_PTR, CN_PTR_CMPm_nodes
 Vector of edges that make pre-defined connections. 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 61 of file ratsnest_data.h.

Constructor & Destructor Documentation

◆ RN_NET()

RN_NET::RN_NET ( )

Definition at line 270 of file ratsnest_data.cpp.

270  : m_dirty( true )
271 {
272  m_triangulator.reset( new TRIANGULATOR_STATE );
273 }
bool m_dirty
std::shared_ptr< TRIANGULATOR_STATE > m_triangulator

References m_triangulator.

Member Function Documentation

◆ AddCluster()

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

Definition at line 358 of file ratsnest_data.cpp.

359 {
360  CN_ANCHOR_PTR firstAnchor;
361 
362  for( CN_ITEM* item : *aCluster )
363  {
364  bool isZone = dynamic_cast<CN_ZONE_LAYER*>( item );
365  std::vector<CN_ANCHOR_PTR>& anchors = item->Anchors();
366  unsigned int nAnchors = isZone ? 1 : anchors.size();
367 
368  if( nAnchors > anchors.size() )
369  nAnchors = anchors.size();
370 
371  for( unsigned int i = 0; i < nAnchors; i++ )
372  {
373  anchors[i]->SetCluster( aCluster );
374  m_nodes.insert( anchors[i] );
375 
376  if( firstAnchor )
377  {
378  if( firstAnchor != anchors[i] )
379  m_boardEdges.emplace_back( firstAnchor, anchors[i], 0 );
380  }
381  else
382  {
383  firstAnchor = anchors[i];
384  }
385  }
386  }
387 }
std::vector< CN_EDGE > m_boardEdges
Vector of edges that makes ratsnest for a given net.
CN_ITEM represents a BOARD_CONNETED_ITEM in the connectivity system (ie: a pad, track/arc/via,...
std::shared_ptr< CN_ANCHOR > CN_ANCHOR_PTR
std::multiset< CN_ANCHOR_PTR, CN_PTR_CMP > m_nodes
Vector of edges that make pre-defined connections.

References m_boardEdges, and m_nodes.

Referenced by CONNECTIVITY_DATA::addRatsnestCluster().

◆ Clear()

void RN_NET::Clear ( )

Definition at line 348 of file ratsnest_data.cpp.

349 {
350  m_rnEdges.clear();
351  m_boardEdges.clear();
352  m_nodes.clear();
353 
354  m_dirty = true;
355 }
bool m_dirty
std::vector< CN_EDGE > m_rnEdges
Flag indicating necessity of recalculation of ratsnest for a net.
std::vector< CN_EDGE > m_boardEdges
Vector of edges that makes ratsnest for a given net.
std::multiset< CN_ANCHOR_PTR, CN_PTR_CMP > m_nodes
Vector of edges that make pre-defined connections.

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 276 of file ratsnest_data.cpp.

277 {
278  // Special cases do not need complicated algorithms (actually, it does not work well with
279  // the Delaunay triangulator)
280  if( m_nodes.size() <= 2 )
281  {
282  m_rnEdges.clear();
283 
284  // Check if the only possible connection exists
285  if( m_boardEdges.size() == 0 && m_nodes.size() == 2 )
286  {
287  auto last = ++m_nodes.begin();
288 
289  // There can be only one possible connection, but it is missing
290  CN_EDGE edge ( *m_nodes.begin(), *last );
291  edge.GetSourceNode()->SetTag( 0 );
292  edge.GetTargetNode()->SetTag( 1 );
293 
294  m_rnEdges.push_back( edge );
295  }
296  else
297  {
298  // Set tags to m_nodes as connected
299  for( const CN_ANCHOR_PTR& node : m_nodes )
300  node->SetTag( 0 );
301  }
302 
303  return;
304  }
305 
306 
307  m_triangulator->Clear();
308 
309  for( const CN_ANCHOR_PTR& n : m_nodes )
310  m_triangulator->AddNode( n );
311 
312  std::vector<CN_EDGE> triangEdges;
313  triangEdges.reserve( m_nodes.size() + m_boardEdges.size() );
314 
315 #ifdef PROFILE
316  PROF_COUNTER cnt("triangulate");
317 #endif
318  m_triangulator->Triangulate( triangEdges );
319 #ifdef PROFILE
320  cnt.Show();
321 #endif
322 
323  for( const CN_EDGE& e : m_boardEdges )
324  triangEdges.emplace_back( e );
325 
326  std::sort( triangEdges.begin(), triangEdges.end() );
327 
328 // Get the minimal spanning tree
329 #ifdef PROFILE
330  PROF_COUNTER cnt2("mst");
331 #endif
332  kruskalMST( triangEdges );
333 #ifdef PROFILE
334  cnt2.Show();
335 #endif
336 }
std::vector< CN_EDGE > m_rnEdges
Flag indicating necessity of recalculation of ratsnest for a net.
A small class to help profiling.
Definition: profile.h:45
void kruskalMST(const std::vector< CN_EDGE > &aEdges)
Vector of nodes.
std::shared_ptr< TRIANGULATOR_STATE > m_triangulator
CN_EDGE represents a point-to-point connection, whether realized or unrealized (ie: tracks etc.
std::vector< CN_EDGE > m_boardEdges
Vector of edges that makes ratsnest for a given net.
std::shared_ptr< CN_ANCHOR > CN_ANCHOR_PTR
std::multiset< CN_ANCHOR_PTR, CN_PTR_CMP > m_nodes
Vector of edges that make pre-defined connections.
CN_ANCHOR_PTR GetSourceNode() const

References CN_EDGE::GetSourceNode(), kruskalMST(), m_boardEdges, m_nodes, m_rnEdges, m_triangulator, and PROF_COUNTER::Show().

Referenced by Update().

◆ GetEdges()

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

Definition at line 102 of file ratsnest_data.h.

102 { return m_rnEdges; }
std::vector< CN_EDGE > m_rnEdges
Flag indicating necessity of recalculation of ratsnest for a net.

References m_rnEdges.

Referenced by CONNECTIVITY_DATA::GetRatsnestForItems(), and CONNECTIVITY_DATA::GetRatsnestForPad().

◆ GetNodeCount()

unsigned int RN_NET::GetNodeCount ( ) const
inline

Definition at line 100 of file ratsnest_data.h.

100 { return m_nodes.size(); }
std::multiset< CN_ANCHOR_PTR, CN_PTR_CMP > m_nodes
Vector of edges that make pre-defined connections.

References m_nodes.

◆ GetUnconnected()

const std::vector<CN_EDGE> RN_NET::GetUnconnected ( ) const
inline

Return pointer to a vector of edges that makes ratsnest for a given net.

Definition at line 90 of file ratsnest_data.h.

90 { return m_rnEdges; }
std::vector< CN_EDGE > m_rnEdges
Flag indicating necessity of recalculation of ratsnest for a net.

References m_rnEdges.

Referenced by RATSNEST_VIEW_ITEM::ViewDraw().

◆ 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 85 of file ratsnest_data.h.

85 { return m_dirty; }
bool m_dirty

References m_dirty.

◆ kruskalMST()

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

Vector of nodes.

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 CN_ANCHOR_PTR& node : m_nodes )
119  node->SetTag( i++ );
120 
121  for( const CN_EDGE& tmp : aEdges )
122  {
123  int u = tmp.GetSourceNode()->GetTag();
124  int v = tmp.GetTargetNode()->GetTag();
125 
126  if( dset.unite( u, v ) )
127  {
128  if( tmp.GetWeight() > 0 )
129  m_rnEdges.push_back( tmp );
130  }
131  }
132 }
std::vector< CN_EDGE > m_rnEdges
Flag indicating necessity of recalculation of ratsnest for a net.
CN_EDGE represents a point-to-point connection, whether realized or unrealized (ie: tracks etc.
std::shared_ptr< CN_ANCHOR > CN_ANCHOR_PTR
std::multiset< CN_ANCHOR_PTR, CN_PTR_CMP > m_nodes
Vector of edges that make pre-defined connections.

Referenced by compute().

◆ MarkDirty()

void RN_NET::MarkDirty ( )
inline

Mark ratsnest for given net as 'dirty', i.e.

requiring recomputation.

Definition at line 77 of file ratsnest_data.h.

77 { m_dirty = true; }
bool m_dirty

References m_dirty.

◆ NearestBicoloredPair()

bool RN_NET::NearestBicoloredPair ( const RN_NET aOtherNet,
CN_ANCHOR_PTR aNode1,
CN_ANCHOR_PTR aNode2 
) 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 390 of file ratsnest_data.cpp.

392 {
393  bool rv = false;
394 
395  SEG::ecoord distMax_sq = VECTOR2I::ECOORD_MAX;
396 
397  auto verify =
398  [&]( const std::shared_ptr<CN_ANCHOR>& aTestNode1,
399  const std::shared_ptr<CN_ANCHOR>& aTestNode2 )
400  {
401  VECTOR2I diff = aTestNode1->Pos() - aTestNode2->Pos();
402  SEG::ecoord dist_sq = diff.SquaredEuclideanNorm();
403 
404  if( dist_sq < distMax_sq )
405  {
406  rv = true;
407  distMax_sq = dist_sq;
408  aNode1 = aTestNode1;
409  aNode2 = aTestNode2;
410  }
411  };
412 
416  for( const std::shared_ptr<CN_ANCHOR>& nodeA : aOtherNet.m_nodes )
417  {
418  if( nodeA->GetNoLine() )
419  continue;
420 
424  auto fwd_it = m_nodes.lower_bound( nodeA );
425  auto rev_it = std::make_reverse_iterator( fwd_it );
426 
427  for( ; fwd_it != m_nodes.end(); ++fwd_it )
428  {
429  const std::shared_ptr<CN_ANCHOR>& nodeB = *fwd_it;
430 
431  if( nodeB->GetNoLine() )
432  continue;
433 
434  SEG::ecoord distX_sq = SEG::Square( nodeA->Pos().x - nodeB->Pos().x );
435 
438  if( distX_sq > distMax_sq )
439  break;
440 
441  verify( nodeA, nodeB );
442  }
443 
445  for( ; rev_it != m_nodes.rend(); ++rev_it )
446  {
447  const std::shared_ptr<CN_ANCHOR>& nodeB = *rev_it;
448 
449  if( nodeB->GetNoLine() )
450  continue;
451 
452  SEG::ecoord distX_sq = SEG::Square( nodeA->Pos().x - nodeB->Pos().x );
453 
454  if( distX_sq > distMax_sq )
455  break;
456 
457  verify( nodeA, nodeB );
458  }
459  }
460 
461  return rv;
462 }
VECTOR2I::extended_type ecoord
Definition: seg.h:43
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 SEG::ecoord Square(int a)
Definition: seg.h:122
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:79
std::multiset< CN_ANCHOR_PTR, CN_PTR_CMP > m_nodes
Vector of edges that make pre-defined connections.

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

Referenced by CONNECTIVITY_DATA::ComputeDynamicRatsnest().

◆ SetVisible()

void RN_NET::SetVisible ( bool  aEnabled)

Set state of the visibility flag.

Parameters
aEnabledis new state. True if ratsnest for a given net is meant to be displayed, false otherwise.

Definition at line 465 of file ratsnest_data.cpp.

466 {
467  for( CN_EDGE& edge : m_rnEdges )
468  edge.SetVisible( aEnabled );
469 }
std::vector< CN_EDGE > m_rnEdges
Flag indicating necessity of recalculation of ratsnest for a net.
CN_EDGE represents a point-to-point connection, whether realized or unrealized (ie: tracks etc.

References m_rnEdges.

◆ Update()

void RN_NET::Update ( )

Recompute ratsnest for a net.

Definition at line 340 of file ratsnest_data.cpp.

341 {
342  compute();
343 
344  m_dirty = false;
345 }
bool m_dirty
void compute()
< Recompute ratsnest from scratch.

References compute(), and m_dirty.

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 118 of file ratsnest_data.h.

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

◆ m_dirty

bool RN_NET::m_dirty
protected

Definition at line 124 of file ratsnest_data.h.

Referenced by Clear(), IsDirty(), MarkDirty(), and Update().

◆ m_nodes

std::multiset<CN_ANCHOR_PTR, CN_PTR_CMP> RN_NET::m_nodes
protected

Vector of edges that make pre-defined connections.

Definition at line 115 of file ratsnest_data.h.

Referenced by AddCluster(), Clear(), compute(), GetNodeCount(), 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 121 of file ratsnest_data.h.

Referenced by Clear(), compute(), GetEdges(), GetUnconnected(), and SetVisible().

◆ m_triangulator

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

Definition at line 126 of file ratsnest_data.h.

Referenced by compute(), and RN_NET().


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