KiCad PCB EDA Suite
ratsnest_data.cpp File Reference

Class that computes missing connections on a PCB. More...

#include <ratsnest_data.h>
#include <functional>
#include <cassert>
#include <algorithm>
#include <limits>

Go to the source code of this file.

Classes

class  RN_NET::TRIANGULATOR_STATE
 

Functions

static uint64_t getDistance (const CN_ANCHOR_PTR &aNode1, const CN_ANCHOR_PTR &aNode2)
 
static bool sortWeight (const CN_EDGE &aEdge1, const CN_EDGE &aEdge2)
 
static const std::vector< CN_EDGEkruskalMST (std::list< CN_EDGE > &aEdges, std::vector< CN_ANCHOR_PTR > &aNodes)
 

Detailed Description

Class that computes missing connections on a PCB.

Definition in file ratsnest_data.cpp.

Function Documentation

static uint64_t getDistance ( const CN_ANCHOR_PTR aNode1,
const CN_ANCHOR_PTR aNode2 
)
static

Definition at line 43 of file ratsnest_data.cpp.

Referenced by RN_NET::TRIANGULATOR_STATE::Triangulate().

44 {
45  double dx = ( aNode1->Pos().x - aNode2->Pos().x );
46  double dy = ( aNode1->Pos().y - aNode2->Pos().y );
47 
48  return sqrt( dx * dx + dy * dy );
49 }
static const std::vector<CN_EDGE> kruskalMST ( std::list< CN_EDGE > &  aEdges,
std::vector< CN_ANCHOR_PTR > &  aNodes 
)
static

Definition at line 58 of file ratsnest_data.cpp.

References i, and sortWeight().

Referenced by RN_NET::compute().

60 {
61  unsigned int nodeNumber = aNodes.size();
62  unsigned int mstExpectedSize = nodeNumber - 1;
63  unsigned int mstSize = 0;
64  bool ratsnestLines = false;
65 
66  // The output
67  std::vector<CN_EDGE> mst;
68 
69  // Set tags for marking cycles
70  std::unordered_map<CN_ANCHOR_PTR, int> tags;
71  unsigned int tag = 0;
72 
73  for( auto& node : aNodes )
74  {
75  node->SetTag( tag );
76  tags[node] = tag++;
77  }
78 
79  // Lists of nodes connected together (subtrees) to detect cycles in the graph
80  std::vector<std::list<int> > cycles( nodeNumber );
81 
82  for( unsigned int i = 0; i < nodeNumber; ++i )
83  cycles[i].push_back( i );
84 
85  // Kruskal algorithm requires edges to be sorted by their weight
86  aEdges.sort( sortWeight );
87 
88  while( mstSize < mstExpectedSize && !aEdges.empty() )
89  {
90  //printf("mstSize %d %d\n", mstSize, mstExpectedSize);
91  auto& dt = aEdges.front();
92 
93  int srcTag = tags[dt.GetSourceNode()];
94  int trgTag = tags[dt.GetTargetNode()];
95 
96  // Check if by adding this edge we are going to join two different forests
97  if( srcTag != trgTag )
98  {
99  // Because edges are sorted by their weight, first we always process connected
100  // items (weight == 0). Once we stumble upon an edge with non-zero weight,
101  // it means that the rest of the lines are ratsnest.
102  if( !ratsnestLines && dt.GetWeight() != 0 )
103  ratsnestLines = true;
104 
105  // Update tags
106  if( ratsnestLines )
107  {
108  for( auto it = cycles[trgTag].begin(); it != cycles[trgTag].end(); ++it )
109  {
110  tags[aNodes[*it]] = srcTag;
111  }
112 
113  // Do a copy of edge, but make it RN_EDGE_MST. In contrary to RN_EDGE,
114  // RN_EDGE_MST saves both source and target node and does not require any other
115  // edges to exist for getting source/target nodes
116  CN_EDGE newEdge ( dt.GetSourceNode(), dt.GetTargetNode(), dt.GetWeight() );
117 
118  assert( newEdge.GetSourceNode()->GetTag() != newEdge.GetTargetNode()->GetTag() );
119  assert( newEdge.GetWeight() > 0 );
120 
121  mst.push_back( newEdge );
122  ++mstSize;
123  }
124  else
125  {
126  // for( it = cycles[trgTag].begin(), itEnd = cycles[trgTag].end(); it != itEnd; ++it )
127  // for( auto it : cycles[trgTag] )
128  for( auto it = cycles[trgTag].begin(); it != cycles[trgTag].end(); ++it )
129  {
130  tags[aNodes[*it]] = srcTag;
131  aNodes[*it]->SetTag( srcTag );
132  }
133 
134  // Processing a connection, decrease the expected size of the ratsnest MST
135  --mstExpectedSize;
136  }
137 
138  // Move nodes that were marked with old tag to the list marked with the new tag
139  cycles[srcTag].splice( cycles[srcTag].end(), cycles[trgTag] );
140  }
141 
142  // Remove the edge that was just processed
143  aEdges.erase( aEdges.begin() );
144  }
145 
146  // Probably we have discarded some of edges, so reduce the size
147  mst.resize( mstSize );
148 
149  return mst;
150 }
static bool sortWeight(const CN_EDGE &aEdge1, const CN_EDGE &aEdge2)
size_t i
Definition: json11.cpp:597
static bool sortWeight ( const CN_EDGE aEdge1,
const CN_EDGE aEdge2 
)
static

Definition at line 52 of file ratsnest_data.cpp.

References CN_EDGE::GetWeight().

Referenced by kruskalMST().

53 {
54  return aEdge1.GetWeight() < aEdge2.GetWeight();
55 }
int GetWeight() const