37 using namespace std::placeholders;
45 double dx = ( aNode1->Pos().x - aNode2->Pos().x );
46 double dy = ( aNode1->Pos().y - aNode2->Pos().y );
48 return sqrt( dx * dx + dy * dy );
58 static const std::vector<CN_EDGE>
kruskalMST( std::list<CN_EDGE>& aEdges,
59 std::vector<CN_ANCHOR_PTR>& aNodes )
61 unsigned int nodeNumber = aNodes.size();
62 unsigned int mstExpectedSize = nodeNumber - 1;
63 unsigned int mstSize = 0;
64 bool ratsnestLines =
false;
67 std::vector<CN_EDGE> mst;
70 std::unordered_map<CN_ANCHOR_PTR, int> tags;
73 for(
auto& node : aNodes )
80 std::vector<std::list<int> > cycles( nodeNumber );
82 for(
unsigned int i = 0;
i < nodeNumber; ++
i )
83 cycles[
i].push_back(
i );
88 while( mstSize < mstExpectedSize && !aEdges.empty() )
91 auto& dt = aEdges.front();
93 int srcTag = tags[dt.GetSourceNode()];
94 int trgTag = tags[dt.GetTargetNode()];
97 if( srcTag != trgTag )
102 if( !ratsnestLines && dt.GetWeight() != 0 )
103 ratsnestLines =
true;
108 for(
auto it = cycles[trgTag].begin(); it != cycles[trgTag].end(); ++it )
110 tags[aNodes[*it]] = srcTag;
116 CN_EDGE newEdge ( dt.GetSourceNode(), dt.GetTargetNode(), dt.GetWeight() );
118 assert( newEdge.GetSourceNode()->GetTag() != newEdge.GetTargetNode()->GetTag() );
119 assert( newEdge.GetWeight() > 0 );
121 mst.push_back( newEdge );
128 for(
auto it = cycles[trgTag].begin(); it != cycles[trgTag].end(); ++it )
130 tags[aNodes[*it]] = srcTag;
131 aNodes[*it]->SetTag( srcTag );
139 cycles[srcTag].splice( cycles[srcTag].end(), cycles[trgTag] );
143 aEdges.erase( aEdges.begin() );
147 mst.resize( mstSize );
162 std::list<hed::EDGE_PTR> edges;
173 if ( aNodes.size() <= 2 )
176 const auto p0 = aNodes[0]->Pos();
177 const auto v0 = aNodes[1]->Pos() - p0;
179 for(
unsigned i = 2;
i < aNodes.size();
i++ )
181 const auto v1 = aNodes[
i]->Pos() - p0;
183 if( v0.Cross( v1 ) != 0 )
201 m_allNodes.push_back( aNode );
206 std::list<CN_EDGE> mstEdges;
207 std::list<hed::EDGE_PTR> triangEdges;
208 std::vector<hed::NODE_PTR> triNodes;
210 using ANCHOR_LIST = std::vector<CN_ANCHOR_PTR>;
211 std::vector<ANCHOR_LIST> anchorChains;
213 triNodes.reserve( m_allNodes.size() );
214 anchorChains.reserve( m_allNodes.size() );
216 std::sort( m_allNodes.begin(), m_allNodes.end(),
219 if( aNode1->Pos().y < aNode2->Pos().y )
221 else if( aNode1->Pos().y == aNode2->Pos().y )
223 return aNode1->Pos().x < aNode2->Pos().x;
233 for(
auto n : m_allNodes )
235 anchorChains.push_back( ANCHOR_LIST() );
238 for(
auto n : m_allNodes )
240 if( !prev || prev->Pos() != n->Pos() )
242 auto tn = std::make_shared<hed::NODE> ( n->Pos().x, n->Pos().y );
245 triNodes.push_back( tn );
254 for(
auto n : triNodes )
256 for(
int i = prevId;
i < n->Id();
i++ )
257 anchorChains[prevId].push_back( m_allNodes[
i ] );
262 for(
int i = prevId;
i < id;
i++ )
263 anchorChains[prevId].push_back( m_allNodes[
i ] );
265 if( triNodes.size() == 1 )
269 else if( areNodesColinear( triNodes ) )
274 for(
int i = 0;
i < (int)triNodes.size() - 1;
i++ )
276 auto src = m_allNodes[ triNodes[
i]->Id() ];
277 auto dst = m_allNodes[ triNodes[
i + 1]->Id() ];
278 mstEdges.emplace_back( src, dst,
getDistance( src, dst ) );
285 triangulator.
GetEdges( triangEdges );
287 for(
auto e : triangEdges )
289 auto src = m_allNodes[ e->GetSourceNode()->Id() ];
290 auto dst = m_allNodes[ e->GetTargetNode()->Id() ];
292 mstEdges.emplace_back( src, dst,
getDistance( src, dst ) );
296 for(
unsigned int i = 0;
i < anchorChains.size();
i++ )
298 auto& chain = anchorChains[
i];
300 if( chain.size() < 2 )
303 std::sort( chain.begin(), chain.end(),
305 return a->GetCluster().get() < b->GetCluster().get();
308 for(
unsigned int j = 1; j < chain.size(); j++ )
310 const auto& prevNode = chain[j - 1];
311 const auto& curNode = chain[j];
312 int weight = prevNode->GetCluster() != curNode->GetCluster() ? 1 : 0;
313 mstEdges.push_back(
CN_EDGE ( prevNode, curNode, weight ) );
344 edge.GetTargetNode()->SetTag( 1 );
375 triangEdges.push_back( e );
411 for(
auto item : *aCluster )
413 bool isZone = dynamic_cast<CN_ZONE*>(item) !=
nullptr;
414 auto& anchors = item->Anchors();
415 unsigned int nAnchors = isZone ? 1 : anchors.size();
417 if( nAnchors > anchors.size() )
418 nAnchors = anchors.size();
420 for(
unsigned int i = 0;
i < nAnchors;
i++ )
422 anchors[
i]->SetCluster( aCluster );
427 if( firstAnchor != anchors[
i] )
434 firstAnchor = anchors[
i];
450 for(
auto nodeB : aOtherNet.
m_nodes )
452 if( !nodeA->GetNoLine() )
454 auto squaredDist = (nodeA->Pos() - nodeB->Pos() ).SquaredEuclideanNorm();
456 if( squaredDist < distMax )
459 distMax = squaredDist;
474 edge.SetVisible( aEnabled );
std::vector< CN_ANCHOR_PTR > m_allNodes
VECTOR2_TRAITS< int >::extended_type extended_type
void Update()
Function Update() Recomputes ratsnest for a net.
const std::list< CN_EDGE > Triangulate()
static bool sortWeight(const CN_EDGE &aEdge1, const CN_EDGE &aEdge2)
bool m_dirty
Flag indicating necessity of recalculation of ratsnest for a net.
Class that computes missing connections on a PCB.
std::vector< CN_EDGE > m_rnEdges
Vector of edges that makes ratsnest for a given net.
void compute()
Recomputes ratsnest from scratch.
The class PROF_COUNTER is a small class to help profiling.
std::vector< CN_ANCHOR_PTR > m_nodes
Vector of nodes
void GetEdges(std::list< EDGE_PTR > &aEdges, bool aSkipBoundaryEdges=false) const
Returns a list of half-edges (one half-edge for each arc)
void AddNode(CN_ANCHOR_PTR aNode)
static constexpr extended_type ECOORD_MAX
RN_NET()
Default constructor.
std::list< hed::EDGE_PTR > hedTriangulation(std::vector< hed::NODE_PTR > &aNodes)
static const std::vector< CN_EDGE > kruskalMST(std::list< CN_EDGE > &aEdges, std::vector< CN_ANCHOR_PTR > &aNodes)
void SetVisible(bool aEnabled)
Function SetVisible() Sets state of the visibility flag.
bool NearestBicoloredPair(const RN_NET &aOtherNet, CN_ANCHOR_PTR &aNode1, CN_ANCHOR_PTR &aNode2) const
void AddCluster(std::shared_ptr< CN_CLUSTER > aCluster)
void CreateDelaunay(NODES_CONTAINER::iterator aFirst, NODES_CONTAINER::iterator aLast)
Creates a Delaunay triangulation from a set of points.
std::shared_ptr< TRIANGULATOR_STATE > m_triangulator
std::vector< CN_EDGE > m_boardEdges
Vector of edges that make pre-defined connections
std::shared_ptr< CN_CLUSTER > CN_CLUSTER_PTR
std::shared_ptr< CN_ANCHOR > CN_ANCHOR_PTR
Class RN_NET Describes ratsnest for a single net.
void Show(std::ostream &aStream=std::cerr)
Print the elapsed time (in a suitable unit) to a stream.
static uint64_t getDistance(const CN_ANCHOR_PTR &aNode1, const CN_ANCHOR_PTR &aNode2)
bool areNodesColinear(const std::vector< hed::NODE_PTR > &aNodes) const
Triangulation class for the half-edge data structure with adaption to TTL.
CN_ANCHOR_PTR GetSourceNode() const