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