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