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 <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 if( dset.unite( source->GetTag(), target->GetTag() ) )
127 {
128 if( tmp.GetWeight() > 0 )
129 m_rnEdges.push_back( tmp );
130 }
131 }
132}
133
134
136{
137private:
138 std::multiset<std::shared_ptr<CN_ANCHOR>, CN_PTR_CMP> m_allNodes;
139
140
141 // Checks if all nodes in aNodes lie on a single line. Requires the nodes to
142 // have unique coordinates!
143 bool areNodesColinear( const std::vector<std::shared_ptr<CN_ANCHOR>>& aNodes ) const
144 {
145 if ( aNodes.size() <= 2 )
146 return true;
147
148 const VECTOR2I p0( aNodes[0]->Pos() );
149 const VECTOR2I v0( aNodes[1]->Pos() - p0 );
150
151 for( unsigned i = 2; i < aNodes.size(); i++ )
152 {
153 const VECTOR2I v1 = aNodes[i]->Pos() - p0;
154
155 if( v0.Cross( v1 ) != 0 )
156 return false;
157 }
158
159 return true;
160 }
161
162public:
163
164 void Clear()
165 {
166 m_allNodes.clear();
167 }
168
169 void AddNode( const std::shared_ptr<CN_ANCHOR>& aNode )
170 {
171 m_allNodes.insert( aNode );
172 }
173
174 void Triangulate( std::vector<CN_EDGE>& mstEdges )
175 {
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() );
179
180 node_pts.reserve( 2 * m_allNodes.size() );
181 anchors.reserve( m_allNodes.size() );
182
183 auto addEdge =
184 [&]( const std::shared_ptr<CN_ANCHOR>& src, const std::shared_ptr<CN_ANCHOR>& dst )
185 {
186 mstEdges.emplace_back( src, dst, src->Dist( *dst ) );
187 };
188
189 std::shared_ptr<CN_ANCHOR> prev = nullptr;
190
191 for( const std::shared_ptr<CN_ANCHOR>& n : m_allNodes )
192 {
193 if( !prev || prev->Pos() != n->Pos() )
194 {
195 node_pts.push_back( n->Pos().x );
196 node_pts.push_back( n->Pos().y );
197 anchors.push_back( n );
198 prev = n;
199 }
200
201 anchorChains[anchors.size() - 1].push_back( n );
202 }
203
204 if( anchors.size() < 2 )
205 {
206 return;
207 }
208 else if( areNodesColinear( anchors ) )
209 {
210 // special case: all nodes are on the same line - there's no
211 // triangulation for such set. In this case, we sort along any coordinate
212 // and chain the nodes together.
213 for( size_t i = 0; i < anchors.size() - 1; i++ )
214 addEdge( anchors[i], anchors[i + 1] );
215 }
216 else
217 {
218 delaunator::Delaunator delaunator( node_pts );
219 auto& triangles = delaunator.triangles;
220
221 for( size_t i = 0; i < triangles.size(); i += 3 )
222 {
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]] );
226 }
227
228 for( size_t i = 0; i < delaunator.halfedges.size(); i++ )
229 {
230 if( delaunator.halfedges[i] == delaunator::INVALID_INDEX )
231 continue;
232
233 addEdge( anchors[triangles[i]], anchors[triangles[delaunator.halfedges[i]]] );
234 }
235 }
236
237 for( size_t i = 0; i < anchorChains.size(); i++ )
238 {
239 std::vector<std::shared_ptr<CN_ANCHOR>>& chain = anchorChains[i];
240
241 if( chain.size() < 2 )
242 continue;
243
244 std::sort( chain.begin(), chain.end(),
245 [] ( const std::shared_ptr<CN_ANCHOR>& a, const std::shared_ptr<CN_ANCHOR>& b )
246 {
247 return a->GetCluster().get() < b->GetCluster().get();
248 } );
249
250 for( unsigned int j = 1; j < chain.size(); j++ )
251 {
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 );
256 }
257 }
258 }
259};
260
261
262RN_NET::RN_NET() : m_dirty( true )
263{
265}
266
267
269{
270 // Special cases do not need complicated algorithms (actually, it does not work well with
271 // the Delaunay triangulator)
272 if( m_nodes.size() <= 2 )
273 {
274 m_rnEdges.clear();
275
276 // Check if the only possible connection exists
277 if( m_boardEdges.size() == 0 && m_nodes.size() == 2 )
278 {
279 // There can be only one possible connection, but it is missing
280 auto it = m_nodes.begin();
281 const std::shared_ptr<CN_ANCHOR>& source = *it++;
282 const std::shared_ptr<CN_ANCHOR>& target = *it;
283
284 source->SetTag( 0 );
285 target->SetTag( 1 );
286 m_rnEdges.emplace_back( source, target );
287 }
288 else
289 {
290 // Set tags to m_nodes as connected
291 for( const std::shared_ptr<CN_ANCHOR>& node : m_nodes )
292 node->SetTag( 0 );
293 }
294
295 return;
296 }
297
298
299 m_triangulator->Clear();
300
301 for( const std::shared_ptr<CN_ANCHOR>& n : m_nodes )
302 m_triangulator->AddNode( n );
303
304 std::vector<CN_EDGE> triangEdges;
305 triangEdges.reserve( m_nodes.size() + m_boardEdges.size() );
306
307#ifdef PROFILE
308 PROF_TIMER cnt( "triangulate" );
309#endif
310 m_triangulator->Triangulate( triangEdges );
311#ifdef PROFILE
312 cnt.Show();
313#endif
314
315 for( const CN_EDGE& e : m_boardEdges )
316 triangEdges.emplace_back( e );
317
318 std::sort( triangEdges.begin(), triangEdges.end() );
319
320// Get the minimal spanning tree
321#ifdef PROFILE
322 PROF_TIMER cnt2( "mst" );
323#endif
324 kruskalMST( triangEdges );
325#ifdef PROFILE
326 cnt2.Show();
327#endif
328}
329
330
332{
333 auto optimizeZoneAnchor =
334 [&]( const VECTOR2I& aPos, const LSET& aLayerSet,
335 const std::shared_ptr<const CN_ANCHOR>& aAnchor,
336 const std::function<void( std::shared_ptr<const CN_ANCHOR> )>& setOptimizedTo )
337 {
338 SEG::ecoord closest_dist_sq = ( aAnchor->Pos() - aPos ).SquaredEuclideanNorm();
339 VECTOR2I closest_pt;
340 CN_ITEM* closest_item = nullptr;
341
342 for( CN_ITEM* item : aAnchor->Item()->ConnectedItems() )
343 {
344 // Don't consider shorted items
345 if( aAnchor->Item()->Net() != item->Net() )
346 continue;
347
348 CN_ZONE_LAYER* zoneLayer = dynamic_cast<CN_ZONE_LAYER*>( item );
349
350 if( zoneLayer && aLayerSet.test( zoneLayer->Layer() ) )
351 {
352 const std::vector<VECTOR2I>& pts = zoneLayer->GetOutline().CPoints();
353
354 for( const VECTOR2I& pt : pts )
355 {
356 SEG::ecoord dist_sq = ( pt - aPos ).SquaredEuclideanNorm();
357
358 if( dist_sq < closest_dist_sq )
359 {
360 closest_pt = pt;
361 closest_item = zoneLayer;
362 closest_dist_sq = dist_sq;
363 }
364 }
365 }
366 }
367
368 if( closest_item )
369 setOptimizedTo( std::make_shared<CN_ANCHOR>( closest_pt, closest_item ) );
370 };
371
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 )
377 {
378 for( CN_ITEM* itemA : a->Item()->ConnectedItems() )
379 {
380 CN_ZONE_LAYER* zoneLayerA = dynamic_cast<CN_ZONE_LAYER*>( itemA );
381
382 if( !zoneLayerA )
383 continue;
384
385 for( CN_ITEM* itemB : b->Item()->ConnectedItems() )
386 {
387 CN_ZONE_LAYER* zoneLayerB = dynamic_cast<CN_ZONE_LAYER*>( itemB );
388
389 if( zoneLayerB && zoneLayerB->Layer() == zoneLayerA->Layer() )
390 {
391 // Process the first matching layer. We don't really care if it's
392 // the "best" layer or not, as anything will be better than the
393 // original anchors (which are connected to the zone and so certainly
394 // don't look like they should have ratsnest lines coming off them).
395
396 VECTOR2I startA = zoneLayerA->GetOutline().GetPoint( 0 );
397 VECTOR2I startB = zoneLayerB->GetOutline().GetPoint( 0 );
398 const SHAPE* shapeA = &zoneLayerA->GetOutline();
399 const SHAPE* shapeB = &zoneLayerB->GetOutline();
400 int startDist = ( startA - startB ).EuclideanNorm();
401
402 VECTOR2I ptA;
403 shapeA->Collide( shapeB, startDist + 10, nullptr, &ptA );
404 setOptimizedATo( std::make_shared<CN_ANCHOR>( ptA, zoneLayerA ) );
405
406 VECTOR2I ptB;
407 shapeB->Collide( shapeA, startDist + 10, nullptr, &ptB );
408 setOptimizedBTo( std::make_shared<CN_ANCHOR>( ptB, zoneLayerB ) );
409 }
410 }
411 }
412 };
413
414 for( CN_EDGE& edge : m_rnEdges )
415 {
416 const std::shared_ptr<const CN_ANCHOR>& source = edge.GetSourceNode();
417 const std::shared_ptr<const CN_ANCHOR>& target = edge.GetTargetNode();
418
419 if( source->ConnectedItemsCount() == 0 )
420 {
421 optimizeZoneAnchor( source->Pos(), source->Parent()->GetLayerSet(), target,
422 [&]( const std::shared_ptr<const CN_ANCHOR>& optimized )
423 {
424 edge.SetTargetNode( optimized );
425 } );
426 }
427 else if( target->ConnectedItemsCount() == 0 )
428 {
429 optimizeZoneAnchor( target->Pos(), target->Parent()->GetLayerSet(), source,
430 [&]( const std::shared_ptr<const CN_ANCHOR>& optimized )
431 {
432 edge.SetSourceNode( optimized );
433 } );
434 }
435 else
436 {
437 optimizeZoneToZoneAnchors( source, target,
438 [&]( const std::shared_ptr<const CN_ANCHOR>& optimized )
439 {
440 edge.SetSourceNode( optimized );
441 },
442 [&]( const std::shared_ptr<const CN_ANCHOR>& optimized )
443 {
444 edge.SetTargetNode( optimized );
445 } );
446 }
447 }
448}
449
450
452{
453 compute();
454
455 m_dirty = false;
456}
457
458
460{
461 m_rnEdges.clear();
462 m_boardEdges.clear();
463 m_nodes.clear();
464
465 m_dirty = true;
466}
467
468
469void RN_NET::AddCluster( std::shared_ptr<CN_CLUSTER> aCluster )
470{
471 std::shared_ptr<CN_ANCHOR> firstAnchor;
472
473 for( CN_ITEM* item : *aCluster )
474 {
475 std::vector<std::shared_ptr<CN_ANCHOR>>& anchors = item->Anchors();
476 unsigned int nAnchors = dynamic_cast<CN_ZONE_LAYER*>( item ) ? 1 : anchors.size();
477
478 if( nAnchors > anchors.size() )
479 nAnchors = anchors.size();
480
481 for( unsigned int i = 0; i < nAnchors; i++ )
482 {
483 anchors[i]->SetCluster( aCluster );
484 m_nodes.insert( anchors[i] );
485
486 if( firstAnchor )
487 {
488 if( firstAnchor != anchors[i] )
489 m_boardEdges.emplace_back( firstAnchor, anchors[i], 0 );
490 }
491 else
492 {
493 firstAnchor = anchors[i];
494 }
495 }
496 }
497}
498
499
500bool RN_NET::NearestBicoloredPair( RN_NET* aOtherNet, VECTOR2I& aPos1, VECTOR2I& aPos2 ) const
501{
502 bool rv = false;
503
505
506 auto verify =
507 [&]( const std::shared_ptr<CN_ANCHOR>& aTestNode1,
508 const std::shared_ptr<CN_ANCHOR>& aTestNode2 )
509 {
510 VECTOR2I diff = aTestNode1->Pos() - aTestNode2->Pos();
511 SEG::ecoord dist_sq = diff.SquaredEuclideanNorm();
512
513 if( dist_sq < distMax_sq )
514 {
515 rv = true;
516 distMax_sq = dist_sq;
517 aPos1 = aTestNode1->Pos();
518 aPos2 = aTestNode2->Pos();
519 }
520 };
521
522 std::multiset<std::shared_ptr<CN_ANCHOR>, CN_PTR_CMP> nodes_b;
523
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(); } );
527
531 for( const std::shared_ptr<CN_ANCHOR>& nodeA : aOtherNet->m_nodes )
532 {
533
534 if( nodeA->GetNoLine() )
535 continue;
536
540 auto fwd_it = nodes_b.lower_bound( nodeA );
541 auto rev_it = std::make_reverse_iterator( fwd_it );
542
543 for( ; fwd_it != nodes_b.end(); ++fwd_it )
544 {
545 const std::shared_ptr<CN_ANCHOR>& nodeB = *fwd_it;
546
547 SEG::ecoord distX_sq = SEG::Square( nodeA->Pos().x - nodeB->Pos().x );
548
551 if( distX_sq > distMax_sq )
552 break;
553
554 verify( nodeA, nodeB );
555 }
556
558 for( ; rev_it != nodes_b.rend(); ++rev_it )
559 {
560 const std::shared_ptr<CN_ANCHOR>& nodeB = *rev_it;
561
562 SEG::ecoord distX_sq = SEG::Square( nodeA->Pos().x - nodeB->Pos().x );
563
564 if( distX_sq > distMax_sq )
565 break;
566
567 verify( nodeA, nodeB );
568 }
569 }
570
571 return rv;
572}
573
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: layer_ids.h:536
A small class to help profiling.
Definition: profile.h:47
void Show(std::ostream &aStream=std::cerr)
Print the elapsed time (in a suitable unit) to a stream.
Definition: profile.h:103
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 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
virtual const VECTOR2I GetPoint(int aIndex) const override
const std::vector< VECTOR2I > & CPoints() const
An abstract shape on 2D plane.
Definition: shape.h:124
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,...
Definition: shape.h:179
extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
Definition: vector2d.h:272
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:457
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)
double EuclideanNorm(const VECTOR2I &vector)
Definition: trigo.h:129