KiCad PCB EDA Suite
Loading...
Searching...
No Matches
ratsnest_data.cpp
Go to the documentation of this file.
1/*
2 * This program source code file is part of KICAD, a free EDA CAD application.
3 *
4 * Copyright (C) 2013-2017 CERN
5 * Copyright (C) 2019-2023 KiCad Developers, see AUTHORS.txt for contributors.
6 *
7 * @author Maciej Suminski <[email protected]>
8 * @author Tomasz Wlostowski <[email protected]>
9 *
10 * This program is free software; you can redistribute it and/or
11 * modify it under the terms of the GNU General Public License
12 * as published by the Free Software Foundation; either version 2
13 * of the License, or (at your option) any later version.
14 *
15 * This program is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19 *
20 * You should have received a copy of the GNU General Public License
21 * along with this program; if not, you may find one here:
22 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
23 * or you may search the http://www.gnu.org website for the version 2 license,
24 * or you may write to the Free Software Foundation, Inc.,
25 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
26 */
27
33#ifdef PROFILE
34#include <core/profile.h>
35#endif
36
38#include <functional>
39using namespace std::placeholders;
40
41#include <algorithm>
42#include <cassert>
43#include <limits>
44
45#include <delaunator.hpp>
46
48{
49
50public:
51 disjoint_set( size_t size )
52 {
53 m_data.resize( size );
54 m_depth.resize( size, 0 );
55
56 for( size_t i = 0; i < size; i++ )
57 m_data[i] = i;
58 }
59
60 int find( int aVal )
61 {
62 int root = aVal;
63
64 while( m_data[root] != root )
65 root = m_data[root];
66
67 // Compress the path
68 while( m_data[aVal] != aVal )
69 {
70 auto& tmp = m_data[aVal];
71 aVal = tmp;
72 tmp = root;
73 }
74
75 return root;
76 }
77
78
79 bool unite( int aVal1, int aVal2 )
80 {
81 aVal1 = find( aVal1 );
82 aVal2 = find( aVal2 );
83
84 if( aVal1 != aVal2 )
85 {
86 if( m_depth[aVal1] < m_depth[aVal2] )
87 {
88 m_data[aVal1] = aVal2;
89 }
90 else
91 {
92 m_data[aVal2] = aVal1;
93
94 if( m_depth[aVal1] == m_depth[aVal2] )
95 m_depth[aVal1]++;
96 }
97
98 return true;
99 }
100
101 return false;
102 }
103
104private:
105 std::vector<int> m_data;
106 std::vector<int> m_depth;
107};
108
109
110void RN_NET::kruskalMST( const std::vector<CN_EDGE> &aEdges )
111{
112 disjoint_set dset( m_nodes.size() );
113
114 m_rnEdges.clear();
115
116 int i = 0;
117
118 for( const std::shared_ptr<CN_ANCHOR>& node : m_nodes )
119 node->SetTag( i++ );
120
121 for( const CN_EDGE& tmp : aEdges )
122 {
123 const std::shared_ptr<const CN_ANCHOR>& source = tmp.GetSourceNode();
124 const std::shared_ptr<const CN_ANCHOR>& target = tmp.GetTargetNode();
125
126 wxCHECK2( source && !source->Dirty() && target && !target->Dirty(), continue );
127
128 if( dset.unite( source->GetTag(), target->GetTag() ) )
129 {
130 if( tmp.GetWeight() > 0 )
131 m_rnEdges.push_back( tmp );
132 }
133 }
134}
135
136
138{
139private:
140 std::multiset<std::shared_ptr<CN_ANCHOR>, CN_PTR_CMP> m_allNodes;
141
142
143 // Checks if all nodes in aNodes lie on a single line. Requires the nodes to
144 // have unique coordinates!
145 bool areNodesColinear( const std::vector<std::shared_ptr<CN_ANCHOR>>& aNodes ) const
146 {
147 if ( aNodes.size() <= 2 )
148 return true;
149
150 const VECTOR2I p0( aNodes[0]->Pos() );
151 const VECTOR2I v0( aNodes[1]->Pos() - p0 );
152
153 for( unsigned i = 2; i < aNodes.size(); i++ )
154 {
155 const VECTOR2I v1 = aNodes[i]->Pos() - p0;
156
157 if( v0.Cross( v1 ) != 0 )
158 return false;
159 }
160
161 return true;
162 }
163
164public:
165
166 void Clear()
167 {
168 m_allNodes.clear();
169 }
170
171 void AddNode( const std::shared_ptr<CN_ANCHOR>& aNode )
172 {
173 m_allNodes.insert( aNode );
174 }
175
176 void Triangulate( std::vector<CN_EDGE>& mstEdges )
177 {
178 std::vector<double> node_pts;
179 std::vector<std::shared_ptr<CN_ANCHOR>> anchors;
180 std::vector< std::vector<std::shared_ptr<CN_ANCHOR>> > anchorChains( m_allNodes.size() );
181
182 node_pts.reserve( 2 * m_allNodes.size() );
183 anchors.reserve( m_allNodes.size() );
184
185 auto addEdge =
186 [&]( const std::shared_ptr<CN_ANCHOR>& src, const std::shared_ptr<CN_ANCHOR>& dst )
187 {
188 mstEdges.emplace_back( src, dst, src->Dist( *dst ) );
189 };
190
191 std::shared_ptr<CN_ANCHOR> prev = nullptr;
192
193 for( const std::shared_ptr<CN_ANCHOR>& n : m_allNodes )
194 {
195 if( !prev || prev->Pos() != n->Pos() )
196 {
197 node_pts.push_back( n->Pos().x );
198 node_pts.push_back( n->Pos().y );
199 anchors.push_back( n );
200 prev = n;
201 }
202
203 anchorChains[anchors.size() - 1].push_back( n );
204 }
205
206 if( anchors.size() < 2 )
207 {
208 return;
209 }
210 else if( areNodesColinear( anchors ) )
211 {
212 // special case: all nodes are on the same line - there's no
213 // triangulation for such set. In this case, we sort along any coordinate
214 // and chain the nodes together.
215 for( size_t i = 0; i < anchors.size() - 1; i++ )
216 addEdge( anchors[i], anchors[i + 1] );
217 }
218 else
219 {
220 delaunator::Delaunator delaunator( node_pts );
221 auto& triangles = delaunator.triangles;
222
223 for( size_t i = 0; i < triangles.size(); i += 3 )
224 {
225 addEdge( anchors[triangles[i]], anchors[triangles[i + 1]] );
226 addEdge( anchors[triangles[i + 1]], anchors[triangles[i + 2]] );
227 addEdge( anchors[triangles[i + 2]], anchors[triangles[i]] );
228 }
229
230 for( size_t i = 0; i < delaunator.halfedges.size(); i++ )
231 {
232 if( delaunator.halfedges[i] == delaunator::INVALID_INDEX )
233 continue;
234
235 addEdge( anchors[triangles[i]], anchors[triangles[delaunator.halfedges[i]]] );
236 }
237 }
238
239 for( size_t i = 0; i < anchorChains.size(); i++ )
240 {
241 std::vector<std::shared_ptr<CN_ANCHOR>>& chain = anchorChains[i];
242
243 if( chain.size() < 2 )
244 continue;
245
246 std::sort( chain.begin(), chain.end(),
247 [] ( const std::shared_ptr<CN_ANCHOR>& a, const std::shared_ptr<CN_ANCHOR>& b )
248 {
249 return a->GetCluster().get() < b->GetCluster().get();
250 } );
251
252 for( unsigned int j = 1; j < chain.size(); j++ )
253 {
254 const std::shared_ptr<CN_ANCHOR>& prevNode = chain[j - 1];
255 const std::shared_ptr<CN_ANCHOR>& curNode = chain[j];
256 int weight = prevNode->GetCluster() != curNode->GetCluster() ? 1 : 0;
257 mstEdges.emplace_back( prevNode, curNode, weight );
258 }
259 }
260 }
261};
262
263
264RN_NET::RN_NET() : m_dirty( true )
265{
267}
268
269
271{
272 // Special cases do not need complicated algorithms (actually, it does not work well with
273 // the Delaunay triangulator)
274 if( m_nodes.size() <= 2 )
275 {
276 m_rnEdges.clear();
277
278 // Check if the only possible connection exists
279 if( m_boardEdges.size() == 0 && m_nodes.size() == 2 )
280 {
281 // There can be only one possible connection, but it is missing
282 auto it = m_nodes.begin();
283 const std::shared_ptr<CN_ANCHOR>& source = *it++;
284 const std::shared_ptr<CN_ANCHOR>& target = *it;
285
286 source->SetTag( 0 );
287 target->SetTag( 1 );
288 m_rnEdges.emplace_back( source, target );
289 }
290 else
291 {
292 // Set tags to m_nodes as connected
293 for( const std::shared_ptr<CN_ANCHOR>& node : m_nodes )
294 node->SetTag( 0 );
295 }
296
297 return;
298 }
299
300
301 m_triangulator->Clear();
302
303 for( const std::shared_ptr<CN_ANCHOR>& n : m_nodes )
304 m_triangulator->AddNode( n );
305
306 std::vector<CN_EDGE> triangEdges;
307 triangEdges.reserve( m_nodes.size() + m_boardEdges.size() );
308
309#ifdef PROFILE
310 PROF_TIMER cnt( "triangulate" );
311#endif
312 m_triangulator->Triangulate( triangEdges );
313#ifdef PROFILE
314 cnt.Show();
315#endif
316
317 for( const CN_EDGE& e : m_boardEdges )
318 triangEdges.emplace_back( e );
319
320 std::sort( triangEdges.begin(), triangEdges.end() );
321
322// Get the minimal spanning tree
323#ifdef PROFILE
324 PROF_TIMER cnt2( "mst" );
325#endif
326 kruskalMST( triangEdges );
327#ifdef PROFILE
328 cnt2.Show();
329#endif
330}
331
332
334{
335 auto optimizeZoneAnchor =
336 [&]( const VECTOR2I& aPos, const LSET& aLayerSet,
337 const std::shared_ptr<const CN_ANCHOR>& aAnchor,
338 const std::function<void( std::shared_ptr<const CN_ANCHOR> )>& setOptimizedTo )
339 {
340 SEG::ecoord closest_dist_sq = ( aAnchor->Pos() - aPos ).SquaredEuclideanNorm();
341 VECTOR2I closest_pt;
342 CN_ITEM* closest_item = nullptr;
343
344 for( CN_ITEM* item : aAnchor->Item()->ConnectedItems() )
345 {
346 // Don't consider shorted items
347 if( aAnchor->Item()->Net() != item->Net() )
348 continue;
349
350 CN_ZONE_LAYER* zoneLayer = dynamic_cast<CN_ZONE_LAYER*>( item );
351
352 if( zoneLayer && aLayerSet.test( zoneLayer->Layer() ) )
353 {
354 const std::vector<VECTOR2I>& pts = zoneLayer->GetOutline().CPoints();
355
356 for( const VECTOR2I& pt : pts )
357 {
358 SEG::ecoord dist_sq = ( pt - aPos ).SquaredEuclideanNorm();
359
360 if( dist_sq < closest_dist_sq )
361 {
362 closest_pt = pt;
363 closest_item = zoneLayer;
364 closest_dist_sq = dist_sq;
365 }
366 }
367 }
368 }
369
370 if( closest_item )
371 setOptimizedTo( std::make_shared<CN_ANCHOR>( closest_pt, closest_item ) );
372 };
373
374 auto optimizeZoneToZoneAnchors =
375 [&]( const std::shared_ptr<const CN_ANCHOR>& a,
376 const std::shared_ptr<const CN_ANCHOR>& b,
377 const std::function<void( const std::shared_ptr<const CN_ANCHOR>& )>&
378 setOptimizedATo,
379 const std::function<void( const std::shared_ptr<const CN_ANCHOR>& )>&
380 setOptimizedBTo )
381 {
382 struct CENTER
383 {
384 VECTOR2I pt;
385 bool valid = false;
386 };
387
388 struct DIST_PAIR
389 {
390 DIST_PAIR( int64_t aDistSq, size_t aIdA, size_t aIdB )
391 : dist_sq( aDistSq ), idA( aIdA ), idB( aIdB )
392 {}
393
394 int64_t dist_sq;
395 size_t idA;
396 size_t idB;
397 };
398
399 const std::vector<CN_ITEM*>& connectedItemsA = a->Item()->ConnectedItems();
400 const std::vector<CN_ITEM*>& connectedItemsB = b->Item()->ConnectedItems();
401
402 std::vector<CENTER> centersA( connectedItemsA.size() );
403 std::vector<CENTER> centersB( connectedItemsB.size() );
404
405 for( size_t i = 0; i < connectedItemsA.size(); i++ )
406 {
407 CN_ITEM* itemA = connectedItemsA[i];
408 CN_ZONE_LAYER* zoneLayerA = dynamic_cast<CN_ZONE_LAYER*>( itemA );
409
410 if( !zoneLayerA )
411 continue;
412
413 const SHAPE_LINE_CHAIN& shapeA = zoneLayerA->GetOutline();
414 centersA[i].pt = shapeA.BBox().GetCenter();
415 centersA[i].valid = true;
416 }
417
418 for( size_t i = 0; i < connectedItemsB.size(); i++ )
419 {
420 CN_ITEM* itemB = connectedItemsB[i];
421 CN_ZONE_LAYER* zoneLayerB = dynamic_cast<CN_ZONE_LAYER*>( itemB );
422
423 if( !zoneLayerB )
424 continue;
425
426 const SHAPE_LINE_CHAIN& shapeB = zoneLayerB->GetOutline();
427 centersB[i].pt = shapeB.BBox().GetCenter();
428 centersB[i].valid = true;
429 }
430
431 std::vector<DIST_PAIR> pairsToTest;
432
433 for( size_t ia = 0; ia < centersA.size(); ia++ )
434 {
435 for( size_t ib = 0; ib < centersB.size(); ib++ )
436 {
437 const CENTER& ca = centersA[ia];
438 const CENTER& cb = centersB[ib];
439
440 if( !ca.valid || !cb.valid )
441 continue;
442
443 VECTOR2L pA( ca.pt );
444 VECTOR2L pB( cb.pt );
445
446 int64_t dist_sq = ( pB - pA ).SquaredEuclideanNorm();
447 pairsToTest.emplace_back( dist_sq, ia, ib );
448 }
449 }
450
451 std::sort( pairsToTest.begin(), pairsToTest.end(),
452 []( const DIST_PAIR& dp_a, const DIST_PAIR& dp_b )
453 {
454 return dp_a.dist_sq < dp_b.dist_sq;
455 } );
456
457 const int c_polyPairsLimit = 3;
458
459 for( size_t i = 0; i < pairsToTest.size() && i < c_polyPairsLimit; i++ )
460 {
461 const DIST_PAIR& pair = pairsToTest[i];
462
463 CN_ZONE_LAYER* zoneLayerA = static_cast<CN_ZONE_LAYER*>( connectedItemsA[pair.idA] );
464 CN_ZONE_LAYER* zoneLayerB = static_cast<CN_ZONE_LAYER*>( connectedItemsB[pair.idB] );
465
466 if( zoneLayerA == zoneLayerB )
467 continue;
468
469 const SHAPE_LINE_CHAIN& shapeA = zoneLayerA->GetOutline();
470 const SHAPE_LINE_CHAIN& shapeB = zoneLayerB->GetOutline();
471
472 VECTOR2I ptA;
473 VECTOR2I ptB;
474
475 if( shapeA.ClosestSegmentsFast( shapeB, ptA, ptB ) )
476 {
477 setOptimizedATo( std::make_shared<CN_ANCHOR>( ptA, zoneLayerA ) );
478 setOptimizedBTo( std::make_shared<CN_ANCHOR>( ptB, zoneLayerB ) );
479 }
480 }
481 };
482
483 for( CN_EDGE& edge : m_rnEdges )
484 {
485 const std::shared_ptr<const CN_ANCHOR>& source = edge.GetSourceNode();
486 const std::shared_ptr<const CN_ANCHOR>& target = edge.GetTargetNode();
487
488 wxCHECK2( source && !source->Dirty() && target && !target->Dirty(), continue );
489
490 if( source->ConnectedItemsCount() == 0 )
491 {
492 optimizeZoneAnchor( source->Pos(), source->Parent()->GetLayerSet(), target,
493 [&]( const std::shared_ptr<const CN_ANCHOR>& optimized )
494 {
495 edge.SetTargetNode( optimized );
496 } );
497 }
498 else if( target->ConnectedItemsCount() == 0 )
499 {
500 optimizeZoneAnchor( target->Pos(), target->Parent()->GetLayerSet(), source,
501 [&]( const std::shared_ptr<const CN_ANCHOR>& optimized )
502 {
503 edge.SetSourceNode( optimized );
504 } );
505 }
506 else
507 {
508 optimizeZoneToZoneAnchors( source, target,
509 [&]( const std::shared_ptr<const CN_ANCHOR>& optimized )
510 {
511 edge.SetSourceNode( optimized );
512 },
513 [&]( const std::shared_ptr<const CN_ANCHOR>& optimized )
514 {
515 edge.SetTargetNode( optimized );
516 } );
517 }
518 }
519}
520
521
523{
524 compute();
525
526 m_dirty = false;
527}
528
529
531{
532 for( CN_EDGE& edge : m_rnEdges )
533 edge.RemoveInvalidRefs();
534
535 for( CN_EDGE& edge : m_boardEdges )
536 edge.RemoveInvalidRefs();
537}
538
539
541{
542 m_rnEdges.clear();
543 m_boardEdges.clear();
544 m_nodes.clear();
545
546 m_dirty = true;
547}
548
549
550void RN_NET::AddCluster( std::shared_ptr<CN_CLUSTER> aCluster )
551{
552 std::shared_ptr<CN_ANCHOR> firstAnchor;
553
554 for( CN_ITEM* item : *aCluster )
555 {
556 std::vector<std::shared_ptr<CN_ANCHOR>>& anchors = item->Anchors();
557 unsigned int nAnchors = dynamic_cast<CN_ZONE_LAYER*>( item ) ? 1 : anchors.size();
558
559 if( nAnchors > anchors.size() )
560 nAnchors = anchors.size();
561
562 for( unsigned int i = 0; i < nAnchors; i++ )
563 {
564 anchors[i]->SetCluster( aCluster );
565 m_nodes.insert( anchors[i] );
566
567 if( firstAnchor )
568 {
569 if( firstAnchor != anchors[i] )
570 m_boardEdges.emplace_back( firstAnchor, anchors[i], 0 );
571 }
572 else
573 {
574 firstAnchor = anchors[i];
575 }
576 }
577 }
578}
579
580
581bool RN_NET::NearestBicoloredPair( RN_NET* aOtherNet, VECTOR2I& aPos1, VECTOR2I& aPos2 ) const
582{
583 bool rv = false;
584
586
587 auto verify =
588 [&]( const std::shared_ptr<CN_ANCHOR>& aTestNode1,
589 const std::shared_ptr<CN_ANCHOR>& aTestNode2 )
590 {
591 VECTOR2I diff = aTestNode1->Pos() - aTestNode2->Pos();
592 SEG::ecoord dist_sq = diff.SquaredEuclideanNorm();
593
594 if( dist_sq < distMax_sq )
595 {
596 rv = true;
597 distMax_sq = dist_sq;
598 aPos1 = aTestNode1->Pos();
599 aPos2 = aTestNode2->Pos();
600 }
601 };
602
606 for( const std::shared_ptr<CN_ANCHOR>& nodeA : aOtherNet->m_nodes )
607 {
608
609 if( nodeA->GetNoLine() )
610 continue;
611
615 auto fwd_it = m_nodes.lower_bound( nodeA );
616 auto rev_it = std::make_reverse_iterator( fwd_it );
617
618 for( ; fwd_it != m_nodes.end(); ++fwd_it )
619 {
620 const std::shared_ptr<CN_ANCHOR>& nodeB = *fwd_it;
621
622 if( nodeB->GetNoLine() )
623 continue;
624
625 SEG::ecoord distX_sq = SEG::Square( nodeA->Pos().x - nodeB->Pos().x );
626
629 if( distX_sq > distMax_sq )
630 break;
631
632 verify( nodeA, nodeB );
633 }
634
636 for( ; rev_it != m_nodes.rend(); ++rev_it )
637 {
638 const std::shared_ptr<CN_ANCHOR>& nodeB = *rev_it;
639
640 if( nodeB->GetNoLine() )
641 continue;
642
643 SEG::ecoord distX_sq = SEG::Square( nodeA->Pos().x - nodeB->Pos().x );
644
645 if( distX_sq > distMax_sq )
646 break;
647
648 verify( nodeA, nodeB );
649 }
650 }
651
652 return rv;
653}
654
const Vec GetCenter() const
Definition: box2.h:220
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.
Definition: lset.h:35
A small class to help profiling.
Definition: profile.h:49
void Show(std::ostream &aStream=std::cerr)
Print the elapsed time (in a suitable unit) to a stream.
Definition: profile.h:105
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.
Definition: ratsnest_data.h:63
std::shared_ptr< TRIANGULATOR_STATE > m_triangulator
std::multiset< std::shared_ptr< CN_ANCHOR >, CN_PTR_CMP > m_nodes
< Vector of nodes
void RemoveInvalidRefs()
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
bool m_dirty
std::vector< CN_EDGE > m_boardEdges
Vector of edges that makes ratsnest for a given net.
void compute()
< Recompute ratsnest from scratch.
void Clear()
void AddCluster(std::shared_ptr< CN_CLUSTER > aCluster)
VECTOR2I::extended_type ecoord
Definition: seg.h:44
static SEG::ecoord Square(int a)
Definition: seg.h:123
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
bool ClosestSegmentsFast(const SHAPE_LINE_CHAIN &aOther, VECTOR2I &aPt0, VECTOR2I &aPt1) const
Finds closest points between segments of this and the other line chain.
const std::vector< VECTOR2I > & CPoints() const
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
Definition: vector2d.h:302
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:75
extended_type Cross(const VECTOR2< T > &aVector) const
Compute cross product of self with aVector.
Definition: vector2d.h:535
disjoint_set(size_t size)
std::vector< int > m_data
std::vector< int > m_depth
int find(int aVal)
bool unite(int aVal1, int aVal2)
Class that computes missing connections on a PCB.
VECTOR3I v1(5, 5, 5)