39using namespace std::placeholders;
45#include <delaunator.hpp>
56 for(
size_t i = 0; i < size; i++ )
64 while(
m_data[root] != root )
68 while(
m_data[aVal] != aVal )
79 bool unite(
int aVal1,
int aVal2 )
81 aVal1 =
find( aVal1 );
82 aVal2 =
find( aVal2 );
118 for(
const std::shared_ptr<CN_ANCHOR>& node :
m_nodes )
121 for(
const CN_EDGE& tmp : aEdges )
123 const std::shared_ptr<const CN_ANCHOR>& source = tmp.GetSourceNode();
124 const std::shared_ptr<const CN_ANCHOR>& target = tmp.GetTargetNode();
126 if( dset.
unite( source->GetTag(), target->GetTag() ) )
128 if( tmp.GetWeight() > 0 )
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++ )
169 void AddNode(
const std::shared_ptr<CN_ANCHOR>& aNode )
176 std::vector<double> node_pts;
177 std::vector<std::shared_ptr<CN_ANCHOR>> anchors;
178 std::vector< std::vector<std::shared_ptr<CN_ANCHOR>> > anchorChains(
m_allNodes.size() );
184 [&](
const std::shared_ptr<CN_ANCHOR>& src,
const std::shared_ptr<CN_ANCHOR>& dst )
186 mstEdges.emplace_back( src, dst, src->Dist( *dst ) );
189 std::shared_ptr<CN_ANCHOR> prev =
nullptr;
191 for(
const std::shared_ptr<CN_ANCHOR>& n :
m_allNodes )
193 if( !prev || prev->Pos() != n->Pos() )
195 node_pts.push_back( n->Pos().x );
196 node_pts.push_back( n->Pos().y );
197 anchors.push_back( n );
201 anchorChains[anchors.size() - 1].push_back( n );
204 if( anchors.size() < 2 )
213 for(
size_t i = 0; i < anchors.size() - 1; i++ )
214 addEdge( anchors[i], anchors[i + 1] );
218 delaunator::Delaunator delaunator( node_pts );
219 auto& triangles = delaunator.triangles;
221 for(
size_t i = 0; i < triangles.size(); i += 3 )
223 addEdge( anchors[triangles[i]], anchors[triangles[i + 1]] );
224 addEdge( anchors[triangles[i + 1]], anchors[triangles[i + 2]] );
225 addEdge( anchors[triangles[i + 2]], anchors[triangles[i]] );
228 for(
size_t i = 0; i < delaunator.halfedges.size(); i++ )
230 if( delaunator.halfedges[i] == delaunator::INVALID_INDEX )
233 addEdge( anchors[triangles[i]], anchors[triangles[delaunator.halfedges[i]]] );
237 for(
size_t i = 0; i < anchorChains.size(); i++ )
239 std::vector<std::shared_ptr<CN_ANCHOR>>& chain = anchorChains[i];
241 if( chain.size() < 2 )
244 std::sort( chain.begin(), chain.end(),
245 [] (
const std::shared_ptr<CN_ANCHOR>& a,
const std::shared_ptr<CN_ANCHOR>& b )
247 return a->GetCluster().get() < b->GetCluster().get();
250 for(
unsigned int j = 1; j < chain.size(); j++ )
252 const std::shared_ptr<CN_ANCHOR>& prevNode = chain[j - 1];
253 const std::shared_ptr<CN_ANCHOR>& curNode = chain[j];
254 int weight = prevNode->GetCluster() != curNode->GetCluster() ? 1 : 0;
255 mstEdges.emplace_back( prevNode, curNode, weight );
281 const std::shared_ptr<CN_ANCHOR>& source = *it++;
282 const std::shared_ptr<CN_ANCHOR>& target = *it;
286 m_rnEdges.emplace_back( source, target );
291 for(
const std::shared_ptr<CN_ANCHOR>& node :
m_nodes )
301 for(
const std::shared_ptr<CN_ANCHOR>& n :
m_nodes )
304 std::vector<CN_EDGE> triangEdges;
316 triangEdges.emplace_back( e );
318 std::sort( triangEdges.begin(), triangEdges.end() );
333 auto optimizeZoneAnchor =
335 const std::shared_ptr<const CN_ANCHOR>& aAnchor,
336 const std::function<void( std::shared_ptr<const CN_ANCHOR> )>& setOptimizedTo )
338 SEG::ecoord closest_dist_sq = ( aAnchor->Pos() - aPos ).SquaredEuclideanNorm();
340 CN_ITEM* closest_item =
nullptr;
345 if( aAnchor->Item()->Net() != item->Net() )
350 if( zoneLayer && aLayerSet.test( zoneLayer->
Layer() ) )
356 SEG::ecoord dist_sq = ( pt - aPos ).SquaredEuclideanNorm();
358 if( dist_sq < closest_dist_sq )
361 closest_item = zoneLayer;
362 closest_dist_sq = dist_sq;
369 setOptimizedTo( std::make_shared<CN_ANCHOR>( closest_pt, closest_item ) );
372 auto optimizeZoneToZoneAnchors =
373 [&](
const std::shared_ptr<const CN_ANCHOR>& a,
374 const std::shared_ptr<const CN_ANCHOR>& b,
375 const std::function<void(
const std::shared_ptr<const CN_ANCHOR>&)>& setOptimizedATo,
376 const std::function<void(
const std::shared_ptr<const CN_ANCHOR>&)>& setOptimizedBTo )
389 if( zoneLayerB && zoneLayerB->
Layer() == zoneLayerA->
Layer() )
403 shapeA->
Collide( shapeB, startDist + 10,
nullptr, &ptA );
404 setOptimizedATo( std::make_shared<CN_ANCHOR>( ptA, zoneLayerA ) );
407 shapeB->
Collide( shapeA, startDist + 10,
nullptr, &ptB );
408 setOptimizedBTo( std::make_shared<CN_ANCHOR>( ptB, zoneLayerB ) );
416 const std::shared_ptr<const CN_ANCHOR>& source = edge.GetSourceNode();
417 const std::shared_ptr<const CN_ANCHOR>& target = edge.GetTargetNode();
419 if( source->ConnectedItemsCount() == 0 )
421 optimizeZoneAnchor( source->Pos(), source->Parent()->GetLayerSet(), target,
422 [&](
const std::shared_ptr<const CN_ANCHOR>& optimized )
424 edge.SetTargetNode( optimized );
427 else if( target->ConnectedItemsCount() == 0 )
429 optimizeZoneAnchor( target->Pos(), target->Parent()->GetLayerSet(), source,
430 [&](
const std::shared_ptr<const CN_ANCHOR>& optimized )
432 edge.SetSourceNode( optimized );
437 optimizeZoneToZoneAnchors( source, target,
438 [&](
const std::shared_ptr<const CN_ANCHOR>& optimized )
440 edge.SetSourceNode( optimized );
442 [&](
const std::shared_ptr<const CN_ANCHOR>& optimized )
444 edge.SetTargetNode( optimized );
471 std::shared_ptr<CN_ANCHOR> firstAnchor;
473 for(
CN_ITEM* item : *aCluster )
475 std::vector<std::shared_ptr<CN_ANCHOR>>& anchors = item->Anchors();
476 unsigned int nAnchors =
dynamic_cast<CN_ZONE_LAYER*
>( item ) ? 1 : anchors.size();
478 if( nAnchors > anchors.size() )
479 nAnchors = anchors.size();
481 for(
unsigned int i = 0; i < nAnchors; i++ )
483 anchors[i]->SetCluster( aCluster );
488 if( firstAnchor != anchors[i] )
489 m_boardEdges.emplace_back( firstAnchor, anchors[i], 0 );
493 firstAnchor = anchors[i];
507 [&](
const std::shared_ptr<CN_ANCHOR>& aTestNode1,
508 const std::shared_ptr<CN_ANCHOR>& aTestNode2 )
510 VECTOR2I diff = aTestNode1->Pos() - aTestNode2->Pos();
513 if( dist_sq < distMax_sq )
516 distMax_sq = dist_sq;
517 aPos1 = aTestNode1->Pos();
518 aPos2 = aTestNode2->Pos();
522 std::multiset<std::shared_ptr<CN_ANCHOR>,
CN_PTR_CMP> nodes_b;
524 std::copy_if(
m_nodes.begin(),
m_nodes.end(), std::inserter( nodes_b, nodes_b.end() ),
525 [](
const std::shared_ptr<CN_ANCHOR> &aVal )
526 { return !aVal->GetNoLine(); } );
531 for(
const std::shared_ptr<CN_ANCHOR>& nodeA : aOtherNet->
m_nodes )
534 if( nodeA->GetNoLine() )
540 auto fwd_it = nodes_b.lower_bound( nodeA );
541 auto rev_it = std::make_reverse_iterator( fwd_it );
543 for( ; fwd_it != nodes_b.end(); ++fwd_it )
545 const std::shared_ptr<CN_ANCHOR>& nodeB = *fwd_it;
551 if( distX_sq > distMax_sq )
554 verify( nodeA, nodeB );
558 for( ; rev_it != nodes_b.rend(); ++rev_it )
560 const std::shared_ptr<CN_ANCHOR>& nodeB = *rev_it;
564 if( distX_sq > distMax_sq )
567 verify( nodeA, nodeB );
CN_EDGE represents a point-to-point connection, whether realized or unrealized (ie: tracks etc.
CN_ITEM represents a BOARD_CONNETED_ITEM in the connectivity system (ie: a pad, track/arc/via,...
virtual int Layer() const
Return the item's layer, for single-layered items only.
const std::vector< CN_ITEM * > & ConnectedItems() const
const SHAPE_LINE_CHAIN & GetOutline() const
LSET is a set of PCB_LAYER_IDs.
A small class to help profiling.
void Show(std::ostream &aStream=std::cerr)
Print the elapsed time (in a suitable unit) to a stream.
void AddNode(const std::shared_ptr< CN_ANCHOR > &aNode)
std::multiset< std::shared_ptr< CN_ANCHOR >, CN_PTR_CMP > m_allNodes
bool areNodesColinear(const std::vector< std::shared_ptr< CN_ANCHOR > > &aNodes) const
void Triangulate(std::vector< CN_EDGE > &mstEdges)
Describe ratsnest for a single net.
std::shared_ptr< TRIANGULATOR_STATE > m_triangulator
std::multiset< std::shared_ptr< CN_ANCHOR >, CN_PTR_CMP > m_nodes
< Vector of nodes
void kruskalMST(const std::vector< CN_EDGE > &aEdges)
void UpdateNet()
Recompute ratsnest for a net.
std::vector< CN_EDGE > m_rnEdges
Flag indicating necessity of recalculation of ratsnest for a net.
void OptimizeRNEdges()
Find optimal ends of RNEdges.
bool NearestBicoloredPair(RN_NET *aOtherNet, VECTOR2I &aPos1, VECTOR2I &aPos2) const
std::vector< CN_EDGE > m_boardEdges
Vector of edges that makes ratsnest for a given net.
void compute()
< Recompute ratsnest from scratch.
void AddCluster(std::shared_ptr< CN_CLUSTER > aCluster)
VECTOR2I::extended_type ecoord
static SEG::ecoord Square(int a)
virtual const VECTOR2I GetPoint(int aIndex) const override
const std::vector< VECTOR2I > & CPoints() const
An abstract shape on 2D plane.
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const
Check if the boundary of shape (this) lies closer to the point aP than aClearance,...
extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
static constexpr extended_type ECOORD_MAX
extended_type Cross(const VECTOR2< T > &aVector) const
Compute cross product of self with aVector.
disjoint_set(size_t size)
std::vector< int > m_data
std::vector< int > m_depth
bool unite(int aVal1, int aVal2)
Class that computes missing connections on a PCB.
double EuclideanNorm(const VECTOR2I &vector)