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