KiCad PCB EDA Suite
pns_node.cpp
Go to the documentation of this file.
1 /*
2  * KiRouter - a push-and-(sometimes-)shove PCB router
3  *
4  * Copyright (C) 2013-2019 CERN
5  * Copyright (C) 2016-2021 KiCad Developers, see AUTHORS.txt for contributors.
6  *
7  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
8  *
9  * This program is free software: you can redistribute it and/or modify it
10  * under the terms of the GNU General Public License as published by the
11  * Free Software Foundation, either version 3 of the License, or (at your
12  * option) any later version.
13  *
14  * This program is distributed in the hope that it will be useful, but
15  * WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17  * General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License along
20  * with this program. If not, see <http://www.gnu.org/licenses/>.
21  */
22 
23 #include <vector>
24 #include <cassert>
25 #include <utility>
26 
27 #include <math/vector2d.h>
28 
29 #include <geometry/seg.h>
31 
32 #include "pns_arc.h"
33 #include "pns_item.h"
34 #include "pns_line.h"
35 #include "pns_node.h"
36 #include "pns_via.h"
37 #include "pns_solid.h"
38 #include "pns_joint.h"
39 #include "pns_index.h"
40 #include "pns_debug_decorator.h"
41 #include "pns_router.h"
42 
43 
44 namespace PNS {
45 
46 #ifdef DEBUG
47 static std::unordered_set<NODE*> allocNodes;
48 #endif
49 
51 {
52  m_depth = 0;
53  m_root = this;
54  m_parent = NULL;
55  m_maxClearance = 800000; // fixme: depends on how thick traces are.
57  m_index = new INDEX;
58 
59 #ifdef DEBUG
60  allocNodes.insert( this );
61 #endif
62 }
63 
64 
66 {
67  if( !m_children.empty() )
68  {
69  wxLogTrace( "PNS", "attempting to free a node that has kids." );
70  assert( false );
71  }
72 
73 #ifdef DEBUG
74  if( allocNodes.find( this ) == allocNodes.end() )
75  {
76  wxLogTrace( "PNS", "attempting to free an already-free'd node." );
77  assert( false );
78  }
79 
80  allocNodes.erase( this );
81 #endif
82 
83  m_joints.clear();
84 
85  for( ITEM* item : *m_index )
86  {
87  if( item->BelongsTo( this ) )
88  delete item;
89  }
90 
92  unlinkParent();
93 
94  delete m_index;
95 }
96 
97 int NODE::GetClearance( const ITEM* aA, const ITEM* aB ) const
98 {
99  if( !m_ruleResolver )
100  return 100000;
101 
102  return m_ruleResolver->Clearance( aA, aB );
103 }
104 
105 
106 int NODE::GetHoleClearance( const ITEM* aA, const ITEM* aB ) const
107  {
108  if( !m_ruleResolver )
109  return 0;
110 
111  return m_ruleResolver->HoleClearance( aA, aB );
112  }
113 
114 
115 int NODE::GetHoleToHoleClearance( const ITEM* aA, const ITEM* aB ) const
116 {
117  if( !m_ruleResolver )
118  return 0;
119 
120  return m_ruleResolver->HoleToHoleClearance( aA, aB );
121 }
122 
123 
125 {
126  NODE* child = new NODE;
127 
128  m_children.insert( child );
129 
130  child->m_depth = m_depth + 1;
131  child->m_parent = this;
133  child->m_root = isRoot() ? this : m_root;
135 
136  // Immediate offspring of the root branch needs not copy anything. For the rest, deep-copy
137  // joints, overridden item maps and pointers to stored items.
138  if( !isRoot() )
139  {
140  JOINT_MAP::iterator j;
141 
142  for( ITEM* item : *m_index )
143  child->m_index->Add( item );
144 
145  child->m_joints = m_joints;
146  child->m_override = m_override;
147  }
148 
149 #if 0
150  wxLogTrace( "PNS", "%d items, %d joints, %d overrides",
151  child->m_index->Size(),
152  (int) child->m_joints.size(),
153  (int) child->m_override.size() );
154 #endif
155 
156  return child;
157 }
158 
159 
161 {
162  if( isRoot() )
163  return;
164 
165  m_parent->m_children.erase( this );
166 }
167 
168 
170  m_item( aItem ),
171  m_node( NULL ),
172  m_override( NULL ),
173  m_extraClearance( 0 )
174 {
175 }
176 
177 
178 void OBSTACLE_VISITOR::SetWorld( const NODE* aNode, const NODE* aOverride )
179 {
180  m_node = aNode;
181  m_override = aOverride;
182 }
183 
184 
185 bool OBSTACLE_VISITOR::visit( ITEM* aCandidate )
186 {
187  // check if there is a more recent branch with a newer (possibly modified) version of this
188  // item.
189  if( m_override && m_override->Overrides( aCandidate ) )
190  return true;
191 
192  return false;
193 }
194 
195 
196 // function object that visits potential obstacles and performs the actual collision refining
198 {
200 
206 
207  DEFAULT_OBSTACLE_VISITOR( NODE::OBSTACLES& aTab, const ITEM* aItem, int aKindMask,
208  bool aDifferentNetsOnly ) :
209  OBSTACLE_VISITOR( aItem ),
210  m_tab( aTab ),
211  m_kindMask( aKindMask ),
212  m_limitCount( -1 ),
213  m_matchCount( 0 ),
214  m_extraClearance( 0 ),
215  m_differentNetsOnly( aDifferentNetsOnly )
216  {
217  if( aItem && aItem->Kind() == ITEM::LINE_T )
218  {
219  m_extraClearance += static_cast<const LINE*>( aItem )->Width() / 2;
220  }
221  }
222 
224  {
225  }
226 
227  void SetCountLimit( int aLimit )
228  {
229  m_limitCount = aLimit;
230  }
231 
232  bool operator()( ITEM* aCandidate ) override
233  {
234  if( !aCandidate->OfKind( m_kindMask ) )
235  return true;
236 
237  if( visit( aCandidate ) )
238  return true;
239 
240  if( !aCandidate->Collide( m_item, m_node, m_differentNetsOnly ) )
241  return true;
242 
243  OBSTACLE obs;
244 
245  obs.m_item = aCandidate;
246  obs.m_head = m_item;
247  m_tab.push_back( obs );
248 
249  m_matchCount++;
250 
251  if( m_limitCount > 0 && m_matchCount >= m_limitCount )
252  return false;
253 
254  return true;
255  };
256 };
257 
258 
259 int NODE::QueryColliding( const ITEM* aItem, NODE::OBSTACLES& aObstacles, int aKindMask,
260  int aLimitCount, bool aDifferentNetsOnly )
261 {
262  DEFAULT_OBSTACLE_VISITOR visitor( aObstacles, aItem, aKindMask, aDifferentNetsOnly );
263 
264 #ifdef DEBUG
265  assert( allocNodes.find( this ) != allocNodes.end() );
266 #endif
267 
268  visitor.SetCountLimit( aLimitCount );
269  visitor.SetWorld( this, NULL );
270 
271  // first, look for colliding items in the local index
272  m_index->Query( aItem, m_maxClearance, visitor );
273 
274  // if we haven't found enough items, look in the root branch as well.
275  if( !isRoot() && ( visitor.m_matchCount < aLimitCount || aLimitCount < 0 ) )
276  {
277  visitor.SetWorld( m_root, this );
278  m_root->m_index->Query( aItem, m_maxClearance, visitor );
279  }
280 
281  return aObstacles.size();
282 }
283 
284 
285 NODE::OPT_OBSTACLE NODE::NearestObstacle( const LINE* aLine, int aKindMask,
286  const std::set<ITEM*>* aRestrictedSet )
287 {
288  OBSTACLES obstacleList;
289  obstacleList.reserve( 100 );
290 
291  for( int i = 0; i < aLine->CLine().SegmentCount(); i++ )
292  {
293  const SEGMENT s( *aLine, aLine->CLine().CSegment( i ) );
294  QueryColliding( &s, obstacleList, aKindMask );
295  }
296 
297  if( aLine->EndsWithVia() )
298  QueryColliding( &aLine->Via(), obstacleList, aKindMask );
299 
300  if( obstacleList.empty() )
301  return OPT_OBSTACLE();
302 
303  OBSTACLE nearest;
304  nearest.m_item = NULL;
305  nearest.m_distFirst = INT_MAX;
306 
307  auto updateNearest =
308  [&]( VECTOR2I pt, ITEM* obstacle, const SHAPE_LINE_CHAIN& hull, bool isHole )
309  {
310  int dist = aLine->CLine().PathLength( pt );
311 
312  if( dist < nearest.m_distFirst )
313  {
314  nearest.m_distFirst = dist;
315  nearest.m_ipFirst = pt;
316  nearest.m_item = obstacle;
317  nearest.m_hull = hull;
318 
319  obstacle->Mark( isHole ? obstacle->Marker() | MK_HOLE
320  : obstacle->Marker() & ~MK_HOLE );
321  }
322  };
323 
324  SHAPE_LINE_CHAIN obstacleHull;
326  std::vector<SHAPE_LINE_CHAIN::INTERSECTION> intersectingPts;
327  int layer = aLine->Layer();
328 
329  for( const OBSTACLE& obstacle : obstacleList )
330  {
331  if( aRestrictedSet && aRestrictedSet->find( obstacle.m_item ) == aRestrictedSet->end() )
332  continue;
333 
334  int clearance = GetClearance( obstacle.m_item, aLine ) + aLine->Width() / 2;
335  obstacleHull = obstacle.m_item->Hull( clearance + PNS_HULL_MARGIN, 0, layer );
336  debugDecorator->AddLine( obstacleHull, 2 );
337 
338  intersectingPts.clear();
339  obstacleHull.Intersect( aLine->CLine(), intersectingPts );
340 
341  for( const SHAPE_LINE_CHAIN::INTERSECTION& ip : intersectingPts )
342  updateNearest( ip.p, obstacle.m_item, obstacleHull, false );
343 
344  if( aLine->EndsWithVia() )
345  {
346  const VIA& via = aLine->Via();
347  // Don't use via.Drill(); it doesn't include the plating thickness
348  int viaHoleRadius = static_cast<const SHAPE_CIRCLE*>( via.Hole() )->GetRadius();
349 
350  int viaClearance = GetClearance( obstacle.m_item, &via ) + via.Diameter() / 2;
351  int holeClearance = GetHoleClearance( obstacle.m_item, &via ) + viaHoleRadius;
352 
353  if( holeClearance > viaClearance )
354  viaClearance = holeClearance;
355 
356  obstacleHull = obstacle.m_item->Hull( viaClearance + PNS_HULL_MARGIN, 0, layer );
357  debugDecorator->AddLine( obstacleHull, 3 );
358 
359  intersectingPts.clear();
360  obstacleHull.Intersect( aLine->CLine(), intersectingPts );
361 
362  for( const SHAPE_LINE_CHAIN::INTERSECTION& ip : intersectingPts )
363  updateNearest( ip.p, obstacle.m_item, obstacleHull, false );
364  }
365 
366  if( obstacle.m_item->Hole() )
367  {
368  clearance = GetHoleClearance( obstacle.m_item, aLine ) + aLine->Width() / 2;
369  obstacleHull = obstacle.m_item->HoleHull( clearance + PNS_HULL_MARGIN, 0, layer );
370  debugDecorator->AddLine( obstacleHull, 4 );
371 
372  intersectingPts.clear();
373  obstacleHull.Intersect( aLine->CLine(), intersectingPts );
374 
375  for( const SHAPE_LINE_CHAIN::INTERSECTION& ip : intersectingPts )
376  updateNearest( ip.p, obstacle.m_item, obstacleHull, true );
377 
378  if( aLine->EndsWithVia() )
379  {
380  const VIA& via = aLine->Via();
381  // Don't use via.Drill(); it doesn't include the plating thickness
382  int viaHoleRadius = static_cast<const SHAPE_CIRCLE*>( via.Hole() )->GetRadius();
383 
384  int viaClearance = GetClearance( obstacle.m_item, &via ) + via.Diameter() / 2;
385  int holeClearance = GetHoleClearance( obstacle.m_item, &via ) + viaHoleRadius;
386  int holeToHole = GetHoleToHoleClearance( obstacle.m_item, &via ) + viaHoleRadius;
387 
388  if( holeClearance > viaClearance )
389  viaClearance = holeClearance;
390 
391  if( holeToHole > viaClearance )
392  viaClearance = holeToHole;
393 
394  obstacleHull = obstacle.m_item->Hull( viaClearance + PNS_HULL_MARGIN, 0, layer );
395  debugDecorator->AddLine( obstacleHull, 5 );
396 
397  intersectingPts.clear();
398  obstacleHull.Intersect( aLine->CLine(), intersectingPts );
399 
400  for( const SHAPE_LINE_CHAIN::INTERSECTION& ip : intersectingPts )
401  updateNearest( ip.p, obstacle.m_item, obstacleHull, true );
402  }
403  }
404  }
405 
406  if( nearest.m_distFirst == INT_MAX )
407  nearest.m_item = obstacleList[0].m_item;
408 
409  return nearest;
410 }
411 
412 
413 NODE::OPT_OBSTACLE NODE::CheckColliding( const ITEM_SET& aSet, int aKindMask )
414 {
415  for( const ITEM* item : aSet.CItems() )
416  {
417  OPT_OBSTACLE obs = CheckColliding( item, aKindMask );
418 
419  if( obs )
420  return obs;
421  }
422 
423  return OPT_OBSTACLE();
424 }
425 
426 
427 NODE::OPT_OBSTACLE NODE::CheckColliding( const ITEM* aItemA, int aKindMask )
428 {
429  OBSTACLES obs;
430 
431  obs.reserve( 100 );
432 
433  if( aItemA->Kind() == ITEM::LINE_T )
434  {
435  int n = 0;
436  const LINE* line = static_cast<const LINE*>( aItemA );
437  const SHAPE_LINE_CHAIN& l = line->CLine();
438 
439  for( int i = 0; i < l.SegmentCount(); i++ )
440  {
441  const SEGMENT s( *line, l.CSegment( i ) );
442  n += QueryColliding( &s, obs, aKindMask, 1 );
443 
444  if( n )
445  return OPT_OBSTACLE( obs[0] );
446  }
447 
448  if( line->EndsWithVia() )
449  {
450  n += QueryColliding( &line->Via(), obs, aKindMask, 1 );
451 
452  if( n )
453  return OPT_OBSTACLE( obs[0] );
454  }
455  }
456  else if( QueryColliding( aItemA, obs, aKindMask, 1 ) > 0 )
457  {
458  return OPT_OBSTACLE( obs[0] );
459  }
460 
461  return OPT_OBSTACLE();
462 }
463 
464 
466 {
469 
470  HIT_VISITOR( ITEM_SET& aTab, const VECTOR2I& aPoint ) :
472  m_items( aTab ),
473  m_point( aPoint )
474  {}
475 
476  virtual ~HIT_VISITOR()
477  {
478  }
479 
480  bool operator()( ITEM* aItem ) override
481  {
482  SHAPE_CIRCLE cp( m_point, 0 );
483 
484  int cl = 0;
485 
486  if( aItem->Shape()->Collide( &cp, cl ) )
487  m_items.Add( aItem );
488 
489  return true;
490  }
491 };
492 
493 
494 const ITEM_SET NODE::HitTest( const VECTOR2I& aPoint ) const
495 {
496  ITEM_SET items;
497 
498  // fixme: we treat a point as an infinitely small circle - this is inefficient.
499  SHAPE_CIRCLE s( aPoint, 0 );
500  HIT_VISITOR visitor( items, aPoint );
501  visitor.SetWorld( this, NULL );
502 
503  m_index->Query( &s, m_maxClearance, visitor );
504 
505  if( !isRoot() ) // fixme: could be made cleaner
506  {
507  ITEM_SET items_root;
508  visitor.SetWorld( m_root, NULL );
509  HIT_VISITOR visitor_root( items_root, aPoint );
510  m_root->m_index->Query( &s, m_maxClearance, visitor_root );
511 
512  for( ITEM* item : items_root.Items() )
513  {
514  if( !Overrides( item ) )
515  items.Add( item );
516  }
517  }
518 
519  return items;
520 }
521 
522 
523 void NODE::addSolid( SOLID* aSolid )
524 {
525  if( aSolid->IsRoutable() )
526  linkJoint( aSolid->Pos(), aSolid->Layers(), aSolid->Net(), aSolid );
527 
528  m_index->Add( aSolid );
529 }
530 
531 
532 void NODE::Add( std::unique_ptr< SOLID > aSolid )
533 {
534  aSolid->SetOwner( this );
535  addSolid( aSolid.release() );
536 }
537 
538 
539 void NODE::addVia( VIA* aVia )
540 {
541  linkJoint( aVia->Pos(), aVia->Layers(), aVia->Net(), aVia );
542 
543  m_index->Add( aVia );
544 }
545 
546 
547 void NODE::Add( std::unique_ptr< VIA > aVia )
548 {
549  aVia->SetOwner( this );
550  addVia( aVia.release() );
551 }
552 
553 
554 void NODE::Add( LINE& aLine, bool aAllowRedundant )
555 {
556  assert( !aLine.IsLinked() );
557 
558  SHAPE_LINE_CHAIN& l = aLine.Line();
559 
560  for( size_t i = 0; i < l.ArcCount(); i++ )
561  {
562  auto s = l.Arc( i );
563  ARC* rarc;
564 
565  if( !aAllowRedundant && ( rarc = findRedundantArc( s.GetP0(), s.GetP1(), aLine.Layers(),
566  aLine.Net() ) ) )
567  {
568  aLine.Link( rarc );
569  }
570  else
571  {
572  auto newarc = std::make_unique< ARC >( aLine, s );
573  aLine.Link( newarc.get() );
574  Add( std::move( newarc ), true );
575  }
576  }
577 
578  for( int i = 0; i < l.SegmentCount(); i++ )
579  {
580  if( l.isArc( i ) )
581  continue;
582 
583  SEG s = l.CSegment( i );
584 
585  if( s.A != s.B )
586  {
587  SEGMENT* rseg;
588 
589  if( !aAllowRedundant && ( rseg = findRedundantSegment( s.A, s.B, aLine.Layers(),
590  aLine.Net() ) ) )
591  {
592  // another line could be referencing this segment too :(
593  aLine.Link( rseg );
594  }
595  else
596  {
597  std::unique_ptr<SEGMENT> newseg = std::make_unique<SEGMENT>( aLine, s );
598  aLine.Link( newseg.get() );
599  Add( std::move( newseg ), true );
600  }
601  }
602  }
603 }
604 
605 
607 {
608  linkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
609  linkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
610 
611  m_index->Add( aSeg );
612 }
613 
614 
615 bool NODE::Add( std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant )
616 {
617  if( aSegment->Seg().A == aSegment->Seg().B )
618  {
619  wxLogTrace( "PNS", "attempting to add a segment with same end coordinates, ignoring." );
620  return false;
621  }
622 
623  if( !aAllowRedundant && findRedundantSegment( aSegment.get() ) )
624  return false;
625 
626  aSegment->SetOwner( this );
627  addSegment( aSegment.release() );
628 
629  return true;
630 }
631 
632 
633 void NODE::addArc( ARC* aArc )
634 {
635  linkJoint( aArc->Anchor( 0 ), aArc->Layers(), aArc->Net(), aArc );
636  linkJoint( aArc->Anchor( 1 ), aArc->Layers(), aArc->Net(), aArc );
637 
638  m_index->Add( aArc );
639 }
640 
641 
642 void NODE::Add( std::unique_ptr< ARC > aArc )
643 {
644  aArc->SetOwner( this );
645  addArc( aArc.release() );
646 }
647 
648 
649 void NODE::Add( std::unique_ptr< ITEM > aItem, bool aAllowRedundant )
650 {
651  switch( aItem->Kind() )
652  {
653  case ITEM::SOLID_T: Add( ItemCast<SOLID>( std::move( aItem ) ) ); break;
654  case ITEM::SEGMENT_T: Add( ItemCast<SEGMENT>( std::move( aItem ) ), aAllowRedundant ); break;
655  case ITEM::VIA_T: Add( ItemCast<VIA>( std::move( aItem ) ) ); break;
656 
657  case ITEM::ARC_T:
658  //todo(snh): Add redundant search
659  Add( ItemCast<ARC>( std::move( aItem ) ) );
660  break;
661 
662  case ITEM::LINE_T:
663  default:
664  assert( false );
665  }
666 }
667 
668 
669 void NODE::doRemove( ITEM* aItem )
670 {
671  // case 1: removing an item that is stored in the root node from any branch:
672  // mark it as overridden, but do not remove
673  if( aItem->BelongsTo( m_root ) && !isRoot() )
674  m_override.insert( aItem );
675 
676  // case 2: the item belongs to this branch or a parent, non-root branch,
677  // or the root itself and we are the root: remove from the index
678  else if( !aItem->BelongsTo( m_root ) || isRoot() )
679  m_index->Remove( aItem );
680 
681  // the item belongs to this particular branch: un-reference it
682  if( aItem->BelongsTo( this ) )
683  {
684  aItem->SetOwner( NULL );
685  m_root->m_garbageItems.insert( aItem );
686  }
687 }
688 
689 
691 {
692  unlinkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
693  unlinkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
694 }
695 
696 
698 {
699  unlinkJoint( aArc->Anchor( 0 ), aArc->Layers(), aArc->Net(), aArc );
700  unlinkJoint( aArc->Anchor( 1 ), aArc->Layers(), aArc->Net(), aArc );
701 }
702 
703 
704 void NODE::rebuildJoint( JOINT* aJoint, ITEM* aItem )
705 {
706  // We have to split a single joint (associated with a via or a pad, binding together multiple
707  // layers) into multiple independent joints. As I'm a lazy bastard, I simply delete the
708  // via/solid and all its links and re-insert them.
709 
710  JOINT::LINKED_ITEMS links( aJoint->LinkList() );
711  JOINT::HASH_TAG tag;
712  int net = aItem->Net();
713 
714  tag.net = net;
715  tag.pos = aJoint->Pos();
716 
717  bool split;
718 
719  do
720  {
721  split = false;
722  auto range = m_joints.equal_range( tag );
723 
724  if( range.first == m_joints.end() )
725  break;
726 
727  // find and remove all joints containing the via to be removed
728 
729  for( auto f = range.first; f != range.second; ++f )
730  {
731  if( aItem->LayersOverlap( &f->second ) )
732  {
733  m_joints.erase( f );
734  split = true;
735  break;
736  }
737  }
738  } while( split );
739 
740  // and re-link them, using the former via's link list
741  for( ITEM* link : links )
742  {
743  if( link != aItem )
744  linkJoint( tag.pos, link->Layers(), net, link );
745  }
746 }
747 
748 
750 {
751  JOINT* jt = FindJoint( aVia->Pos(), aVia->Layers().Start(), aVia->Net() );
752  assert( jt );
753  rebuildJoint( jt, aVia );
754 }
755 
756 
758 {
759  if( !aSolid->IsRoutable() )
760  return;
761 
762  // fixme: redundant code
763  JOINT* jt = FindJoint( aSolid->Pos(), aSolid->Layers().Start(), aSolid->Net() );
764  assert( jt );
765  rebuildJoint( jt, aSolid );
766 }
767 
768 
769 void NODE::Replace( ITEM* aOldItem, std::unique_ptr< ITEM > aNewItem )
770 {
771  Remove( aOldItem );
772  Add( std::move( aNewItem ) );
773 }
774 
775 
776 void NODE::Replace( LINE& aOldLine, LINE& aNewLine )
777 {
778  Remove( aOldLine );
779  Add( aNewLine );
780 }
781 
782 
783 void NODE::Remove( SOLID* aSolid )
784 {
785  removeSolidIndex( aSolid );
786  doRemove( aSolid );
787 }
788 
789 
790 void NODE::Remove( VIA* aVia )
791 {
792  removeViaIndex( aVia );
793  doRemove( aVia );
794 }
795 
796 
797 void NODE::Remove( SEGMENT* aSegment )
798 {
799  removeSegmentIndex( aSegment );
800  doRemove( aSegment );
801 }
802 
803 
804 void NODE::Remove( ARC* aArc )
805 {
806  removeArcIndex( aArc );
807  doRemove( aArc );
808 }
809 
810 
811 void NODE::Remove( ITEM* aItem )
812 {
813  switch( aItem->Kind() )
814  {
815  case ITEM::ARC_T:
816  Remove( static_cast<ARC*>( aItem ) );
817  break;
818 
819  case ITEM::SOLID_T:
820  Remove( static_cast<SOLID*>( aItem ) );
821  break;
822 
823  case ITEM::SEGMENT_T:
824  Remove( static_cast<SEGMENT*>( aItem ) );
825  break;
826 
827  case ITEM::LINE_T:
828  {
829  LINE* l = static_cast<LINE*>( aItem );
830 
831  for ( LINKED_ITEM* s : l->Links() )
832  Remove( s );
833 
834  break;
835  }
836 
837  case ITEM::VIA_T:
838  Remove( static_cast<VIA*>( aItem ) );
839  break;
840 
841  default:
842  break;
843  }
844 }
845 
846 
847 void NODE::Remove( LINE& aLine )
848 {
849  // LINE does not have a separate remover, as LINEs are never truly a member of the tree
850  std::vector<LINKED_ITEM*>& segRefs = aLine.Links();
851 
852  for( LINKED_ITEM* li : segRefs )
853  {
854  if( li->OfKind( ITEM::SEGMENT_T ) )
855  Remove( static_cast<SEGMENT*>( li ) );
856  else if( li->OfKind( ITEM::ARC_T ) )
857  Remove( static_cast<ARC*>( li ) );
858  }
859 
860  aLine.SetOwner( nullptr );
861  aLine.ClearLinks();
862 }
863 
864 
865 void NODE::followLine( LINKED_ITEM* aCurrent, bool aScanDirection, int& aPos, int aLimit,
866  VECTOR2I* aCorners, LINKED_ITEM** aSegments, bool* aArcReversed,
867  bool& aGuardHit, bool aStopAtLockedJoints )
868 {
869  bool prevReversed = false;
870 
871  const VECTOR2I guard = aCurrent->Anchor( aScanDirection );
872 
873  for( int count = 0 ; ; ++count )
874  {
875  const VECTOR2I p = aCurrent->Anchor( aScanDirection ^ prevReversed );
876  const JOINT* jt = FindJoint( p, aCurrent );
877 
878  assert( jt );
879 
880  aCorners[aPos] = jt->Pos();
881  aSegments[aPos] = aCurrent;
882  aArcReversed[aPos] = false;
883 
884  if( aCurrent->Kind() == ITEM::ARC_T )
885  {
886  if( ( aScanDirection && jt->Pos() == aCurrent->Anchor( 0 ) ) ||
887  ( !aScanDirection && jt->Pos() == aCurrent->Anchor( 1 ) ) )
888  aArcReversed[aPos] = true;
889  }
890 
891  aPos += ( aScanDirection ? 1 : -1 );
892 
893  if( count && guard == p )
894  {
895  aSegments[aPos] = NULL;
896  aGuardHit = true;
897  break;
898  }
899 
900  bool locked = aStopAtLockedJoints ? jt->IsLocked() : false;
901 
902  if( locked || !jt->IsLineCorner() || aPos < 0 || aPos == aLimit )
903  break;
904 
905  aCurrent = jt->NextSegment( aCurrent );
906 
907  prevReversed = ( jt->Pos() == aCurrent->Anchor( aScanDirection ) );
908  }
909 }
910 
911 
912 const LINE NODE::AssembleLine( LINKED_ITEM* aSeg, int* aOriginSegmentIndex,
913  bool aStopAtLockedJoints )
914 {
915  const int MaxVerts = 1024 * 16;
916 
917  std::array<VECTOR2I, MaxVerts + 1> corners;
918  std::array<LINKED_ITEM*, MaxVerts + 1> segs;
919  std::array<bool, MaxVerts + 1> arcReversed;
920 
921  LINE pl;
922  bool guardHit = false;
923 
924  int i_start = MaxVerts / 2, i_end = i_start + 1;
925 
926  pl.SetWidth( aSeg->Width() );
927  pl.SetLayers( aSeg->Layers() );
928  pl.SetNet( aSeg->Net() );
929  pl.SetOwner( this );
930 
931  followLine( aSeg, false, i_start, MaxVerts, corners.data(), segs.data(), arcReversed.data(),
932  guardHit, aStopAtLockedJoints );
933 
934  if( !guardHit )
935  {
936  followLine( aSeg, true, i_end, MaxVerts, corners.data(), segs.data(), arcReversed.data(), guardHit,
937  aStopAtLockedJoints );
938  }
939 
940  int n = 0;
941 
942  LINKED_ITEM* prev_seg = NULL;
943  bool originSet = false;
944 
945  for( int i = i_start + 1; i < i_end; i++ )
946  {
947  const VECTOR2I& p = corners[i];
948  LINKED_ITEM* li = segs[i];
949 
950  if( !li || li->Kind() != ITEM::ARC_T )
951  pl.Line().Append( p );
952 
953  if( li && prev_seg != li )
954  {
955  if( li->Kind() == ITEM::ARC_T )
956  {
957  const ARC* arc = static_cast<const ARC*>( li );
958  const SHAPE_ARC* sa = static_cast<const SHAPE_ARC*>( arc->Shape() );
959  pl.Line().Append( arcReversed[i] ? sa->Reversed() : *sa );
960  }
961 
962  pl.Link( li );
963 
964  // latter condition to avoid loops
965  if( li == aSeg && aOriginSegmentIndex && !originSet )
966  {
967  *aOriginSegmentIndex = n;
968  originSet = true;
969  }
970 
971  n++;
972  }
973 
974  prev_seg = li;
975  }
976 
977  // Remove duplicate verts, but do NOT remove colinear segments here!
978  pl.Line().Simplify( false );
979 
980  assert( pl.SegmentCount() != 0 );
981 
982  return pl;
983 }
984 
985 
986 void NODE::FindLineEnds( const LINE& aLine, JOINT& aA, JOINT& aB )
987 {
988  aA = *FindJoint( aLine.CPoint( 0 ), &aLine );
989  aB = *FindJoint( aLine.CPoint( -1 ), &aLine );
990 }
991 
992 
993 int NODE::FindLinesBetweenJoints( const JOINT& aA, const JOINT& aB, std::vector<LINE>& aLines )
994 {
995  for( ITEM* item : aA.LinkList() )
996  {
997  if( item->Kind() == ITEM::SEGMENT_T || item->Kind() == ITEM::ARC_T )
998  {
999  LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
1000  LINE line = AssembleLine( li );
1001 
1002  if( !line.Layers().Overlaps( aB.Layers() ) )
1003  continue;
1004 
1005  JOINT j_start, j_end;
1006 
1007  FindLineEnds( line, j_start, j_end );
1008 
1009  int id_start = line.CLine().Find( aA.Pos() );
1010  int id_end = line.CLine().Find( aB.Pos() );
1011 
1012  if( id_end < id_start )
1013  std::swap( id_end, id_start );
1014 
1015  if( id_start >= 0 && id_end >= 0 )
1016  {
1017  line.ClipVertexRange( id_start, id_end );
1018  aLines.push_back( line );
1019  }
1020  }
1021  }
1022 
1023  return 0;
1024 }
1025 
1026 
1027 JOINT* NODE::FindJoint( const VECTOR2I& aPos, int aLayer, int aNet )
1028 {
1029  JOINT::HASH_TAG tag;
1030 
1031  tag.net = aNet;
1032  tag.pos = aPos;
1033 
1034  JOINT_MAP::iterator f = m_joints.find( tag ), end = m_joints.end();
1035 
1036  if( f == end && !isRoot() )
1037  {
1038  end = m_root->m_joints.end();
1039  f = m_root->m_joints.find( tag ); // m_root->FindJoint(aPos, aLayer, aNet);
1040  }
1041 
1042  if( f == end )
1043  return NULL;
1044 
1045  while( f != end )
1046  {
1047  if( f->second.Layers().Overlaps( aLayer ) )
1048  return &f->second;
1049 
1050  ++f;
1051  }
1052 
1053  return NULL;
1054 }
1055 
1056 
1057 void NODE::LockJoint( const VECTOR2I& aPos, const ITEM* aItem, bool aLock )
1058 {
1059  JOINT& jt = touchJoint( aPos, aItem->Layers(), aItem->Net() );
1060  jt.Lock( aLock );
1061 }
1062 
1063 
1064 JOINT& NODE::touchJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet )
1065 {
1066  JOINT::HASH_TAG tag;
1067 
1068  tag.pos = aPos;
1069  tag.net = aNet;
1070 
1071  // try to find the joint in this node.
1072  JOINT_MAP::iterator f = m_joints.find( tag );
1073 
1074  std::pair<JOINT_MAP::iterator, JOINT_MAP::iterator> range;
1075 
1076  // not found and we are not root? find in the root and copy results here.
1077  if( f == m_joints.end() && !isRoot() )
1078  {
1079  range = m_root->m_joints.equal_range( tag );
1080 
1081  for( f = range.first; f != range.second; ++f )
1082  m_joints.insert( *f );
1083  }
1084 
1085  // now insert and combine overlapping joints
1086  JOINT jt( aPos, aLayers, aNet );
1087 
1088  bool merged;
1089 
1090  do
1091  {
1092  merged = false;
1093  range = m_joints.equal_range( tag );
1094 
1095  if( range.first == m_joints.end() )
1096  break;
1097 
1098  for( f = range.first; f != range.second; ++f )
1099  {
1100  if( aLayers.Overlaps( f->second.Layers() ) )
1101  {
1102  jt.Merge( f->second );
1103  m_joints.erase( f );
1104  merged = true;
1105  break;
1106  }
1107  }
1108  }
1109  while( merged );
1110 
1111  return m_joints.insert( TagJointPair( tag, jt ) )->second;
1112 }
1113 
1114 
1115 void JOINT::Dump() const
1116 {
1117  wxLogTrace( "PNS", "joint layers %d-%d, net %d, pos %s, links: %d",
1118  m_layers.Start(),
1119  m_layers.End(),
1120  m_tag.net,
1121  m_tag.pos.Format().c_str(),
1122  LinkCount() );
1123 }
1124 
1125 
1126 void NODE::linkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet, ITEM* aWhere )
1127 {
1128  JOINT& jt = touchJoint( aPos, aLayers, aNet );
1129 
1130  jt.Link( aWhere );
1131 }
1132 
1133 
1134 void NODE::unlinkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet, ITEM* aWhere )
1135 {
1136  // fixme: remove dangling joints
1137  JOINT& jt = touchJoint( aPos, aLayers, aNet );
1138 
1139  jt.Unlink( aWhere );
1140 }
1141 
1142 
1143 void NODE::Dump( bool aLong )
1144 {
1145 #if 0
1146  std::unordered_set<SEGMENT*> all_segs;
1148 
1149  for( i = m_items.begin(); i != m_items.end(); i++ )
1150  {
1151  if( (*i)->GetKind() == ITEM::SEGMENT_T )
1152  all_segs.insert( static_cast<SEGMENT*>( *i ) );
1153  }
1154 
1155  if( !isRoot() )
1156  {
1157  for( i = m_root->m_items.begin(); i != m_root->m_items.end(); i++ )
1158  {
1159  if( (*i)->GetKind() == ITEM::SEGMENT_T && !overrides( *i ) )
1160  all_segs.insert( static_cast<SEGMENT*>(*i) );
1161  }
1162  }
1163 
1164  JOINT_MAP::iterator j;
1165 
1166  if( aLong )
1167  {
1168  for( j = m_joints.begin(); j != m_joints.end(); ++j )
1169  {
1170  wxLogTrace( "PNS", "joint : %s, links : %d\n",
1171  j->second.GetPos().Format().c_str(), j->second.LinkCount() );
1172  JOINT::LINKED_ITEMS::const_iterator k;
1173 
1174  for( k = j->second.GetLinkList().begin(); k != j->second.GetLinkList().end(); ++k )
1175  {
1176  const ITEM* m_item = *k;
1177 
1178  switch( m_item->GetKind() )
1179  {
1180  case ITEM::SEGMENT_T:
1181  {
1182  const SEGMENT* seg = static_cast<const SEGMENT*>( m_item );
1183  wxLogTrace( "PNS", " -> seg %s %s\n", seg->GetSeg().A.Format().c_str(),
1184  seg->GetSeg().B.Format().c_str() );
1185  break;
1186  }
1187 
1188  default:
1189  break;
1190  }
1191  }
1192  }
1193  }
1194 
1195  int lines_count = 0;
1196 
1197  while( !all_segs.empty() )
1198  {
1199  SEGMENT* s = *all_segs.begin();
1200  LINE* l = AssembleLine( s );
1201 
1202  LINE::LinkedSegments* seg_refs = l->GetLinkedSegments();
1203 
1204  if( aLong )
1205  wxLogTrace( "PNS", "Line: %s, net %d ", l->GetLine().Format().c_str(), l->GetNet() );
1206 
1207  for( std::vector<SEGMENT*>::iterator j = seg_refs->begin(); j != seg_refs->end(); ++j )
1208  {
1209  wxLogTrace( "PNS", "%s ", (*j)->GetSeg().A.Format().c_str() );
1210 
1211  if( j + 1 == seg_refs->end() )
1212  wxLogTrace( "PNS", "%s\n", (*j)->GetSeg().B.Format().c_str() );
1213 
1214  all_segs.erase( *j );
1215  }
1216 
1217  lines_count++;
1218  }
1219 
1220  wxLogTrace( "PNS", "Local joints: %d, lines : %d \n", m_joints.size(), lines_count );
1221 #endif
1222 }
1223 
1224 
1226 {
1227  if( isRoot() )
1228  return;
1229 
1230  if( m_override.size() )
1231  aRemoved.reserve( m_override.size() );
1232 
1233  if( m_index->Size() )
1234  aAdded.reserve( m_index->Size() );
1235 
1236  for( ITEM* item : m_override )
1237  aRemoved.push_back( item );
1238 
1239  for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
1240  aAdded.push_back( *i );
1241 }
1242 
1243 
1245 {
1246  // copy the kids as the NODE destructor erases the item from the parent node.
1247  std::set<NODE*> kids = m_children;
1248 
1249  for( NODE* node : kids )
1250  {
1251  node->releaseChildren();
1252  delete node;
1253  }
1254 }
1255 
1256 
1258 {
1259  if( !isRoot() )
1260  return;
1261 
1262  for( ITEM* item : m_garbageItems )
1263  {
1264  if( !item->BelongsTo( this ) )
1265  delete item;
1266  }
1267 
1268  m_garbageItems.clear();
1269 }
1270 
1271 
1272 void NODE::Commit( NODE* aNode )
1273 {
1274  if( aNode->isRoot() )
1275  return;
1276 
1277  for( ITEM* item : aNode->m_override )
1278  Remove( item );
1279 
1280  for( ITEM* item : *aNode->m_index )
1281  {
1282  item->SetRank( -1 );
1283  item->Unmark();
1284  Add( std::unique_ptr<ITEM>( item ) );
1285  }
1286 
1287  releaseChildren();
1288  releaseGarbage();
1289 }
1290 
1291 
1293 {
1294  releaseChildren();
1295 }
1296 
1297 
1298 void NODE::AllItemsInNet( int aNet, std::set<ITEM*>& aItems, int aKindMask)
1299 {
1300  INDEX::NET_ITEMS_LIST* l_cur = m_index->GetItemsForNet( aNet );
1301 
1302  if( l_cur )
1303  {
1304  for( ITEM* item : *l_cur )
1305  {
1306  if( item->OfKind( aKindMask ) && item->IsRoutable() )
1307  aItems.insert( item );
1308  }
1309  }
1310 
1311  if( !isRoot() )
1312  {
1313  INDEX::NET_ITEMS_LIST* l_root = m_root->m_index->GetItemsForNet( aNet );
1314 
1315  if( l_root )
1316  {
1317  for( ITEM* item : *l_root )
1318  {
1319  if( !Overrides( item ) && item->OfKind( aKindMask ) && item->IsRoutable() )
1320  aItems.insert( item );
1321  }
1322  }
1323  }
1324 }
1325 
1326 
1327 void NODE::ClearRanks( int aMarkerMask )
1328 {
1329  for( ITEM* item : *m_index )
1330  {
1331  item->SetRank( -1 );
1332  item->Mark( item->Marker() & ~aMarkerMask );
1333  }
1334 }
1335 
1336 
1337 void NODE::RemoveByMarker( int aMarker )
1338 {
1339  std::list<ITEM*> garbage;
1340 
1341  for( ITEM* item : *m_index )
1342  {
1343  if( item->Marker() & aMarker )
1344  garbage.push_back( item );
1345  }
1346 
1347  for( ITEM* item : garbage )
1348  Remove( item );
1349 }
1350 
1351 
1353  int aNet )
1354 {
1355  JOINT* jtStart = FindJoint( A, lr.Start(), aNet );
1356 
1357  if( !jtStart )
1358  return nullptr;
1359 
1360  for( ITEM* item : jtStart->LinkList() )
1361  {
1362  if( item->OfKind( ITEM::SEGMENT_T ) )
1363  {
1364  SEGMENT* seg2 = (SEGMENT*)item;
1365 
1366  const VECTOR2I a2( seg2->Seg().A );
1367  const VECTOR2I b2( seg2->Seg().B );
1368 
1369  if( seg2->Layers().Start() == lr.Start()
1370  && ( ( A == a2 && B == b2 ) || ( A == b2 && B == a2 ) ) )
1371  {
1372  return seg2;
1373  }
1374  }
1375  }
1376 
1377  return nullptr;
1378 }
1379 
1380 
1382 {
1383  return findRedundantSegment( aSeg->Seg().A, aSeg->Seg().B, aSeg->Layers(), aSeg->Net() );
1384 }
1385 
1386 
1388  int aNet )
1389 {
1390  JOINT* jtStart = FindJoint( A, lr.Start(), aNet );
1391 
1392  if( !jtStart )
1393  return nullptr;
1394 
1395  for( ITEM* item : jtStart->LinkList() )
1396  {
1397  if( item->OfKind( ITEM::ARC_T ) )
1398  {
1399  ARC* seg2 = static_cast<ARC*>( item );
1400 
1401  const VECTOR2I a2( seg2->Anchor( 0 ) );
1402  const VECTOR2I b2( seg2->Anchor( 1 ) );
1403 
1404  if( seg2->Layers().Start() == lr.Start()
1405  && ( ( A == a2 && B == b2 ) || ( A == b2 && B == a2 ) ) )
1406  {
1407  return seg2;
1408  }
1409  }
1410  }
1411 
1412  return nullptr;
1413 }
1414 
1415 
1417 {
1418  return findRedundantArc( aArc->Anchor( 0 ), aArc->Anchor( 1 ), aArc->Layers(), aArc->Net() );
1419 }
1420 
1421 
1422 int NODE::QueryJoints( const BOX2I& aBox, std::vector<JOINT*>& aJoints, LAYER_RANGE aLayerMask,
1423  int aKindMask )
1424 {
1425  int n = 0;
1426 
1427  aJoints.clear();
1428 
1429  for( JOINT_MAP::value_type& j : m_joints )
1430  {
1431  if( !j.second.Layers().Overlaps( aLayerMask ) )
1432  continue;
1433 
1434  if( aBox.Contains( j.second.Pos() ) && j.second.LinkCount( aKindMask ) )
1435  {
1436  aJoints.push_back( &j.second );
1437  n++;
1438  }
1439  }
1440 
1441  if( isRoot() )
1442  return n;
1443 
1444  for( JOINT_MAP::value_type& j : m_root->m_joints )
1445  {
1446  if( !Overrides( &j.second ) && j.second.Layers().Overlaps( aLayerMask ) )
1447  {
1448  if( aBox.Contains( j.second.Pos() ) && j.second.LinkCount( aKindMask ) )
1449  {
1450  aJoints.push_back( &j.second );
1451  n++;
1452  }
1453  }
1454  }
1455 
1456  return n;
1457 }
1458 
1459 
1461 {
1462  if( aParent->IsConnected() )
1463  {
1464  const BOARD_CONNECTED_ITEM* cItem = static_cast<const BOARD_CONNECTED_ITEM*>( aParent );
1465 
1467 
1468  if( l_cur )
1469  {
1470  for( ITEM* item : *l_cur )
1471  {
1472  if( item->Parent() == aParent )
1473  return item;
1474  }
1475  }
1476  }
1477 
1478  return NULL;
1479 }
1480 
1481 }
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION|MK_HOLE)
Definition: pns_node.cpp:1327
int Find(const VECTOR2I &aP) const
Function Find()
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:137
Base class for PNS router board items.
Definition: pns_item.h:55
int Query(const ITEM *aItem, int aMinDistance, Visitor &aVisitor) const
Searches items in the index that are in proximity of aItem.
Definition: pns_index.h:141
std::list< ITEM * > NET_ITEMS_LIST
Definition: pns_index.h:48
OPT_OBSTACLE NearestObstacle(const LINE *aLine, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=NULL)
Follow the line in search of an obstacle that is nearest to the starting to the line's starting point...
Definition: pns_node.cpp:285
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:448
ITEM * m_item
Item found to be colliding with m_head.
Definition: pns_node.h:110
const SHAPE_ARC & Arc(size_t aArc) const
DEFAULT_OBSTACLE_VISITOR(NODE::OBSTACLES &aTab, const ITEM *aItem, int aKindMask, bool aDifferentNetsOnly)
Definition: pns_node.cpp:207
const NODE * m_node
node we are searching in (either root or a branch)
Definition: pns_node.h:135
void SetOwner(NODE *aOwner)
Set the node that owns this item.
Definition: pns_item.h:172
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
virtual int Layer() const
Definition: pns_item.h:154
Keep the router "world" - i.e.
Definition: pns_node.h:149
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, int aType=0, int aWidth=0, const std::string aName="")
int GetHoleToHoleClearance(const ITEM *aA, const ITEM *aB) const
Return the pre-set worst case clearance between any pair of items.
Definition: pns_node.cpp:115
bool IsRoutable() const
Definition: pns_item.h:229
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition: board_item.h:82
void releaseChildren()
Definition: pns_node.cpp:1244
int SegmentCount() const
Definition: pns_line.h:139
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Function Simplify()
void unlinkParent()
Definition: pns_node.cpp:160
bool Unlink(ITEM *aItem)
For trivial joints, return the segment adjacent to (aCurrent).
Definition: pns_joint.h:151
LINKED_ITEM * NextSegment(ITEM *aCurrent) const
Definition: pns_joint.h:159
ENTRIES & Items()
Definition: pns_itemset.h:138
int m_distFirst
... and the distance thereof
Definition: pns_node.h:113
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
Destroy all child nodes. Applicable only to the root node.
Definition: pns_node.cpp:986
void doRemove(ITEM *aItem)
Definition: pns_node.cpp:669
void removeSegmentIndex(SEGMENT *aSeg)
Definition: pns_node.cpp:690
bool IsLocked() const
Definition: pns_joint.h:249
#define PNS_HULL_MARGIN
Definition: pns_line.h:44
bool Overlaps(const LAYER_RANGE &aOther) const
Definition: pns_layerset.h:67
LAYER_RANGE m_layers
Definition: pns_item.h:239
int FindLinesBetweenJoints(const JOINT &aA, const JOINT &aB, std::vector< LINE > &aLines)
Find the joints corresponding to the ends of line aLine.
Definition: pns_node.cpp:993
virtual int Clearance(const ITEM *aA, const ITEM *aB)=0
void Lock(bool aLock=true)
Definition: pns_joint.h:244
const SEG & Seg() const
Definition: pns_segment.h:84
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:60
virtual void Unmark(int aMarker=-1) const
Definition: pns_item.h:207
bool Overrides(ITEM *aItem) const
Definition: pns_node.h:383
void linkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
Unlink an item from a joint.
Definition: pns_node.cpp:1126
int GetHoleClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_node.cpp:106
A base class derived from BOARD_ITEM for items that can be connected and have a net,...
void Add(const LINE &aLine)
Definition: pns_itemset.cpp:32
void Commit(NODE *aNode)
Apply the changes from a given branch (aNode) to the root branch.
Definition: pns_node.cpp:1272
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:124
const VECTOR2I & Pos() const
Definition: pns_via.h:96
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:165
ITEM_SET & m_items
Definition: pns_node.cpp:467
bool EndsWithVia() const
Definition: pns_line.h:191
void unlinkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
Helpers for adding/removing items.
Definition: pns_node.cpp:1134
bool operator()(ITEM *aItem) override
Definition: pns_node.cpp:480
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
bool isRoot() const
Definition: pns_node.h:421
virtual ~HIT_VISITOR()
Definition: pns_node.cpp:476
int PathLength(const VECTOR2I &aP) const
Function PathLength()
INDEX * m_index
Geometric/Net index of the items.
Definition: pns_node.h:455
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:804
void SetWidth(int aWidth)
Return line width.
Definition: pns_line.h:149
int Start() const
Definition: pns_layerset.h:82
void SetNet(int aNet)
Definition: pns_item.h:147
bool LayersOverlap(const ITEM *aOther) const
Return true if the set of layers spanned by aOther overlaps our layers.
Definition: pns_item.h:159
const VECTOR2I & CPoint(int aIdx) const
Definition: pns_line.h:145
virtual int Width() const
int End() const
Definition: pns_layerset.h:87
void addSegment(SEGMENT *aSeg)
Definition: pns_node.cpp:606
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:447
int m_depth
depth of the node (number of parent nodes in the inheritance chain)
Definition: pns_node.h:456
Represents a 2D point on a given set of layers and belonging to a certain net, that links together a ...
Definition: pns_joint.h:42
RULE_RESOLVER * m_ruleResolver
Design rules resolver.
Definition: pns_node.h:454
int Diameter() const
Definition: pns_via.h:107
bool IsLineCorner() const
Definition: pns_joint.h:100
void addSolid(SOLID *aSeg)
Definition: pns_node.cpp:523
int GetClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_node.cpp:97
void KillChildren()
Definition: pns_node.cpp:1292
bool BelongsTo(NODE *aNode) const
Definition: pns_item.h:177
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:912
#define NULL
void rebuildJoint(JOINT *aJoint, ITEM *aItem)
Definition: pns_node.cpp:704
ITEM * FindItemByParent(const BOARD_ITEM *aParent)
Definition: pns_node.cpp:1460
virtual const SHAPE * Shape() const
Return the geometrical shape of the item.
Definition: pns_item.h:196
int Net() const
Definition: pns_item.h:148
HIT_VISITOR(ITEM_SET &aTab, const VECTOR2I &aPoint)
Definition: pns_node.cpp:470
SEGMENT * findRedundantSegment(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1352
bool Contains(const Vec &aPoint) const
Function Contains.
Definition: box2.h:151
const std::string Format() const
Return the vector formatted as a string.
Definition: vector2d.h:434
virtual int HoleClearance(const ITEM *aA, const ITEM *aB)=0
OBSTACLE_VISITOR(const ITEM *aItem)
Definition: pns_node.cpp:169
void ClipVertexRange(int aStart, int aEnd)
Return the number of corners of angles specified by mask aAngles.
Definition: pns_line.cpp:912
bool operator()(ITEM *aCandidate) override
Definition: pns_node.cpp:232
bool visit(ITEM *aCandidate)
Definition: pns_node.cpp:185
bool Collide(const ITEM *aOther, const NODE *aNode, bool aDifferentNetsOnly=true) const
Check for a collision (clearance violation) with between us and item aOther.
Definition: pns_item.cpp:97
std::unordered_set< ITEM * > m_override
hash of root's items that have been changed in this node
Definition: pns_node.h:450
int QueryJoints(const BOX2I &aBox, std::vector< JOINT * > &aJoints, LAYER_RANGE aLayerMask=LAYER_RANGE::All(), int aKindMask=ITEM::ANY_T)
Definition: pns_node.cpp:1422
const SHAPE_CIRCLE * Hole() const override
Definition: pns_via.h:126
void SetWorld(const NODE *aNode, const NODE *aOverride=NULL)
Definition: pns_node.cpp:178
int m_kindMask
(solids, vias, segments, etc...)
Definition: pns_node.cpp:201
virtual int HoleToHoleClearance(const ITEM *aA, const ITEM *aB)=0
const ITEM * m_item
the item we are looking for collisions with
Definition: pns_node.h:133
void releaseGarbage()
Definition: pns_node.cpp:1257
void addVia(VIA *aVia)
Definition: pns_node.cpp:539
ITEM_SET::ENTRIES LINKED_ITEMS
Joints are hashed by their position, layers and net.
Definition: pns_joint.h:45
virtual void SetRank(int aRank)
Definition: pns_item.h:210
const LINKED_ITEMS & LinkList() const
Definition: pns_joint.h:195
~NODE()
Return the expected clearance between items a and b.
Definition: pns_node.cpp:65
int SegmentCount() const
Function SegmentCount()
ARC * findRedundantArc(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1387
const ITEM_SET HitTest(const VECTOR2I &aPoint) const
Find all items that contain the point aPoint.
Definition: pns_node.cpp:494
void addArc(ARC *aVia)
Definition: pns_node.cpp:633
void SetLayers(const LAYER_RANGE &aLayers)
Definition: pns_item.h:151
int QueryColliding(const ITEM *aItem, OBSTACLES &aObstacles, int aKindMask=ITEM::ANY_T, int aLimitCount=-1, bool aDifferentNetsOnly=true)
Find items colliding (closer than clearance) with the item aItem.
Definition: pns_node.cpp:259
SHAPE_LINE_CHAIN m_hull
Hull of the colliding m_item.
Definition: pns_node.h:111
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
Definition: pns_node.cpp:1027
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:136
NET_ITEMS_LIST * GetItemsForNet(int aNet)
Returns list of all items in a given net.
Definition: pns_index.cpp:71
const VECTOR2I & Pos() const
Definition: pns_solid.h:101
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Replace an item with another one.
Definition: pns_node.cpp:769
virtual VECTOR2I Anchor(int n) const
Definition: pns_item.h:213
void RemoveByMarker(int aMarker)
Definition: pns_node.cpp:1337
Definition: seg.h:41
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
const SHAPE * Shape() const override
Return the geometrical shape of the item.
Definition: pns_arc.h:78
void removeSolidIndex(SOLID *aSeg)
Definition: pns_node.cpp:757
ITEM_SET::iterator end()
Definition: pns_index.h:118
JOINT_MAP::value_type TagJointPair
Definition: pns_node.h:441
ITEM_SET::iterator begin()
Definition: pns_index.h:117
void Dump(bool aLong=false)
Definition: pns_node.cpp:1143
const SEG CSegment(int aIndex) const
Function CSegment()
void Dump() const
Definition: pns_node.cpp:1115
int Size() const
Returns number of items stored in the index.
Definition: pns_index.h:115
SHAPE_LINE_CHAIN.
void AllItemsInNet(int aNet, std::set< ITEM * > &aItems, int aKindMask=-1)
Definition: pns_node.cpp:1298
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Check if the item collides with anything else in the world, and if found, returns the obstacle.
Definition: pns_node.cpp:427
HASH_TAG m_tag
< hash tag for unordered_multimap
Definition: pns_joint.h:256
JOINT & touchJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet)
Touch a joint and links it to an m_item.
Definition: pns_node.cpp:1064
VECTOR2I A
Definition: seg.h:49
bool OfKind(int aKindMask) const
Return true if the item's type matches the mask aKindMask.
Definition: pns_item.h:134
std::unordered_set< ITEM * > m_garbageItems
Definition: pns_node.h:459
void Add(ITEM *aItem)
Adds item to the spatial index.
Definition: pns_index.cpp:28
const ENTRIES & CItems() const
Definition: pns_itemset.h:139
void removeViaIndex(VIA *aVia)
Definition: pns_node.cpp:749
int Width() const
Return true if the line is geometrically identical as line aOther.
Definition: pns_line.h:156
void followLine(LINKED_ITEM *aCurrent, bool aScanDirection, int &aPos, int aLimit, VECTOR2I *aCorners, LINKED_ITEM **aSegments, bool *aArcReversed, bool &aGuardHit, bool aStopAtLockedJoints)
Definition: pns_node.cpp:865
const ITEM * m_head
Item we search collisions with.
Definition: pns_node.h:108
void Merge(const JOINT &aJoint)
Definition: pns_joint.h:222
void GetUpdatedItems(ITEM_VECTOR &aRemoved, ITEM_VECTOR &aAdded)
Return the list of items removed and added in this branch with respect to the root branch.
Definition: pns_node.cpp:1225
void removeArcIndex(ARC *aVia)
Definition: pns_node.cpp:697
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:126
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:152
virtual bool IsConnected() const
Returns information if the object is derived from BOARD_CONNECTED_ITEM.
Definition: board_item.h:136
SHAPE_ARC Reversed() const
Definition: shape_arc.cpp:483
int LinkCount(int aMask=-1) const
Definition: pns_joint.h:210
const VECTOR2I & Pos() const
Definition: pns_joint.h:185
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:453
const VECTOR2I & m_point
Definition: pns_node.cpp:468
void Link(ITEM *aItem)
Unlink a given board item from the joint (upon its removal from a NODE)
Definition: pns_joint.h:141
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:443
const VIA & Via() const
Definition: pns_line.h:196
VECTOR2I m_ipFirst
First intersection between m_head and m_hull.
Definition: pns_node.h:112
std::vector< OBSTACLE > OBSTACLES
Definition: pns_node.h:154
const NODE * m_override
node that overrides root entries
Definition: pns_node.h:136
Push and Shove diff pair dimensions (gap) settings dialog.
virtual VECTOR2I Anchor(int n) const override
Definition: pns_arc.h:100
NODE * m_parent
node this node was branched from
Definition: pns_node.h:446
void Remove(ITEM *aItem)
Removes an item from the spatial index.
Definition: pns_index.cpp:46
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:615
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:215
INDEX.
Definition: pns_index.h:45
static ROUTER * GetInstance()
Definition: pns_router.cpp:79
Represent a contiguous set of PCB layers.
Definition: pns_layerset.h:31
const LAYER_RANGE & Layers() const
Definition: pns_item.h:150
void LockJoint(const VECTOR2I &aPos, const ITEM *aItem, bool aLock)
Definition: pns_node.cpp:1057
std::vector< ITEM * > ITEM_VECTOR
Definition: pns_node.h:153
static std::vector< std::string > split(const std::string &aStr, const std::string &aDelim)
Splits the input string into a vector of output strings.
Definition: kicad_string.h:273
Hold an object colliding with another object, along with some useful data about the collision.
Definition: pns_node.h:106
VECTOR2I B
Definition: seg.h:50