KiCad PCB EDA Suite
pns_optimizer.cpp
Go to the documentation of this file.
1 /*
2  * KiRouter - a push-and-(sometimes-)shove PCB router
3  *
4  * Copyright (C) 2013-2014 CERN
5  * Copyright (C) 2016 KiCad Developers, see AUTHORS.txt for contributors.
6  * Author: Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
7  *
8  * This program is free software: you can redistribute it and/or modify it
9  * under the terms of the GNU General Public License as published by the
10  * Free Software Foundation, either version 3 of the License, or (at your
11  * option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful, but
14  * WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16  * General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License along
19  * with this program. If not, see <http://www.gnu.org/licenses/>.
20  */
21 
23 #include <geometry/shape_rect.h>
24 #include <geometry/shape_simple.h>
25 #include <cmath>
26 
27 #include "pns_line.h"
28 #include "pns_diff_pair.h"
29 #include "pns_node.h"
30 #include "pns_solid.h"
31 #include "pns_optimizer.h"
32 
33 #include "pns_utils.h"
34 #include "pns_router.h"
35 
36 namespace PNS {
37 
41 int COST_ESTIMATOR::CornerCost( const SEG& aA, const SEG& aB )
42 {
43  DIRECTION_45 dir_a( aA ), dir_b( aB );
44 
45  switch( dir_a.Angle( dir_b ) )
46  {
48  return 10;
49 
51  return 5;
52 
54  return 50;
55 
57  return 30;
58 
60  return 60;
61 
62  default:
63  return 100;
64  }
65 }
66 
67 
69 {
70  int total = 0;
71 
72  for( int i = 0; i < aLine.SegmentCount() - 1; ++i )
73  total += CornerCost( aLine.CSegment( i ), aLine.CSegment( i + 1 ) );
74 
75  return total;
76 }
77 
78 
79 int COST_ESTIMATOR::CornerCost( const LINE& aLine )
80 {
81  return CornerCost( aLine.CLine() );
82 }
83 
84 
85 void COST_ESTIMATOR::Add( LINE& aLine )
86 {
87  m_lengthCost += aLine.CLine().Length();
88  m_cornerCost += CornerCost( aLine );
89 }
90 
91 
93 {
94  m_lengthCost -= aLine.CLine().Length();
95  m_cornerCost -= CornerCost( aLine );
96 }
97 
98 
99 void COST_ESTIMATOR::Replace( LINE& aOldLine, LINE& aNewLine )
100 {
101  m_lengthCost -= aOldLine.CLine().Length();
102  m_cornerCost -= CornerCost( aOldLine );
103  m_lengthCost += aNewLine.CLine().Length();
104  m_cornerCost += CornerCost( aNewLine );
105 }
106 
107 
109  double aLengthTolerance,
110  double aCornerTolerance ) const
111 {
112  if( aOther.m_cornerCost < m_cornerCost && aOther.m_lengthCost < m_lengthCost )
113  return true;
114 
115  else if( aOther.m_cornerCost < m_cornerCost * aCornerTolerance &&
116  aOther.m_lengthCost < m_lengthCost * aLengthTolerance )
117  return true;
118 
119  return false;
120 }
121 
122 
127  m_world( aWorld ),
128  m_collisionKindMask( ITEM::ANY_T ),
129  m_effortLevel( MERGE_SEGMENTS ),
130  m_keepPostures( false ),
131  m_restrictAreaActive( false )
132 {
133 }
134 
135 
137 {
138 }
139 
140 
142 {
143  CACHE_VISITOR( const ITEM* aOurItem, NODE* aNode, int aMask ) :
144  m_ourItem( aOurItem ),
146  m_node( aNode ),
147  m_mask( aMask )
148  {}
149 
150  bool operator()( ITEM* aOtherItem )
151  {
152  if( !( m_mask & aOtherItem->Kind() ) )
153  return true;
154 
155  int clearance = m_node->GetClearance( aOtherItem, m_ourItem );
156 
157  if( !aOtherItem->Collide( m_ourItem, clearance, false, nullptr, m_node ) )
158  return true;
159 
160  m_collidingItem = aOtherItem;
161  return false;
162  }
163 
164  const ITEM* m_ourItem;
167  int m_mask;
168 };
169 
170 
171 void OPTIMIZER::cacheAdd( ITEM* aItem, bool aIsStatic = false )
172 {
173  if( m_cacheTags.find( aItem ) != m_cacheTags.end() )
174  return;
175 
176  m_cache.Add( aItem );
177  m_cacheTags[aItem].m_hits = 1;
178  m_cacheTags[aItem].m_isStatic = aIsStatic;
179 }
180 
181 
182 void OPTIMIZER::removeCachedSegments( LINE* aLine, int aStartVertex, int aEndVertex )
183 {
184  if( !aLine->IsLinked() ) return;
185 
186  LINE::SEGMENT_REFS& segs = aLine->LinkedSegments();
187 
188  if( aEndVertex < 0 )
189  aEndVertex += aLine->PointCount();
190 
191  for( int i = aStartVertex; i < aEndVertex - 1; i++ )
192  {
193  SEGMENT* s = segs[i];
194  m_cacheTags.erase( s );
195  m_cache.Remove( s );
196  }
197 }
198 
199 
201 {
202  if( aItem->Kind() == ITEM::LINE_T )
203  removeCachedSegments( static_cast<LINE*>( aItem ) );
204 }
205 
206 
208 {
209  cacheAdd( aItem, true );
210 }
211 
212 
213 void OPTIMIZER::ClearCache( bool aStaticOnly )
214 {
215  if( !aStaticOnly )
216  {
217  m_cacheTags.clear();
218  m_cache.Clear();
219  return;
220  }
221 
222  for( CachedItemTags::iterator i = m_cacheTags.begin(); i!= m_cacheTags.end(); ++i )
223  {
224  if( i->second.m_isStatic )
225  {
226  m_cache.Remove( i->first );
227  m_cacheTags.erase( i->first );
228  }
229  }
230 }
231 
232 
234 {
235  public:
238 
239  void Build( NODE* aWorld, LINE* aOriginLine, const SHAPE_LINE_CHAIN& aLine, const BOX2I& aRestrictedArea, bool aRestrictedAreaEnable );
240  bool Check ( int aVertex1, int aVertex2, const SHAPE_LINE_CHAIN& aReplacement );
241  void Dump();
242 
243  private:
244  int allowedAngles( NODE* aWorld, const LINE* aLine, const VECTOR2I& aP, bool aFirst );
245 
246  struct RVERTEX
247  {
248  RVERTEX ( bool aRestricted, int aAllowedAngles ) :
249  restricted( aRestricted ),
250  allowedAngles( aAllowedAngles )
251  {
252  }
253 
256  };
257 
258  std::vector<RVERTEX> m_rs;
259 };
260 
261 
262 // fixme: use later
263 int LINE_RESTRICTIONS::allowedAngles( NODE* aWorld, const LINE* aLine, const VECTOR2I& aP, bool aFirst )
264 {
265  JOINT* jt = aWorld->FindJoint( aP , aLine );
266 
267  if( !jt )
268  return 0xff;
269 
270  DIRECTION_45 dirs [8];
271 
272  int n_dirs = 0;
273 
274  for( const ITEM* item : jt->Links().CItems() )
275  {
276  if( item->OfKind( ITEM::VIA_T ) || item->OfKind( ITEM::SOLID_T ) )
277  return 0xff;
278  else if( const SEGMENT* seg = dyn_cast<const SEGMENT*>( item ) )
279  {
280  SEG s = seg->Seg();
281  if( s.A != aP )
282  s.Reverse();
283 
284  if( n_dirs < 8 )
285  dirs[n_dirs++] = aFirst ? DIRECTION_45( s ) : DIRECTION_45( s ).Opposite();
286  }
287  }
288 
290  int outputMask = 0xff;
291 
292  for( int d = 0; d < 8; d++ )
293  {
294  DIRECTION_45 refDir( ( DIRECTION_45::Directions ) d );
295 
296  for( int i = 0; i < n_dirs; i++ )
297  {
298  if( !( refDir.Angle( dirs[i] ) & angleMask ) )
299  outputMask &= ~refDir.Mask();
300  }
301  }
302 
303  //DrawDebugDirs( aP, outputMask, 3 );
304  return 0xff;
305 }
306 
307 
308 void LINE_RESTRICTIONS::Build( NODE* aWorld, LINE* aOriginLine, const SHAPE_LINE_CHAIN& aLine, const BOX2I& aRestrictedArea, bool aRestrictedAreaEnable )
309 {
310  const SHAPE_LINE_CHAIN& l = aLine;
311  VECTOR2I v_prev;
312  int n = l.PointCount( );
313 
314  m_rs.reserve( n );
315 
316  for( int i = 0; i < n; i++ )
317  {
318  const VECTOR2I &v = l.CPoint( i );
319  RVERTEX r( false, 0xff );
320 
321  if( aRestrictedAreaEnable )
322  {
323  bool exiting = ( i > 0 && aRestrictedArea.Contains( v_prev ) && !aRestrictedArea.Contains( v ) );
324  bool entering = false;
325 
326  if( i != l.PointCount() - 1 )
327  {
328  const VECTOR2I& v_next = l.CPoint( i + 1 );
329  entering = ( !aRestrictedArea.Contains( v ) && aRestrictedArea.Contains( v_next ) );
330  }
331 
332  if( entering )
333  {
334  const SEG& sp = l.CSegment( i );
335  r.allowedAngles = DIRECTION_45( sp ).Mask();
336  }
337  else if( exiting )
338  {
339  const SEG& sp = l.CSegment( i - 1 );
340  r.allowedAngles = DIRECTION_45( sp ).Mask();
341  }
342  else
343  {
344  r.allowedAngles = ( !aRestrictedArea.Contains( v ) ) ? 0 : 0xff;
345  r.restricted = r.allowedAngles ? false : true;
346  }
347  }
348 
349  v_prev = v;
350  m_rs.push_back( r );
351  }
352 }
353 
354 
356 {
357 }
358 
359 
360 bool LINE_RESTRICTIONS::Check( int aVertex1, int aVertex2, const SHAPE_LINE_CHAIN& aReplacement )
361 {
362  if( m_rs.empty( ) )
363  return true;
364 
365  for( int i = aVertex1; i <= aVertex2; i++ )
366  if ( m_rs[i].restricted )
367  return false;
368 
369  const RVERTEX& v1 = m_rs[ aVertex1 ];
370  const RVERTEX& v2 = m_rs[ aVertex2 ];
371 
372  int m1 = DIRECTION_45( aReplacement.CSegment( 0 ) ).Mask();
373  int m2;
374 
375  if( aReplacement.SegmentCount() == 1 )
376  m2 = m1;
377  else
378  m2 = DIRECTION_45( aReplacement.CSegment( 1 ) ).Mask();
379 
380  return ( ( v1.allowedAngles & m1 ) != 0 ) &&
381  ( ( v2.allowedAngles & m2 ) != 0 );
382 }
383 
384 
385 bool OPTIMIZER::checkColliding( ITEM* aItem, bool aUpdateCache )
386 {
388 
389  return static_cast<bool>( m_world->CheckColliding( aItem ) );
390 
391 #if 0
392  // something is wrong with the cache, need to investigate.
393  m_cache.Query( aItem->Shape(), m_world->GetMaxClearance(), v, false );
394 
395  if( !v.m_collidingItem )
396  {
397  NODE::OPT_OBSTACLE obs = m_world->CheckColliding( aItem );
398 
399  if( obs )
400  {
401  if( aUpdateCache )
402  cacheAdd( obs->m_item );
403 
404  return true;
405  }
406  }
407  else
408  {
409  m_cacheTags[v.m_collidingItem].m_hits++;
410  return true;
411  }
412 
413  return false;
414 #endif
415 }
416 
417 
418 bool OPTIMIZER::checkColliding( LINE* aLine, const SHAPE_LINE_CHAIN& aOptPath )
419 {
420  LINE tmp( *aLine, aOptPath );
421 
422  return checkColliding( &tmp );
423 }
424 
425 
427 {
428  SHAPE_LINE_CHAIN& line = aLine->Line();
429 
430  int step = line.PointCount() - 3;
431  int iter = 0;
432  int segs_pre = line.SegmentCount();
433 
434  if( step < 0 )
435  return false;
436 
437  SHAPE_LINE_CHAIN current_path( line );
438 
439  while( 1 )
440  {
441  iter++;
442  int n_segs = current_path.SegmentCount();
443  int max_step = n_segs - 2;
444 
445  if( step > max_step )
446  step = max_step;
447 
448  if( step < 2 )
449  {
450  line = current_path;
451  return current_path.SegmentCount() < segs_pre;
452  }
453 
454  bool found_anything = false;
455  int n = 0;
456 
457  while( n < n_segs - step )
458  {
459  const SEG s1 = current_path.CSegment( n );
460  const SEG s2 = current_path.CSegment( n + step );
461  SEG s1opt, s2opt;
462 
463  if( DIRECTION_45( s1 ).IsObtuse( DIRECTION_45( s2 ) ) )
464  {
465  VECTOR2I ip = *s1.IntersectLines( s2 );
466 
467  if( s1.Distance( ip ) <= 1 || s2.Distance( ip ) <= 1 )
468  {
469  s1opt = SEG( s1.A, ip );
470  s2opt = SEG( ip, s2.B );
471  }
472  else
473  {
474  s1opt = SEG( s1.A, ip );
475  s2opt = SEG( ip, s2.B );
476  }
477 
478  if( DIRECTION_45( s1opt ).IsObtuse( DIRECTION_45( s2opt ) ) )
479  {
480  SHAPE_LINE_CHAIN opt_path;
481  opt_path.Append( s1opt.A );
482  opt_path.Append( s1opt.B );
483  opt_path.Append( s2opt.B );
484 
485  LINE opt_track( *aLine, opt_path );
486 
487  if( !checkColliding( &opt_track ) )
488  {
489  current_path.Replace( s1.Index() + 1, s2.Index(), ip );
490  // removeCachedSegments(aLine, s1.Index(), s2.Index());
491  n_segs = current_path.SegmentCount();
492  found_anything = true;
493  break;
494  }
495  }
496  }
497 
498  n++;
499  }
500 
501  if( !found_anything )
502  {
503  if( step <= 2 )
504  {
505  line = current_path;
506  return line.SegmentCount() < segs_pre;
507  }
508 
509  step--;
510  }
511  }
512 
513  return line.SegmentCount() < segs_pre;
514 }
515 
516 
518 {
519  SHAPE_LINE_CHAIN& line = aLine->Line();
520  int step = line.SegmentCount() - 1;
521 
522  int segs_pre = line.SegmentCount();
523 
524  line.Simplify();
525 
526  if( step < 0 )
527  return false;
528 
529  SHAPE_LINE_CHAIN current_path( line );
530 
531  while( 1 )
532  {
533  int n_segs = current_path.SegmentCount();
534  int max_step = n_segs - 2;
535 
536  if( step > max_step )
537  step = max_step;
538 
539  if( step < 1 )
540  break;
541 
542  bool found_anything = mergeStep( aLine, current_path, step );
543 
544  if( !found_anything )
545  step--;
546  }
547 
548  aLine->SetShape( current_path );
549 
550  return current_path.SegmentCount() < segs_pre;
551 }
552 
553 
554 bool OPTIMIZER::Optimize( LINE* aLine, LINE* aResult )
555 {
556  if( !aResult )
557  aResult = aLine;
558  else
559  *aResult = *aLine;
560 
561  m_keepPostures = false;
562 
563  bool rv = false;
564 
566  rv |= mergeFull( aResult );
567 
569  rv |= mergeObtuse( aResult );
570 
571  if( m_effortLevel & SMART_PADS )
572  rv |= runSmartPads( aResult );
573 
575  rv |= fanoutCleanup( aResult );
576 
577  return rv;
578 }
579 
580 
581 bool OPTIMIZER::mergeStep( LINE* aLine, SHAPE_LINE_CHAIN& aCurrentPath, int step )
582 {
583  int n = 0;
584  int n_segs = aCurrentPath.SegmentCount();
585 
586  int cost_orig = COST_ESTIMATOR::CornerCost( aCurrentPath );
587 
588  LINE_RESTRICTIONS restr;
589 
590  if( aLine->SegmentCount() < 4 )
591  return false;
592 
593  DIRECTION_45 orig_start( aLine->CSegment( 0 ) );
594  DIRECTION_45 orig_end( aLine->CSegment( -1 ) );
595 
596  restr.Build( m_world, aLine, aCurrentPath, m_restrictArea, m_restrictAreaActive );
597 
598  while( n < n_segs - step )
599  {
600  const SEG s1 = aCurrentPath.CSegment( n );
601  const SEG s2 = aCurrentPath.CSegment( n + step );
602 
603  SHAPE_LINE_CHAIN path[2];
604  SHAPE_LINE_CHAIN* picked = NULL;
605  int cost[2];
606 
607  for( int i = 0; i < 2; i++ )
608  {
609  bool postureMatch = true;
610  SHAPE_LINE_CHAIN bypass = DIRECTION_45().BuildInitialTrace( s1.A, s2.B, i );
611  cost[i] = INT_MAX;
612 
613  bool restrictionsOK = restr.Check ( n, n + step + 1, bypass );
614 
615  if( n == 0 && orig_start != DIRECTION_45( bypass.CSegment( 0 ) ) )
616  postureMatch = false;
617  else if( n == n_segs - step && orig_end != DIRECTION_45( bypass.CSegment( -1 ) ) )
618  postureMatch = false;
619 
620  if( restrictionsOK && (postureMatch || !m_keepPostures) && !checkColliding( aLine, bypass ) )
621  {
622  path[i] = aCurrentPath;
623  path[i].Replace( s1.Index(), s2.Index(), bypass );
624  path[i].Simplify();
625  cost[i] = COST_ESTIMATOR::CornerCost( path[i] );
626  }
627  }
628 
629  if( cost[0] < cost_orig && cost[0] < cost[1] )
630  picked = &path[0];
631  else if( cost[1] < cost_orig )
632  picked = &path[1];
633 
634  if( picked )
635  {
636  n_segs = aCurrentPath.SegmentCount();
637  aCurrentPath = *picked;
638  return true;
639  }
640 
641  n++;
642  }
643 
644  return false;
645 }
646 
647 
649  const SHAPE* aShape, bool aPermitDiagonal ) const
650 {
651  BREAKOUT_LIST breakouts;
652 
653  for( int angle = 0; angle < 360; angle += 45 )
654  {
655  const SHAPE_CIRCLE* cir = static_cast<const SHAPE_CIRCLE*>( aShape );
657  VECTOR2I p0 = cir->GetCenter();
658  VECTOR2I v0( cir->GetRadius() * M_SQRT2, 0 );
659  l.Append( p0 );
660  l.Append( p0 + v0.Rotate( angle * M_PI / 180.0 ) );
661  breakouts.push_back( l );
662  }
663 
664  return breakouts;
665 }
666 
667 
669  const ITEM* aItem, bool aPermitDiagonal ) const
670 {
671  BREAKOUT_LIST breakouts;
672  const SHAPE_SIMPLE* convex = static_cast<const SHAPE_SIMPLE*>( aItem->Shape() );
673 
674  BOX2I bbox = convex->BBox( 0 );
675  VECTOR2I p0 = static_cast<const SOLID*>( aItem )->Pos();
676  // must be large enough to guarantee intersecting the convex polygon
677  int length = std::max( bbox.GetWidth(), bbox.GetHeight() ) / 2 + 5;
678 
679  for( int angle = 0; angle < 360; angle += ( aPermitDiagonal ? 45 : 90 ) )
680  {
682  VECTOR2I v0( p0 + VECTOR2I( length, 0 ).Rotate( angle * M_PI / 180.0 ) );
683  SHAPE_LINE_CHAIN::INTERSECTIONS intersections;
684  int n = convex->Vertices().Intersect( SEG( p0, v0 ), intersections );
685  // if n == 1 intersected a segment
686  // if n == 2 intersected the common point of 2 segments
687  // n == 0 can not happen I think, but...
688  if( n > 0 )
689  {
690  l.Append( p0 );
691 
692  // for a breakout distance relative to the distance between
693  // center and polygon edge
694  //l.Append( intersections[0].p + (v0 - p0).Resize( (intersections[0].p - p0).EuclideanNorm() * 0.4 ) );
695 
696  // for an absolute breakout distance, e.g. 0.1 mm
697  //l.Append( intersections[0].p + (v0 - p0).Resize( 100000 ) );
698 
699  // for the breakout right on the polygon edge
700  l.Append( intersections[0].p );
701 
702  breakouts.push_back( l );
703  }
704  }
705 
706  return breakouts;
707 }
708 
709 
711  const SHAPE* aShape, bool aPermitDiagonal ) const
712 {
713  const SHAPE_RECT* rect = static_cast<const SHAPE_RECT*>(aShape);
714  VECTOR2I s = rect->GetSize();
715  VECTOR2I c = rect->GetPosition() + VECTOR2I( s.x / 2, s.y / 2 );
716  BREAKOUT_LIST breakouts;
717 
718  VECTOR2I d_offset;
719 
720  d_offset.x = ( s.x > s.y ) ? ( s.x - s.y ) / 2 : 0;
721  d_offset.y = ( s.x < s.y ) ? ( s.y - s.x ) / 2 : 0;
722 
723  VECTOR2I d_vert = VECTOR2I( 0, s.y / 2 + aWidth );
724  VECTOR2I d_horiz = VECTOR2I( s.x / 2 + aWidth, 0 );
725 
726  breakouts.push_back( SHAPE_LINE_CHAIN( { c, c + d_horiz } ) );
727  breakouts.push_back( SHAPE_LINE_CHAIN( { c, c - d_horiz } ) );
728  breakouts.push_back( SHAPE_LINE_CHAIN( { c, c + d_vert } ) );
729  breakouts.push_back( SHAPE_LINE_CHAIN( { c, c - d_vert } ) );
730 
731  if( aPermitDiagonal )
732  {
733  int l = aWidth + std::min( s.x, s.y ) / 2;
734  VECTOR2I d_diag;
735 
736  if( s.x >= s.y )
737  {
738  breakouts.push_back(
739  SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( l, l ) } ) );
740  breakouts.push_back(
741  SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset - VECTOR2I( -l, l ) } ) );
742  breakouts.push_back(
743  SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset + VECTOR2I( -l, l ) } ) );
744  breakouts.push_back(
745  SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( l, l ) } ) );
746  }
747  else
748  {
749  // fixme: this could be done more efficiently
750  breakouts.push_back(
751  SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( l, l ) } ) );
752  breakouts.push_back(
753  SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( -l, l ) } ) );
754  breakouts.push_back(
755  SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( -l, l ) } ) );
756  breakouts.push_back(
757  SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( l, l ) } ) );
758  }
759  }
760 
761  return breakouts;
762 }
763 
764 
766  const ITEM* aItem, bool aPermitDiagonal ) const
767 {
768  switch( aItem->Kind() )
769  {
770  case ITEM::VIA_T:
771  {
772  const VIA* via = static_cast<const VIA*>( aItem );
773  return circleBreakouts( aWidth, via->Shape(), aPermitDiagonal );
774  }
775 
776  case ITEM::SOLID_T:
777  {
778  const SHAPE* shape = aItem->Shape();
779 
780  switch( shape->Type() )
781  {
782  case SH_RECT:
783  return rectBreakouts( aWidth, shape, aPermitDiagonal );
784 
785  case SH_SEGMENT:
786  {
787  const SHAPE_SEGMENT* seg = static_cast<const SHAPE_SEGMENT*> (shape);
788  const SHAPE_RECT rect = ApproximateSegmentAsRect ( *seg );
789  return rectBreakouts( aWidth, &rect, aPermitDiagonal );
790  }
791 
792  case SH_CIRCLE:
793  return circleBreakouts( aWidth, shape, aPermitDiagonal );
794 
795  case SH_SIMPLE:
796  return customBreakouts( aWidth, aItem, aPermitDiagonal );
797 
798  default:
799  break;
800  }
801 
802  break;
803  }
804 
805  default:
806  break;
807  }
808 
809  return BREAKOUT_LIST();
810 }
811 
812 
813 ITEM* OPTIMIZER::findPadOrVia( int aLayer, int aNet, const VECTOR2I& aP ) const
814 {
815  JOINT* jt = m_world->FindJoint( aP, aLayer, aNet );
816 
817  if( !jt )
818  return NULL;
819 
820  for( ITEM* item : jt->LinkList() )
821  {
822  if( item->OfKind( ITEM::VIA_T | ITEM::SOLID_T ) )
823  return item;
824  }
825 
826  return NULL;
827 }
828 
829 
830 int OPTIMIZER::smartPadsSingle( LINE* aLine, ITEM* aPad, bool aEnd, int aEndVertex )
831 {
832  DIRECTION_45 dir;
833 
834  const int ForbiddenAngles = DIRECTION_45::ANG_ACUTE | DIRECTION_45::ANG_RIGHT |
836 
837  typedef std::tuple<int, long long int, SHAPE_LINE_CHAIN> RtVariant;
838  std::vector<RtVariant> variants;
839 
840  SOLID* solid = dyn_cast<SOLID*>( aPad );
841 
842  // don't do optimized connections for offset pads
843  if( solid && solid->Offset() != VECTOR2I( 0, 0 ) )
844  return -1;
845 
846 
847  BREAKOUT_LIST breakouts = computeBreakouts( aLine->Width(), aPad, true );
848  SHAPE_LINE_CHAIN line = ( aEnd ? aLine->CLine().Reverse() : aLine->CLine() );
849  int p_end = std::min( aEndVertex, std::min( 3, line.PointCount() - 1 ) );
850 
851  // Start at 1 to find a potentially better breakout (0 is the pad connection)
852  for( int p = 1; p <= p_end; p++ )
853  {
854  // If the line is contained inside the pad, don't optimize
855  if( solid && solid->Shape() && !solid->Shape()->Collide(
856  SEG( line.CPoint( 0 ), line.CPoint( p ) ), aLine->Width() / 2 ) )
857  continue;
858 
859  for( SHAPE_LINE_CHAIN & breakout : breakouts ) {
860 
861  for( int diag = 0; diag < 2; diag++ )
862  {
864  SHAPE_LINE_CHAIN connect = dir.BuildInitialTrace(
865  breakout.CPoint( -1 ), line.CPoint( p ), diag == 0 );
866 
867  DIRECTION_45 dir_bkout( breakout.CSegment( -1 ) );
868 
869  if(!connect.SegmentCount())
870  continue;
871 
872  int ang1 = dir_bkout.Angle( DIRECTION_45( connect.CSegment( 0 ) ) );
873 
874  if( ang1 & ForbiddenAngles )
875  continue;
876 
877  if( breakout.Length() > line.Length() )
878  continue;
879 
880  v = breakout;
881  v.Append( connect );
882 
883  for( int i = p + 1; i < line.PointCount(); i++ )
884  v.Append( line.CPoint( i ) );
885 
886  LINE tmp( *aLine, v );
887  int cc = tmp.CountCorners( ForbiddenAngles );
888 
889  if( cc == 0 )
890  {
891  RtVariant vp;
892  std::get<0>( vp ) = p;
893  std::get<1>( vp ) = breakout.Length();
894  std::get<2>( vp ) = aEnd ? v.Reverse() : v;
895  std::get<2>( vp ).Simplify();
896  variants.push_back( vp );
897  }
898  }
899  }
900  }
901 
902  // We attempt to minimize the corner cost (minimizes the segments and types of corners)
903  // but given two, equally valid costs, we want to pick the longer pad exit. The logic
904  // here is that if the pad is oblong, the track should not exit the shorter side and parallel
905  // the pad but should follow the pad's preferential direction before exiting.
906  // The baseline guess is to start with the existing line the user has drawn.
907  int min_cost = COST_ESTIMATOR::CornerCost( *aLine );
908  long long int max_length = 0;
909  bool found = false;
910  int p_best = -1;
911  SHAPE_LINE_CHAIN l_best;
912 
913  for( RtVariant& vp : variants )
914  {
915  LINE tmp( *aLine, std::get<2>( vp ) );
916  int cost = COST_ESTIMATOR::CornerCost( std::get<2>( vp ) );
917  long long int len = std::get<1>( vp );
918 
919  if( !checkColliding( &tmp ) )
920  {
921  if( cost < min_cost || ( cost == min_cost && len > max_length ) )
922  {
923  l_best = std::get<2>( vp );
924  p_best = std::get<0>( vp );
925  found = true;
926 
927  if( cost <= min_cost )
928  max_length = std::max<int>( len, max_length );
929 
930  min_cost = std::min( cost, min_cost );
931  }
932  }
933  }
934 
935  if( found )
936  {
937  aLine->SetShape( l_best );
938  return p_best;
939  }
940 
941  return -1;
942 }
943 
945 {
946  SHAPE_LINE_CHAIN& line = aLine->Line();
947 
948  if( line.PointCount() < 3 )
949  return false;
950 
951  VECTOR2I p_start = line.CPoint( 0 ), p_end = line.CPoint( -1 );
952 
953  ITEM* startPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_start );
954  ITEM* endPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_end );
955 
956  int vtx = -1;
957 
958  if( startPad )
959  vtx = smartPadsSingle( aLine, startPad, false, 3 );
960 
961  if( endPad )
962  smartPadsSingle( aLine, endPad, true,
963  vtx < 0 ? line.PointCount() - 1 : line.PointCount() - 1 - vtx );
964 
965  aLine->Line().Simplify();
966 
967  return true;
968 }
969 
970 
971 bool OPTIMIZER::Optimize( LINE* aLine, int aEffortLevel, NODE* aWorld )
972 {
973  OPTIMIZER opt( aWorld );
974 
975  opt.SetEffortLevel( aEffortLevel );
976  opt.SetCollisionMask( -1 );
977  return opt.Optimize( aLine );
978 }
979 
980 
982 {
983  if( aLine->PointCount() < 3 )
984  return false;
985 
986  VECTOR2I p_start = aLine->CPoint( 0 ), p_end = aLine->CPoint( -1 );
987 
988  ITEM* startPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_start );
989  ITEM* endPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_end );
990 
991  int thr = aLine->Width() * 10;
992  int len = aLine->CLine().Length();
993 
994  if( !startPad )
995  return false;
996 
997  bool startMatch = startPad->OfKind( ITEM::VIA_T | ITEM::SOLID_T );
998  bool endMatch = false;
999 
1000  if(endPad)
1001  {
1002  endMatch = endPad->OfKind( ITEM::VIA_T | ITEM::SOLID_T );
1003  }
1004  else
1005  {
1006  endMatch = aLine->EndsWithVia();
1007  }
1008 
1009  if( startMatch && endMatch && len < thr )
1010  {
1011  for( int i = 0; i < 2; i++ )
1012  {
1013  SHAPE_LINE_CHAIN l2 = DIRECTION_45().BuildInitialTrace( p_start, p_end, i );
1014  LINE repl;
1015  repl = LINE( *aLine, l2 );
1016 
1017  if( !m_world->CheckColliding( &repl ) )
1018  {
1019  aLine->SetShape( repl.CLine() );
1020  return true;
1021  }
1022  }
1023  }
1024 
1025  return false;
1026 }
1027 
1028 
1029 int findCoupledVertices( const VECTOR2I& aVertex, const SEG& aOrigSeg, const SHAPE_LINE_CHAIN& aCoupled, DIFF_PAIR* aPair, int* aIndices )
1030 {
1031  int count = 0;
1032  for ( int i = 0; i < aCoupled.SegmentCount(); i++ )
1033  {
1034  SEG s = aCoupled.CSegment( i );
1035  VECTOR2I projOverCoupled = s.LineProject ( aVertex );
1036 
1037  if( s.ApproxParallel ( aOrigSeg ) )
1038  {
1039  int64_t dist = ( projOverCoupled - aVertex ).EuclideanNorm() - aPair->Width();
1040 
1041  if( aPair->GapConstraint().Matches( dist ) )
1042  {
1043  *aIndices++ = i;
1044  count++;
1045  }
1046  }
1047  }
1048 
1049  return count;
1050 }
1051 
1052 
1053 bool verifyDpBypass( NODE* aNode, DIFF_PAIR* aPair, bool aRefIsP, const SHAPE_LINE_CHAIN& aNewRef, const SHAPE_LINE_CHAIN& aNewCoupled )
1054 {
1055  LINE refLine ( aRefIsP ? aPair->PLine() : aPair->NLine(), aNewRef );
1056  LINE coupledLine ( aRefIsP ? aPair->NLine() : aPair->PLine(), aNewCoupled );
1057 
1058  if( aNode->CheckColliding( &refLine, &coupledLine, ITEM::ANY_T, aPair->Gap() - 10 ) )
1059  return false;
1060 
1061  if( aNode->CheckColliding ( &refLine ) )
1062  return false;
1063 
1064  if( aNode->CheckColliding ( &coupledLine ) )
1065  return false;
1066 
1067  return true;
1068 }
1069 
1070 
1071 bool coupledBypass( NODE* aNode, DIFF_PAIR* aPair, bool aRefIsP, const SHAPE_LINE_CHAIN& aRef, const SHAPE_LINE_CHAIN& aRefBypass, const SHAPE_LINE_CHAIN& aCoupled, SHAPE_LINE_CHAIN& aNewCoupled )
1072 {
1073  int vStartIdx[1024]; // fixme: possible overflow
1074 
1075  int nStarts = findCoupledVertices( aRefBypass.CPoint( 0 ), aRefBypass.CSegment( 0 ), aCoupled, aPair, vStartIdx );
1076  DIRECTION_45 dir( aRefBypass.CSegment( 0 ) );
1077 
1078  int64_t bestLength = -1;
1079  bool found = false;
1080  SHAPE_LINE_CHAIN bestBypass;
1081  int si, ei;
1082 
1083  for( int i=0; i< nStarts; i++ )
1084  {
1085  for( int j = 1; j < aCoupled.PointCount() - 1; j++ )
1086  {
1087  int delta = std::abs ( vStartIdx[i] - j );
1088 
1089  if( delta > 1 )
1090  {
1091  const VECTOR2I& vs = aCoupled.CPoint( vStartIdx[i] );
1092  SHAPE_LINE_CHAIN bypass = dir.BuildInitialTrace( vs, aCoupled.CPoint(j), dir.IsDiagonal() );
1093 
1094  int64_t coupledLength = aPair->CoupledLength( aRef, bypass );
1095 
1096  SHAPE_LINE_CHAIN newCoupled = aCoupled;
1097 
1098  si = vStartIdx[i];
1099  ei = j;
1100 
1101  if(si < ei)
1102  newCoupled.Replace( si, ei, bypass );
1103  else
1104  newCoupled.Replace( ei, si, bypass.Reverse() );
1105 
1106  if(coupledLength > bestLength && verifyDpBypass( aNode, aPair, aRefIsP, aRef, newCoupled) )
1107  {
1108  bestBypass = newCoupled;
1109  bestLength = coupledLength;
1110  found = true;
1111  }
1112  }
1113  }
1114  }
1115 
1116 
1117  if( found )
1118  aNewCoupled = bestBypass;
1119 
1120  return found;
1121 }
1122 
1123 
1124 bool checkDpColliding( NODE* aNode, DIFF_PAIR* aPair, bool aIsP, const SHAPE_LINE_CHAIN& aPath )
1125 {
1126  LINE tmp ( aIsP ? aPair->PLine() : aPair->NLine(), aPath );
1127 
1128  return static_cast<bool>( aNode->CheckColliding( &tmp ) );
1129 }
1130 
1131 
1132 bool OPTIMIZER::mergeDpStep( DIFF_PAIR* aPair, bool aTryP, int step )
1133 {
1134  int n = 1;
1135 
1136  SHAPE_LINE_CHAIN currentPath = aTryP ? aPair->CP() : aPair->CN();
1137  SHAPE_LINE_CHAIN coupledPath = aTryP ? aPair->CN() : aPair->CP();
1138 
1139  int n_segs = currentPath.SegmentCount() - 1;
1140 
1141  int64_t clenPre = aPair->CoupledLength( currentPath, coupledPath );
1142  int64_t budget = clenPre / 10; // fixme: come up with somethig more intelligent here...
1143 
1144  while( n < n_segs - step )
1145  {
1146  const SEG s1 = currentPath.CSegment( n );
1147  const SEG s2 = currentPath.CSegment( n + step );
1148 
1149  DIRECTION_45 dir1( s1 );
1150  DIRECTION_45 dir2( s2 );
1151 
1152  if( dir1.IsObtuse( dir2 ) )
1153  {
1154  SHAPE_LINE_CHAIN bypass = DIRECTION_45().BuildInitialTrace( s1.A, s2.B, dir1.IsDiagonal() );
1155  SHAPE_LINE_CHAIN newRef;
1156  SHAPE_LINE_CHAIN newCoup;
1157  int64_t deltaCoupled = -1, deltaUni = -1;
1158 
1159  newRef = currentPath;
1160  newRef.Replace( s1.Index(), s2.Index(), bypass );
1161 
1162  deltaUni = aPair->CoupledLength ( newRef, coupledPath ) - clenPre + budget;
1163 
1164  if ( coupledBypass( m_world, aPair, aTryP, newRef, bypass, coupledPath, newCoup ) )
1165  {
1166  deltaCoupled = aPair->CoupledLength( newRef, newCoup ) - clenPre + budget;
1167 
1168  if( deltaCoupled >= 0 )
1169  {
1170  newRef.Simplify();
1171  newCoup.Simplify();
1172 
1173  aPair->SetShape( newRef, newCoup, !aTryP );
1174  return true;
1175  }
1176  }
1177  else if( deltaUni >= 0 && verifyDpBypass ( m_world, aPair, aTryP, newRef, coupledPath ) )
1178  {
1179  newRef.Simplify();
1180  coupledPath.Simplify();
1181 
1182  aPair->SetShape( newRef, coupledPath, !aTryP );
1183  return true;
1184  }
1185  }
1186 
1187  n++;
1188  }
1189 
1190  return false;
1191 }
1192 
1193 
1195 {
1196  int step_p = aPair->CP().SegmentCount() - 2;
1197  int step_n = aPair->CN().SegmentCount() - 2;
1198 
1199  while( 1 )
1200  {
1201  int n_segs_p = aPair->CP().SegmentCount();
1202  int n_segs_n = aPair->CN().SegmentCount();
1203 
1204  int max_step_p = n_segs_p - 2;
1205  int max_step_n = n_segs_n - 2;
1206 
1207  if( step_p > max_step_p )
1208  step_p = max_step_p;
1209 
1210  if( step_n > max_step_n )
1211  step_n = max_step_n;
1212 
1213  if( step_p < 1 && step_n < 1)
1214  break;
1215 
1216  bool found_anything_p = false;
1217  bool found_anything_n = false;
1218 
1219  if( step_p > 1 )
1220  found_anything_p = mergeDpStep( aPair, true, step_p );
1221 
1222  if( step_n > 1 )
1223  found_anything_n = mergeDpStep( aPair, false, step_n );
1224 
1225  if( !found_anything_n && !found_anything_p )
1226  {
1227  step_n--;
1228  step_p--;
1229  }
1230  }
1231  return true;
1232 }
1233 
1234 
1236 {
1237  return mergeDpSegments( aPair );
1238 }
1239 
1240 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:123
bool m_restrictAreaActive
const SHAPE_LINE_CHAIN & CLine() const
Const accessor to the underlying shape
Definition: pns_line.h:141
BREAKOUT_LIST computeBreakouts(int aWidth, const ITEM *aItem, bool aPermitDiagonal) const
ITEM.
Definition: pns_item.h:53
int Index() const
Function Index()
Definition: seg.h:317
const SHAPE * Shape() const override
Function Shape()
Definition: pns_solid.h:64
long long int Length() const
Function Length()
RVERTEX(bool aRestricted, int aAllowedAngles)
void CacheStaticItem(ITEM *aItem)
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:202
SHAPE_SIMPLE.
Definition: shape_simple.h:42
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
std::vector< INTERSECTION > INTERSECTIONS
virtual int Layer() const
Definition: pns_item.h:154
BREAKOUT_LIST circleBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
VECTOR2I Offset() const
Definition: pns_solid.h:106
NODE.
Definition: pns_node.h:140
void CacheRemove(ITEM *aItem)
void removeCachedSegments(LINE *aLine, int aStartVertex=0, int aEndVertex=-1)
static const int dist[10][10]
Definition: ar_matrix.cpp:326
int GetRadius() const
Definition: shape_circle.h:83
void SetShape(const SHAPE_LINE_CHAIN &aP, const SHAPE_LINE_CHAIN &aN, bool aSwapLanes=false)
int Gap() const
int SegmentCount() const
Returns the number of segments in the line
Definition: pns_line.h:147
int Mask() const
Definition: direction45.h:317
const SEG CSegment(int aIdx) const
Returns the aIdx-th segment of the line
Definition: pns_line.h:165
void Replace(LINE &aOldLine, LINE &aNewLine)
int Width() const
const SHAPE_LINE_CHAIN & CN() const
bool mergeStep(LINE *aLine, SHAPE_LINE_CHAIN &aCurrentLine, int step)
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false) const
Function BuildInitialTrace()
Definition: direction45.h:203
ITEM * findPadOrVia(int aLayer, int aNet, const VECTOR2I &aP) const
SHAPE_TYPE Type() const
Function Type()
Definition: shape.h:85
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
double CoupledLength() const
std::vector< RVERTEX > m_rs
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Function IntersectLines()
Definition: seg.h:186
const VECTOR2I GetCenter() const
Definition: shape_circle.h:88
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
BREAKOUT_LIST rectBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
const BOX2I BBox(int aClearance=0) const override
Function BBox()
Definition: shape_simple.h:74
bool runSmartPads(LINE *aLine)
VECTOR2< int > VECTOR2I
Definition: vector2d.h:594
bool mergeFull(LINE *aLine)
virtual bool Collide(const VECTOR2I &aP, int aClearance=0) const
Function Collide()
Definition: shape.h:109
int PointCount() const
Function PointCount()
const RANGED_NUM< int > GapConstraint() const
const SHAPE * Shape() const override
Function Shape()
Definition: pns_via.h:148
int PointCount() const
Returns the number of points in the line
Definition: pns_line.h:153
bool EndsWithVia() const
Definition: pns_line.h:267
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
int allowedAngles(NODE *aWorld, const LINE *aLine, const VECTOR2I &aP, bool aFirst)
const VECTOR2I & CPoint(int aIdx) const
Returns the aIdx-th point of the line
Definition: pns_line.h:159
void SetCollisionMask(int aMask)
const VECTOR2I GetSize() const
Function GetSize()
Definition: shape_rect.h:111
bool mergeDpStep(DIFF_PAIR *aPair, bool aTryP, int step)
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Assigns a shape to the line (a polyline/line chain)
Definition: pns_line.h:122
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
ITEM_SET & Links()
Definition: pns_joint.h:205
AngleType Angle(const DIRECTION_45 &aOther) const
Function Angle() Returns the type of angle between directions (this) and aOther.
Definition: direction45.h:150
const VECTOR2I & CPoint(int aIndex) const
Function Point()
JOINT.
Definition: pns_joint.h:43
BREAKOUT_LIST customBreakouts(int aWidth, const ITEM *aItem, bool aPermitDiagonal) const
VECTOR2I LineProject(const VECTOR2I &aP) const
Function LineProject()
Definition: seg.h:344
int GetClearance(const ITEM *aA, const ITEM *aB) const
Returns the expected clearance between items a and b.
Definition: pns_node.cpp:95
#define NULL
bool ApproxParallel(const SEG &aSeg) const
Definition: seg.h:260
virtual const SHAPE * Shape() const
Function Shape()
Definition: pns_item.h:213
int Net() const
Definition: pns_item.h:148
DIRECTION_45.
Definition: direction45.h:37
const VECTOR2I & GetPosition() const
Function GetPosition()
Definition: shape_rect.h:101
bool Contains(const Vec &aPoint) const
Function Contains.
Definition: box2.h:150
bool mergeDpSegments(DIFF_PAIR *aPair)
std::vector< SEGMENT * > SEGMENT_REFS
Definition: pns_line.h:64
bool coupledBypass(NODE *aNode, DIFF_PAIR *aPair, bool aRefIsP, const SHAPE_LINE_CHAIN &aRef, const SHAPE_LINE_CHAIN &aRefBypass, const SHAPE_LINE_CHAIN &aCoupled, SHAPE_LINE_CHAIN &aNewCoupled)
DIRECTION_45 Opposite() const
Function Opposite() Returns a direction opposite (180 degree) to (this)
Definition: direction45.h:139
bool IsDiagonal() const
Function IsDiagonal() Returns true if the direction is diagonal (e.g.
Definition: direction45.h:183
const SHAPE_LINE_CHAIN & Vertices() const
Function Vertices()
Definition: shape_simple.h:125
bool Check(int aVertex1, int aVertex2, const SHAPE_LINE_CHAIN &aReplacement)
bool mergeObtuse(LINE *aLine)
SHAPE.
Definition: shape.h:60
const LINKED_ITEMS & LinkList() const
Definition: pns_joint.h:195
int SegmentCount() const
Function SegmentCount()
int findCoupledVertices(const VECTOR2I &aVertex, const SEG &aOrigSeg, const SHAPE_LINE_CHAIN &aCoupled, DIFF_PAIR *aPair, int *aIndices)
line chain (polyline)
Definition: shape.h:48
CachedItemTags m_cacheTags
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:954
void Build(NODE *aWorld, LINE *aOriginLine, const SHAPE_LINE_CHAIN &aLine, const BOX2I &aRestrictedArea, bool aRestrictedAreaEnable)
SHAPE_LINE_CHAIN & Line()
Modifiable accessor to the underlying shape
Definition: pns_line.h:135
Definition: seg.h:39
OPTIMIZER(NODE *aWorld)
Optimizer.
DIFF_PAIR.
void cacheAdd(ITEM *aItem, bool aIsStatic)
bool operator()(ITEM *aOtherItem)
void Reverse()
Definition: seg.h:326
const SHAPE_LINE_CHAIN & CP() const
VECTOR2< T > Rotate(double aAngle) const
Function Rotate rotates the vector by a given angle.
Definition: vector2d.h:377
bool verifyDpBypass(NODE *aNode, DIFF_PAIR *aPair, bool aRefIsP, const SHAPE_LINE_CHAIN &aNewRef, const SHAPE_LINE_CHAIN &aNewCoupled)
CACHE_VISITOR(const ITEM *aOurItem, NODE *aNode, int aMask)
SEGMENT_REFS & LinkedSegments()
Returns the list of segments from the owning node that constitute this line (or NULL if the line is n...
Definition: pns_line.h:200
const SEG CSegment(int aIndex) const
Function CSegment()
bool fanoutCleanup(LINE *aLine)
SHAPE_LINE_CHAIN.
SHAPE_RECT ApproximateSegmentAsRect(const SHAPE_SEGMENT &aSeg)
Definition: pns_utils.cpp:158
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:421
int GetMaxClearance() const
Returns the pre-set worst case clearance between any pair of items
Definition: pns_node.h:154
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
VECTOR2I A
Definition: seg.h:47
bool OfKind(int aKindMask) const
Function OfKind()
Definition: pns_item.h:132
bool checkColliding(ITEM *aItem, bool aUpdateCache=true)
void Add(LINE &aLine)
const ENTRIES & CItems() const
Definition: pns_itemset.h:141
int Width() const
Returns line width
Definition: pns_line.h:178
static int CornerCost(const SEG &aA, const SEG &aB)
Cost Estimator Methods.
PnsKind Kind() const
Function Kind()
Definition: pns_item.h:122
OPTIMIZER.
Definition: pns_optimizer.h:90
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:143
bool Matches(const T &aOther) const
Definition: ranged_num.h:43
int smartPadsSingle(LINE *aLine, ITEM *aPad, bool aEnd, int aEndVertex)
SHAPE_INDEX_LIST< ITEM * > m_cache
void SetEffortLevel(int aEffort)
Definition: shape.h:45
std::vector< SHAPE_LINE_CHAIN > BREAKOUT_LIST
bool IsLinked() const
Definition: pns_line.h:205
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Function Replace()
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld)
a quick shortcut to optmize a line without creating and setting up an optimizer
COST_ESTIMATOR.
Definition: pns_optimizer.h:45
Directions
Enum Directions Represents available directions - there are 8 of them, as on a rectilinear map (north...
Definition: direction45.h:46
Push and Shove diff pair dimensions (gap) settings dialog.
void Remove(LINE &aLine)
bool checkDpColliding(NODE *aNode, DIFF_PAIR *aPair, bool aIsP, const SHAPE_LINE_CHAIN &aPath)
circle
Definition: shape.h:49
void ClearCache(bool aStaticOnly=false)
bool IsObtuse(const DIRECTION_45 &aOther) const
Function IsObtuse()
Definition: direction45.h:173
bool IsBetter(COST_ESTIMATOR &aOther, double aLengthTolerance, double aCornerTollerace) const
axis-aligned rectangle
Definition: shape.h:46
int CountCorners(int aAngles) const
Returns the number of corners of angles specified by mask aAngles.
Definition: pns_line.cpp:138
VECTOR2I B
Definition: seg.h:48