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>
#include <connectivity_algo.h>

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

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

50 {
51  double dx = ( aNode1->Pos().x - aNode2->Pos().x );
52  double dy = ( aNode1->Pos().y - aNode2->Pos().y );
53 
54  return sqrt( dx * dx + dy * dy );
55 }
static const std::vector<CN_EDGE> kruskalMST ( std::list< CN_EDGE > &  aEdges,
std::vector< CN_ANCHOR_PTR > &  aNodes 
)
static

Definition at line 64 of file ratsnest_data.cpp.

References sortWeight().

Referenced by RN_NET::compute().

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

Definition at line 58 of file ratsnest_data.cpp.

References CN_EDGE::GetWeight().

Referenced by kruskalMST().

59 {
60  return aEdge1.GetWeight() < aEdge2.GetWeight();
61 }
int GetWeight() const