KiCad PCB EDA Suite
RN_NET Class Reference

RN_NET Describes ratsnest for a single net. More...

#include <ratsnest_data.h>

Classes

class  TRIANGULATOR_STATE
 

Public Member Functions

 RN_NET ()
 

Default constructor.

More...
 
void SetVisible (bool aEnabled)
 Function SetVisible() Sets state of the visibility flag. More...
 
void MarkDirty ()
 Function MarkDirty() Marks ratsnest for given net as 'dirty', i.e. More...
 
bool IsDirty () const
 Function IsDirty() Returns 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
 Function GetUnconnected() Returns pointer to a vector of edges that makes ratsnest for a given net. More...
 
void Update ()
 Function Update() Recomputes ratsnest for a net. More...
 
void Clear ()
 
void AddCluster (std::shared_ptr< CN_CLUSTER > aCluster)
 
unsigned int GetNodeCount () const
 
std::list< CN_ANCHOR_PTRGetNodes (const BOARD_CONNECTED_ITEM *aItem) const
 Function GetNodes() Returns list of nodes that are associated with a given item. More...
 
const std::vector< CN_EDGE > & GetEdges () const
 
void GetAllItems (std::list< BOARD_CONNECTED_ITEM * > &aOutput, const KICAD_T aTypes[]) const
 Function GetAllItems() Adds all stored items to a list. More...
 
const CN_ANCHOR_PTR GetClosestNode (const CN_ANCHOR_PTR &aNode) const
 Function GetClosestNode() Returns a single node that lies in the shortest distance from a specific node. More...
 
bool NearestBicoloredPair (const RN_NET &aOtherNet, CN_ANCHOR_PTR &aNode1, CN_ANCHOR_PTR &aNode2) const
 

Protected Member Functions

void compute ()
 

Recomputes ratsnest from scratch.

More...
 
void kruskalMST (const std::vector< CN_EDGE > &aEdges)
 

Compute the minimum spanning tree using Kruskal's algorithm

More...
 

Protected Attributes

std::multiset< CN_ANCHOR_PTR, CN_PTR_CMPm_nodes
 

Vector of nodes

More...
 
std::vector< CN_EDGEm_boardEdges
 

Vector of edges that make pre-defined connections

More...
 
std::vector< CN_EDGEm_rnEdges
 

Vector of edges that makes ratsnest for a given net.

More...
 
bool m_dirty
 

Flag indicating necessity of recalculation of ratsnest for a net.

More...
 
std::shared_ptr< TRIANGULATOR_STATEm_triangulator
 

Detailed Description

RN_NET Describes ratsnest for a single net.

Definition at line 61 of file ratsnest_data.h.

Constructor & Destructor Documentation

◆ RN_NET()

RN_NET::RN_NET ( )

Default constructor.

Definition at line 271 of file ratsnest_data.cpp.

271  : m_dirty( true )
272 {
273  m_triangulator.reset( new TRIANGULATOR_STATE );
274 }
bool m_dirty
Flag indicating necessity of recalculation of ratsnest for a net.
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 361 of file ratsnest_data.cpp.

362 {
363  CN_ANCHOR_PTR firstAnchor;
364 
365  for( auto item : *aCluster )
366  {
367  bool isZone = dynamic_cast<CN_ZONE*>(item) != nullptr;
368  auto& anchors = item->Anchors();
369  unsigned int nAnchors = isZone ? 1 : anchors.size();
370 
371  if( nAnchors > anchors.size() )
372  nAnchors = anchors.size();
373 
374  for( unsigned int i = 0; i < nAnchors; i++ )
375  {
376  anchors[i]->SetCluster( aCluster );
377  m_nodes.insert( anchors[i] );
378 
379  if( firstAnchor )
380  {
381  if( firstAnchor != anchors[i] )
382  {
383  m_boardEdges.emplace_back( firstAnchor, anchors[i], 0 );
384  }
385  }
386  else
387  {
388  firstAnchor = anchors[i];
389  }
390  }
391  }
392 }
std::vector< CN_EDGE > m_boardEdges
Vector of edges that make pre-defined connections
std::shared_ptr< CN_ANCHOR > CN_ANCHOR_PTR
std::multiset< CN_ANCHOR_PTR, CN_PTR_CMP > m_nodes
Vector of nodes

References m_boardEdges, and m_nodes.

◆ Clear()

void RN_NET::Clear ( )

Definition at line 351 of file ratsnest_data.cpp.

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

References m_boardEdges, m_dirty, m_nodes, and m_rnEdges.

◆ compute()

void RN_NET::compute ( )
protected

Recomputes ratsnest from scratch.

Definition at line 277 of file ratsnest_data.cpp.

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

◆ GetAllItems()

void RN_NET::GetAllItems ( std::list< BOARD_CONNECTED_ITEM * > &  aOutput,
const KICAD_T  aTypes[] 
) const

Function GetAllItems() Adds all stored items to a list.

Parameters
aOutputis the list that will have items added.
aTypesdetermines the type of added items.

◆ GetClosestNode()

const CN_ANCHOR_PTR RN_NET::GetClosestNode ( const CN_ANCHOR_PTR aNode) const

Function GetClosestNode() Returns a single node that lies in the shortest distance from a specific node.

Parameters
aNodeis the node for which the closest node is searched.

◆ GetEdges()

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

Definition at line 127 of file ratsnest_data.h.

128  {
129  return m_rnEdges;
130  }
std::vector< CN_EDGE > m_rnEdges
Vector of edges that makes ratsnest for a given net.

References m_rnEdges.

◆ GetNodeCount()

unsigned int RN_NET::GetNodeCount ( ) const
inline

Definition at line 114 of file ratsnest_data.h.

115  {
116  return m_nodes.size();
117  }
std::multiset< CN_ANCHOR_PTR, CN_PTR_CMP > m_nodes
Vector of nodes

References m_nodes.

◆ GetNodes()

std::list<CN_ANCHOR_PTR> RN_NET::GetNodes ( const BOARD_CONNECTED_ITEM aItem) const

Function GetNodes() Returns list of nodes that are associated with a given item.

Parameters
aItemis an item for which the list is generated.
Returns
List of associated nodes.

◆ GetUnconnected()

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

Function GetUnconnected() Returns pointer to a vector of edges that makes ratsnest for a given net.

Returns
Pointer to a vector of edges that makes ratsnest for a given net.

Definition at line 100 of file ratsnest_data.h.

101  {
102  return m_rnEdges;
103  }
std::vector< CN_EDGE > m_rnEdges
Vector of edges that makes ratsnest for a given net.

References m_rnEdges.

Referenced by KIGFX::RATSNEST_VIEWITEM::ViewDraw().

◆ IsDirty()

bool RN_NET::IsDirty ( ) const
inline

Function IsDirty() Returns 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 90 of file ratsnest_data.h.

91  {
92  return m_dirty;
93  }
bool m_dirty
Flag indicating necessity of recalculation of ratsnest for a net.

References m_dirty.

◆ kruskalMST()

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

Compute the minimum spanning tree using Kruskal's algorithm

Definition at line 109 of file ratsnest_data.cpp.

110 {
111  disjoint_set dset( m_nodes.size() );
112 
113  m_rnEdges.clear();
114 
115  int i = 0;
116 
117  for( auto& node : m_nodes )
118  node->SetTag( i++ );
119 
120  for( auto& tmp : aEdges )
121  {
122  int u = tmp.GetSourceNode()->GetTag();
123  int v = tmp.GetTargetNode()->GetTag();
124 
125  if( dset.unite( u, v ) )
126  {
127  if( tmp.GetWeight() > 0 )
128  m_rnEdges.push_back( tmp );
129  }
130  }
131 }
std::vector< CN_EDGE > m_rnEdges
Vector of edges that makes ratsnest for a given net.
std::multiset< CN_ANCHOR_PTR, CN_PTR_CMP > m_nodes
Vector of nodes

Referenced by compute().

◆ MarkDirty()

void RN_NET::MarkDirty ( )
inline

Function MarkDirty() Marks ratsnest for given net as 'dirty', i.e.

requiring recomputation.

Definition at line 79 of file ratsnest_data.h.

80  {
81  m_dirty = true;
82  }
bool m_dirty
Flag indicating necessity of recalculation of ratsnest for a net.

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

397 {
398  bool rv = false;
399 
401 
402  auto verify = [&]( auto& aTestNode1, auto& aTestNode2 )
403  {
404  auto squaredDist = ( aTestNode1->Pos() - aTestNode2->Pos() ).SquaredEuclideanNorm();
405 
406  if( squaredDist < distMax )
407  {
408  rv = true;
409  distMax = squaredDist;
410  aNode1 = aTestNode1;
411  aNode2 = aTestNode2;
412  }
413  };
414 
418  for( const auto& nodeA : aOtherNet.m_nodes )
419  {
420  if( nodeA->GetNoLine() )
421  continue;
422 
426  auto fwd_it = m_nodes.lower_bound( nodeA );
427  auto rev_it = std::make_reverse_iterator( fwd_it );
428 
429  for( ; fwd_it != m_nodes.end(); ++fwd_it )
430  {
431  auto nodeB = *fwd_it;
432 
433  if( nodeB->GetNoLine() )
434  continue;
435 
436  VECTOR2I::extended_type distX = nodeA->Pos().x - nodeB->Pos().x;
437 
440  if( distX * distX > distMax )
441  break;
442 
443  verify( nodeA, nodeB );
444  }
445 
447  if( rev_it != m_nodes.rend() )
448  ++rev_it;
449 
450  for( ; rev_it != m_nodes.rend(); ++rev_it )
451  {
452  auto nodeB = *rev_it;
453 
454  if( nodeB->GetNoLine() )
455  continue;
456 
457  VECTOR2I::extended_type distX = nodeA->Pos().x - nodeB->Pos().x;
458 
459  if( distX * distX > distMax )
460  break;
461 
462  verify( nodeA, nodeB );
463  }
464  }
465 
466  return rv;
467 }
VECTOR2_TRAITS< int >::extended_type extended_type
Definition: vector2d.h:77
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:80
std::multiset< CN_ANCHOR_PTR, CN_PTR_CMP > m_nodes
Vector of nodes

References VECTOR2< T >::ECOORD_MAX, and m_nodes.

◆ SetVisible()

void RN_NET::SetVisible ( bool  aEnabled)

Function SetVisible() Sets 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 470 of file ratsnest_data.cpp.

471 {
472  for( auto& edge : m_rnEdges )
473  edge.SetVisible( aEnabled );
474 }
std::vector< CN_EDGE > m_rnEdges
Vector of edges that makes ratsnest for a given net.

References m_rnEdges.

◆ Update()

void RN_NET::Update ( )

Function Update() Recomputes ratsnest for a net.

Definition at line 343 of file ratsnest_data.cpp.

344 {
345  compute();
346 
347  m_dirty = false;
348 }
bool m_dirty
Flag indicating necessity of recalculation of ratsnest for a net.
void compute()
Recomputes 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 make pre-defined connections

Definition at line 160 of file ratsnest_data.h.

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

◆ m_dirty

bool RN_NET::m_dirty
protected

Flag indicating necessity of recalculation of ratsnest for a net.

Definition at line 166 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 nodes

Definition at line 157 of file ratsnest_data.h.

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

◆ m_rnEdges

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

Vector of edges that makes ratsnest for a given net.

Definition at line 163 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 168 of file ratsnest_data.h.

Referenced by compute(), and RN_NET().


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