KiCad PCB EDA Suite
pns_node.cpp
Go to the documentation of this file.
1 /*
2  * KiRouter - a push-and-(sometimes-)shove PCB router
3  *
4  * Copyright (C) 2013-2019 CERN
5  * Copyright (C) 2016 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 #include <utility>
25 
26 #include <math/vector2d.h>
27 
28 #include <geometry/seg.h>
30 
31 #include "pns_arc.h"
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 
40 
41 namespace PNS {
42 
43 #ifdef DEBUG
44 static std::unordered_set<NODE*> allocNodes;
45 #endif
46 
48 {
49  wxLogTrace( "PNS", "NODE::create %p", this );
50  m_depth = 0;
51  m_root = this;
52  m_parent = NULL;
53  m_maxClearance = 800000; // fixme: depends on how thick traces are.
55  m_index = new INDEX;
56 
57 #ifdef DEBUG
58  allocNodes.insert( this );
59 #endif
60 }
61 
62 
64 {
65  wxLogTrace( "PNS", "NODE::delete %p", this );
66 
67  if( !m_children.empty() )
68  {
69  wxLogTrace( "PNS", "attempting to free a node that has kids." );
70  assert( false );
71  }
72 
73 #ifdef DEBUG
74  if( allocNodes.find( this ) == allocNodes.end() )
75  {
76  wxLogTrace( "PNS", "attempting to free an already-free'd node." );
77  assert( false );
78  }
79 
80  allocNodes.erase( this );
81 #endif
82 
83  m_joints.clear();
84 
85  for( ITEM* item : *m_index )
86  {
87  if( item->BelongsTo( this ) )
88  delete item;
89  }
90 
92  unlinkParent();
93 
94  delete m_index;
95 }
96 
97 int NODE::GetClearance( const ITEM* aA, const ITEM* aB ) const
98 {
99  if( !m_ruleResolver )
100  return 100000;
101 
102  return m_ruleResolver->Clearance( aA, aB );
103 }
104 
105 
107 {
108  NODE* child = new NODE;
109 
110  wxLogTrace( "PNS", "NODE::branch %p (parent %p)", child, this );
111 
112  m_children.insert( child );
113 
114  child->m_depth = m_depth + 1;
115  child->m_parent = this;
117  child->m_root = isRoot() ? this : m_root;
119 
120  // Immmediate offspring of the root branch needs not copy anything. For the rest, deep-copy
121  // joints, overridden item maps and pointers to stored items.
122  if( !isRoot() )
123  {
124  JOINT_MAP::iterator j;
125 
126  for( ITEM* item : *m_index )
127  child->m_index->Add( item );
128 
129  child->m_joints = m_joints;
130  child->m_override = m_override;
131  }
132 
133  wxLogTrace( "PNS", "%d items, %d joints, %d overrides",
134  child->m_index->Size(), (int) child->m_joints.size(), (int) child->m_override.size() );
135 
136  return child;
137 }
138 
139 
141 {
142  if( isRoot() )
143  return;
144 
145  m_parent->m_children.erase( this );
146 }
147 
148 
150  m_item( aItem ),
151  m_node( NULL ),
152  m_override( NULL ),
153  m_extraClearance( 0 )
154 {
155 }
156 
157 
158 void OBSTACLE_VISITOR::SetWorld( const NODE* aNode, const NODE* aOverride )
159 {
160  m_node = aNode;
161  m_override = aOverride;
162 }
163 
164 
165 bool OBSTACLE_VISITOR::visit( ITEM* aCandidate )
166 {
167  // check if there is a more recent branch with a newer
168  // (possibily modified) version of this item.
169  if( m_override && m_override->Overrides( aCandidate ) )
170  return true;
171 
172  return false;
173 }
174 
175 
176 // function object that visits potential obstacles and performs
177 // the actual collision refining
179 {
182 
185 
188 
191 
194 
196 
198 
199  DEFAULT_OBSTACLE_VISITOR( NODE::OBSTACLES& aTab, const ITEM* aItem, int aKindMask, bool aDifferentNetsOnly ) :
200  OBSTACLE_VISITOR( aItem ),
201  m_tab( aTab ),
202  m_kindMask( aKindMask ),
203  m_limitCount( -1 ),
204  m_matchCount( 0 ),
205  m_extraClearance( 0 ),
206  m_differentNetsOnly( aDifferentNetsOnly ),
207  m_forceClearance( -1 )
208  {
209  if( aItem && aItem->Kind() == ITEM::LINE_T )
210  {
211  m_extraClearance += static_cast<const LINE*>( aItem )->Width() / 2;
212  }
213  }
214 
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, false, nullptr, m_node, 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, NODE::OBSTACLES& aObstacles, int aKindMask,
279  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( const OBSTACLE& obs : obs_list )
335  {
336  VECTOR2I 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( const 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( const 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, false, nullptr, this );
479 }
480 
481 
483 {
486 
487  HIT_VISITOR( ITEM_SET& aTab, const VECTOR2I& aPoint ) :
489  m_items( aTab ), m_point( aPoint )
490  {}
491 
492  virtual ~HIT_VISITOR()
493  {
494  }
495 
496  bool operator()( ITEM* aItem ) override
497  {
498  SHAPE_CIRCLE cp( m_point, 0 );
499 
500  int cl = 0;
501 
502  if( aItem->Shape()->Collide( &cp, cl ) )
503  m_items.Add( aItem );
504 
505  return true;
506  }
507 };
508 
509 
510 const ITEM_SET NODE::HitTest( const VECTOR2I& aPoint ) const
511 {
512  ITEM_SET items;
513 
514  // fixme: we treat a point as an infinitely small circle - this is inefficient.
515  SHAPE_CIRCLE s( aPoint, 0 );
516  HIT_VISITOR visitor( items, aPoint );
517  visitor.SetWorld( this, NULL );
518 
519  m_index->Query( &s, m_maxClearance, visitor );
520 
521  if( !isRoot() ) // fixme: could be made cleaner
522  {
523  ITEM_SET items_root;
524  visitor.SetWorld( m_root, NULL );
525  HIT_VISITOR visitor_root( items_root, aPoint );
526  m_root->m_index->Query( &s, m_maxClearance, visitor_root );
527 
528  for( ITEM* item : items_root.Items() )
529  {
530  if( !Overrides( item ) )
531  items.Add( item );
532  }
533  }
534 
535  return items;
536 }
537 
538 
539 void NODE::addSolid( SOLID* aSolid )
540 {
541  if( aSolid->IsRoutable() )
542  linkJoint( aSolid->Pos(), aSolid->Layers(), aSolid->Net(), aSolid );
543 
544  m_index->Add( aSolid );
545 }
546 
547 void NODE::Add( std::unique_ptr< SOLID > aSolid )
548 {
549  aSolid->SetOwner( this );
550  addSolid( aSolid.release() );
551 }
552 
553 void NODE::addVia( VIA* aVia )
554 {
555  linkJoint( aVia->Pos(), aVia->Layers(), aVia->Net(), aVia );
556  m_index->Add( aVia );
557 }
558 
559 void NODE::Add( std::unique_ptr< VIA > aVia )
560 {
561  aVia->SetOwner( this );
562  addVia( aVia.release() );
563 }
564 
565 void NODE::Add( LINE& aLine, bool aAllowRedundant )
566 {
567  assert( !aLine.IsLinked() );
568 
569  SHAPE_LINE_CHAIN& l = aLine.Line();
570 
571  for( size_t i = 0; i < l.ArcCount(); i++ )
572  {
573  auto s = l.Arc( i );
574  ARC* rarc;
575 
576  if( !aAllowRedundant && ( rarc = findRedundantArc( s.GetP0(), s.GetP1(), aLine.Layers(), aLine.Net() ) ) )
577  aLine.LinkSegment( rarc );
578  else
579  {
580  auto newarc = std::make_unique< ARC >( aLine, s );
581  aLine.LinkSegment( newarc.get() );
582  Add( std::move( newarc ), true );
583  }
584  }
585 
586  for( int i = 0; i < l.SegmentCount(); i++ )
587  {
588  if( l.isArc( i ) )
589  continue;
590 
591  SEG s = l.CSegment( i );
592 
593  if( s.A != s.B )
594  {
595  SEGMENT* rseg;
596  if( !aAllowRedundant &&
597  (rseg = findRedundantSegment( s.A, s.B, aLine.Layers(), aLine.Net() )) )
598  {
599  // another line could be referencing this segment too :(
600  aLine.LinkSegment( rseg );
601  }
602  else
603  {
604  std::unique_ptr< SEGMENT > newseg( new SEGMENT( aLine, s ) );
605  aLine.LinkSegment( newseg.get() );
606  Add( std::move( newseg ), true );
607  }
608  }
609  }
610 }
611 
613 {
614  linkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
615  linkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
616 
617  m_index->Add( aSeg );
618 }
619 
620 bool NODE::Add( std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant )
621 {
622  if( aSegment->Seg().A == aSegment->Seg().B )
623  {
624  wxLogTrace( "PNS", "attempting to add a segment with same end coordinates, ignoring." );
625  return false;
626  }
627 
628  if( !aAllowRedundant && findRedundantSegment( aSegment.get() ) )
629  return false;
630 
631  aSegment->SetOwner( this );
632  addSegment( aSegment.release() );
633 
634  return true;
635 }
636 
637 void NODE::addArc( ARC* aArc )
638 {
639  linkJoint( aArc->Anchor( 0 ), aArc->Layers(), aArc->Net(), aArc );
640  linkJoint( aArc->Anchor( 1 ), aArc->Layers(), aArc->Net(), aArc );
641 
642  m_index->Add( aArc );
643 }
644 
645 void NODE::Add( std::unique_ptr< ARC > aArc )
646 {
647  aArc->SetOwner( this );
648  addArc( aArc.release() );
649 }
650 
651 void NODE::Add( std::unique_ptr< ITEM > aItem, bool aAllowRedundant )
652 {
653  switch( aItem->Kind() )
654  {
655  case ITEM::SOLID_T: Add( ItemCast<SOLID>( std::move( aItem ) ) ); break;
656  case ITEM::SEGMENT_T: Add( ItemCast<SEGMENT>( std::move( aItem ) ), aAllowRedundant ); break;
657  case ITEM::VIA_T: Add( ItemCast<VIA>( std::move( aItem ) ) ); break;
658 
659  case ITEM::ARC_T:
660  //todo(snh): Add redundant search
661  Add( ItemCast<ARC>( std::move( aItem ) ) );
662  break;
663 
664  case ITEM::LINE_T:
665  default:
666  assert( false );
667  }
668 }
669 
670 
671 void NODE::doRemove( ITEM* aItem )
672 {
673  // case 1: removing an item that is stored in the root node from any branch:
674  // mark it as overridden, but do not remove
675  if( aItem->BelongsTo( m_root ) && !isRoot() )
676  m_override.insert( aItem );
677 
678  // case 2: the item belongs to this branch or a parent, non-root branch,
679  // or the root itself and we are the root: remove from the index
680  else if( !aItem->BelongsTo( m_root ) || isRoot() )
681  m_index->Remove( aItem );
682 
683  // the item belongs to this particular branch: un-reference it
684  if( aItem->BelongsTo( this ) )
685  {
686  aItem->SetOwner( NULL );
687  m_root->m_garbageItems.insert( aItem );
688  }
689 }
690 
691 
693 {
694  unlinkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
695  unlinkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
696 }
697 
698 
700 {
701  unlinkJoint( aArc->Anchor( 0 ), aArc->Layers(), aArc->Net(), aArc );
702  unlinkJoint( aArc->Anchor( 1 ), aArc->Layers(), aArc->Net(), aArc );
703 }
704 
705 
706 void NODE::rebuildJoint( JOINT* aJoint, ITEM* aItem )
707 {
708  // We have to split a single joint (associated with a via or a pad, binding together multiple layers)
709  // into multiple independent joints. As I'm a lazy bastard, I simply delete the via/solid and all its links and re-insert them.
710 
711  JOINT::LINKED_ITEMS links( aJoint->LinkList() );
712  JOINT::HASH_TAG tag;
713  int net = aItem->Net();
714 
715  tag.net = net;
716  tag.pos = aJoint->Pos();
717 
718  bool split;
719  do
720  {
721  split = false;
722  auto range = m_joints.equal_range( tag );
723 
724  if( range.first == m_joints.end() )
725  break;
726 
727  // find and remove all joints containing the via to be removed
728 
729  for( auto f = range.first; f != range.second; ++f )
730  {
731  if( aItem->LayersOverlap( &f->second ) )
732  {
733  m_joints.erase( f );
734  split = true;
735  break;
736  }
737  }
738  } while( split );
739 
740  // and re-link them, using the former via's link list
741  for(ITEM* link : links)
742  {
743  if( link != aItem )
744  linkJoint( tag.pos, link->Layers(), net, link );
745  }
746 }
747 
748 
750 {
751  JOINT* jt = FindJoint( aVia->Pos(), aVia->Layers().Start(), aVia->Net() );
752  assert( jt );
753  rebuildJoint( jt, aVia );
754 }
755 
756 
758 {
759  // fixme: redundant code
760  JOINT* jt = FindJoint( aSolid->Pos(), aSolid->Layers().Start(), aSolid->Net() );
761  assert( jt );
762  rebuildJoint( jt, aSolid );
763 }
764 
765 
766 void NODE::Replace( ITEM* aOldItem, std::unique_ptr< ITEM > aNewItem )
767 {
768  Remove( aOldItem );
769  Add( std::move( aNewItem ) );
770 }
771 
772 void NODE::Replace( LINE& aOldLine, LINE& aNewLine )
773 {
774  Remove( aOldLine );
775  Add( aNewLine );
776 }
777 
778 void NODE::Remove( SOLID* aSolid )
779 {
780  removeSolidIndex( aSolid );
781  doRemove( aSolid );
782 }
783 
784 void NODE::Remove( VIA* aVia )
785 {
786  removeViaIndex( aVia );
787  doRemove( aVia );
788 }
789 
790 void NODE::Remove( SEGMENT* aSegment )
791 {
792  removeSegmentIndex( aSegment );
793  doRemove( aSegment );
794 }
795 
796 void NODE::Remove( ARC* aArc )
797 {
798  removeArcIndex( aArc );
799  doRemove( aArc );
800 }
801 
802 void NODE::Remove( ITEM* aItem )
803 {
804  switch( aItem->Kind() )
805  {
806  case ITEM::ARC_T:
807  Remove( static_cast<ARC*>( aItem ) );
808  break;
809 
810  case ITEM::SOLID_T:
811  Remove( static_cast<SOLID*>( aItem ) );
812  break;
813 
814  case ITEM::SEGMENT_T:
815  Remove( static_cast<SEGMENT*>( aItem ) );
816  break;
817 
818  case ITEM::LINE_T:
819  {
820  auto l = static_cast<LINE *> ( aItem );
821 
822  for ( auto s : l->LinkedSegments() )
823  Remove( s );
824 
825  break;
826  }
827 
828  case ITEM::VIA_T:
829  Remove( static_cast<VIA*>( aItem ) );
830  break;
831 
832  default:
833  break;
834  }
835 }
836 
837 
838 void NODE::Remove( LINE& aLine )
839 {
840  // LINE does not have a seperate remover, as LINEs are never truly a member of the tree
841  std::vector<LINKED_ITEM*>& segRefs = aLine.LinkedSegments();
842 
843  for( auto li : segRefs )
844  {
845  if( li->OfKind( ITEM::SEGMENT_T ) )
846  Remove( static_cast<SEGMENT*>( li ) );
847  else if( li->OfKind( ITEM::ARC_T ) )
848  Remove( static_cast<ARC*>( li ) );
849  }
850 
851  aLine.SetOwner( nullptr );
852  aLine.ClearSegmentLinks();
853 }
854 
855 
856 void NODE::followLine( LINKED_ITEM* aCurrent, int aScanDirection, int& aPos, int aLimit, VECTOR2I* aCorners,
857  LINKED_ITEM** aSegments, bool& aGuardHit, bool aStopAtLockedJoints )
858 {
859  bool prevReversed = false;
860 
861  const VECTOR2I guard = aCurrent->Anchor( aScanDirection );
862 
863  for( int count = 0 ; ; ++count )
864  {
865  const VECTOR2I p = aCurrent->Anchor( aScanDirection ^ prevReversed );
866  const JOINT* jt = FindJoint( p, aCurrent );
867 
868  assert( jt );
869 
870  aCorners[aPos] = jt->Pos();
871  aSegments[aPos] = aCurrent;
872  aPos += ( aScanDirection ? 1 : -1 );
873 
874  if( count && guard == p)
875  {
876  aSegments[aPos] = NULL;
877  aGuardHit = true;
878  break;
879  }
880 
881  bool locked = aStopAtLockedJoints ? jt->IsLocked() : false;
882 
883  if( locked || !jt->IsLineCorner() || aPos < 0 || aPos == aLimit )
884  break;
885 
886  aCurrent = jt->NextSegment( aCurrent );
887 
888  prevReversed = ( jt->Pos() == aCurrent->Anchor( aScanDirection ) );
889  }
890 }
891 
892 
893 const LINE NODE::AssembleLine( LINKED_ITEM* aSeg, int* aOriginSegmentIndex, bool aStopAtLockedJoints )
894 {
895  const int MaxVerts = 1024 * 16;
896 
897  VECTOR2I corners[MaxVerts + 1];
898  LINKED_ITEM* segs[MaxVerts + 1];
899 
900  LINE pl;
901  bool guardHit = false;
902 
903  int i_start = MaxVerts / 2, i_end = i_start + 1;
904 
905  pl.SetWidth( aSeg->Width() );
906  pl.SetLayers( aSeg->Layers() );
907  pl.SetNet( aSeg->Net() );
908  pl.SetOwner( this );
909 
910  followLine( aSeg, false, i_start, MaxVerts, corners, segs, guardHit, aStopAtLockedJoints );
911 
912  if( !guardHit )
913  followLine( aSeg, true, i_end, MaxVerts, corners, segs, guardHit, aStopAtLockedJoints );
914 
915  int n = 0;
916 
917  LINKED_ITEM* prev_seg = NULL;
918  bool originSet = false;
919 
920  for( int i = i_start + 1; i < i_end; i++ )
921  {
922  const VECTOR2I& p = corners[i];
923 
924  pl.Line().Append( p );
925 
926  if( segs[i] && prev_seg != segs[i] )
927  {
928  pl.LinkSegment( segs[i] );
929 
930  // latter condition to avoid loops
931  if( segs[i] == aSeg && aOriginSegmentIndex && !originSet )
932  {
933  *aOriginSegmentIndex = n;
934  originSet = true;
935  }
936  n++;
937  }
938 
939  prev_seg = segs[i];
940  }
941 
942  assert( pl.SegmentCount() != 0 );
943 
944  return pl;
945 }
946 
947 
948 void NODE::FindLineEnds( const LINE& aLine, JOINT& aA, JOINT& aB )
949 {
950  aA = *FindJoint( aLine.CPoint( 0 ), &aLine );
951  aB = *FindJoint( aLine.CPoint( -1 ), &aLine );
952 }
953 
954 
955 #if 0
956 void NODE::MapConnectivity( JOINT* aStart, std::vector<JOINT*>& aFoundJoints )
957 {
958  std::deque<JOINT*> searchQueue;
959  std::set<JOINT*> processed;
960 
961  searchQueue.push_back( aStart );
962  processed.insert( aStart );
963 
964  while( !searchQueue.empty() )
965  {
966  JOINT* current = searchQueue.front();
967  searchQueue.pop_front();
968 
969  for( ITEM* item : current->LinkList() )
970  {
971  if( item->OfKind( ITEM::SEGMENT_T ) )
972  {
973  SEGMENT* seg = static_cast<SEGMENT *>( item );
974  JOINT* a = FindJoint( seg->Seg().A, seg );
975  JOINT* b = FindJoint( seg->Seg().B, seg );
976  JOINT* next = ( *a == *current ) ? b : a;
977 
978  if( processed.find( next ) == processed.end() )
979  {
980  processed.insert( next );
981  searchQueue.push_back( next );
982  }
983  }
984  }
985  }
986 
987  for(JOINT* jt : processed)
988  aFoundJoints.push_back( jt );
989 }
990 #endif
991 
992 
993 int NODE::FindLinesBetweenJoints( JOINT& aA, JOINT& aB, std::vector<LINE>& aLines )
994 {
995  for( ITEM* item : aA.LinkList() )
996  {
997  if( item->Kind() == ITEM::SEGMENT_T )
998  {
999  SEGMENT* seg = static_cast<SEGMENT*>( item );
1000  LINE line = AssembleLine( seg );
1001 
1002  if( !line.Layers().Overlaps( aB.Layers() ) )
1003  continue;
1004 
1005  JOINT j_start, j_end;
1006 
1007  FindLineEnds( line, j_start, j_end );
1008 
1009  int id_start = line.CLine().Find( aA.Pos() );
1010  int id_end = line.CLine().Find( aB.Pos() );
1011 
1012  if( id_end < id_start )
1013  std::swap( id_end, id_start );
1014 
1015  if( id_start >= 0 && id_end >= 0 )
1016  {
1017  line.ClipVertexRange( id_start, id_end );
1018  aLines.push_back( line );
1019  }
1020  }
1021  }
1022 
1023  return 0;
1024 }
1025 
1026 
1027 JOINT* NODE::FindJoint( const VECTOR2I& aPos, int aLayer, int aNet )
1028 {
1029  JOINT::HASH_TAG tag;
1030 
1031  tag.net = aNet;
1032  tag.pos = aPos;
1033 
1034  JOINT_MAP::iterator f = m_joints.find( tag ), end = m_joints.end();
1035 
1036  if( f == end && !isRoot() )
1037  {
1038  end = m_root->m_joints.end();
1039  f = m_root->m_joints.find( tag ); // m_root->FindJoint(aPos, aLayer, aNet);
1040  }
1041 
1042  if( f == end )
1043  return NULL;
1044 
1045  while( f != end )
1046  {
1047  if( f->second.Layers().Overlaps( aLayer ) )
1048  return &f->second;
1049 
1050  ++f;
1051  }
1052 
1053  return NULL;
1054 }
1055 
1056 
1057 void NODE::LockJoint( const VECTOR2I& aPos, const ITEM* aItem, bool aLock )
1058 {
1059  JOINT& jt = touchJoint( aPos, aItem->Layers(), aItem->Net() );
1060  jt.Lock( aLock );
1061 }
1062 
1063 
1064 JOINT& NODE::touchJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet )
1065 {
1066  JOINT::HASH_TAG tag;
1067 
1068  tag.pos = aPos;
1069  tag.net = aNet;
1070 
1071  // try to find the joint in this node.
1072  JOINT_MAP::iterator f = m_joints.find( tag );
1073 
1074  std::pair<JOINT_MAP::iterator, JOINT_MAP::iterator> range;
1075 
1076  // not found and we are not root? find in the root and copy results here.
1077  if( f == m_joints.end() && !isRoot() )
1078  {
1079  range = m_root->m_joints.equal_range( tag );
1080 
1081  for( f = range.first; f != range.second; ++f )
1082  m_joints.insert( *f );
1083  }
1084 
1085  // now insert and combine overlapping joints
1086  JOINT jt( aPos, aLayers, aNet );
1087 
1088  bool merged;
1089 
1090  do
1091  {
1092  merged = false;
1093  range = m_joints.equal_range( tag );
1094 
1095  if( range.first == m_joints.end() )
1096  break;
1097 
1098  for( f = range.first; f != range.second; ++f )
1099  {
1100  if( aLayers.Overlaps( f->second.Layers() ) )
1101  {
1102  jt.Merge( f->second );
1103  m_joints.erase( f );
1104  merged = true;
1105  break;
1106  }
1107  }
1108  }
1109  while( merged );
1110 
1111  return m_joints.insert( TagJointPair( tag, jt ) )->second;
1112 }
1113 
1114 
1115 void JOINT::Dump() const
1116 {
1117  wxLogTrace( "PNS", "joint layers %d-%d, net %d, pos %s, links: %d", m_layers.Start(),
1118  m_layers.End(), m_tag.net, m_tag.pos.Format().c_str(), LinkCount() );
1119 }
1120 
1121 
1122 void NODE::linkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers,
1123  int aNet, ITEM* aWhere )
1124 {
1125  JOINT& jt = touchJoint( aPos, aLayers, aNet );
1126 
1127  jt.Link( aWhere );
1128 }
1129 
1130 
1131 void NODE::unlinkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers,
1132  int aNet, ITEM* aWhere )
1133 {
1134  // fixme: remove dangling joints
1135  JOINT& jt = touchJoint( aPos, aLayers, aNet );
1136 
1137  jt.Unlink( aWhere );
1138 }
1139 
1140 
1141 void NODE::Dump( bool aLong )
1142 {
1143 #if 0
1144  std::unordered_set<SEGMENT*> all_segs;
1146 
1147  for( i = m_items.begin(); i != m_items.end(); i++ )
1148  {
1149  if( (*i)->GetKind() == ITEM::SEGMENT_T )
1150  all_segs.insert( static_cast<SEGMENT*>( *i ) );
1151  }
1152 
1153  if( !isRoot() )
1154  {
1155  for( i = m_root->m_items.begin(); i != m_root->m_items.end(); i++ )
1156  {
1157  if( (*i)->GetKind() == ITEM::SEGMENT_T && !overrides( *i ) )
1158  all_segs.insert( static_cast<SEGMENT*>(*i) );
1159  }
1160  }
1161 
1162  JOINT_MAP::iterator j;
1163 
1164  if( aLong )
1165  for( j = m_joints.begin(); j != m_joints.end(); ++j )
1166  {
1167  wxLogTrace( "PNS", "joint : %s, links : %d\n",
1168  j->second.GetPos().Format().c_str(), j->second.LinkCount() );
1169  JOINT::LINKED_ITEMS::const_iterator k;
1170 
1171  for( k = j->second.GetLinkList().begin(); k != j->second.GetLinkList().end(); ++k )
1172  {
1173  const ITEM* m_item = *k;
1174 
1175  switch( m_item->GetKind() )
1176  {
1177  case ITEM::SEGMENT_T:
1178  {
1179  const SEGMENT* seg = static_cast<const SEGMENT*>( m_item );
1180  wxLogTrace( "PNS", " -> seg %s %s\n", seg->GetSeg().A.Format().c_str(),
1181  seg->GetSeg().B.Format().c_str() );
1182  break;
1183  }
1184 
1185  default:
1186  break;
1187  }
1188  }
1189  }
1190 
1191 
1192  int lines_count = 0;
1193 
1194  while( !all_segs.empty() )
1195  {
1196  SEGMENT* s = *all_segs.begin();
1197  LINE* l = AssembleLine( s );
1198 
1199  LINE::LinkedSegments* seg_refs = l->GetLinkedSegments();
1200 
1201  if( aLong )
1202  wxLogTrace( "PNS", "Line: %s, net %d ", l->GetLine().Format().c_str(), l->GetNet() );
1203 
1204  for( std::vector<SEGMENT*>::iterator j = seg_refs->begin(); j != seg_refs->end(); ++j )
1205  {
1206  wxLogTrace( "PNS", "%s ", (*j)->GetSeg().A.Format().c_str() );
1207 
1208  if( j + 1 == seg_refs->end() )
1209  wxLogTrace( "PNS", "%s\n", (*j)->GetSeg().B.Format().c_str() );
1210 
1211  all_segs.erase( *j );
1212  }
1213 
1214  lines_count++;
1215  }
1216 
1217  wxLogTrace( "PNS", "Local joints: %d, lines : %d \n", m_joints.size(), lines_count );
1218 #endif
1219 }
1220 
1221 
1223 {
1224  if( isRoot() )
1225  return;
1226 
1227  if( m_override.size() )
1228  aRemoved.reserve( m_override.size() );
1229 
1230  if( m_index->Size() )
1231  aAdded.reserve( m_index->Size() );
1232 
1233  for( ITEM* item : m_override )
1234  aRemoved.push_back( item );
1235 
1236  for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
1237  aAdded.push_back( *i );
1238 }
1239 
1241 {
1242  // copy the kids as the NODE destructor erases the item from the parent node.
1243  std::set<NODE*> kids = m_children;
1244 
1245  for( NODE* node : kids )
1246  {
1247  node->releaseChildren();
1248  delete node;
1249  }
1250 }
1251 
1252 
1254 {
1255  if( !isRoot() )
1256  return;
1257 
1258  for( ITEM* item : m_garbageItems )
1259  {
1260  if( !item->BelongsTo( this ) )
1261  delete item;
1262  }
1263 
1264  m_garbageItems.clear();
1265 }
1266 
1267 
1268 void NODE::Commit( NODE* aNode )
1269  {
1270  if( aNode->isRoot() )
1271  return;
1272 
1273  for( ITEM* item : aNode->m_override )
1274  Remove( item );
1275 
1276  for( auto i : *aNode->m_index )
1277  {
1278  i->SetRank( -1 );
1279  i->Unmark();
1280  Add( std::unique_ptr<ITEM>( i ) );
1281  }
1282 
1283  releaseChildren();
1284  releaseGarbage();
1285  }
1286 
1287 
1289 {
1290  releaseChildren();
1291 }
1292 
1293 
1294 void NODE::AllItemsInNet( int aNet, std::set<ITEM*>& aItems )
1295 {
1296  INDEX::NET_ITEMS_LIST* l_cur = m_index->GetItemsForNet( aNet );
1297 
1298  if( l_cur )
1299  {
1300  for( ITEM*item : *l_cur )
1301  aItems.insert( item );
1302  }
1303 
1304  if( !isRoot() )
1305  {
1306  INDEX::NET_ITEMS_LIST* l_root = m_root->m_index->GetItemsForNet( aNet );
1307 
1308  if( l_root )
1309  for( INDEX::NET_ITEMS_LIST::iterator i = l_root->begin(); i!= l_root->end(); ++i )
1310  if( !Overrides( *i ) )
1311  aItems.insert( *i );
1312  }
1313 }
1314 
1315 
1316 void NODE::ClearRanks( int aMarkerMask )
1317 {
1318  for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
1319  {
1320  (*i)->SetRank( -1 );
1321  (*i)->Mark( (*i)->Marker() & (~aMarkerMask) );
1322  }
1323 }
1324 
1325 
1326 void NODE::RemoveByMarker( int aMarker )
1327 {
1328  std::list<ITEM*> garbage;
1329 
1330  for( ITEM* item : *m_index )
1331  {
1332  if( item->Marker() & aMarker )
1333  garbage.push_back( item );
1334  }
1335 
1336  for( ITEM* item : garbage )
1337  Remove( item );
1338 }
1339 
1341  int aNet )
1342 {
1343  JOINT* jtStart = FindJoint( A, lr.Start(), aNet );
1344 
1345  if( !jtStart )
1346  return nullptr;
1347 
1348  for( ITEM* item : jtStart->LinkList() )
1349  {
1350  if( item->OfKind( ITEM::SEGMENT_T ) )
1351  {
1352  SEGMENT* seg2 = (SEGMENT*)item;
1353 
1354  const VECTOR2I a2( seg2->Seg().A );
1355  const VECTOR2I b2( seg2->Seg().B );
1356 
1357  if( seg2->Layers().Start() == lr.Start() &&
1358  ((A == a2 && B == b2) || (A == b2 && B == a2)) )
1359  return seg2;
1360  }
1361  }
1362 
1363  return nullptr;
1364 }
1365 
1367 {
1368  return findRedundantSegment( aSeg->Seg().A, aSeg->Seg().B, aSeg->Layers(), aSeg->Net() );
1369 }
1370 
1371 ARC* NODE::findRedundantArc( const VECTOR2I& A, const VECTOR2I& B, const LAYER_RANGE& lr,
1372  int aNet )
1373 {
1374  JOINT* jtStart = FindJoint( A, lr.Start(), aNet );
1375 
1376  if( !jtStart )
1377  return nullptr;
1378 
1379  for( ITEM* item : jtStart->LinkList() )
1380  {
1381  if( item->OfKind( ITEM::ARC_T ) )
1382  {
1383  ARC* seg2 = static_cast<ARC*>( item );
1384 
1385  const VECTOR2I a2( seg2->Anchor( 0 ) );
1386  const VECTOR2I b2( seg2->Anchor( 1 ) );
1387 
1388  if( seg2->Layers().Start() == lr.Start() &&
1389  ((A == a2 && B == b2) || (A == b2 && B == a2)) )
1390  return seg2;
1391  }
1392  }
1393 
1394  return nullptr;
1395 }
1396 
1398 {
1399  return findRedundantArc( aArc->Anchor( 0 ), aArc->Anchor( 1 ), aArc->Layers(), aArc->Net() );
1400 }
1401 
1402 
1403 int NODE::QueryJoints( const BOX2I& aBox,
1404  std::vector<JOINT*>& aJoints,
1405  int aLayerMask,
1406  int aKindMask
1407  )
1408 {
1409  int n = 0;
1410 
1411  aJoints.clear();
1412 
1413  for( auto j = m_joints.begin(); j != m_joints.end(); ++j )
1414  {
1415  if ( aBox.Contains(j->second.Pos()) && j->second.LinkCount ( aKindMask ) )
1416  {
1417  aJoints.push_back( &j->second );
1418  n++;
1419 
1420  }
1421  }
1422 
1423  if ( isRoot() )
1424  return n;
1425 
1426  for( auto j = m_root->m_joints.begin(); j != m_root->m_joints.end(); ++j )
1427  {
1428  if( ! Overrides( &j->second) )
1429  { if ( aBox.Contains(j->second.Pos()) && j->second.LinkCount ( aKindMask ) )
1430  {
1431  aJoints.push_back( &j->second );
1432  n++;
1433  }
1434  }
1435  }
1436 
1437  return n;
1438 
1439 
1440 }
1441 
1442 
1444 {
1445  INDEX::NET_ITEMS_LIST* l_cur = m_index->GetItemsForNet( aParent->GetNetCode() );
1446 
1447  if( l_cur )
1448  {
1449  for( ITEM* item : *l_cur )
1450  if( item->Parent() == aParent )
1451  return item;
1452  }
1453 
1454  return NULL;
1455 }
1456 
1457 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:128
int Find(const VECTOR2I &aP) const
Function Find()
const SHAPE_LINE_CHAIN & CLine() const
Const accessor to the underlying shape
Definition: pns_line.h:144
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:1316
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:505
ITEM * m_item
Item found to be colliding with m_head
Definition: pns_node.h:86
const SHAPE_ARC & Arc(size_t aArc) const
DEFAULT_OBSTACLE_VISITOR(NODE::OBSTACLES &aTab, const ITEM *aItem, int aKindMask, bool aDifferentNetsOnly)
Definition: pns_node.cpp:199
long long int Length() const
Function Length()
const NODE * m_node
node we are searching in (either root or a branch)
Definition: pns_node.h:124
void SetOwner(NODE *aOwner)
Functon SetOwner()
Definition: pns_item.h:180
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
int GetNetCode() const
Function GetNetCode.
VECTOR2I m_ipLast
Definition: pns_node.h:93
NODE.
Definition: pns_node.h:145
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:304
bool IsRoutable() const
Definition: pns_item.h:242
void releaseChildren()
Definition: pns_node.cpp:1240
int SegmentCount() const
Returns the number of segments in the line
Definition: pns_line.h:150
void unlinkParent()
Definition: pns_node.cpp:140
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:152
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:993
LINKED_ITEM * NextSegment(ITEM *aCurrent) const
For trivial joints, returns the segment adjacent to (aCurrent).
Definition: pns_joint.h:160
ENTRIES & Items()
Definition: pns_itemset.h:140
int m_distFirst
... and the distance thereof
Definition: pns_node.h:96
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
finds the joints corresponding to the ends of line aLine
Definition: pns_node.cpp:948
void AllItemsInNet(int aNet, std::set< ITEM * > &aItems)
Definition: pns_node.cpp:1294
void doRemove(ITEM *aItem)
Definition: pns_node.cpp:671
void removeSegmentIndex(SEGMENT *aSeg)
Definition: pns_node.cpp:692
bool IsLocked() const
Definition: pns_joint.h:250
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:253
int QueryJoints(const BOX2I &aBox, std::vector< JOINT * > &aJoints, int aLayerMask=-1, int aKindMask=ITEM::ANY_T)
Definition: pns_node.cpp:1403
void Lock(bool aLock=true)
Definition: pns_joint.h:245
const SEG & Seg() const
Definition: pns_segment.h:83
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:434
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:1122
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:1268
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:106
const VECTOR2I & Pos() const
Definition: pns_via.h:100
ITEM_SET & m_items
Definition: pns_node.cpp:484
bool EndsWithVia() const
Definition: pns_line.h:276
void unlinkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
unlinks an item from a joint
Definition: pns_node.cpp:1131
bool operator()(ITEM *aItem) override
Definition: pns_node.cpp:496
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
bool isRoot() const
Definition: pns_node.h:477
virtual ~HIT_VISITOR()
Definition: pns_node.cpp:492
int PathLength(const VECTOR2I &aP) const
Function PathLength()
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:517
void Remove(ARC *aArc)
Function Remove()
Definition: pns_node.cpp:796
void SetWidth(int aWidth)
Sets line width
Definition: pns_line.h:180
int Start() const
Definition: pns_layerset.h:83
void SetNet(int aNet)
Definition: pns_item.h:148
bool LayersOverlap(const ITEM *aOther) const
Function LayersOverlap()
Definition: pns_item.h:163
const VECTOR2I & CPoint(int aIdx) const
Returns the aIdx-th point of the line
Definition: pns_line.h:168
virtual int Width() const
int End() const
Definition: pns_layerset.h:88
void addSegment(SEGMENT *aSeg)
Definition: pns_node.cpp:612
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:502
int m_depth
depth of the node (number of parent nodes in the inheritance chain)
Definition: pns_node.h:520
JOINT.
Definition: pns_joint.h:43
RULE_RESOLVER * m_ruleResolver
Design rules resolver
Definition: pns_node.h:514
Struct OBSTACLE_VISITOR.
Definition: pns_node.h:102
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:539
int GetClearance(const ITEM *aA, const ITEM *aB) const
Returns the expected clearance between items a and b.
Definition: pns_node.cpp:97
void KillChildren()
Destroys all child nodes. Applicable only to the root node.
Definition: pns_node.cpp:1288
bool BelongsTo(NODE *aNode) const
Function BelongsTo()
Definition: pns_item.h:187
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Function AssembleLine()
Definition: pns_node.cpp:893
#define NULL
void rebuildJoint(JOINT *aJoint, ITEM *aItem)
Definition: pns_node.cpp:706
OBSTACLES & m_tab
list of encountered obstacles
Definition: pns_node.cpp:181
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:214
int Net() const
Definition: pns_item.h:149
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:1340
virtual int Clearance(const ITEM *aA, const ITEM *aB) const =0
bool Contains(const Vec &aPoint) const
Function Contains.
Definition: box2.h:150
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:149
void ClipVertexRange(int aStart, int aEnd)
Clips the line to a given range of vertices.
Definition: pns_line.cpp:901
bool operator()(ITEM *aCandidate) override
Definition: pns_node.cpp:224
bool visit(ITEM *aCandidate)
Definition: pns_node.cpp:165
std::unordered_set< ITEM * > m_override
hash of root's items that have been changed in this node
Definition: pns_node.h:508
void SetWorld(const NODE *aNode, const NODE *aOverride=NULL)
Definition: pns_node.cpp:158
int m_kindMask
acccepted kinds of colliding items (solids, vias, segments, etc...)
Definition: pns_node.cpp:184
void LinkSegment(LINKED_ITEM *aSeg)
Adds a reference to a segment registered in a NODE that is a part of this line.
Definition: pns_line.h:202
const ITEM * m_item
the item we are looking for collisions with
Definition: pns_node.h:121
void releaseGarbage()
Definition: pns_node.cpp:1253
void addVia(VIA *aVia)
Definition: pns_node.cpp:553
ITEM_SET::ENTRIES LINKED_ITEMS
Definition: pns_joint.h:46
const LINKED_ITEMS & LinkList() const
Definition: pns_joint.h:196
int m_distLast
Definition: pns_node.h:96
int SegmentCount() const
Function SegmentCount()
ARC * findRedundantArc(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1371
const ITEM_SET HitTest(const VECTOR2I &aPoint) const
Function HitTest()
Definition: pns_node.cpp:510
void addArc(ARC *aVia)
Definition: pns_node.cpp:637
void SetLayers(const LAYER_RANGE &aLayers)
Definition: pns_item.h:152
SHAPE_LINE_CHAIN m_hull
Hull of the colliding m_item
Definition: pns_node.h:89
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:1027
SHAPE_LINE_CHAIN & Line()
Modifiable accessor to the underlying shape
Definition: pns_line.h:138
NET_ITEMS_LIST * GetItemsForNet(int aNet)
Function GetItemsForNet()
Definition: pns_index.cpp:139
const VECTOR2I & Pos() const
Definition: pns_solid.h:76
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Function Replace()
Definition: pns_node.cpp:766
virtual VECTOR2I Anchor(int n) const
Definition: pns_item.h:226
void RemoveByMarker(int aMarker)
Definition: pns_node.cpp:1326
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:757
int m_extraClearance
additional clearance
Definition: pns_node.cpp:193
ITEM_SET::iterator end()
Definition: pns_index.h:141
JOINT_MAP::value_type TagJointPair
Definition: pns_node.h:442
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:209
void ClearSegmentLinks()
Erases the linking information. Used to detach the line from the owning node.
Definition: pns_line.cpp:936
ITEM_SET::iterator begin()
Definition: pns_index.h:140
void Dump(bool aLong=false)
Prints the contents and joints structure
Definition: pns_node.cpp:1141
int m_limitCount
max number of hits
Definition: pns_node.cpp:187
const SEG CSegment(int aIndex) const
Function CSegment()
void Dump() const
Definition: pns_node.cpp:1115
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:427
HASH_TAG m_tag
hash tag for unordered_multimap
Definition: pns_joint.h:257
int m_matchCount
number of items found so far
Definition: pns_node.cpp:190
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:1064
VECTOR2I A
Definition: seg.h:47
bool OfKind(int aKindMask) const
Function OfKind()
Definition: pns_item.h:133
std::unordered_set< ITEM * > m_garbageItems
Definition: pns_node.h:522
void Add(ITEM *aItem)
Function Add()
Definition: pns_index.cpp:86
const ENTRIES & CItems() const
Definition: pns_itemset.h:141
void removeViaIndex(VIA *aVia)
Definition: pns_node.cpp:749
int Width() const
Returns line width
Definition: pns_line.h:187
const ITEM * m_head
Item we search collisions with
Definition: pns_node.h:83
ITEM * FindItemByParent(const BOARD_CONNECTED_ITEM *aParent)
Definition: pns_node.cpp:1443
void Merge(const JOINT &aJoint)
Definition: pns_joint.h:223
void GetUpdatedItems(ITEM_VECTOR &aRemoved, ITEM_VECTOR &aAdded)
Function GetUpdatedItems()
Definition: pns_node.cpp:1222
void removeArcIndex(ARC *aVia)
Definition: pns_node.cpp:699
PnsKind Kind() const
Function Kind()
Definition: pns_item.h:123
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:148
int LinkCount(int aMask=-1) const
Definition: pns_joint.h:211
const VECTOR2I & Pos() const
Definition: pns_joint.h:186
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:511
void followLine(LINKED_ITEM *aCurrent, int aScanDirection, int &aPos, int aLimit, VECTOR2I *aCorners, LINKED_ITEM **aSegments, bool &aGuardHit, bool aStopAtLockedJoints)
scans the joint map, forming a line starting from segment (current).
Definition: pns_node.cpp:856
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:142
bool IsLinked() const
Definition: pns_line.h:214
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:496
const VIA & Via() const
Definition: pns_line.h:281
VECTOR2I m_ipFirst
First and last intersection point between the head item and the hull of the colliding m_item
Definition: pns_node.h:93
std::vector< OBSTACLE > OBSTACLES
Definition: pns_node.h:150
const NODE * m_override
node that overrides root entries
Definition: pns_node.h:127
Push and Shove diff pair dimensions (gap) settings dialog.
virtual VECTOR2I Anchor(int n) const override
Definition: pns_arc.h:97
NODE * m_parent
node this node was branched from
Definition: pns_node.h:499
void Remove(ITEM *aItem)
Function Remove()
Definition: pns_index.cpp:103
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
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:620
INDEX.
Definition: pns_index.h:46
LAYER_RANGE.
Definition: pns_layerset.h:32
const LAYER_RANGE & Layers() const
Definition: pns_item.h:151
void LockJoint(const VECTOR2I &aPos, const ITEM *aItem, bool aLock)
Definition: pns_node.cpp:1057
std::vector< ITEM * > ITEM_VECTOR
Definition: pns_node.h:149
Struct OBSTACLE.
Definition: pns_node.h:80
VECTOR2I B
Definition: seg.h:48