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