KiCad PCB EDA Suite
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-2015 CERN
5  * Copyright (C) 2016 KiCad Developers, see AUTHORS.txt for contributors.
6  * @author Maciej Suminski <maciej.suminski@cern.ch>
7  *
8  * This program is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU General Public License
10  * as published by the Free Software Foundation; either version 2
11  * of the License, or (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, you may find one here:
20  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
21  * or you may search the http://www.gnu.org website for the version 2 license,
22  * or you may write to the Free Software Foundation, Inc.,
23  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
24  */
25 
31 #ifdef USE_OPENMP
32 #include <omp.h>
33 #endif /* USE_OPENMP */
34 
35 #include <ratsnest_data.h>
36 
37 #include <class_board.h>
38 #include <class_module.h>
39 #include <class_pad.h>
40 #include <class_track.h>
41 #include <class_zone.h>
42 
43 #include <functional>
44 using namespace std::placeholders;
45 
47 
48 #include <cassert>
49 #include <algorithm>
50 #include <limits>
51 
52 #ifdef PROFILE
53 #include <profile.h>
54 #endif
55 
56 static uint64_t getDistance( const RN_NODE_PTR& aNode1, const RN_NODE_PTR& aNode2 )
57 {
58  // Drop the least significant bits to avoid overflow
59  int64_t x = ( aNode1->GetX() - aNode2->GetX() ) >> 16;
60  int64_t y = ( aNode1->GetY() - aNode2->GetY() ) >> 16;
61 
62  // We do not need sqrt() here, as the distance is computed only for comparison
63  return ( x * x + y * y );
64 }
65 
66 
67 static bool sortDistance( const RN_NODE_PTR& aOrigin, const RN_NODE_PTR& aNode1,
68  const RN_NODE_PTR& aNode2 )
69 {
70  return getDistance( aOrigin, aNode1 ) < getDistance( aOrigin, aNode2 );
71 }
72 
73 
74 static bool sortWeight( const RN_EDGE_PTR& aEdge1, const RN_EDGE_PTR& aEdge2 )
75 {
76  return aEdge1->GetWeight() < aEdge2->GetWeight();
77 }
78 
79 
80 bool sortArea( const RN_POLY& aP1, const RN_POLY& aP2 )
81 {
82  return aP1.m_bbox.GetArea() < aP2.m_bbox.GetArea();
83 }
84 
85 
86 bool operator==( const RN_NODE_PTR& aFirst, const RN_NODE_PTR& aSecond )
87 {
88  return aFirst->GetX() == aSecond->GetX() && aFirst->GetY() == aSecond->GetY();
89 }
90 
91 
92 bool operator!=( const RN_NODE_PTR& aFirst, const RN_NODE_PTR& aSecond )
93 {
94  return aFirst->GetX() != aSecond->GetX() || aFirst->GetY() != aSecond->GetY();
95 }
96 
97 
98 RN_NODE_AND_FILTER operator&&( const RN_NODE_FILTER& aFilter1, const RN_NODE_FILTER& aFilter2 )
99 {
100  return RN_NODE_AND_FILTER( aFilter1, aFilter2 );
101 }
102 
103 
104 RN_NODE_OR_FILTER operator||( const RN_NODE_FILTER& aFilter1, const RN_NODE_FILTER& aFilter2 )
105 {
106  return RN_NODE_OR_FILTER( aFilter1, aFilter2 );
107 }
108 
109 
110 static bool isEdgeConnectingNode( const RN_EDGE_PTR& aEdge, const RN_NODE_PTR& aNode )
111 {
112  return aEdge->GetSourceNode() == aNode || aEdge->GetTargetNode() == aNode;
113 }
114 
115 
116 static std::vector<RN_EDGE_MST_PTR>* kruskalMST( RN_LINKS::RN_EDGE_LIST& aEdges,
117  std::vector<RN_NODE_PTR>& aNodes )
118 {
119  unsigned int nodeNumber = aNodes.size();
120  unsigned int mstExpectedSize = nodeNumber - 1;
121  unsigned int mstSize = 0;
122  bool ratsnestLines = false;
123 
124  // The output
125  std::vector<RN_EDGE_MST_PTR>* mst = new std::vector<RN_EDGE_MST_PTR>;
126  mst->reserve( mstExpectedSize );
127 
128  // Set tags for marking cycles
129  std::unordered_map<RN_NODE_PTR, int> tags;
130  unsigned int tag = 0;
131 
132  for( RN_NODE_PTR& node : aNodes )
133  {
134  node->SetTag( tag );
135  tags[node] = tag++;
136  }
137 
138  // Lists of nodes connected together (subtrees) to detect cycles in the graph
139  std::vector<std::list<int> > cycles( nodeNumber );
140  for( unsigned int i = 0; i < nodeNumber; ++i )
141  cycles[i].push_back( i );
142 
143  // Kruskal algorithm requires edges to be sorted by their weight
144  aEdges.sort( sortWeight );
145 
146  while( mstSize < mstExpectedSize && !aEdges.empty() )
147  {
148  RN_EDGE_PTR& dt = aEdges.front();
149 
150  int srcTag = tags[dt->GetSourceNode()];
151  int trgTag = tags[dt->GetTargetNode()];
152 
153  // Check if by adding this edge we are going to join two different forests
154  if( srcTag != trgTag )
155  {
156  // Because edges are sorted by their weight, first we always process connected
157  // items (weight == 0). Once we stumble upon an edge with non-zero weight,
158  // it means that the rest of the lines are ratsnest.
159  if( !ratsnestLines && dt->GetWeight() != 0 )
160  ratsnestLines = true;
161 
162  // Update tags
163  if( ratsnestLines )
164  {
165  for( auto it = cycles[trgTag].begin(); it != cycles[trgTag].end(); ++it )
166  {
167  tags[aNodes[*it]] = srcTag;
168  }
169  // Do a copy of edge, but make it RN_EDGE_MST. In contrary to RN_EDGE,
170  // RN_EDGE_MST saves both source and target node and does not require any other
171  // edges to exist for getting source/target nodes
172  RN_EDGE_MST_PTR newEdge = std::make_shared<RN_EDGE_MST>( dt->GetSourceNode(),
173  dt->GetTargetNode(),
174  dt->GetWeight() );
175 
176  assert( newEdge->GetSourceNode()->GetTag() != newEdge->GetTargetNode()->GetTag() );
177  assert( newEdge->GetWeight() > 0 );
178 
179  mst->push_back( newEdge );
180  ++mstSize;
181  }
182  else
183  {
184  //for( it = cycles[trgTag].begin(), itEnd = cycles[trgTag].end(); it != itEnd; ++it )
185  //for( auto it : cycles[trgTag] )
186  for( auto it = cycles[trgTag].begin(); it != cycles[trgTag].end(); ++it )
187  {
188  tags[aNodes[*it]] = srcTag;
189  aNodes[*it]->SetTag( srcTag );
190  }
191 
192  // Processing a connection, decrease the expected size of the ratsnest MST
193  --mstExpectedSize;
194  }
195 
196  // Move nodes that were marked with old tag to the list marked with the new tag
197  cycles[srcTag].splice( cycles[srcTag].end(), cycles[trgTag] );
198  }
199 
200  // Remove the edge that was just processed
201  aEdges.erase( aEdges.begin() );
202  }
203 
204  // Probably we have discarded some of edges, so reduce the size
205  mst->resize( mstSize );
206 
207  return mst;
208 }
209 
210 
212 {
213  RN_NODE_PTR source = aEdge->GetSourceNode();
214  RN_NODE_PTR target = aEdge->GetTargetNode();
215  bool update = false, changed = false;
216 
217  // If any of nodes belonging to the edge has the flag set,
218  // change it to the closest node that has flag cleared
219  // note: finding the right nodes can be done iteratively to get the best results,
220  // but it is not likely to be worth the time cost
221  do
222  {
223  if( changed || source->GetNoLine() )
224  {
225  changed = false;
226  std::list<RN_NODE_PTR> closest = GetClosestNodes( target,
227  LINE_TARGET_SAME_TAG( source->GetTag() ) );
228 
229  if( !closest.empty() )
230  {
231  RN_NODE_PTR& node = closest.front();
232 
233  if( node != source )
234  {
235  changed = true;
236  update = true;
237  source = node;
238  }
239  }
240  }
241 
242  if( changed || target->GetNoLine() )
243  {
244  changed = false;
245  std::list<RN_NODE_PTR> closest = GetClosestNodes( source,
246  LINE_TARGET_SAME_TAG( target->GetTag() ) );
247 
248  if( !closest.empty() )
249  {
250  RN_NODE_PTR& node = closest.front();
251 
252  if( node != target )
253  {
254  changed = true;
255  update = true;
256  target = node;
257  }
258  }
259  }
260  }
261  while( changed );
262 
263  assert( source->GetTag() >= 0 && target->GetTag() >= 0 );
264  assert( source->GetTag() != target->GetTag() );
265  assert( source != target );
266 
267  // Replace an invalid edge with new, valid one
268  if( update )
269  aEdge.reset( new RN_EDGE_MST( source, target ) );
270 }
271 
272 
274 {
275  aNode->RemoveParent( aParent );
276 
277  if( m_links.RemoveNode( aNode ) )
278  {
279  clearNode( aNode );
280  m_dirty = true;
281  }
282 }
283 
284 
286 {
287  // Save nodes, so they can be cleared later
288  RN_NODE_PTR start = aEdge->GetSourceNode();
289  RN_NODE_PTR end = aEdge->GetTargetNode();
290 
291  start->RemoveParent( aParent );
292  end->RemoveParent( aParent );
293 
294  // Connection has to be removed before running RemoveNode(),
295  // as RN_NODE influences the reference counter
296  m_links.RemoveConnection( aEdge );
297 
298  // Remove nodes associated with the edge. It is done in a safe way, there is a check
299  // if nodes are not used by other edges.
300  if( m_links.RemoveNode( start ) )
301  clearNode( start );
302 
303  if( m_links.RemoveNode( end ) )
304  clearNode( end );
305 
306  m_dirty = true;
307 }
308 
309 
310 const RN_NODE_PTR& RN_LINKS::AddNode( int aX, int aY )
311 {
312  RN_NODE_SET::iterator node;
313  bool wasNewElement;
314 
315  std::tie( node, wasNewElement ) = m_nodes.emplace( std::make_shared<RN_NODE>( aX, aY ) );
316 
317  return *node;
318 }
319 
320 
321 bool RN_LINKS::RemoveNode( const RN_NODE_PTR& aNode )
322 {
323  if( aNode->GetRefCount() == 0 )
324  {
325  m_nodes.erase( aNode );
326 
327  return true;
328  }
329 
330  return false;
331 }
332 
333 
335  unsigned int aDistance )
336 {
337  assert( aNode1 != aNode2 );
338  RN_EDGE_MST_PTR edge = std::make_shared<RN_EDGE_MST>( aNode1, aNode2, aDistance );
339  m_edges.push_back( edge );
340 
341  return edge;
342 }
343 
344 
346 {
347  const RN_LINKS::RN_NODE_SET& boardNodes = m_links.GetNodes();
348  const RN_LINKS::RN_EDGE_LIST& boardEdges = m_links.GetConnections();
349 
350  // Special cases do not need complicated algorithms (actually, it does not work well with
351  // the Delaunay triangulator)
352  if( boardNodes.size() <= 2 )
353  {
354  m_rnEdges.reset( new std::vector<RN_EDGE_MST_PTR>( 0 ) );
355 
356  // Check if the only possible connection exists
357  if( boardEdges.size() == 0 && boardNodes.size() == 2 )
358  {
359  RN_LINKS::RN_NODE_SET::const_iterator last = ++boardNodes.begin();
360 
361  // There can be only one possible connection, but it is missing
362  RN_EDGE_MST_PTR edge = std::make_shared<RN_EDGE_MST>( *boardNodes.begin(), *last );
363  edge->GetSourceNode()->SetTag( 0 );
364  edge->GetTargetNode()->SetTag( 1 );
365  m_rnEdges->push_back( edge );
366  }
367  else
368  {
369  // Set tags to nodes as connected
370  for( RN_NODE_PTR node : boardNodes )
371  node->SetTag( 0 );
372  }
373 
374 
375  return;
376  }
377 
378  // Move and sort (sorting speeds up) all nodes to a vector for the Delaunay triangulation
379  std::vector<RN_NODE_PTR> nodes( boardNodes.size() );
380  std::partial_sort_copy( boardNodes.begin(), boardNodes.end(), nodes.begin(), nodes.end() );
381 
382  TRIANGULATOR triangulator;
383  triangulator.CreateDelaunay( nodes.begin(), nodes.end() );
384  std::unique_ptr<RN_LINKS::RN_EDGE_LIST> triangEdges( triangulator.GetEdges() );
385 
386  // Compute weight/distance for edges resulting from triangulation
387  RN_LINKS::RN_EDGE_LIST::iterator eit, eitEnd;
388  for( eit = (*triangEdges).begin(), eitEnd = (*triangEdges).end(); eit != eitEnd; ++eit )
389  (*eit)->SetWeight( getDistance( (*eit)->GetSourceNode(), (*eit)->GetTargetNode() ) );
390 
391  // Add the currently existing connections list to the results of triangulation
392  std::copy( boardEdges.begin(), boardEdges.end(), std::front_inserter( *triangEdges ) );
393 
394  // Get the minimal spanning tree
395  m_rnEdges.reset( kruskalMST( *triangEdges, nodes ) );
396 }
397 
398 
399 void RN_NET::clearNode( const RN_NODE_PTR& aNode )
400 {
401  if( !m_rnEdges )
402  return;
403 
404  std::vector<RN_EDGE_MST_PTR>::iterator newEnd;
405 
406  // Remove all ratsnest edges for associated with the node
407  newEnd = std::remove_if( m_rnEdges->begin(), m_rnEdges->end(),
408  std::bind( isEdgeConnectingNode, _1, std::cref( aNode ) ) );
409 
410  m_rnEdges->resize( std::distance( m_rnEdges->begin(), newEnd ) );
411 }
412 
413 
415  int aSubpolygonIndex,
416  RN_LINKS& aConnections, const BOX2I& aBBox ) :
417  m_subpolygonIndex( aSubpolygonIndex ),
418  m_bbox( aBBox ),
419  m_parentPolyset( aParent )
420 {
421  const VECTOR2I& p = aParent->CVertex( 0, aSubpolygonIndex );
422 
423  m_node = aConnections.AddNode( p.x, p.y );
424 
425  // Mark it as not appropriate as a destination of ratsnest edges
426  // (edges coming out from a polygon vertex look weird)
427  m_node->SetNoLine( true );
428 }
429 
430 
431 bool RN_POLY::HitTest( const RN_NODE_PTR& aNode ) const
432 {
433  VECTOR2I p( aNode->GetX(), aNode->GetY() );
434 
436 }
437 
438 
440 {
441  // Add edges resulting from nodes being connected by zones
442  processZones();
443  processPads();
444 
445  compute();
446 
447  for( RN_EDGE_MST_PTR& edge : *m_rnEdges )
448  validateEdge( edge );
449 
450  m_dirty = false;
451 }
452 
453 
454 bool RN_NET::AddItem( const D_PAD* aPad )
455 {
456  // Ratsnest is not computed for non-copper pads
457  if( ( aPad->GetLayerSet() & LSET::AllCuMask() ).none() )
458  return false;
459 
460  RN_NODE_PTR node = m_links.AddNode( aPad->GetPosition().x, aPad->GetPosition().y );
461  node->AddParent( aPad );
462  m_pads[aPad].m_Node = node;
463  m_dirty = true;
464 
465  return true;
466 }
467 
468 
469 bool RN_NET::AddItem( const VIA* aVia )
470 {
471  RN_NODE_PTR node = m_links.AddNode( aVia->GetPosition().x, aVia->GetPosition().y );
472  node->AddParent( aVia );
473  m_vias[aVia] = node;
474  m_dirty = true;
475 
476  return true;
477 }
478 
479 
480 bool RN_NET::AddItem( const TRACK* aTrack )
481 {
482  if( aTrack->GetStart() == aTrack->GetEnd() )
483  return false;
484 
485  RN_NODE_PTR start = m_links.AddNode( aTrack->GetStart().x, aTrack->GetStart().y );
486  RN_NODE_PTR end = m_links.AddNode( aTrack->GetEnd().x, aTrack->GetEnd().y );
487 
488  start->AddParent( aTrack );
489  end->AddParent( aTrack );
490  m_tracks[aTrack] = m_links.AddConnection( start, end );
491  m_dirty = true;
492 
493  return true;
494 }
495 
496 
497 bool RN_NET::AddItem( const ZONE_CONTAINER* aZone )
498 {
499  // Prepare a list of polygons (every zone can contain one or more polygons)
500  const SHAPE_POLY_SET& polySet = aZone->GetFilledPolysList();
501 
502  // This ensures that we record aZone as added even if it contains no polygons.
503  (void) m_zones[aZone];
504 
505  for( int i = 0; i < polySet.OutlineCount(); ++i )
506  {
507  const SHAPE_LINE_CHAIN& path = polySet.COutline( i );
508 
509  RN_POLY poly = RN_POLY( &polySet, i, m_links, path.BBox() );
510  m_zones[aZone].m_Polygons.push_back( poly );
511  }
512 
513  m_dirty = true;
514 
515  return true;
516 }
517 
518 
519 bool RN_NET::RemoveItem( const D_PAD* aPad )
520 {
521  PAD_NODE_MAP::iterator it = m_pads.find( aPad );
522 
523  if( it == m_pads.end() )
524  return false;
525 
526  RN_PAD_DATA& pad_data = it->second;
527  removeNode( pad_data.m_Node, aPad );
528 
529  for( RN_EDGE_MST_PTR& edge : pad_data.m_Edges )
530  removeEdge( edge, aPad );
531 
532  m_pads.erase( aPad );
533 
534  return true;
535 }
536 
537 
538 bool RN_NET::RemoveItem( const VIA* aVia )
539 {
540  VIA_NODE_MAP::iterator it = m_vias.find( aVia );
541 
542  if( it == m_vias.end() )
543  return false;
544 
545  removeNode( it->second, aVia );
546  m_vias.erase( it );
547 
548  return true;
549 }
550 
551 
552 bool RN_NET::RemoveItem( const TRACK* aTrack )
553 {
554  TRACK_EDGE_MAP::iterator it = m_tracks.find( aTrack );
555 
556  if( it == m_tracks.end() )
557  return false;
558 
559  removeEdge( it->second, aTrack );
560  m_tracks.erase( it );
561 
562  return true;
563 }
564 
565 
566 bool RN_NET::RemoveItem( const ZONE_CONTAINER* aZone )
567 {
568  ZONE_DATA_MAP::iterator it = m_zones.find( aZone );
569 
570  if( it == m_zones.end() )
571  return false;
572 
573  RN_ZONE_DATA& zoneData = it->second;
574 
575  // Remove all subpolygons that make the zone
576  std::deque<RN_POLY>& polygons = zoneData.m_Polygons;
577  for( RN_POLY& polygon : polygons )
578  removeNode( polygon.GetNode(), aZone );
579  polygons.clear();
580 
581  // Remove all connections added by the zone
582  std::deque<RN_EDGE_MST_PTR>& edges = zoneData.m_Edges;
583 
584  for( RN_EDGE_MST_PTR edge : edges )
585  removeEdge( edge, aZone );
586 
587  edges.clear();
588  m_zones.erase( it );
589 
590  return true;
591 }
592 
593 
594 const RN_NODE_PTR RN_NET::GetClosestNode( const RN_NODE_PTR& aNode ) const
595 {
596  const RN_LINKS::RN_NODE_SET& nodes = m_links.GetNodes();
597  RN_LINKS::RN_NODE_SET::const_iterator it, itEnd;
598 
599  unsigned int minDistance = std::numeric_limits<unsigned int>::max();
600  RN_NODE_PTR closest;
601 
602  for( it = nodes.begin(), itEnd = nodes.end(); it != itEnd; ++it )
603  {
604  RN_NODE_PTR node = *it;
605 
606  // Obviously the distance between node and itself is the shortest,
607  // that's why we have to skip it
608  if( node != aNode )
609  {
610  unsigned int distance = getDistance( node, aNode );
611  if( distance < minDistance )
612  {
613  minDistance = distance;
614  closest = node;
615  }
616  }
617  }
618 
619  return closest;
620 }
621 
622 
624  const RN_NODE_FILTER& aFilter ) const
625 {
626  const RN_LINKS::RN_NODE_SET& nodes = m_links.GetNodes();
627  RN_LINKS::RN_NODE_SET::const_iterator it, itEnd;
628 
629  unsigned int minDistance = std::numeric_limits<unsigned int>::max();
630  RN_NODE_PTR closest;
631 
632  for( it = nodes.begin(), itEnd = nodes.end(); it != itEnd; ++it )
633  {
634  RN_NODE_PTR node = *it;
635 
636  // Obviously the distance between node and itself is the shortest,
637  // that's why we have to skip it
638  if( node != aNode && aFilter( node ) )
639  {
640  unsigned int distance = getDistance( node, aNode );
641 
642  if( distance < minDistance )
643  {
644  minDistance = distance;
645  closest = node;
646  }
647  }
648  }
649 
650  return closest;
651 }
652 
653 
654 std::list<RN_NODE_PTR> RN_NET::GetClosestNodes( const RN_NODE_PTR& aNode, int aNumber ) const
655 {
656  std::list<RN_NODE_PTR> closest;
657  const RN_LINKS::RN_NODE_SET& nodes = m_links.GetNodes();
658 
659  // Copy nodes
660  std::copy( nodes.begin(), nodes.end(), std::back_inserter( closest ) );
661 
662  // Sort by the distance from aNode
663  closest.sort( std::bind( sortDistance, std::cref( aNode ), _1, _2 ) );
664 
665  // aNode should not be returned in the results
666  closest.remove( aNode );
667 
668  // Trim the result to the asked size
669  if( aNumber > 0 )
670  closest.resize( std::min( (size_t)aNumber, nodes.size() ) );
671 
672  return closest;
673 }
674 
675 
676 std::list<RN_NODE_PTR> RN_NET::GetClosestNodes( const RN_NODE_PTR& aNode,
677  const RN_NODE_FILTER& aFilter, int aNumber ) const
678 {
679  std::list<RN_NODE_PTR> closest;
680  const RN_LINKS::RN_NODE_SET& nodes = m_links.GetNodes();
681 
682  // Copy filtered nodes
683  std::copy_if( nodes.begin(), nodes.end(), std::back_inserter( closest ), std::cref( aFilter ) );
684 
685  // Sort by the distance from aNode
686  closest.sort( std::bind( sortDistance, std::cref( aNode ), _1, _2 ) );
687 
688  // aNode should not be returned in the results
689  closest.remove( aNode );
690 
691  // Trim the result to the asked size
692  if( aNumber > 0 )
693  closest.resize( std::min( static_cast<size_t>( aNumber ), nodes.size() ) );
694 
695  return closest;
696 }
697 
698 
700 {
701  for( RN_NODE_PTR node : GetNodes( aItem ) )
702  {
703  // Block all nodes, so they do not become targets for dynamic ratsnest lines
704  AddBlockedNode( node );
705 
706  // Filter out junctions
707  if( node->GetRefCount() == 1 )
708  m_simpleNodes.insert( node );
709  }
710 }
711 
712 
713 std::list<RN_NODE_PTR> RN_NET::GetNodes( const BOARD_CONNECTED_ITEM* aItem ) const
714 {
715  std::list<RN_NODE_PTR> nodes;
716 
717  switch( aItem->Type() )
718  {
719  case PCB_PAD_T:
720  {
721  PAD_NODE_MAP::const_iterator it = m_pads.find( static_cast<const D_PAD*>( aItem ) );
722 
723  if( it != m_pads.end() )
724  nodes.push_back( it->second.m_Node );
725  }
726  break;
727 
728  case PCB_VIA_T:
729  {
730  VIA_NODE_MAP::const_iterator it = m_vias.find( static_cast<const VIA*>( aItem ) );
731 
732  if( it != m_vias.end() )
733  nodes.push_back( it->second );
734  }
735  break;
736 
737  case PCB_TRACE_T:
738  {
739  TRACK_EDGE_MAP::const_iterator it = m_tracks.find( static_cast<const TRACK*>( aItem ) );
740 
741  if( it != m_tracks.end() )
742  {
743  nodes.push_back( it->second->GetSourceNode() );
744  nodes.push_back( it->second->GetTargetNode() );
745  }
746  }
747  break;
748 
749  case PCB_ZONE_AREA_T:
750  {
751  ZONE_DATA_MAP::const_iterator itz = m_zones.find( static_cast<const ZONE_CONTAINER*>( aItem ) );
752 
753  if( itz != m_zones.end() )
754  {
755  const std::deque<RN_POLY>& polys = itz->second.m_Polygons;
756 
757  for( std::deque<RN_POLY>::const_iterator it = polys.begin(); it != polys.end(); ++it )
758  nodes.push_back( it->GetNode() );
759  }
760  }
761  break;
762 
763  default:
764  break;
765  }
766 
767  return nodes;
768 }
769 
770 
771 void RN_NET::GetAllItems( std::list<BOARD_CONNECTED_ITEM*>& aOutput, RN_ITEM_TYPE aType ) const
772 {
773  if( aType & RN_PADS )
774  {
775  for( auto it : m_pads )
776  aOutput.push_back( const_cast<D_PAD*>( it.first ) );
777  }
778 
779  if( aType & RN_VIAS )
780  {
781  for( auto it : m_vias )
782  aOutput.push_back( const_cast<VIA*>( it.first ) );
783  }
784 
785  if( aType & RN_TRACKS )
786  {
787  for( auto it : m_tracks )
788  aOutput.push_back( const_cast<TRACK*>( it.first ) );
789  }
790 
791  if( aType & RN_ZONES )
792  {
793  for( auto it : m_zones )
794  aOutput.push_back( const_cast<ZONE_CONTAINER*>( it.first ) );
795  }
796 }
797 
798 
800 {
801  for( const RN_NODE_PTR& node : m_blockedNodes )
802  node->SetNoLine( false );
803 
804  m_blockedNodes.clear();
805  m_simpleNodes.clear();
806 }
807 
808 
810  std::list<BOARD_CONNECTED_ITEM*>& aOutput,
811  RN_ITEM_TYPE aTypes ) const
812 {
813  std::list<RN_NODE_PTR> nodes = GetNodes( aItem );
814  assert( !nodes.empty() );
815 
816  int tag = nodes.front()->GetTag();
817  assert( tag >= 0 );
818 
819  if( aTypes & RN_PADS )
820  {
821  for( PAD_NODE_MAP::const_iterator it = m_pads.begin(); it != m_pads.end(); ++it )
822  {
823  if( it->second.m_Node->GetTag() == tag )
824  aOutput.push_back( const_cast<D_PAD*>( it->first ) );
825  }
826  }
827 
828  if( aTypes & RN_VIAS )
829  {
830  for( VIA_NODE_MAP::const_iterator it = m_vias.begin(); it != m_vias.end(); ++it )
831  {
832  if( it->second->GetTag() == tag )
833  aOutput.push_back( const_cast<VIA*>( it->first ) );
834  }
835  }
836 
837  if( aTypes & RN_TRACKS )
838  {
839  for( TRACK_EDGE_MAP::const_iterator it = m_tracks.begin(); it != m_tracks.end(); ++it )
840  {
841  if( it->second->GetTag() == tag )
842  aOutput.push_back( const_cast<TRACK*>( it->first ) );
843  }
844  }
845 
846  if( aTypes & RN_ZONES )
847  {
848  for( ZONE_DATA_MAP::const_iterator it = m_zones.begin(); it != m_zones.end(); ++it )
849  {
850  for( const RN_EDGE_MST_PTR& edge : it->second.m_Edges )
851  {
852  if( edge->GetTag() == tag )
853  {
854  aOutput.push_back( const_cast<ZONE_CONTAINER*>( it->first ) );
855  break;
856  }
857  }
858  }
859  }
860 }
861 
862 
863 void RN_DATA::AddSimple( const BOARD_ITEM* aItem )
864 {
865  if( aItem->IsConnected() )
866  {
867  const BOARD_CONNECTED_ITEM* item = static_cast<const BOARD_CONNECTED_ITEM*>( aItem );
868  int net = item->GetNetCode();
869 
870  // Do not process orphaned & unconnected items
871  if( net <= NETINFO_LIST::UNCONNECTED )
872  return;
873 
874  m_nets[net].AddSimple( item );
875  }
876  else if( aItem->Type() == PCB_MODULE_T )
877  {
878  const MODULE* module = static_cast<const MODULE*>( aItem );
879 
880  for( const D_PAD* pad = module->Pads().GetFirst(); pad; pad = pad->Next() )
881  AddSimple( pad );
882  }
883 }
884 
885 
886 void RN_DATA::AddBlocked( const BOARD_ITEM* aItem )
887 {
888  if( aItem->IsConnected() )
889  {
890  const BOARD_CONNECTED_ITEM* item = static_cast<const BOARD_CONNECTED_ITEM*>( aItem );
891  int net = item->GetNetCode();
892 
893  // Do not process orphaned & unconnected items
894  if( net <= NETINFO_LIST::UNCONNECTED )
895  return;
896 
897  // Block all nodes belonging to the item
898  for( RN_NODE_PTR node : m_nets[net].GetNodes( item ) )
899  m_nets[net].AddBlockedNode( node );
900  }
901  else if( aItem->Type() == PCB_MODULE_T )
902  {
903  const MODULE* module = static_cast<const MODULE*>( aItem );
904 
905  for( const D_PAD* pad = module->Pads().GetFirst(); pad; pad = pad->Next() )
906  AddBlocked( pad );
907  }
908 }
909 
910 
912  std::list<BOARD_CONNECTED_ITEM*>& aOutput,
913  RN_ITEM_TYPE aTypes ) const
914 {
915  int net = aItem->GetNetCode();
916 
917  if( net < 1 )
918  return;
919 
920  assert( net < (int) m_nets.size() );
921 
922  m_nets[net].GetConnectedItems( aItem, aOutput, aTypes );
923 }
924 
925 
926 void RN_DATA::GetNetItems( int aNetCode, std::list<BOARD_CONNECTED_ITEM*>& aOutput,
927  RN_ITEM_TYPE aTypes ) const
928 {
929  if( aNetCode < 1 )
930  return;
931 
932  assert( aNetCode < (int) m_nets.size() );
933 
934  m_nets[aNetCode].GetAllItems( aOutput, aTypes );
935 }
936 
937 
939 {
940  int net1 = aItem->GetNetCode();
941  int net2 = aOther->GetNetCode();
942 
943  if( net1 < 1 || net2 < 1 || net1 != net2 )
944  return false;
945 
946  assert( net1 < (int) m_nets.size() && net2 < (int) m_nets.size() );
947 
948  // net1 == net2
949  std::list<RN_NODE_PTR> items1 = m_nets[net1].GetNodes( aItem );
950  std::list<RN_NODE_PTR> items2 = m_nets[net1].GetNodes( aOther );
951 
952  assert( !items1.empty() && !items2.empty() );
953 
954  return ( items1.front()->GetTag() == items2.front()->GetTag() );
955 }
956 
957 
959 {
960  int count = 0;
961 
962  for( unsigned i = 0; i < m_nets.size(); ++i )
963  {
964  const std::vector<RN_EDGE_MST_PTR>* unconnected = m_nets[i].GetUnconnected();
965 
966  if( unconnected )
967  count += unconnected->size();
968  }
969 
970  return count;
971 }
972 
973 
975 {
976  for( ZONE_DATA_MAP::iterator it = m_zones.begin(); it != m_zones.end(); ++it )
977  {
978  const ZONE_CONTAINER* zone = it->first;
979  RN_ZONE_DATA& zoneData = it->second;
980 
981  // Reset existing connections
982  for( RN_EDGE_MST_PTR edge : zoneData.m_Edges )
983  m_links.RemoveConnection( edge );
984 
985  zoneData.m_Edges.clear();
986  LSET layers = zone->GetLayerSet();
987 
988  // Compute new connections
989  RN_LINKS::RN_NODE_SET candidates = m_links.GetNodes();
990  RN_LINKS::RN_NODE_SET::const_iterator point, pointEnd;
991 
992  // Sorting by area should speed up the processing, as smaller polygons are computed
993  // faster and may reduce the number of points for further checks
994  std::sort( zoneData.m_Polygons.begin(), zoneData.m_Polygons.end(), sortArea );
995 
996  for( std::deque<RN_POLY>::iterator poly = zoneData.m_Polygons.begin(),
997  polyEnd = zoneData.m_Polygons.end(); poly != polyEnd; ++poly )
998  {
999  const RN_NODE_PTR& node = poly->GetNode();
1000 
1001  point = candidates.begin();
1002  pointEnd = candidates.end();
1003 
1004  while( point != pointEnd )
1005  {
1006  if( *point != node && ( (*point)->GetLayers() & layers ).any()
1007  && poly->HitTest( *point ) )
1008  {
1009  //(*point)->AddParent( zone ); // do not assign parent for helper links
1010 
1011  RN_EDGE_MST_PTR connection = m_links.AddConnection( node, *point );
1012  zoneData.m_Edges.push_back( connection );
1013 
1014  // This point already belongs to a polygon, we do not need to check it anymore
1015  point = candidates.erase( point );
1016  pointEnd = candidates.end();
1017  }
1018  else
1019  {
1020  ++point;
1021  }
1022  }
1023  }
1024  }
1025 }
1026 
1027 
1029 {
1030  for( PAD_NODE_MAP::iterator it = m_pads.begin(); it != m_pads.end(); ++it )
1031  {
1032  const D_PAD* pad = it->first;
1033  RN_NODE_PTR node = it->second.m_Node;
1034  std::deque<RN_EDGE_MST_PTR>& edges = it->second.m_Edges;
1035 
1036  // Reset existing connections
1037  for( RN_EDGE_MST_PTR edge : edges )
1038  m_links.RemoveConnection( edge );
1039 
1040  LSET layers = pad->GetLayerSet();
1041  const RN_LINKS::RN_NODE_SET& candidates = m_links.GetNodes();
1042  RN_LINKS::RN_NODE_SET::const_iterator point, pointEnd;
1043 
1044  point = candidates.begin();
1045  pointEnd = candidates.end();
1046 
1047  while( point != pointEnd )
1048  {
1049  if( *point != node && ( (*point)->GetLayers() & layers ).any() &&
1050  pad->HitTest( wxPoint( (*point)->GetX(), (*point)->GetY() ) ) )
1051  {
1052  //(*point)->AddParent( pad ); // do not assign parent for helper links
1053 
1054  RN_EDGE_MST_PTR connection = m_links.AddConnection( node, *point );
1055  edges.push_back( connection );
1056  }
1057 
1058  ++point;
1059  }
1060  }
1061 }
1062 
1063 
1064 bool RN_DATA::Add( const BOARD_ITEM* aItem )
1065 {
1066  int net = NETINFO_LIST::ORPHANED;
1067 
1068  if( aItem->IsConnected() )
1069  {
1070  net = static_cast<const BOARD_CONNECTED_ITEM*>( aItem )->GetNetCode();
1071  }
1072  else if( aItem->Type() == PCB_MODULE_T )
1073  {
1074  const MODULE* module = static_cast<const MODULE*>( aItem );
1075 
1076  for( const D_PAD* pad = module->Pads().GetFirst(); pad; pad = pad->Next() )
1077  {
1078  net = pad->GetNetCode();
1079 
1080  // Do not process orphaned items
1081  if( net <= NETINFO_LIST::ORPHANED )
1082  continue;
1083 
1084  Add( pad );
1085  }
1086 
1087  return true;
1088  }
1089  else if( aItem->Type() == PCB_NETINFO_T )
1090  {
1091  int netCount = m_board->GetNetCount();
1092 
1093  if( (unsigned) netCount > m_nets.size() )
1094  m_nets.resize( netCount );
1095 
1096  return true;
1097  }
1098  else
1099  {
1100  return false;
1101  }
1102 
1103  if( net < 0 )
1104  return false;
1105 
1106  // Autoresize is necessary e.g. for module editor
1107  if( net >= (int) m_nets.size() )
1108  m_nets.resize( net + 1 );
1109 
1110  switch( aItem->Type() )
1111  {
1112  case PCB_PAD_T:
1113  return m_nets[net].AddItem( static_cast<const D_PAD*>( aItem ) );
1114  break;
1115 
1116  case PCB_TRACE_T:
1117  return m_nets[net].AddItem( static_cast<const TRACK*>( aItem ) );
1118  break;
1119 
1120  case PCB_VIA_T:
1121  return m_nets[net].AddItem( static_cast<const VIA*>( aItem ) );
1122  break;
1123 
1124  case PCB_ZONE_AREA_T:
1125  return m_nets[net].AddItem( static_cast<const ZONE_CONTAINER*>( aItem ) );
1126  break;
1127 
1128  default:
1129  break;
1130  }
1131 
1132  return false;
1133 }
1134 
1135 
1136 bool RN_DATA::Remove( const BOARD_ITEM* aItem )
1137 {
1138  int net = NETINFO_LIST::ORPHANED;
1139 
1140  if( aItem->IsConnected() )
1141  {
1142  net = static_cast<const BOARD_CONNECTED_ITEM*>( aItem )->GetNetCode();
1143  }
1144  else if( aItem->Type() == PCB_MODULE_T )
1145  {
1146  const MODULE* module = static_cast<const MODULE*>( aItem );
1147 
1148  for( const D_PAD* pad = module->Pads().GetFirst(); pad; pad = pad->Next() )
1149  {
1150  net = pad->GetNetCode();
1151 
1152  // Do not process orphaned items
1153  if( net <= NETINFO_LIST::ORPHANED )
1154  continue;
1155 
1156  Remove( pad );
1157  }
1158 
1159  return true;
1160  }
1161  else
1162  {
1163  return false;
1164  }
1165 
1166  if( net < 0 )
1167  return false;
1168 
1169  // Autoresize is necessary e.g. for module editor
1170  if( net >= (int) m_nets.size() )
1171  {
1172  m_nets.resize( net + 1 );
1173  return false; // if it was resized, then surely the item had not been added before
1174  }
1175 
1176  switch( aItem->Type() )
1177  {
1178  case PCB_PAD_T:
1179  return m_nets[net].RemoveItem( static_cast<const D_PAD*>( aItem ) );
1180  break;
1181 
1182  case PCB_TRACE_T:
1183  return m_nets[net].RemoveItem( static_cast<const TRACK*>( aItem ) );
1184  break;
1185 
1186  case PCB_VIA_T:
1187  return m_nets[net].RemoveItem( static_cast<const VIA*>( aItem ) );
1188  break;
1189 
1190  case PCB_ZONE_AREA_T:
1191  return m_nets[net].RemoveItem( static_cast<const ZONE_CONTAINER*>( aItem ) );
1192  break;
1193 
1194  default:
1195  break;
1196  }
1197 
1198  return false;
1199 }
1200 
1201 
1202 bool RN_DATA::Update( const BOARD_ITEM* aItem )
1203 {
1204  if( Remove( aItem ) )
1205  {
1206  bool res = Add( aItem );
1207  assert( res );
1208  (void) res;
1209  return true;
1210  }
1211 
1212  return false;
1213 }
1214 
1215 
1217 {
1218  int netCount = m_board->GetNetCount();
1219  m_nets.clear();
1220  m_nets.resize( netCount );
1221  int netCode;
1222 
1223  // Iterate over all items that may need to be connected
1224  for( MODULE* module = m_board->m_Modules; module; module = module->Next() )
1225  {
1226  for( D_PAD* pad = module->Pads().GetFirst(); pad; pad = pad->Next() )
1227  {
1228  netCode = pad->GetNetCode();
1229 
1230  assert( netCode >= 0 && netCode < netCount );
1231 
1232  if( netCode >= 0 && netCode < netCount )
1233  m_nets[netCode].AddItem( pad );
1234  }
1235  }
1236 
1237  for( TRACK* track = m_board->m_Track; track; track = track->Next() )
1238  {
1239  netCode = track->GetNetCode();
1240 
1241  assert( netCode >= 0 && netCode < netCount );
1242 
1243  if( netCode >= 0 && netCode < netCount )
1244  {
1245  if( track->Type() == PCB_VIA_T )
1246  m_nets[netCode].AddItem( static_cast<VIA*>( track ) );
1247  else if( track->Type() == PCB_TRACE_T )
1248  m_nets[netCode].AddItem( track );
1249  }
1250  }
1251 
1252  for( int i = 0; i < m_board->GetAreaCount(); ++i )
1253  {
1254  ZONE_CONTAINER* zone = m_board->GetArea( i );
1255 
1256  netCode = zone->GetNetCode();
1257 
1258  assert( netCode >= 0 && netCode < netCount );
1259 
1260  if( netCode >= 0 && netCode < netCount )
1261  m_nets[netCode].AddItem( zone );
1262  }
1263 
1264  Recalculate();
1265 }
1266 
1267 
1268 void RN_DATA::Recalculate( int aNet )
1269 {
1270  unsigned int netCount = m_board->GetNetCount();
1271 
1272  if( aNet <= 0 && netCount > 1 ) // Recompute everything
1273  {
1274 #ifdef PROFILE
1275  PROF_COUNTER totalRealTime;
1276 #endif
1277 
1278  unsigned int i;
1279 
1280 #ifdef USE_OPENMP
1281  #pragma omp parallel shared(netCount) private(i)
1282  {
1283  #pragma omp for schedule(guided, 1)
1284 #else /* USE_OPENMP */
1285  {
1286 #endif
1287  // Start with net number 1, as 0 stands for not connected
1288  for( i = 1; i < netCount; ++i )
1289  {
1290  if( m_nets[i].IsDirty() )
1291  updateNet( i );
1292  }
1293  } /* end of parallel section */
1294 #ifdef PROFILE
1295  totalRealTime.Stop();
1296  wxLogDebug( "Recalculate all nets: %.1f ms", totalRealTime.msecs() );
1297 #endif /* PROFILE */
1298  }
1299  else if( aNet > 0 ) // Recompute only specific net
1300  {
1301  updateNet( aNet );
1302  }
1303 }
1304 
1305 
1306 void RN_DATA::updateNet( int aNetCode )
1307 {
1308  assert( aNetCode < (int) m_nets.size() );
1309 
1310  if( aNetCode < 1 || aNetCode > (int) m_nets.size() )
1311  return;
1312 
1313  m_nets[aNetCode].ClearSimple();
1314  m_nets[aNetCode].Update();
1315 }
void removeNode(RN_NODE_PTR &aNode, const BOARD_CONNECTED_ITEM *aParent)
Removes a link between a node and a parent, and clears linked edges if it was the last parent...
const SHAPE_POLY_SET * m_parentPolyset
Polygon set containing the geometry
static LSET AllCuMask(int aCuLayerCount=MAX_CU_LAYERS)
Function AllCuMask returns a mask holding the requested number of Cu LAYER_IDs.
Definition: lset.cpp:638
void Stop()
save the time when this function was called, and set the counter stane to stop
Definition: profile.h:82
KICAD_T Type() const
Function Type()
Definition: base_struct.h:198
Class ZONE_CONTAINER handles a list of polygons defining a copper zone.
Definition: class_zone.h:78
void GetConnectedItems(const BOARD_CONNECTED_ITEM *aItem, std::list< BOARD_CONNECTED_ITEM * > &aOutput, RN_ITEM_TYPE aTypes=RN_ALL) const
Function GetConnectedItems() Adds items that are connected together to a list.
hed::EDGE_PTR RN_EDGE_PTR
Definition: ratsnest_data.h:66
void Update()
Function Update() Recomputes ratsnest for a net.
std::deque< RN_POLY > m_Polygons
Subpolygons belonging to a zone
void ClearSimple()
Function ClearSimple() Removes all nodes and edges that are used for displaying ratsnest in simple mo...
bool HitTest(const wxPoint &aPosition) const override
Function HitTest tests if aPosition is contained within or on the bounding area of an item...
Definition: class_pad.cpp:700
void processPads()
Adds additional edges to account for connections made by items located in pads areas.
Leaves nodes that can be a ratsnest line target and have a specific tag
Class BOARD_ITEM is a base class for any item which can be embedded within the BOARD container class...
hed::NODE_PTR RN_NODE_PTR
Definition: ratsnest_data.h:64
ZONE_DATA_MAP m_zones
Map that associates groups of subpolygons in the ratsnest model to respective zones.
bool operator==(const RN_NODE_PTR &aFirst, const RN_NODE_PTR &aSecond)
bool m_dirty
Flag indicating necessity of recalculation of ratsnest for a net.
Class BOARD to handle a board.
Class that computes missing connections on a PCB.
Structure to hold ratsnest data for ZONE_CONTAINER objects.
bool RemoveItem(const D_PAD *aPad)
Function RemoveItem() Removes all nodes and edges associated with selected pad, so they are not taken...
MODULE * Next() const
Definition: class_module.h:99
class ZONE_CONTAINER, a zone area
Definition: typeinfo.h:114
RN_LINKS m_links
int m_subpolygonIndex
Index of the outline in the parent polygon set
RN_NODE_AND_FILTER operator&&(const RN_NODE_FILTER &aFilter1, const RN_NODE_FILTER &aFilter2)
static bool sortDistance(const RN_NODE_PTR &aOrigin, const RN_NODE_PTR &aNode1, const RN_NODE_PTR &aNode2)
ecoord_type GetArea() const
Function GetArea returns the area of the rectangle.
Definition: box2.h:391
Classes to handle copper zones.
class D_PAD, a pad in a footprint
Definition: typeinfo.h:102
bool Update(const BOARD_ITEM *aItem)
Function Update() Updates the ratsnest data for an item.
static bool sortWeight(const RN_EDGE_PTR &aEdge1, const RN_EDGE_PTR &aEdge2)
void compute()
Recomputes ratsnset from scratch.
int OutlineCount() const
Returns the number of outlines in the set
void GetAllItems(std::list< BOARD_CONNECTED_ITEM * > &aOutput, RN_ITEM_TYPE aType=RN_ALL) const
Function GetAllItems() Adds all stored items to a list.
PAD_NODE_MAP m_pads
Map that associates nodes in the ratsnest model to respective nodes.
The class PROF_COUNTER is a small class to help profiling.
Definition: profile.h:45
Class BOARD_CONNECTED_ITEM is a base class derived from BOARD_ITEM for items that can be connected an...
static std::vector< RN_EDGE_MST_PTR > * kruskalMST(RN_LINKS::RN_EDGE_LIST &aEdges, std::vector< RN_NODE_PTR > &aNodes)
const wxPoint & GetEnd() const
Definition: class_track.h:117
Functions relatives to tracks, vias and segments used to fill zones.
class TRACK, a track segment (segment on a copper layer)
Definition: typeinfo.h:107
Structureo to hold ratsnest data for D_PAD objects.
std::deque< RN_EDGE_MST_PTR > m_Edges
Connections to other nodes
bool Remove(const BOARD_ITEM *aItem)
Function Remove() Removes an item from the ratsnest data.
void AddSimple(const BOARD_CONNECTED_ITEM *aItem)
Function AddSimple() Changes drawing mode for an item to simple (i.e.
void validateEdge(RN_EDGE_MST_PTR &aEdge)
Validates edge, i.e.
bool HitTest(const RN_NODE_PTR &aNode) const
Function HitTest() Tests if selected node is located within polygon boundaries.
const BOARD * m_board
Board to be processed.
TRACK_EDGE_MAP m_tracks
Map that associates edges in the ratsnest model to respective tracks.
static bool isEdgeConnectingNode(const RN_EDGE_PTR &aEdge, const RN_NODE_PTR &aNode)
class MODULE, a footprint
Definition: typeinfo.h:101
Class RN_POLY Describes a single subpolygon (ZONE_CONTAINER is supposed to contain one or more of tho...
const RN_NODE_PTR GetClosestNode(const RN_NODE_PTR &aNode) const
Function GetClosestNode() Returns a single node that lies in the shortest distance from a specific no...
bool AreConnected(const BOARD_CONNECTED_ITEM *aItem, const BOARD_CONNECTED_ITEM *aOther)
Function AreConnected() Checks if two items are connected with copper.
Class LSET is a set of LAYER_IDs.
const BOX2I BBox(int aClearance=0) const override
Function BBox()
bool sortArea(const RN_POLY &aP1, const RN_POLY &aP2)
Class SHAPE_POLY_SET.
bool AddItem(const D_PAD *aPad)
Function AddItem() Adds an appropriate node associated with selected pad, so it is taken into account...
const wxPoint & GetStart() const
Definition: class_track.h:120
const wxPoint & GetPosition() const override
Definition: class_pad.h:170
std::shared_ptr< hed::EDGE_MST > RN_EDGE_MST_PTR
Definition: ratsnest_data.h:69
LSET GetLayerSet() const override
Function GetLayerSet returns a "layer mask", which is a bitmap of all layers on which the TRACK segme...
Definition: class_pad.h:235
void ProcessBoard()
Function ProcessBoard() Prepares data for computing (computes a list of current nodes and connections...
void GetNetItems(int aNetCode, std::list< BOARD_CONNECTED_ITEM * > &aOutput, RN_ITEM_TYPE aTypes=RN_ALL) const
Function GetNetItems() Adds all items that belong to a certain net to a list.
T * GetFirst() const
Function GetFirst returns the first T* in the list without removing it, or NULL if the list is empty...
Definition: dlist.h:163
std::unordered_set< RN_NODE_PTR > m_simpleNodes
Nodes to be displayed using the simplified ratsnest algorithm.
virtual LSET GetLayerSet() const
Function GetLayerSet returns a "layer mask", which is a bitmap of all layers on which the TRACK segme...
D_PAD * Next() const
Definition: class_pad.h:106
void clearNode(const RN_NODE_PTR &aNode)
Removes all ratsnest edges for a given node.
static uint64_t getDistance(const RN_NODE_PTR &aNode1, const RN_NODE_PTR &aNode2)
std::shared_ptr< std::vector< RN_EDGE_MST_PTR > > m_rnEdges
Vector of edges that makes ratsnest for a given net.
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
hed::EDGE_MST RN_EDGE_MST
Definition: ratsnest_data.h:67
int GetAreaCount() const
Function GetAreaCount.
Definition: class_board.h:1051
RN_ITEM_TYPE
Types of items that are handled by the class
Definition: ratsnest_data.h:53
void updateNet(int aNetCode)
Function updateNet() Recomputes ratsnest for a single net.
const SHAPE_POLY_SET & GetFilledPolysList() const
Function GetFilledPolysList returns a reference to the list of filled polygons.
Definition: class_zone.h:470
std::vector< RN_NET > m_nets
Stores information about ratsnest grouped by net numbers.
Pad object description.
const VECTOR2I & CVertex(int index, int aOutline=-1, int aHole=-1) const
Returns the index-th vertex in a given hole outline within a given outline
static const int ORPHANED
Constant that forces initialization of a netinfo item to the NETINFO_ITEM ORPHANED (typically -1) whe...
RN_POLY(const SHAPE_POLY_SET *aParent, int aSubpolygonIndex, RN_LINKS &aConnections, const BOX2I &aBBox)
void Recalculate(int aNet=-1)
Function Recalculate() Recomputes ratsnest for selected net number or all nets that need updating...
int GetNetCode() const
Function GetNetCode.
double msecs() const
Definition: profile.h:121
void processZones()
Adds appropriate edges for nodes that are connected by zones.
void CreateDelaunay(NODES_CONTAINER::iterator aFirst, NODES_CONTAINER::iterator aLast)
Creates a Delaunay triangulation from a set of points.
Definition: hetriang.cpp:195
TRACK * Next() const
Definition: class_track.h:97
BOX2I m_bbox
Bounding box of the polygon.
RN_NODE_PTR m_Node
Node representing the pad.
ZONE_CONTAINER * GetArea(int index) const
Function GetArea returns the Area (Zone Container) at a given index.
Definition: class_board.h:1022
#define max(a, b)
Definition: auxiliary.h:86
DLIST< MODULE > m_Modules
Definition: class_board.h:243
Class SHAPE_LINE_CHAIN.
std::list< RN_NODE_PTR > GetClosestNodes(const RN_NODE_PTR &aNode, int aNumber=-1) const
Function GetClosestNodes() Returns list of nodes sorted by the distance from a specific node...
void removeEdge(RN_EDGE_MST_PTR &aEdge, const BOARD_CONNECTED_ITEM *aParent)
Removes a link between an edge and a parent, and clears its node data if it was the last parent...
virtual bool IsConnected() const
Function IsConnected() Returns information if the object is derived from BOARD_CONNECTED_ITEM.
bool operator!=(const RN_NODE_PTR &aFirst, const RN_NODE_PTR &aSecond)
class NETINFO_ITEM, a description of a net
Definition: typeinfo.h:116
const wxPoint & GetPosition() const override
Definition: class_track.h:415
bool Add(const BOARD_ITEM *aItem)
Function Add() Adds an item to the ratsnest data.
class VIA, a via (like a track segment on a copper layer)
Definition: typeinfo.h:108
DLIST< D_PAD > & Pads()
Definition: class_module.h:133
std::list< RN_NODE_PTR > GetNodes(const BOARD_CONNECTED_ITEM *aItem) const
Function GetNodes() Returns list of nodes that are associated with a given item.
DLIST< TRACK > m_Track
Definition: class_board.h:244
void AddBlocked(const BOARD_ITEM *aItem)
Function AddBlocked() Specifies an item as not suitable as a ratsnest line target (i...
Module description (excepted pads)
std::deque< RN_EDGE_MST_PTR > m_Edges
Helper nodes that make for connections to items located in the pad area.
std::unordered_set< RN_NODE_PTR > m_blockedNodes
List of nodes which will not be used as ratsnest target nodes.
void GetConnectedItems(const BOARD_CONNECTED_ITEM *aItem, std::list< BOARD_CONNECTED_ITEM * > &aOutput, RN_ITEM_TYPE aTypes=RN_ALL) const
Function GetConnectedItems() Adds items that are connected together to a list.
RN_NODE_PTR m_node
Node representing a polygon (it has the same coordinates as the first point of its bounding polyline...
void AddSimple(const BOARD_ITEM *aItem)
Function AddSimple() Sets an item to be drawn in simple mode (i.e.
VIA_NODE_MAP m_vias
Map that associates nodes in the ratsnest model to respective vias.
void AddBlockedNode(RN_NODE_PTR &aNode)
Function AddBlockedNode() Specifies a node as not suitable as a ratsnest line target (i...
static const int UNCONNECTED
Constant that holds the "unconnected net" number (typically 0) all items "connected" to this net are ...
Triangulation class for the half-edge data structure with adaption to TTL.
Definition: hetriang.h:384
RN_NODE_OR_FILTER operator||(const RN_NODE_FILTER &aFilter1, const RN_NODE_FILTER &aFilter2)
bool Contains(const VECTOR2I &aP, int aSubpolyIndex=-1) const
Returns true is a given subpolygon contains the point aP.
General interface for filtering out nodes in search functions.
Definition: ratsnest_data.h:78
unsigned GetNetCount() const
Function GetNetCount.
Definition: class_board.h:814
#define min(a, b)
Definition: auxiliary.h:85
int GetUnconnectedCount() const
Function GetUnconnectedCount() Returns the number of missing connections.