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