KiCad PCB EDA Suite
ratsnest_data.cpp File Reference

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

#include <ratsnest_data.h>
#include <class_board.h>
#include <class_module.h>
#include <class_pad.h>
#include <class_track.h>
#include <class_zone.h>
#include <functional>
#include <geometry/shape_poly_set.h>
#include <cassert>
#include <algorithm>
#include <limits>

Go to the source code of this file.

Functions

static uint64_t getDistance (const RN_NODE_PTR &aNode1, const RN_NODE_PTR &aNode2)
 
static bool sortDistance (const RN_NODE_PTR &aOrigin, const RN_NODE_PTR &aNode1, const RN_NODE_PTR &aNode2)
 
static bool sortWeight (const RN_EDGE_PTR &aEdge1, const RN_EDGE_PTR &aEdge2)
 
bool sortArea (const RN_POLY &aP1, const RN_POLY &aP2)
 
bool operator== (const RN_NODE_PTR &aFirst, const RN_NODE_PTR &aSecond)
 
bool operator!= (const RN_NODE_PTR &aFirst, const RN_NODE_PTR &aSecond)
 
RN_NODE_AND_FILTER operator&& (const RN_NODE_FILTER &aFilter1, const RN_NODE_FILTER &aFilter2)
 
RN_NODE_OR_FILTER operator|| (const RN_NODE_FILTER &aFilter1, const RN_NODE_FILTER &aFilter2)
 
static bool isEdgeConnectingNode (const RN_EDGE_PTR &aEdge, const RN_NODE_PTR &aNode)
 
static std::vector< RN_EDGE_MST_PTR > * kruskalMST (RN_LINKS::RN_EDGE_LIST &aEdges, std::vector< RN_NODE_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 RN_NODE_PTR aNode1,
const RN_NODE_PTR aNode2 
)
static

Definition at line 56 of file ratsnest_data.cpp.

Referenced by RN_NET::compute(), RN_NET::GetClosestNode(), and sortDistance().

57 {
58  // Drop the least significant bits to avoid overflow
59  int64_t x = ( aNode1->GetX() - aNode2->GetX() ) >> 16;
60  int64_t y = ( aNode1->GetY() - aNode2->GetY() ) >> 16;
61 
62  // We do not need sqrt() here, as the distance is computed only for comparison
63  return ( x * x + y * y );
64 }
static bool isEdgeConnectingNode ( const RN_EDGE_PTR aEdge,
const RN_NODE_PTR aNode 
)
static

Definition at line 110 of file ratsnest_data.cpp.

Referenced by RN_NET::clearNode().

111 {
112  return aEdge->GetSourceNode() == aNode || aEdge->GetTargetNode() == aNode;
113 }
static std::vector<RN_EDGE_MST_PTR>* kruskalMST ( RN_LINKS::RN_EDGE_LIST aEdges,
std::vector< RN_NODE_PTR > &  aNodes 
)
static

Definition at line 116 of file ratsnest_data.cpp.

References sortWeight().

Referenced by RN_NET::compute().

118 {
119  unsigned int nodeNumber = aNodes.size();
120  unsigned int mstExpectedSize = nodeNumber - 1;
121  unsigned int mstSize = 0;
122  bool ratsnestLines = false;
123 
124  // The output
125  std::vector<RN_EDGE_MST_PTR>* mst = new std::vector<RN_EDGE_MST_PTR>;
126  mst->reserve( mstExpectedSize );
127 
128  // Set tags for marking cycles
129  std::unordered_map<RN_NODE_PTR, int> tags;
130  unsigned int tag = 0;
131 
132  for( RN_NODE_PTR& node : aNodes )
133  {
134  node->SetTag( tag );
135  tags[node] = tag++;
136  }
137 
138  // Lists of nodes connected together (subtrees) to detect cycles in the graph
139  std::vector<std::list<int> > cycles( nodeNumber );
140  for( unsigned int i = 0; i < nodeNumber; ++i )
141  cycles[i].push_back( i );
142 
143  // Kruskal algorithm requires edges to be sorted by their weight
144  aEdges.sort( sortWeight );
145 
146  while( mstSize < mstExpectedSize && !aEdges.empty() )
147  {
148  RN_EDGE_PTR& dt = aEdges.front();
149 
150  int srcTag = tags[dt->GetSourceNode()];
151  int trgTag = tags[dt->GetTargetNode()];
152 
153  // Check if by adding this edge we are going to join two different forests
154  if( srcTag != trgTag )
155  {
156  // Because edges are sorted by their weight, first we always process connected
157  // items (weight == 0). Once we stumble upon an edge with non-zero weight,
158  // it means that the rest of the lines are ratsnest.
159  if( !ratsnestLines && dt->GetWeight() != 0 )
160  ratsnestLines = true;
161 
162  // Update tags
163  if( ratsnestLines )
164  {
165  for( auto it = cycles[trgTag].begin(); it != cycles[trgTag].end(); ++it )
166  {
167  tags[aNodes[*it]] = srcTag;
168  }
169  // Do a copy of edge, but make it RN_EDGE_MST. In contrary to RN_EDGE,
170  // RN_EDGE_MST saves both source and target node and does not require any other
171  // edges to exist for getting source/target nodes
172  RN_EDGE_MST_PTR newEdge = std::make_shared<RN_EDGE_MST>( dt->GetSourceNode(),
173  dt->GetTargetNode(),
174  dt->GetWeight() );
175 
176  assert( newEdge->GetSourceNode()->GetTag() != newEdge->GetTargetNode()->GetTag() );
177  assert( newEdge->GetWeight() > 0 );
178 
179  mst->push_back( newEdge );
180  ++mstSize;
181  }
182  else
183  {
184  //for( it = cycles[trgTag].begin(), itEnd = cycles[trgTag].end(); it != itEnd; ++it )
185  //for( auto it : cycles[trgTag] )
186  for( auto it = cycles[trgTag].begin(); it != cycles[trgTag].end(); ++it )
187  {
188  tags[aNodes[*it]] = srcTag;
189  aNodes[*it]->SetTag( srcTag );
190  }
191 
192  // Processing a connection, decrease the expected size of the ratsnest MST
193  --mstExpectedSize;
194  }
195 
196  // Move nodes that were marked with old tag to the list marked with the new tag
197  cycles[srcTag].splice( cycles[srcTag].end(), cycles[trgTag] );
198  }
199 
200  // Remove the edge that was just processed
201  aEdges.erase( aEdges.begin() );
202  }
203 
204  // Probably we have discarded some of edges, so reduce the size
205  mst->resize( mstSize );
206 
207  return mst;
208 }
hed::EDGE_PTR RN_EDGE_PTR
Definition: ratsnest_data.h:66
hed::NODE_PTR RN_NODE_PTR
Definition: ratsnest_data.h:64
static bool sortWeight(const RN_EDGE_PTR &aEdge1, const RN_EDGE_PTR &aEdge2)
std::shared_ptr< hed::EDGE_MST > RN_EDGE_MST_PTR
Definition: ratsnest_data.h:69
bool operator!= ( const RN_NODE_PTR aFirst,
const RN_NODE_PTR aSecond 
)

Definition at line 92 of file ratsnest_data.cpp.

93 {
94  return aFirst->GetX() != aSecond->GetX() || aFirst->GetY() != aSecond->GetY();
95 }
RN_NODE_AND_FILTER operator&& ( const RN_NODE_FILTER aFilter1,
const RN_NODE_FILTER aFilter2 
)

Definition at line 98 of file ratsnest_data.cpp.

99 {
100  return RN_NODE_AND_FILTER( aFilter1, aFilter2 );
101 }
bool operator== ( const RN_NODE_PTR aFirst,
const RN_NODE_PTR aSecond 
)

Definition at line 86 of file ratsnest_data.cpp.

87 {
88  return aFirst->GetX() == aSecond->GetX() && aFirst->GetY() == aSecond->GetY();
89 }
RN_NODE_OR_FILTER operator|| ( const RN_NODE_FILTER aFilter1,
const RN_NODE_FILTER aFilter2 
)

Definition at line 104 of file ratsnest_data.cpp.

105 {
106  return RN_NODE_OR_FILTER( aFilter1, aFilter2 );
107 }
bool sortArea ( const RN_POLY aP1,
const RN_POLY aP2 
)

Definition at line 80 of file ratsnest_data.cpp.

References BOX2< Vec >::GetArea(), and RN_POLY::m_bbox.

Referenced by RN_NET::processZones().

81 {
82  return aP1.m_bbox.GetArea() < aP2.m_bbox.GetArea();
83 }
ecoord_type GetArea() const
Function GetArea returns the area of the rectangle.
Definition: box2.h:391
BOX2I m_bbox
Bounding box of the polygon.
static bool sortDistance ( const RN_NODE_PTR aOrigin,
const RN_NODE_PTR aNode1,
const RN_NODE_PTR aNode2 
)
static

Definition at line 67 of file ratsnest_data.cpp.

References getDistance().

Referenced by RN_NET::GetClosestNodes().

69 {
70  return getDistance( aOrigin, aNode1 ) < getDistance( aOrigin, aNode2 );
71 }
static uint64_t getDistance(const RN_NODE_PTR &aNode1, const RN_NODE_PTR &aNode2)
static bool sortWeight ( const RN_EDGE_PTR aEdge1,
const RN_EDGE_PTR aEdge2 
)
static

Definition at line 74 of file ratsnest_data.cpp.

Referenced by kruskalMST().

75 {
76  return aEdge1->GetWeight() < aEdge2->GetWeight();
77 }