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