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