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