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(), aItem->Layer() );
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 
557  m_index->Add( aVia );
558 }
559 
560 void NODE::Add( std::unique_ptr< VIA > aVia )
561 {
562  aVia->SetOwner( this );
563  addVia( aVia.release() );
564 }
565 
566 void NODE::Add( LINE& aLine, bool aAllowRedundant )
567 {
568  assert( !aLine.IsLinked() );
569 
570  SHAPE_LINE_CHAIN& l = aLine.Line();
571 
572  for( size_t i = 0; i < l.ArcCount(); i++ )
573  {
574  auto s = l.Arc( i );
575  ARC* rarc;
576 
577  if( !aAllowRedundant
578  && ( rarc = findRedundantArc( s.GetP0(), s.GetP1(), aLine.Layers(), aLine.Net() ) ) )
579  {
580  aLine.Link( rarc );
581  }
582  else
583  {
584  auto newarc = std::make_unique< ARC >( aLine, s );
585  aLine.Link( newarc.get() );
586  Add( std::move( newarc ), true );
587  }
588  }
589 
590  for( int i = 0; i < l.SegmentCount(); i++ )
591  {
592  if( l.isArc( i ) )
593  continue;
594 
595  SEG s = l.CSegment( i );
596 
597  if( s.A != s.B )
598  {
599  SEGMENT* rseg;
600 
601  if( !aAllowRedundant
602  && ( rseg = findRedundantSegment( s.A, s.B, aLine.Layers(), aLine.Net() ) ) )
603  {
604  // another line could be referencing this segment too :(
605  aLine.Link( rseg );
606  }
607  else
608  {
609  std::unique_ptr<SEGMENT> newseg = std::make_unique<SEGMENT>( aLine, s );
610  aLine.Link( newseg.get() );
611  Add( std::move( newseg ), true );
612  }
613  }
614  }
615 }
616 
618 {
619  linkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
620  linkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
621 
622  m_index->Add( aSeg );
623 }
624 
625 bool NODE::Add( std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant )
626 {
627  if( aSegment->Seg().A == aSegment->Seg().B )
628  {
629  wxLogTrace( "PNS", "attempting to add a segment with same end coordinates, ignoring." );
630  return false;
631  }
632 
633  if( !aAllowRedundant && findRedundantSegment( aSegment.get() ) )
634  return false;
635 
636  aSegment->SetOwner( this );
637  addSegment( aSegment.release() );
638 
639  return true;
640 }
641 
642 void NODE::addArc( ARC* aArc )
643 {
644  linkJoint( aArc->Anchor( 0 ), aArc->Layers(), aArc->Net(), aArc );
645  linkJoint( aArc->Anchor( 1 ), aArc->Layers(), aArc->Net(), aArc );
646 
647  m_index->Add( aArc );
648 }
649 
650 void NODE::Add( std::unique_ptr< ARC > aArc )
651 {
652  aArc->SetOwner( this );
653  addArc( aArc.release() );
654 }
655 
656 void NODE::Add( std::unique_ptr< ITEM > aItem, bool aAllowRedundant )
657 {
658  switch( aItem->Kind() )
659  {
660  case ITEM::SOLID_T: Add( ItemCast<SOLID>( std::move( aItem ) ) ); break;
661  case ITEM::SEGMENT_T: Add( ItemCast<SEGMENT>( std::move( aItem ) ), aAllowRedundant ); break;
662  case ITEM::VIA_T: Add( ItemCast<VIA>( std::move( aItem ) ) ); break;
663 
664  case ITEM::ARC_T:
665  //todo(snh): Add redundant search
666  Add( ItemCast<ARC>( std::move( aItem ) ) );
667  break;
668 
669  case ITEM::LINE_T:
670  default:
671  assert( false );
672  }
673 }
674 
675 
676 void NODE::doRemove( ITEM* aItem )
677 {
678  // case 1: removing an item that is stored in the root node from any branch:
679  // mark it as overridden, but do not remove
680  if( aItem->BelongsTo( m_root ) && !isRoot() )
681  m_override.insert( aItem );
682 
683  // case 2: the item belongs to this branch or a parent, non-root branch,
684  // or the root itself and we are the root: remove from the index
685  else if( !aItem->BelongsTo( m_root ) || isRoot() )
686  m_index->Remove( aItem );
687 
688  // the item belongs to this particular branch: un-reference it
689  if( aItem->BelongsTo( this ) )
690  {
691  aItem->SetOwner( NULL );
692  m_root->m_garbageItems.insert( aItem );
693  }
694 }
695 
696 
698 {
699  unlinkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
700  unlinkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
701 }
702 
703 
705 {
706  unlinkJoint( aArc->Anchor( 0 ), aArc->Layers(), aArc->Net(), aArc );
707  unlinkJoint( aArc->Anchor( 1 ), aArc->Layers(), aArc->Net(), aArc );
708 }
709 
710 
711 void NODE::rebuildJoint( JOINT* aJoint, ITEM* aItem )
712 {
713  // We have to split a single joint (associated with a via or a pad, binding together multiple layers)
714  // into multiple independent joints. As I'm a lazy bastard, I simply delete the via/solid and all its links and re-insert them.
715 
716  JOINT::LINKED_ITEMS links( aJoint->LinkList() );
717  JOINT::HASH_TAG tag;
718  int net = aItem->Net();
719 
720  tag.net = net;
721  tag.pos = aJoint->Pos();
722 
723  bool split;
724  do
725  {
726  split = false;
727  auto range = m_joints.equal_range( tag );
728 
729  if( range.first == m_joints.end() )
730  break;
731 
732  // find and remove all joints containing the via to be removed
733 
734  for( auto f = range.first; f != range.second; ++f )
735  {
736  if( aItem->LayersOverlap( &f->second ) )
737  {
738  m_joints.erase( f );
739  split = true;
740  break;
741  }
742  }
743  } while( split );
744 
745  // and re-link them, using the former via's link list
746  for(ITEM* link : links)
747  {
748  if( link != aItem )
749  linkJoint( tag.pos, link->Layers(), net, link );
750  }
751 }
752 
753 
755 {
756  JOINT* jt = FindJoint( aVia->Pos(), aVia->Layers().Start(), aVia->Net() );
757  assert( jt );
758  rebuildJoint( jt, aVia );
759 }
760 
761 
763 {
764  if( !aSolid->IsRoutable() )
765  return;
766 
767  // fixme: redundant code
768  JOINT* jt = FindJoint( aSolid->Pos(), aSolid->Layers().Start(), aSolid->Net() );
769  assert( jt );
770  rebuildJoint( jt, aSolid );
771 }
772 
773 
774 void NODE::Replace( ITEM* aOldItem, std::unique_ptr< ITEM > aNewItem )
775 {
776  Remove( aOldItem );
777  Add( std::move( aNewItem ) );
778 }
779 
780 void NODE::Replace( LINE& aOldLine, LINE& aNewLine )
781 {
782  Remove( aOldLine );
783  Add( aNewLine );
784 }
785 
786 void NODE::Remove( SOLID* aSolid )
787 {
788  removeSolidIndex( aSolid );
789  doRemove( aSolid );
790 }
791 
792 void NODE::Remove( VIA* aVia )
793 {
794  removeViaIndex( aVia );
795  doRemove( aVia );
796 }
797 
798 void NODE::Remove( SEGMENT* aSegment )
799 {
800  removeSegmentIndex( aSegment );
801  doRemove( aSegment );
802 }
803 
804 void NODE::Remove( ARC* aArc )
805 {
806  removeArcIndex( aArc );
807  doRemove( aArc );
808 }
809 
810 void NODE::Remove( ITEM* aItem )
811 {
812  switch( aItem->Kind() )
813  {
814  case ITEM::ARC_T:
815  Remove( static_cast<ARC*>( aItem ) );
816  break;
817 
818  case ITEM::SOLID_T:
819  Remove( static_cast<SOLID*>( aItem ) );
820  break;
821 
822  case ITEM::SEGMENT_T:
823  Remove( static_cast<SEGMENT*>( aItem ) );
824  break;
825 
826  case ITEM::LINE_T:
827  {
828  auto l = static_cast<LINE *> ( aItem );
829 
830  for ( auto s : l->Links() )
831  Remove( s );
832 
833  break;
834  }
835 
836  case ITEM::VIA_T:
837  Remove( static_cast<VIA*>( aItem ) );
838  break;
839 
840  default:
841  break;
842  }
843 }
844 
845 
846 void NODE::Remove( LINE& aLine )
847 {
848  // LINE does not have a seperate remover, as LINEs are never truly a member of the tree
849  std::vector<LINKED_ITEM*>& segRefs = aLine.Links();
850 
851  for( auto li : segRefs )
852  {
853  if( li->OfKind( ITEM::SEGMENT_T ) )
854  Remove( static_cast<SEGMENT*>( li ) );
855  else if( li->OfKind( ITEM::ARC_T ) )
856  Remove( static_cast<ARC*>( li ) );
857  }
858 
859  aLine.SetOwner( nullptr );
860  aLine.ClearLinks();
861 }
862 
863 
864 void NODE::followLine( LINKED_ITEM* aCurrent, int aScanDirection, int& aPos, int aLimit, VECTOR2I* aCorners,
865  LINKED_ITEM** aSegments, bool& aGuardHit, bool aStopAtLockedJoints )
866 {
867  bool prevReversed = false;
868 
869  const VECTOR2I guard = aCurrent->Anchor( aScanDirection );
870 
871  for( int count = 0 ; ; ++count )
872  {
873  const VECTOR2I p = aCurrent->Anchor( aScanDirection ^ prevReversed );
874  const JOINT* jt = FindJoint( p, aCurrent );
875 
876  assert( jt );
877 
878  aCorners[aPos] = jt->Pos();
879  aSegments[aPos] = aCurrent;
880  aPos += ( aScanDirection ? 1 : -1 );
881 
882  if( count && guard == p)
883  {
884  aSegments[aPos] = NULL;
885  aGuardHit = true;
886  break;
887  }
888 
889  bool locked = aStopAtLockedJoints ? jt->IsLocked() : false;
890 
891  if( locked || !jt->IsLineCorner() || aPos < 0 || aPos == aLimit )
892  break;
893 
894  aCurrent = jt->NextSegment( aCurrent );
895 
896  prevReversed = ( jt->Pos() == aCurrent->Anchor( aScanDirection ) );
897  }
898 }
899 
900 
901 const LINE NODE::AssembleLine( LINKED_ITEM* aSeg, int* aOriginSegmentIndex, bool aStopAtLockedJoints )
902 {
903  const int MaxVerts = 1024 * 16;
904 
905  VECTOR2I corners[MaxVerts + 1];
906  LINKED_ITEM* segs[MaxVerts + 1];
907 
908  LINE pl;
909  bool guardHit = false;
910 
911  int i_start = MaxVerts / 2, i_end = i_start + 1;
912 
913  pl.SetWidth( aSeg->Width() );
914  pl.SetLayers( aSeg->Layers() );
915  pl.SetNet( aSeg->Net() );
916  pl.SetOwner( this );
917 
918  followLine( aSeg, false, i_start, MaxVerts, corners, segs, guardHit, aStopAtLockedJoints );
919 
920  if( !guardHit )
921  followLine( aSeg, true, i_end, MaxVerts, corners, segs, guardHit, aStopAtLockedJoints );
922 
923  int n = 0;
924 
925  LINKED_ITEM* prev_seg = NULL;
926  bool originSet = false;
927 
928  for( int i = i_start + 1; i < i_end; i++ )
929  {
930  const VECTOR2I& p = corners[i];
931 
932  pl.Line().Append( p );
933 
934  if( segs[i] && prev_seg != segs[i] )
935  {
936  pl.Link( segs[i] );
937 
938  // latter condition to avoid loops
939  if( segs[i] == aSeg && aOriginSegmentIndex && !originSet )
940  {
941  *aOriginSegmentIndex = n;
942  originSet = true;
943  }
944  n++;
945  }
946 
947  prev_seg = segs[i];
948  }
949 
950  assert( pl.SegmentCount() != 0 );
951 
952  return pl;
953 }
954 
955 
956 void NODE::FindLineEnds( const LINE& aLine, JOINT& aA, JOINT& aB )
957 {
958  aA = *FindJoint( aLine.CPoint( 0 ), &aLine );
959  aB = *FindJoint( aLine.CPoint( -1 ), &aLine );
960 }
961 
962 
963 #if 0
964 void NODE::MapConnectivity( JOINT* aStart, std::vector<JOINT*>& aFoundJoints )
965 {
966  std::deque<JOINT*> searchQueue;
967  std::set<JOINT*> processed;
968 
969  searchQueue.push_back( aStart );
970  processed.insert( aStart );
971 
972  while( !searchQueue.empty() )
973  {
974  JOINT* current = searchQueue.front();
975  searchQueue.pop_front();
976 
977  for( ITEM* item : current->LinkList() )
978  {
979  if( item->OfKind( ITEM::SEGMENT_T ) )
980  {
981  SEGMENT* seg = static_cast<SEGMENT *>( item );
982  JOINT* a = FindJoint( seg->Seg().A, seg );
983  JOINT* b = FindJoint( seg->Seg().B, seg );
984  JOINT* next = ( *a == *current ) ? b : a;
985 
986  if( processed.find( next ) == processed.end() )
987  {
988  processed.insert( next );
989  searchQueue.push_back( next );
990  }
991  }
992  }
993  }
994 
995  for(JOINT* jt : processed)
996  aFoundJoints.push_back( jt );
997 }
998 #endif
999 
1000 
1001 int NODE::FindLinesBetweenJoints( const JOINT& aA, const JOINT& aB, std::vector<LINE>& aLines )
1002 {
1003  for( ITEM* item : aA.LinkList() )
1004  {
1005  if( item->Kind() == ITEM::SEGMENT_T )
1006  {
1007  SEGMENT* seg = static_cast<SEGMENT*>( item );
1008  LINE line = AssembleLine( seg );
1009 
1010  if( !line.Layers().Overlaps( aB.Layers() ) )
1011  continue;
1012 
1013  JOINT j_start, j_end;
1014 
1015  FindLineEnds( line, j_start, j_end );
1016 
1017  int id_start = line.CLine().Find( aA.Pos() );
1018  int id_end = line.CLine().Find( aB.Pos() );
1019 
1020  if( id_end < id_start )
1021  std::swap( id_end, id_start );
1022 
1023  if( id_start >= 0 && id_end >= 0 )
1024  {
1025  line.ClipVertexRange( id_start, id_end );
1026  aLines.push_back( line );
1027  }
1028  }
1029  }
1030 
1031  return 0;
1032 }
1033 
1034 
1035 JOINT* NODE::FindJoint( const VECTOR2I& aPos, int aLayer, int aNet )
1036 {
1037  JOINT::HASH_TAG tag;
1038 
1039  tag.net = aNet;
1040  tag.pos = aPos;
1041 
1042  JOINT_MAP::iterator f = m_joints.find( tag ), end = m_joints.end();
1043 
1044  if( f == end && !isRoot() )
1045  {
1046  end = m_root->m_joints.end();
1047  f = m_root->m_joints.find( tag ); // m_root->FindJoint(aPos, aLayer, aNet);
1048  }
1049 
1050  if( f == end )
1051  return NULL;
1052 
1053  while( f != end )
1054  {
1055  if( f->second.Layers().Overlaps( aLayer ) )
1056  return &f->second;
1057 
1058  ++f;
1059  }
1060 
1061  return NULL;
1062 }
1063 
1064 
1065 void NODE::LockJoint( const VECTOR2I& aPos, const ITEM* aItem, bool aLock )
1066 {
1067  JOINT& jt = touchJoint( aPos, aItem->Layers(), aItem->Net() );
1068  jt.Lock( aLock );
1069 }
1070 
1071 
1072 JOINT& NODE::touchJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet )
1073 {
1074  JOINT::HASH_TAG tag;
1075 
1076  tag.pos = aPos;
1077  tag.net = aNet;
1078 
1079  // try to find the joint in this node.
1080  JOINT_MAP::iterator f = m_joints.find( tag );
1081 
1082  std::pair<JOINT_MAP::iterator, JOINT_MAP::iterator> range;
1083 
1084  // not found and we are not root? find in the root and copy results here.
1085  if( f == m_joints.end() && !isRoot() )
1086  {
1087  range = m_root->m_joints.equal_range( tag );
1088 
1089  for( f = range.first; f != range.second; ++f )
1090  m_joints.insert( *f );
1091  }
1092 
1093  // now insert and combine overlapping joints
1094  JOINT jt( aPos, aLayers, aNet );
1095 
1096  bool merged;
1097 
1098  do
1099  {
1100  merged = false;
1101  range = m_joints.equal_range( tag );
1102 
1103  if( range.first == m_joints.end() )
1104  break;
1105 
1106  for( f = range.first; f != range.second; ++f )
1107  {
1108  if( aLayers.Overlaps( f->second.Layers() ) )
1109  {
1110  jt.Merge( f->second );
1111  m_joints.erase( f );
1112  merged = true;
1113  break;
1114  }
1115  }
1116  }
1117  while( merged );
1118 
1119  return m_joints.insert( TagJointPair( tag, jt ) )->second;
1120 }
1121 
1122 
1123 void JOINT::Dump() const
1124 {
1125  wxLogTrace( "PNS", "joint layers %d-%d, net %d, pos %s, links: %d", m_layers.Start(),
1126  m_layers.End(), m_tag.net, m_tag.pos.Format().c_str(), LinkCount() );
1127 }
1128 
1129 
1130 void NODE::linkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers,
1131  int aNet, ITEM* aWhere )
1132 {
1133  JOINT& jt = touchJoint( aPos, aLayers, aNet );
1134 
1135  jt.Link( aWhere );
1136 }
1137 
1138 
1139 void NODE::unlinkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers,
1140  int aNet, ITEM* aWhere )
1141 {
1142  // fixme: remove dangling joints
1143  JOINT& jt = touchJoint( aPos, aLayers, aNet );
1144 
1145  jt.Unlink( aWhere );
1146 }
1147 
1148 
1149 void NODE::Dump( bool aLong )
1150 {
1151 #if 0
1152  std::unordered_set<SEGMENT*> all_segs;
1154 
1155  for( i = m_items.begin(); i != m_items.end(); i++ )
1156  {
1157  if( (*i)->GetKind() == ITEM::SEGMENT_T )
1158  all_segs.insert( static_cast<SEGMENT*>( *i ) );
1159  }
1160 
1161  if( !isRoot() )
1162  {
1163  for( i = m_root->m_items.begin(); i != m_root->m_items.end(); i++ )
1164  {
1165  if( (*i)->GetKind() == ITEM::SEGMENT_T && !overrides( *i ) )
1166  all_segs.insert( static_cast<SEGMENT*>(*i) );
1167  }
1168  }
1169 
1170  JOINT_MAP::iterator j;
1171 
1172  if( aLong )
1173  for( j = m_joints.begin(); j != m_joints.end(); ++j )
1174  {
1175  wxLogTrace( "PNS", "joint : %s, links : %d\n",
1176  j->second.GetPos().Format().c_str(), j->second.LinkCount() );
1177  JOINT::LINKED_ITEMS::const_iterator k;
1178 
1179  for( k = j->second.GetLinkList().begin(); k != j->second.GetLinkList().end(); ++k )
1180  {
1181  const ITEM* m_item = *k;
1182 
1183  switch( m_item->GetKind() )
1184  {
1185  case ITEM::SEGMENT_T:
1186  {
1187  const SEGMENT* seg = static_cast<const SEGMENT*>( m_item );
1188  wxLogTrace( "PNS", " -> seg %s %s\n", seg->GetSeg().A.Format().c_str(),
1189  seg->GetSeg().B.Format().c_str() );
1190  break;
1191  }
1192 
1193  default:
1194  break;
1195  }
1196  }
1197  }
1198 
1199 
1200  int lines_count = 0;
1201 
1202  while( !all_segs.empty() )
1203  {
1204  SEGMENT* s = *all_segs.begin();
1205  LINE* l = AssembleLine( s );
1206 
1207  LINE::LinkedSegments* seg_refs = l->GetLinkedSegments();
1208 
1209  if( aLong )
1210  wxLogTrace( "PNS", "Line: %s, net %d ", l->GetLine().Format().c_str(), l->GetNet() );
1211 
1212  for( std::vector<SEGMENT*>::iterator j = seg_refs->begin(); j != seg_refs->end(); ++j )
1213  {
1214  wxLogTrace( "PNS", "%s ", (*j)->GetSeg().A.Format().c_str() );
1215 
1216  if( j + 1 == seg_refs->end() )
1217  wxLogTrace( "PNS", "%s\n", (*j)->GetSeg().B.Format().c_str() );
1218 
1219  all_segs.erase( *j );
1220  }
1221 
1222  lines_count++;
1223  }
1224 
1225  wxLogTrace( "PNS", "Local joints: %d, lines : %d \n", m_joints.size(), lines_count );
1226 #endif
1227 }
1228 
1229 
1231 {
1232  if( isRoot() )
1233  return;
1234 
1235  if( m_override.size() )
1236  aRemoved.reserve( m_override.size() );
1237 
1238  if( m_index->Size() )
1239  aAdded.reserve( m_index->Size() );
1240 
1241  for( ITEM* item : m_override )
1242  aRemoved.push_back( item );
1243 
1244  for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
1245  aAdded.push_back( *i );
1246 }
1247 
1249 {
1250  // copy the kids as the NODE destructor erases the item from the parent node.
1251  std::set<NODE*> kids = m_children;
1252 
1253  for( NODE* node : kids )
1254  {
1255  node->releaseChildren();
1256  delete node;
1257  }
1258 }
1259 
1260 
1262 {
1263  if( !isRoot() )
1264  return;
1265 
1266  for( ITEM* item : m_garbageItems )
1267  {
1268  if( !item->BelongsTo( this ) )
1269  delete item;
1270  }
1271 
1272  m_garbageItems.clear();
1273 }
1274 
1275 
1276 void NODE::Commit( NODE* aNode )
1277  {
1278  if( aNode->isRoot() )
1279  return;
1280 
1281  for( ITEM* item : aNode->m_override )
1282  Remove( item );
1283 
1284  for( auto i : *aNode->m_index )
1285  {
1286  i->SetRank( -1 );
1287  i->Unmark();
1288  Add( std::unique_ptr<ITEM>( i ) );
1289  }
1290 
1291  releaseChildren();
1292  releaseGarbage();
1293  }
1294 
1295 
1297 {
1298  releaseChildren();
1299 }
1300 
1301 
1302 void NODE::AllItemsInNet( int aNet, std::set<ITEM*>& aItems, int aKindMask)
1303 {
1304  INDEX::NET_ITEMS_LIST* l_cur = m_index->GetItemsForNet( aNet );
1305 
1306  if( l_cur )
1307  {
1308  for( ITEM*item : *l_cur )
1309  if( item->OfKind( aKindMask ) )
1310  aItems.insert( item );
1311  }
1312 
1313  if( !isRoot() )
1314  {
1315  INDEX::NET_ITEMS_LIST* l_root = m_root->m_index->GetItemsForNet( aNet );
1316 
1317  if( l_root )
1318  {
1319  for( INDEX::NET_ITEMS_LIST::iterator i = l_root->begin(); i != l_root->end(); ++i )
1320  {
1321  if( !Overrides( *i ) && (*i)->OfKind( aKindMask ) )
1322  aItems.insert( *i );
1323  }
1324  }
1325  }
1326 }
1327 
1328 
1329 void NODE::ClearRanks( int aMarkerMask )
1330 {
1331  for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
1332  {
1333  (*i)->SetRank( -1 );
1334  (*i)->Mark( (*i)->Marker() & (~aMarkerMask) );
1335  }
1336 }
1337 
1338 
1339 void NODE::RemoveByMarker( int aMarker )
1340 {
1341  std::list<ITEM*> garbage;
1342 
1343  for( ITEM* item : *m_index )
1344  {
1345  if( item->Marker() & aMarker )
1346  garbage.push_back( item );
1347  }
1348 
1349  for( ITEM* item : garbage )
1350  Remove( item );
1351 }
1352 
1354  int aNet )
1355 {
1356  JOINT* jtStart = FindJoint( A, lr.Start(), aNet );
1357 
1358  if( !jtStart )
1359  return nullptr;
1360 
1361  for( ITEM* item : jtStart->LinkList() )
1362  {
1363  if( item->OfKind( ITEM::SEGMENT_T ) )
1364  {
1365  SEGMENT* seg2 = (SEGMENT*)item;
1366 
1367  const VECTOR2I a2( seg2->Seg().A );
1368  const VECTOR2I b2( seg2->Seg().B );
1369 
1370  if( seg2->Layers().Start() == lr.Start()
1371  && ( ( A == a2 && B == b2 ) || ( A == b2 && B == a2 ) ) )
1372  {
1373  return seg2;
1374  }
1375  }
1376  }
1377 
1378  return nullptr;
1379 }
1380 
1382 {
1383  return findRedundantSegment( aSeg->Seg().A, aSeg->Seg().B, aSeg->Layers(), aSeg->Net() );
1384 }
1385 
1387  int aNet )
1388 {
1389  JOINT* jtStart = FindJoint( A, lr.Start(), aNet );
1390 
1391  if( !jtStart )
1392  return nullptr;
1393 
1394  for( ITEM* item : jtStart->LinkList() )
1395  {
1396  if( item->OfKind( ITEM::ARC_T ) )
1397  {
1398  ARC* seg2 = static_cast<ARC*>( item );
1399 
1400  const VECTOR2I a2( seg2->Anchor( 0 ) );
1401  const VECTOR2I b2( seg2->Anchor( 1 ) );
1402 
1403  if( seg2->Layers().Start() == lr.Start()
1404  && ( ( A == a2 && B == b2 ) || ( A == b2 && B == a2 ) ) )
1405  {
1406  return seg2;
1407  }
1408  }
1409  }
1410 
1411  return nullptr;
1412 }
1413 
1415 {
1416  return findRedundantArc( aArc->Anchor( 0 ), aArc->Anchor( 1 ), aArc->Layers(), aArc->Net() );
1417 }
1418 
1419 
1420 int NODE::QueryJoints( const BOX2I& aBox, std::vector<JOINT*>& aJoints, int aLayerMask,
1421  int aKindMask )
1422 {
1423  int n = 0;
1424 
1425  aJoints.clear();
1426 
1427  for( auto j = m_joints.begin(); j != m_joints.end(); ++j )
1428  {
1429  if( aBox.Contains( j->second.Pos() ) && j->second.LinkCount( aKindMask ) )
1430  {
1431  aJoints.push_back( &j->second );
1432  n++;
1433  }
1434  }
1435 
1436  if( isRoot() )
1437  return n;
1438 
1439  for( auto j = m_root->m_joints.begin(); j != m_root->m_joints.end(); ++j )
1440  {
1441  if( !Overrides( &j->second) )
1442  {
1443  if( aBox.Contains( j->second.Pos() ) && j->second.LinkCount( aKindMask ) )
1444  {
1445  aJoints.push_back( &j->second );
1446  n++;
1447  }
1448  }
1449  }
1450 
1451  return n;
1452 }
1453 
1454 
1456 {
1457  if( aParent->IsConnected() )
1458  {
1459  const BOARD_CONNECTED_ITEM* cItem = static_cast<const BOARD_CONNECTED_ITEM*>( aParent );
1460 
1462 
1463  if( l_cur )
1464  {
1465  for( ITEM* item : *l_cur )
1466  {
1467  if( item->Parent() == aParent )
1468  return item;
1469  }
1470  }
1471  }
1472 
1473  return NULL;
1474 }
1475 
1476 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:134
int Find(const VECTOR2I &aP) const
Function Find()
const SHAPE_LINE_CHAIN & CLine() const
Const accessor to the underlying shape
Definition: pns_line.h:149
CITER next(CITER it)
Definition: ptree.cpp:126
ITEM.
Definition: pns_item.h:54
int Query(const ITEM *aItem, int aMinDistance, Visitor &aVisitor) const
Searches items in the index that are in proximity of aItem.
Definition: pns_index.h:141
std::list< ITEM * > NET_ITEMS_LIST
Definition: pns_index.h:48
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:529
ITEM * m_item
Item found to be colliding with m_head
Definition: pns_node.h:110
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:148
void SetOwner(NODE *aOwner)
Functon SetOwner()
Definition: pns_item.h:181
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
int GetNetCode() const
Function GetNetCode.
virtual int Layer() const
Definition: pns_item.h:156
VECTOR2I m_ipLast
Definition: pns_node.h:117
NODE.
Definition: pns_node.h:169
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:248
BOARD_ITEM is a base class for any item which can be embedded within the BOARD container class,...
Definition: board_item.h:86
void releaseChildren()
Definition: pns_node.cpp:1248
int SegmentCount() const
Returns the number of segments in the line
Definition: pns_line.h:155
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
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:120
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
finds the joints corresponding to the ends of line aLine
Definition: pns_node.cpp:956
void doRemove(ITEM *aItem)
Definition: pns_node.cpp:676
void removeSegmentIndex(SEGMENT *aSeg)
Definition: pns_node.cpp:697
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:85
LAYER_RANGE m_layers
Definition: pns_item.h:259
int FindLinesBetweenJoints(const JOINT &aA, const JOINT &aB, std::vector< LINE > &aLines)
finds all lines between a pair of joints. Used by the loop removal procedure.
Definition: pns_node.cpp:1001
int QueryJoints(const BOX2I &aBox, std::vector< JOINT * > &aJoints, int aLayerMask=-1, int aKindMask=ITEM::ANY_T)
Definition: pns_node.cpp:1420
virtual int Clearance(const ITEM *aA, const ITEM *aB)=0
void Lock(bool aLock=true)
Definition: pns_joint.h:245
const SEG & Seg() const
Definition: pns_segment.h:84
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:458
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:1130
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:1276
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:106
const VECTOR2I & Pos() const
Definition: pns_via.h:95
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const
Function Collide()
Definition: shape.h:176
ITEM_SET & m_items
Definition: pns_node.cpp:484
bool EndsWithVia() const
Definition: pns_line.h:234
void unlinkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
unlinks an item from a joint
Definition: pns_node.cpp:1139
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:501
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:541
void Remove(ARC *aArc)
Function Remove()
Definition: pns_node.cpp:804
void SetWidth(int aWidth)
Sets line width
Definition: pns_line.h:185
int Start() const
Definition: pns_layerset.h:83
void SetNet(int aNet)
Definition: pns_item.h:149
bool LayersOverlap(const ITEM *aOther) const
Function LayersOverlap()
Definition: pns_item.h:164
const VECTOR2I & CPoint(int aIdx) const
Returns the aIdx-th point of the line
Definition: pns_line.h:173
virtual int Width() const
int End() const
Definition: pns_layerset.h:88
void addSegment(SEGMENT *aSeg)
Definition: pns_node.cpp:617
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:526
int m_depth
depth of the node (number of parent nodes in the inheritance chain)
Definition: pns_node.h:544
JOINT.
Definition: pns_joint.h:43
RULE_RESOLVER * m_ruleResolver
Design rules resolver
Definition: pns_node.h:538
Struct OBSTACLE_VISITOR.
Definition: pns_node.h:126
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:1296
bool BelongsTo(NODE *aNode) const
Function BelongsTo()
Definition: pns_item.h:188
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Function AssembleLine()
Definition: pns_node.cpp:901
#define NULL
void rebuildJoint(JOINT *aJoint, ITEM *aItem)
Definition: pns_node.cpp:711
OBSTACLES & m_tab
list of encountered obstacles
Definition: pns_node.cpp:181
ITEM * FindItemByParent(const BOARD_ITEM *aParent)
Definition: pns_node.cpp:1455
virtual const SHAPE * Shape() const
Function Shape()
Definition: pns_item.h:215
int Net() const
Definition: pns_item.h:150
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:1353
bool Contains(const Vec &aPoint) const
Function Contains.
Definition: box2.h:151
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:867
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:532
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
const ITEM * m_item
the item we are looking for collisions with
Definition: pns_node.h:145
void releaseGarbage()
Definition: pns_node.cpp:1261
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:120
int SegmentCount() const
Function SegmentCount()
ARC * findRedundantArc(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1386
const ITEM_SET HitTest(const VECTOR2I &aPoint) const
Function HitTest()
Definition: pns_node.cpp:510
void addArc(ARC *aVia)
Definition: pns_node.cpp:642
void SetLayers(const LAYER_RANGE &aLayers)
Definition: pns_item.h:153
SHAPE_LINE_CHAIN m_hull
Hull of the colliding m_item
Definition: pns_node.h:113
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:1035
SHAPE_LINE_CHAIN & Line()
Modifiable accessor to the underlying shape
Definition: pns_line.h:143
NET_ITEMS_LIST * GetItemsForNet(int aNet)
Returns list of all items in a given net.
Definition: pns_index.cpp:92
const VECTOR2I & Pos() const
Definition: pns_solid.h:96
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Function Replace()
Definition: pns_node.cpp:774
virtual VECTOR2I Anchor(int n) const
Definition: pns_item.h:232
void RemoveByMarker(int aMarker)
Definition: pns_node.cpp:1339
Definition: seg.h:39
void removeSolidIndex(SOLID *aSeg)
Definition: pns_node.cpp:762
int m_extraClearance
additional clearance
Definition: pns_node.cpp:193
ITEM_SET::iterator end()
Definition: pns_index.h:118
JOINT_MAP::value_type TagJointPair
Definition: pns_node.h:466
ITEM_SET::iterator begin()
Definition: pns_index.h:117
const SHAPE_LINE_CHAIN Hull(int aClearance=0, int aWalkaroundThickness=0, int aLayer=-1) const override
Definition: pns_via.cpp:74
void Dump(bool aLong=false)
Prints the contents and joints structure
Definition: pns_node.cpp:1149
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:1123
int Size() const
Returns number of items stored in the index.
Definition: pns_index.h:115
SHAPE_LINE_CHAIN.
void AllItemsInNet(int aNet, std::set< ITEM * > &aItems, int aKindMask=-1)
Definition: pns_node.cpp:1302
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:1072
VECTOR2I A
Definition: seg.h:47
bool OfKind(int aKindMask) const
Function OfKind()
Definition: pns_item.h:134
std::unordered_set< ITEM * > m_garbageItems
Definition: pns_node.h:546
void Add(ITEM *aItem)
Adds item to the spatial index.
Definition: pns_index.cpp:28
const ENTRIES & CItems() const
Definition: pns_itemset.h:141
void removeViaIndex(VIA *aVia)
Definition: pns_node.cpp:754
int Width() const
Returns line width
Definition: pns_line.h:192
const ITEM * m_head
Item we search collisions with
Definition: pns_node.h:107
void Merge(const JOINT &aJoint)
Definition: pns_joint.h:223
void GetUpdatedItems(ITEM_VECTOR &aRemoved, ITEM_VECTOR &aAdded)
Function GetUpdatedItems()
Definition: pns_node.cpp:1230
void removeArcIndex(ARC *aVia)
Definition: pns_node.cpp:704
PnsKind Kind() const
Function Kind()
Definition: pns_item.h:124
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:172
virtual bool IsConnected() const
Function IsConnected() Returns information if the object is derived from BOARD_CONNECTED_ITEM.
Definition: board_item.h:146
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:535
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:864
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
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:520
const VIA & Via() const
Definition: pns_line.h:239
VECTOR2I m_ipFirst
First and last intersection point between the head item and the hull of the colliding m_item
Definition: pns_node.h:117
std::vector< OBSTACLE > OBSTACLES
Definition: pns_node.h:174
const NODE * m_override
node that overrides root entries
Definition: pns_node.h:151
Push and Shove diff pair dimensions (gap) settings dialog.
virtual VECTOR2I Anchor(int n) const override
Definition: pns_arc.h:100
NODE * m_parent
node this node was branched from
Definition: pns_node.h:523
void Remove(ITEM *aItem)
Removes an item from the spatial index.
Definition: pns_index.cpp:67
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:625
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION|MK_ALT_SHAPE)
Definition: pns_node.cpp:1329
INDEX.
Definition: pns_index.h:45
LAYER_RANGE.
Definition: pns_layerset.h:32
const LAYER_RANGE & Layers() const
Definition: pns_item.h:152
void LockJoint(const VECTOR2I &aPos, const ITEM *aItem, bool aLock)
Definition: pns_node.cpp:1065
std::vector< ITEM * > ITEM_VECTOR
Definition: pns_node.h:173
static std::vector< std::string > split(const std::string &aStr, const std::string &aDelim)
Splits the input string into a vector of output strings.
Definition: kicad_string.h:268
Struct OBSTACLE.
Definition: pns_node.h:104
VECTOR2I B
Definition: seg.h:48