39 using namespace std::placeholders;
45 #include <delaunator.hpp> 53 m_data.resize( size );
54 m_depth.resize( size, 0 );
56 for(
size_t i = 0; i < size; i++ )
64 while( m_data[root] != root )
68 while( m_data[aVal] != aVal )
70 auto& tmp = m_data[aVal];
79 bool unite(
int aVal1,
int aVal2 )
81 aVal1 =
find( aVal1 );
82 aVal2 =
find( aVal2 );
86 if( m_depth[aVal1] < m_depth[aVal2] )
88 m_data[aVal1] = aVal2;
92 m_data[aVal2] = aVal1;
94 if( m_depth[aVal1] == m_depth[aVal2] )
121 for(
const CN_EDGE& tmp : aEdges )
123 int u = tmp.GetSourceNode()->GetTag();
124 int v = tmp.GetTargetNode()->GetTag();
126 if( dset.unite( u, v ) )
128 if( tmp.GetWeight() > 0 )
129 m_rnEdges.push_back( tmp );
145 if ( aNodes.size() <= 2 )
148 const VECTOR2I p0( aNodes[0]->Pos() );
149 const VECTOR2I v0( aNodes[1]->Pos() - p0 );
151 for(
unsigned i = 2; i < aNodes.size(); i++ )
153 const VECTOR2I v1 = aNodes[i]->Pos() - p0;
155 if( v0.
Cross( v1 ) != 0 )
171 m_allNodes.insert( aNode );
176 std::vector<double> node_pts;
177 std::vector<CN_ANCHOR_PTR> anchors;
178 std::vector< std::vector<CN_ANCHOR_PTR> > anchorChains( m_allNodes.size() );
180 node_pts.reserve( 2 * m_allNodes.size() );
181 anchors.reserve( m_allNodes.size() );
187 if( !prev || prev->Pos() != n->Pos() )
189 node_pts.push_back( n->Pos().x );
190 node_pts.push_back( n->Pos().y );
191 anchors.push_back( n );
195 anchorChains[anchors.size() - 1].push_back( n );
198 if( anchors.size() < 2 )
202 else if( areNodesColinear( anchors ) )
207 for(
size_t i = 0; i < anchors.size() - 1; i++ )
211 mstEdges.emplace_back( src, dst, src->Dist( *dst ) );
216 delaunator::Delaunator delaunator( node_pts );
217 auto& triangles = delaunator.triangles;
219 for(
size_t i = 0; i < triangles.size(); i += 3 )
223 mstEdges.emplace_back( src, dst, src->Dist( *dst ) );
225 src = anchors[triangles[i + 1]];
226 dst = anchors[triangles[i + 2]];
227 mstEdges.emplace_back( src, dst, src->Dist( *dst ) );
229 src = anchors[triangles[i + 2]];
230 dst = anchors[triangles[i]];
231 mstEdges.emplace_back( src, dst, src->Dist( *dst ) );
234 for(
size_t i = 0; i < delaunator.halfedges.size(); i++ )
236 if( delaunator.halfedges[i] == delaunator::INVALID_INDEX )
240 const CN_ANCHOR_PTR& dst = anchors[triangles[delaunator.halfedges[i]]];
241 mstEdges.emplace_back( src, dst, src->Dist( *dst ) );
245 for(
size_t i = 0; i < anchorChains.size(); i++ )
247 std::vector<CN_ANCHOR_PTR>& chain = anchorChains[i];
249 if( chain.size() < 2 )
252 std::sort( chain.begin(), chain.end(),
255 return a->GetCluster().get() < b->GetCluster().get();
258 for(
unsigned int j = 1; j < chain.size(); j++ )
262 int weight = prevNode->GetCluster() != curNode->GetCluster() ? 1 : 0;
263 mstEdges.emplace_back( prevNode, curNode, weight );
292 edge.GetTargetNode()->SetTag( 1 );
312 std::vector<CN_EDGE> triangEdges;
324 triangEdges.emplace_back( e );
326 std::sort( triangEdges.begin(), triangEdges.end() );
362 for(
CN_ITEM* item : *aCluster )
364 bool isZone = dynamic_cast<CN_ZONE_LAYER*>( item );
365 std::vector<CN_ANCHOR_PTR>& anchors = item->Anchors();
366 unsigned int nAnchors = isZone ? 1 : anchors.size();
368 if( nAnchors > anchors.size() )
369 nAnchors = anchors.size();
371 for(
unsigned int i = 0; i < nAnchors; i++ )
373 anchors[i]->SetCluster( aCluster );
378 if( firstAnchor != anchors[i] )
379 m_boardEdges.emplace_back( firstAnchor, anchors[i], 0 );
383 firstAnchor = anchors[i];
398 [&](
const std::shared_ptr<CN_ANCHOR>& aTestNode1,
399 const std::shared_ptr<CN_ANCHOR>& aTestNode2 )
401 VECTOR2I diff = aTestNode1->Pos() - aTestNode2->Pos();
404 if( dist_sq < distMax_sq )
407 distMax_sq = dist_sq;
416 for(
const std::shared_ptr<CN_ANCHOR>& nodeA : aOtherNet.
m_nodes )
418 if( nodeA->GetNoLine() )
424 auto fwd_it =
m_nodes.lower_bound( nodeA );
425 auto rev_it = std::make_reverse_iterator( fwd_it );
427 for( ; fwd_it !=
m_nodes.end(); ++fwd_it )
429 const std::shared_ptr<CN_ANCHOR>& nodeB = *fwd_it;
431 if( nodeB->GetNoLine() )
438 if( distX_sq > distMax_sq )
441 verify( nodeA, nodeB );
445 for( ; rev_it !=
m_nodes.rend(); ++rev_it )
447 const std::shared_ptr<CN_ANCHOR>& nodeB = *rev_it;
449 if( nodeB->GetNoLine() )
454 if( distX_sq > distMax_sq )
457 verify( nodeA, nodeB );
468 edge.SetVisible( aEnabled );
extended_type Cross(const VECTOR2< T > &aVector) const
Compute cross product of self with aVector.
void Update()
Recompute ratsnest for a net.
std::multiset< CN_ANCHOR_PTR, CN_PTR_CMP > m_allNodes
std::vector< int > m_depth
Class that computes missing connections on a PCB.
VECTOR2I::extended_type ecoord
bool areNodesColinear(const std::vector< CN_ANCHOR_PTR > &aNodes) const
extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
std::vector< CN_EDGE > m_rnEdges
Flag indicating necessity of recalculation of ratsnest for a net.
void compute()
< Recompute ratsnest from scratch.
static SEG::ecoord Square(int a)
A thread-safe event counter.
void AddNode(CN_ANCHOR_PTR aNode)
static constexpr extended_type ECOORD_MAX
disjoint_set(size_t size)
void kruskalMST(const std::vector< CN_EDGE > &aEdges)
Vector of nodes.
void SetVisible(bool aEnabled)
Set 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)
std::shared_ptr< TRIANGULATOR_STATE > m_triangulator
CN_EDGE represents a point-to-point connection, whether realized or unrealized (ie: tracks etc.
std::vector< CN_EDGE > m_boardEdges
Vector of edges that makes ratsnest for a given net.
CN_ITEM represents a BOARD_CONNETED_ITEM in the connectivity system (ie: a pad, track/arc/via,...
bool unite(int aVal1, int aVal2)
std::shared_ptr< CN_CLUSTER > CN_CLUSTER_PTR
std::shared_ptr< CN_ANCHOR > CN_ANCHOR_PTR
Describe ratsnest for a single net.
void Show(std::ostream &aStream=std::cerr)
std::vector< int > m_data
std::multiset< CN_ANCHOR_PTR, CN_PTR_CMP > m_nodes
Vector of edges that make pre-defined connections.
CN_ANCHOR_PTR GetSourceNode() const
void Triangulate(std::vector< CN_EDGE > &mstEdges)