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 <geometry/shape_file_io.h>
26 
27 #include <cmath>
28 
29 #include "pns_arc.h"
30 #include "pns_line.h"
31 #include "pns_diff_pair.h"
32 #include "pns_node.h"
33 #include "pns_solid.h"
34 #include "pns_optimizer.h"
35 
36 #include "pns_utils.h"
37 #include "pns_router.h"
38 #include "pns_debug_decorator.h"
39 
40 
41 namespace PNS {
42 
43 
48 int COST_ESTIMATOR::CornerCost( const SEG& aA, const SEG& aB )
49 {
50  DIRECTION_45 dir_a( aA ), dir_b( aB );
51 
52  switch( dir_a.Angle( dir_b ) )
53  {
55  return 10;
56 
58  return 5;
59 
61  return 50;
62 
64  return 30;
65 
67  return 60;
68 
69  default:
70  return 100;
71  }
72 }
73 
74 
76 {
77  int total = 0;
78 
79  for( int i = 0; i < aLine.SegmentCount() - 1; ++i )
80  total += CornerCost( aLine.CSegment( i ), aLine.CSegment( i + 1 ) );
81 
82  return total;
83 }
84 
85 
86 int COST_ESTIMATOR::CornerCost( const LINE& aLine )
87 {
88  return CornerCost( aLine.CLine() );
89 }
90 
91 
92 void COST_ESTIMATOR::Add( LINE& aLine )
93 {
94  m_lengthCost += aLine.CLine().Length();
95  m_cornerCost += CornerCost( aLine );
96 }
97 
98 
100 {
101  m_lengthCost -= aLine.CLine().Length();
102  m_cornerCost -= CornerCost( aLine );
103 }
104 
105 
106 void COST_ESTIMATOR::Replace( LINE& aOldLine, LINE& aNewLine )
107 {
108  m_lengthCost -= aOldLine.CLine().Length();
109  m_cornerCost -= CornerCost( aOldLine );
110  m_lengthCost += aNewLine.CLine().Length();
111  m_cornerCost += CornerCost( aNewLine );
112 }
113 
114 
116  double aLengthTolerance,
117  double aCornerTolerance ) const
118 {
119  if( aOther.m_cornerCost < m_cornerCost && aOther.m_lengthCost < m_lengthCost )
120  return true;
121 
122  else if( aOther.m_cornerCost < m_cornerCost * aCornerTolerance &&
123  aOther.m_lengthCost < m_lengthCost * aLengthTolerance )
124  return true;
125 
126  return false;
127 }
128 
129 
134  m_world( aWorld ),
135  m_collisionKindMask( ITEM::ANY_T ),
136  m_effortLevel( MERGE_SEGMENTS ),
137  m_keepPostures( false ),
138  m_restrictAreaActive( false )
139 {
140 }
141 
142 
144 {
145 }
146 
147 
149 {
150  CACHE_VISITOR( const ITEM* aOurItem, NODE* aNode, int aMask ) :
151  m_ourItem( aOurItem ),
153  m_node( aNode ),
154  m_mask( aMask )
155  {}
156 
157  bool operator()( ITEM* aOtherItem )
158  {
159  if( !( m_mask & aOtherItem->Kind() ) )
160  return true;
161 
162  int clearance = m_node->GetClearance( aOtherItem, m_ourItem );
163 
164  if( !aOtherItem->Collide( m_ourItem, clearance, false, nullptr, m_node ) )
165  return true;
166 
167  m_collidingItem = aOtherItem;
168  return false;
169  }
170 
171  const ITEM* m_ourItem;
174  int m_mask;
175 };
176 
177 
178 void OPTIMIZER::cacheAdd( ITEM* aItem, bool aIsStatic = false )
179 {
180  if( m_cacheTags.find( aItem ) != m_cacheTags.end() )
181  return;
182 
183  m_cache.Add( aItem );
184  m_cacheTags[aItem].m_hits = 1;
185  m_cacheTags[aItem].m_isStatic = aIsStatic;
186 }
187 
188 
189 void OPTIMIZER::removeCachedSegments( LINE* aLine, int aStartVertex, int aEndVertex )
190 {
191  if( !aLine->IsLinked() ) return;
192 
193  auto links = aLine->Links();
194 
195  if( aEndVertex < 0 )
196  aEndVertex += aLine->PointCount();
197 
198  for( int i = aStartVertex; i < aEndVertex - 1; i++ )
199  {
200  LINKED_ITEM* s = links[i];
201  m_cacheTags.erase( s );
202  m_cache.Remove( s );
203  }
204 }
205 
206 
208 {
209  if( aItem->Kind() == ITEM::LINE_T )
210  removeCachedSegments( static_cast<LINE*>( aItem ) );
211 }
212 
213 
215 {
216  cacheAdd( aItem, true );
217 }
218 
219 
220 void OPTIMIZER::ClearCache( bool aStaticOnly )
221 {
222  if( !aStaticOnly )
223  {
224  m_cacheTags.clear();
225  m_cache.Clear();
226  return;
227  }
228 
229  for( CachedItemTags::iterator i = m_cacheTags.begin(); i!= m_cacheTags.end(); ++i )
230  {
231  if( i->second.m_isStatic )
232  {
233  m_cache.Remove( i->first );
234  m_cacheTags.erase( i->first );
235  }
236  }
237 }
238 
239 
240 bool ANGLE_CONSTRAINT_45::Check ( int aVertex1, int aVertex2, LINE* aOriginLine, const SHAPE_LINE_CHAIN& aCurrentPath, const SHAPE_LINE_CHAIN& aReplacement )
241 {
242  auto dir_orig0 = DIRECTION_45( aOriginLine->CSegment( aVertex1 ) );
243  auto dir_orig1 = DIRECTION_45( aOriginLine->CSegment( aVertex2 - 1) );
244 
245  if( aVertex1 == 0 )
246  {
247  if( ( dir_orig0.Mask() & m_entryDirectionMask ) == 0 )
248  return false; // disallowed entry angle
249  }
250 
251  if( aVertex2 == aOriginLine->SegmentCount() - 1 )
252  {
253  if( ( dir_orig1.Mask() & m_exitDirectionMask ) == 0 )
254  return false; // disallowed exit ngle
255  }
256 
257 
258 
259  /*auto ang_rep0 = DIRECTION_45( aReplacement.CSegment(0) ).Angle( dir_orig0 );
260  auto ang_rep1 = DIRECTION_45( aReplacement.CSegment(-1) ).Angle( dir_orig1 );*/
261 
262  return true;
263 }
264 
265 bool AREA_CONSTRAINT::Check ( int aVertex1, int aVertex2, LINE* aOriginLine, const SHAPE_LINE_CHAIN& aCurrentPath, const SHAPE_LINE_CHAIN& aReplacement )
266 {
267  auto p1 = aOriginLine->CPoint( aVertex1 );
268  auto p2 = aOriginLine->CPoint( aVertex2 );
269 
270  auto p1_in = m_allowedArea.Contains( p1 );
271  auto p2_in = m_allowedArea.Contains( p2 );
272 
273  return p1_in || p2_in;
274 }
275 
277  {
278  public:
279  JOINT_CACHE( NODE *aWorld, int aLayer, int aMaxJoints );
280 
281  bool CheckInside( const VECTOR2I& aPos ) const;
282 
283  private:
284 
285  struct ENTRY {
287  int score;
288  };
289 };
290 
291 
292 bool PRESERVE_VERTEX_CONSTRAINT::Check ( int aVertex1, int aVertex2, LINE* aOriginLine, const SHAPE_LINE_CHAIN& aCurrentPath, const SHAPE_LINE_CHAIN& aReplacement )
293 {
294  bool cv = false;
295 
296  for( int i = aVertex1; i < aVertex2; i++ )
297  {
298  int dist = aCurrentPath.CSegment(i).Distance( m_v );
299  if ( dist <= 1 )
300  {
301  cv = true;
302  break;
303  }
304  }
305 
306  if(!cv)
307  {
308  return true;
309  }
310 
311  for( int i = 0; i < aReplacement.SegmentCount(); i++ )
312  {
313  int dist = aReplacement.CSegment(i).Distance( m_v );
314 
315  if ( dist <= 1 )
316  {
317  return true;
318  }
319  }
320 
321  return false;
322 }
323 
324 
325 // fixme: integrate into SHAPE_LINE_CHAIN, check corner cases against current PointInside implementation
326 static bool pointInside2( const SHAPE_LINE_CHAIN& aL, const VECTOR2I& aP )
327 {
328  if( !aL.IsClosed() || aL.SegmentCount() < 3 )
329  return false;
330 
331  // returns 0 if false, +1 if true, -1 if pt ON polygon boundary
332  int result = 0;
333  size_t cnt = aL.PointCount();
334 
335  auto ip = aL.CPoint( 0 );
336 
337  for( size_t i = 1; i <= cnt; ++i )
338  {
339  auto ipNext = (i == cnt ? aL.CPoint( 0 ) : aL.CPoint( i ));
340 
341  if( ipNext.y == aP.y )
342  {
343  if( (ipNext.x ==aP.x) || ( ip.y ==aP.y
344  && ( (ipNext.x >aP.x) == (ip.x <aP.x) ) ) )
345  return -1;
346  }
347 
348  if( (ip.y <aP.y) != (ipNext.y <aP.y) )
349  {
350  if( ip.x >=aP.x )
351  {
352  if( ipNext.x >aP.x )
353  result = 1 - result;
354  else
355  {
356  double d = (double) (ip.x -aP.x) * (ipNext.y -aP.y) -
357  (double) (ipNext.x -aP.x) * (ip.y -aP.y);
358 
359  if( !d )
360  return -1;
361 
362  if( (d > 0) == (ipNext.y > ip.y) )
363  result = 1 - result;
364  }
365  }
366  else
367  {
368  if( ipNext.x >aP.x )
369  {
370  double d = (double) (ip.x -aP.x) * (ipNext.y -aP.y) -
371  (double) (ipNext.x -aP.x) * (ip.y -aP.y);
372 
373  if( !d )
374  return -1;
375 
376  if( (d > 0) == (ipNext.y > ip.y) )
377  result = 1 - result;
378  }
379  }
380  }
381 
382  ip = ipNext;
383  }
384 
385  return result > 0;
386 }
387 
388 
389 bool KEEP_TOPOLOGY_CONSTRAINT::Check ( int aVertex1, int aVertex2, LINE* aOriginLine, const SHAPE_LINE_CHAIN& aCurrentPath, const SHAPE_LINE_CHAIN& aReplacement )
390  {
391  SHAPE_LINE_CHAIN encPoly = aOriginLine->CLine().Slice( aVertex1, aVertex2 );
392 
393  // fixme: this is a remarkably shitty implementation...
394  encPoly.Append( aReplacement.Reverse() );
395  encPoly.SetClosed( true );
396 
397  auto bb = encPoly.BBox();
398  std::vector<JOINT*> joints;
399 
400  int cnt = m_world->QueryJoints( bb, joints, aOriginLine->Layers().Start(), ITEM::SOLID_T );
401 
402  if( !cnt )
403  return true;
404 
405  for( auto j : joints )
406  {
407  if ( j->Net() == aOriginLine->Net() )
408  continue;
409 
410  if ( pointInside2( encPoly, j->Pos() ) )
411  {
412  bool falsePositive = false;
413  for( int k = 0; k < encPoly.PointCount(); k++)
414  if(encPoly.CPoint(k) == j->Pos() )
415  {
416  falsePositive = true;
417  break;
418  }
419 
420  if( !falsePositive )
421  {
422  //dbg->AddPoint(j->Pos(), 5);
423  return false;
424  }
425  }
426  }
427 
428  return true;
429 }
430 
431 bool OPTIMIZER::checkColliding( ITEM* aItem, bool aUpdateCache )
432 {
434 
435  return static_cast<bool>( m_world->CheckColliding( aItem ) );
436 }
437 
439 {
440  for (auto c : m_constraints)
441  delete c;
442  m_constraints.clear();
443 }
444 
446  {
447  m_constraints.push_back(aConstraint);
448 }
449 
450 bool OPTIMIZER::checkConstraints( int aVertex1, int aVertex2, LINE* aOriginLine, const SHAPE_LINE_CHAIN& aCurrentPath, const SHAPE_LINE_CHAIN& aReplacement )
451 {
452  for( auto c: m_constraints)
453  {
454  if ( !c->Check( aVertex1, aVertex2, aOriginLine, aCurrentPath, aReplacement ) )
455  {
456  return false;
457  }
458  }
459 
460  return true;
461 }
462 
463 
464 bool OPTIMIZER::checkColliding( LINE* aLine, const SHAPE_LINE_CHAIN& aOptPath )
465 {
466  LINE tmp( *aLine, aOptPath );
467 
468  return checkColliding( &tmp );
469 }
470 
471 
473 {
474  SHAPE_LINE_CHAIN& line = aLine->Line();
475 
476  int step = line.PointCount() - 3;
477  int iter = 0;
478  int segs_pre = line.SegmentCount();
479 
480  if( step < 0 )
481  return false;
482 
483  SHAPE_LINE_CHAIN current_path( line );
484 
485  while( 1 )
486  {
487  iter++;
488  int n_segs = current_path.SegmentCount();
489  int max_step = n_segs - 2;
490 
491  if( step > max_step )
492  step = max_step;
493 
494  if( step < 2 )
495  {
496  line = current_path;
497  return current_path.SegmentCount() < segs_pre;
498  }
499 
500  bool found_anything = false;
501 
502  for( int n = 0; n < n_segs - step; n++ )
503  {
504  const SEG s1 = current_path.CSegment( n );
505  const SEG s2 = current_path.CSegment( n + step );
506  SEG s1opt, s2opt;
507 
508  if( DIRECTION_45( s1 ).IsObtuse( DIRECTION_45( s2 ) ) )
509  {
510  VECTOR2I ip = *s1.IntersectLines( s2 );
511 
512  s1opt = SEG( s1.A, ip );
513  s2opt = SEG( ip, s2.B );
514 
515  if( DIRECTION_45( s1opt ).IsObtuse( DIRECTION_45( s2opt ) ) )
516  {
517  SHAPE_LINE_CHAIN opt_path;
518  opt_path.Append( s1opt.A );
519  opt_path.Append( s1opt.B );
520  opt_path.Append( s2opt.B );
521 
522  LINE opt_track( *aLine, opt_path );
523 
524  if( !checkColliding( &opt_track ) )
525  {
526  current_path.Replace( s1.Index() + 1, s2.Index(), ip );
527  // removeCachedSegments(aLine, s1.Index(), s2.Index());
528  n_segs = current_path.SegmentCount();
529  found_anything = true;
530  break;
531  }
532  }
533  }
534  }
535 
536  if( !found_anything )
537  {
538  if( step <= 2 )
539  {
540  line = current_path;
541  return line.SegmentCount() < segs_pre;
542  }
543 
544  step--;
545  }
546  }
547 
548  return line.SegmentCount() < segs_pre;
549 }
550 
551 
553 {
554  SHAPE_LINE_CHAIN& line = aLine->Line();
555  int step = line.SegmentCount() - 1;
556 
557  int segs_pre = line.SegmentCount();
558 
559  line.Simplify();
560 
561  if( step < 0 )
562  return false;
563 
564  SHAPE_LINE_CHAIN current_path( line );
565 
566  while( 1 )
567  {
568  int n_segs = current_path.SegmentCount();
569  int max_step = n_segs - 2;
570 
571  if( step > max_step )
572  step = max_step;
573 
574  if( step < 1 )
575  break;
576 
577  bool found_anything = mergeStep( aLine, current_path, step );
578 
579  if( !found_anything )
580  step--;
581 
582  if( !step )
583  break;
584  }
585 
586  aLine->SetShape( current_path );
587 
588  return current_path.SegmentCount() < segs_pre;
589 }
590 
591 
592 bool OPTIMIZER::Optimize( LINE* aLine, LINE* aResult )
593 {
594  if( !aResult )
595  aResult = aLine;
596  else
597  {
598  *aResult = *aLine;
599  aResult->ClearLinks();
600  }
601 
602  m_keepPostures = false;
603 
604  bool rv = false;
605 
607  rv |= mergeFull( aResult );
608 
610  rv |= mergeObtuse( aResult );
611 
612  if( m_effortLevel & SMART_PADS )
613  rv |= runSmartPads( aResult );
614 
616  rv |= fanoutCleanup( aResult );
617 
618  return rv;
619 }
620 
621 
622 bool OPTIMIZER::mergeStep( LINE* aLine, SHAPE_LINE_CHAIN& aCurrentPath, int step )
623 {
624  int n_segs = aCurrentPath.SegmentCount();
625 
626  int cost_orig = COST_ESTIMATOR::CornerCost( aCurrentPath );
627 
628  if( aLine->SegmentCount() < 2 )
629  return false;
630 
631  DIRECTION_45 orig_start( aLine->CSegment( 0 ) );
632  DIRECTION_45 orig_end( aLine->CSegment( -1 ) );
633 
634 
635  for( int n = 0; n < n_segs - step; n++ )
636  {
637  // Do not attempt to merge false segments that are part of an arc
638  if( aCurrentPath.isArc( n ) || aCurrentPath.isArc( n + step ) )
639  continue;
640 
641  const SEG s1 = aCurrentPath.CSegment( n );
642  const SEG s2 = aCurrentPath.CSegment( n + step );
643 
644  SHAPE_LINE_CHAIN path[2];
645  SHAPE_LINE_CHAIN* picked = NULL;
646  int cost[2];
647 
648  for( int i = 0; i < 2; i++ )
649  {
650  SHAPE_LINE_CHAIN bypass = DIRECTION_45().BuildInitialTrace( s1.A, s2.B, i );
651  cost[i] = INT_MAX;
652 
653 
654  bool ok = false;
655  if ( !checkColliding( aLine, bypass ) )
656  {
657  ok = checkConstraints ( n, n + step + 1, aLine, aCurrentPath, bypass );
658  }
659 
660  if( ok )
661  {
662  path[i] = aCurrentPath;
663  path[i].Replace( s1.Index(), s2.Index(), bypass );
664  path[i].Simplify();
665  cost[i] = COST_ESTIMATOR::CornerCost( path[i] );
666  }
667  }
668 
669  if( cost[0] < cost_orig && cost[0] < cost[1] )
670  picked = &path[0];
671  else if( cost[1] < cost_orig )
672  picked = &path[1];
673 
674  if( picked )
675  {
676  n_segs = aCurrentPath.SegmentCount();
677  aCurrentPath = *picked;
678  return true;
679  }
680  }
681 
682  return false;
683 }
684 
685 
687  const SHAPE* aShape, bool aPermitDiagonal ) const
688 {
689  BREAKOUT_LIST breakouts;
690 
691  for( int angle = 0; angle < 360; angle += 45 )
692  {
693  const SHAPE_CIRCLE* cir = static_cast<const SHAPE_CIRCLE*>( aShape );
695  VECTOR2I p0 = cir->GetCenter();
696  VECTOR2I v0( cir->GetRadius() * M_SQRT2, 0 );
697  l.Append( p0 );
698  l.Append( p0 + v0.Rotate( angle * M_PI / 180.0 ) );
699  breakouts.push_back( l );
700  }
701 
702  return breakouts;
703 }
704 
705 
707  const ITEM* aItem, bool aPermitDiagonal ) const
708 {
709  BREAKOUT_LIST breakouts;
710  const SHAPE_SIMPLE* convex = static_cast<const SHAPE_SIMPLE*>( aItem->Shape() );
711 
712  BOX2I bbox = convex->BBox( 0 );
713  VECTOR2I p0 = static_cast<const SOLID*>( aItem )->Pos();
714  // must be large enough to guarantee intersecting the convex polygon
715  int length = std::max( bbox.GetWidth(), bbox.GetHeight() ) / 2 + 5;
716 
717  for( int angle = 0; angle < 360; angle += ( aPermitDiagonal ? 45 : 90 ) )
718  {
720  VECTOR2I v0( p0 + VECTOR2I( length, 0 ).Rotate( angle * M_PI / 180.0 ) );
721  SHAPE_LINE_CHAIN::INTERSECTIONS intersections;
722  int n = convex->Vertices().Intersect( SEG( p0, v0 ), intersections );
723  // if n == 1 intersected a segment
724  // if n == 2 intersected the common point of 2 segments
725  // n == 0 can not happen I think, but...
726  if( n > 0 )
727  {
728  l.Append( p0 );
729 
730  // for a breakout distance relative to the distance between
731  // center and polygon edge
732  //l.Append( intersections[0].p + (v0 - p0).Resize( (intersections[0].p - p0).EuclideanNorm() * 0.4 ) );
733 
734  // for an absolute breakout distance, e.g. 0.1 mm
735  //l.Append( intersections[0].p + (v0 - p0).Resize( 100000 ) );
736 
737  // for the breakout right on the polygon edge
738  l.Append( intersections[0].p );
739 
740  breakouts.push_back( l );
741  }
742  }
743 
744  return breakouts;
745 }
746 
747 
749  const SHAPE* aShape, bool aPermitDiagonal ) const
750 {
751  const SHAPE_RECT* rect = static_cast<const SHAPE_RECT*>(aShape);
752  VECTOR2I s = rect->GetSize();
753  VECTOR2I c = rect->GetPosition() + VECTOR2I( s.x / 2, s.y / 2 );
754  BREAKOUT_LIST breakouts;
755 
756  VECTOR2I d_offset;
757 
758  d_offset.x = ( s.x > s.y ) ? ( s.x - s.y ) / 2 : 0;
759  d_offset.y = ( s.x < s.y ) ? ( s.y - s.x ) / 2 : 0;
760 
761  VECTOR2I d_vert = VECTOR2I( 0, s.y / 2 + aWidth );
762  VECTOR2I d_horiz = VECTOR2I( s.x / 2 + aWidth, 0 );
763 
764  breakouts.push_back( SHAPE_LINE_CHAIN( { c, c + d_horiz } ) );
765  breakouts.push_back( SHAPE_LINE_CHAIN( { c, c - d_horiz } ) );
766  breakouts.push_back( SHAPE_LINE_CHAIN( { c, c + d_vert } ) );
767  breakouts.push_back( SHAPE_LINE_CHAIN( { c, c - d_vert } ) );
768 
769  if( aPermitDiagonal )
770  {
771  int l = aWidth + std::min( s.x, s.y ) / 2;
772  VECTOR2I d_diag;
773 
774  if( s.x >= s.y )
775  {
776  breakouts.push_back(
777  SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( l, l ) } ) );
778  breakouts.push_back(
779  SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset - VECTOR2I( -l, l ) } ) );
780  breakouts.push_back(
781  SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset + VECTOR2I( -l, l ) } ) );
782  breakouts.push_back(
783  SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( l, l ) } ) );
784  }
785  else
786  {
787  // fixme: this could be done more efficiently
788  breakouts.push_back(
789  SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( l, l ) } ) );
790  breakouts.push_back(
791  SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( -l, l ) } ) );
792  breakouts.push_back(
793  SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( -l, l ) } ) );
794  breakouts.push_back(
795  SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( l, l ) } ) );
796  }
797  }
798 
799  return breakouts;
800 }
801 
802 
804  const ITEM* aItem, bool aPermitDiagonal ) const
805 {
806  switch( aItem->Kind() )
807  {
808  case ITEM::VIA_T:
809  {
810  const VIA* via = static_cast<const VIA*>( aItem );
811  return circleBreakouts( aWidth, via->Shape(), aPermitDiagonal );
812  }
813 
814  case ITEM::SOLID_T:
815  {
816  const SHAPE* shape = aItem->Shape();
817 
818  switch( shape->Type() )
819  {
820  case SH_RECT:
821  return rectBreakouts( aWidth, shape, aPermitDiagonal );
822 
823  case SH_SEGMENT:
824  {
825  const SHAPE_SEGMENT* seg = static_cast<const SHAPE_SEGMENT*> (shape);
826  const SHAPE_RECT rect = ApproximateSegmentAsRect ( *seg );
827  return rectBreakouts( aWidth, &rect, aPermitDiagonal );
828  }
829 
830  case SH_CIRCLE:
831  return circleBreakouts( aWidth, shape, aPermitDiagonal );
832 
833  case SH_SIMPLE:
834  return customBreakouts( aWidth, aItem, aPermitDiagonal );
835 
836  default:
837  break;
838  }
839 
840  break;
841  }
842 
843  default:
844  break;
845  }
846 
847  return BREAKOUT_LIST();
848 }
849 
850 
851 ITEM* OPTIMIZER::findPadOrVia( int aLayer, int aNet, const VECTOR2I& aP ) const
852 {
853  JOINT* jt = m_world->FindJoint( aP, aLayer, aNet );
854 
855  if( !jt )
856  return NULL;
857 
858  for( ITEM* item : jt->LinkList() )
859  {
860  if( item->OfKind( ITEM::VIA_T | ITEM::SOLID_T ) )
861  return item;
862  }
863 
864  return NULL;
865 }
866 
867 
868 int OPTIMIZER::smartPadsSingle( LINE* aLine, ITEM* aPad, bool aEnd, int aEndVertex )
869 {
870  DIRECTION_45 dir;
871 
872  const int ForbiddenAngles = DIRECTION_45::ANG_ACUTE | DIRECTION_45::ANG_RIGHT |
874 
875  typedef std::tuple<int, long long int, SHAPE_LINE_CHAIN> RtVariant;
876  std::vector<RtVariant> variants;
877 
878  SOLID* solid = dyn_cast<SOLID*>( aPad );
879 
880  // don't do optimized connections for offset pads
881  if( solid && solid->Offset() != VECTOR2I( 0, 0 ) )
882  return -1;
883 
884 
885  BREAKOUT_LIST breakouts = computeBreakouts( aLine->Width(), aPad, true );
886  SHAPE_LINE_CHAIN line = ( aEnd ? aLine->CLine().Reverse() : aLine->CLine() );
887  int p_end = std::min( aEndVertex, std::min( 3, line.PointCount() - 1 ) );
888 
889  // Start at 1 to find a potentially better breakout (0 is the pad connection)
890  for( int p = 1; p <= p_end; p++ )
891  {
892  // If the line is contained inside the pad, don't optimize
893  if( solid && solid->Shape() && !solid->Shape()->Collide(
894  SEG( line.CPoint( 0 ), line.CPoint( p ) ), aLine->Width() / 2 ) )
895  continue;
896 
897  for( SHAPE_LINE_CHAIN & breakout : breakouts ) {
898 
899  for( int diag = 0; diag < 2; diag++ )
900  {
902  SHAPE_LINE_CHAIN connect = dir.BuildInitialTrace(
903  breakout.CPoint( -1 ), line.CPoint( p ), diag == 0 );
904 
905  DIRECTION_45 dir_bkout( breakout.CSegment( -1 ) );
906 
907  if(!connect.SegmentCount())
908  continue;
909 
910  int ang1 = dir_bkout.Angle( DIRECTION_45( connect.CSegment( 0 ) ) );
911 
912  if( ang1 & ForbiddenAngles )
913  continue;
914 
915  if( breakout.Length() > line.Length() )
916  continue;
917 
918  v = breakout;
919  v.Append( connect );
920 
921  for( int i = p + 1; i < line.PointCount(); i++ )
922  v.Append( line.CPoint( i ) );
923 
924  LINE tmp( *aLine, v );
925  int cc = tmp.CountCorners( ForbiddenAngles );
926 
927  if( cc == 0 )
928  {
929  RtVariant vp;
930  std::get<0>( vp ) = p;
931  std::get<1>( vp ) = breakout.Length();
932  std::get<2>( vp ) = aEnd ? v.Reverse() : v;
933  std::get<2>( vp ).Simplify();
934  variants.push_back( vp );
935  }
936  }
937  }
938  }
939 
940  // We attempt to minimize the corner cost (minimizes the segments and types of corners)
941  // but given two, equally valid costs, we want to pick the longer pad exit. The logic
942  // here is that if the pad is oblong, the track should not exit the shorter side and parallel
943  // the pad but should follow the pad's preferential direction before exiting.
944  // The baseline guess is to start with the existing line the user has drawn.
945  int min_cost = COST_ESTIMATOR::CornerCost( *aLine );
946  long long int max_length = 0;
947  bool found = false;
948  int p_best = -1;
949  SHAPE_LINE_CHAIN l_best;
950 
951  for( RtVariant& vp : variants )
952  {
953  LINE tmp( *aLine, std::get<2>( vp ) );
954  int cost = COST_ESTIMATOR::CornerCost( std::get<2>( vp ) );
955  long long int len = std::get<1>( vp );
956 
957  if( !checkColliding( &tmp ) )
958  {
959  if( cost < min_cost || ( cost == min_cost && len > max_length ) )
960  {
961  l_best = std::get<2>( vp );
962  p_best = std::get<0>( vp );
963  found = true;
964 
965  if( cost <= min_cost )
966  max_length = std::max<int>( len, max_length );
967 
968  min_cost = std::min( cost, min_cost );
969  }
970  }
971  }
972 
973  if( found )
974  {
975  aLine->SetShape( l_best );
976  return p_best;
977  }
978 
979  return -1;
980 }
981 
983 {
984  SHAPE_LINE_CHAIN& line = aLine->Line();
985 
986  if( line.PointCount() < 3 )
987  return false;
988 
989  VECTOR2I p_start = line.CPoint( 0 ), p_end = line.CPoint( -1 );
990 
991  ITEM* startPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_start );
992  ITEM* endPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_end );
993 
994  int vtx = -1;
995 
996  if( startPad )
997  vtx = smartPadsSingle( aLine, startPad, false, 3 );
998 
999  if( endPad )
1000  smartPadsSingle( aLine, endPad, true,
1001  vtx < 0 ? line.PointCount() - 1 : line.PointCount() - 1 - vtx );
1002 
1003  aLine->Line().Simplify();
1004 
1005  return true;
1006 }
1007 
1008 
1009 bool OPTIMIZER::Optimize( LINE* aLine, int aEffortLevel, NODE* aWorld, const VECTOR2I aV )
1010 {
1011  OPTIMIZER opt( aWorld );
1012 
1014 
1015  opt.SetEffortLevel( aEffortLevel );
1016  opt.SetCollisionMask( -1 );
1017 
1018  if ( aEffortLevel & PRESERVE_VERTEX )
1019  {
1020  auto c = new PRESERVE_VERTEX_CONSTRAINT( aWorld, aV );
1021  opt.AddConstraint( c );
1022  }
1023 
1024  if ( aEffortLevel & KEEP_TOPOLOGY )
1025  {
1026  auto c = new KEEP_TOPOLOGY_CONSTRAINT( aWorld );
1027  opt.AddConstraint( c );
1028  }
1029 
1030  return opt.Optimize( aLine );
1031 }
1032 
1033 
1035 {
1036  if( aLine->PointCount() < 3 )
1037  return false;
1038 
1039  VECTOR2I p_start = aLine->CPoint( 0 ), p_end = aLine->CPoint( -1 );
1040 
1041  ITEM* startPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_start );
1042  ITEM* endPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_end );
1043 
1044  int thr = aLine->Width() * 10;
1045  int len = aLine->CLine().Length();
1046 
1047  if( !startPad )
1048  return false;
1049 
1050  bool startMatch = startPad->OfKind( ITEM::VIA_T | ITEM::SOLID_T );
1051  bool endMatch = false;
1052 
1053  if(endPad)
1054  {
1055  endMatch = endPad->OfKind( ITEM::VIA_T | ITEM::SOLID_T );
1056  }
1057  else
1058  {
1059  endMatch = aLine->EndsWithVia();
1060  }
1061 
1062  if( startMatch && endMatch && len < thr )
1063  {
1064  for( int i = 0; i < 2; i++ )
1065  {
1066  SHAPE_LINE_CHAIN l2 = DIRECTION_45().BuildInitialTrace( p_start, p_end, i );
1067  LINE repl;
1068  repl = LINE( *aLine, l2 );
1069 
1070  if( !m_world->CheckColliding( &repl ) )
1071  {
1072  aLine->SetShape( repl.CLine() );
1073  return true;
1074  }
1075  }
1076  }
1077 
1078  return false;
1079 }
1080 
1081 
1082 int findCoupledVertices( const VECTOR2I& aVertex, const SEG& aOrigSeg, const SHAPE_LINE_CHAIN& aCoupled, DIFF_PAIR* aPair, int* aIndices )
1083 {
1084  int count = 0;
1085  for ( int i = 0; i < aCoupled.SegmentCount(); i++ )
1086  {
1087  SEG s = aCoupled.CSegment( i );
1088  VECTOR2I projOverCoupled = s.LineProject ( aVertex );
1089 
1090  if( s.ApproxParallel ( aOrigSeg ) )
1091  {
1092  int64_t dist = ( projOverCoupled - aVertex ).EuclideanNorm() - aPair->Width();
1093 
1094  if( aPair->GapConstraint().Matches( dist ) )
1095  {
1096  *aIndices++ = i;
1097  count++;
1098  }
1099  }
1100  }
1101 
1102  return count;
1103 }
1104 
1105 
1106 bool verifyDpBypass( NODE* aNode, DIFF_PAIR* aPair, bool aRefIsP, const SHAPE_LINE_CHAIN& aNewRef, const SHAPE_LINE_CHAIN& aNewCoupled )
1107 {
1108  LINE refLine ( aRefIsP ? aPair->PLine() : aPair->NLine(), aNewRef );
1109  LINE coupledLine ( aRefIsP ? aPair->NLine() : aPair->PLine(), aNewCoupled );
1110 
1111  if( aNode->CheckColliding( &refLine, &coupledLine, ITEM::ANY_T, aPair->Gap() - 10 ) )
1112  return false;
1113 
1114  if( aNode->CheckColliding ( &refLine ) )
1115  return false;
1116 
1117  if( aNode->CheckColliding ( &coupledLine ) )
1118  return false;
1119 
1120  return true;
1121 }
1122 
1123 
1124 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 )
1125 {
1126  int vStartIdx[1024]; // fixme: possible overflow
1127 
1128  int nStarts = findCoupledVertices( aRefBypass.CPoint( 0 ), aRefBypass.CSegment( 0 ), aCoupled, aPair, vStartIdx );
1129  DIRECTION_45 dir( aRefBypass.CSegment( 0 ) );
1130 
1131  int64_t bestLength = -1;
1132  bool found = false;
1133  SHAPE_LINE_CHAIN bestBypass;
1134  int si, ei;
1135 
1136  for( int i=0; i< nStarts; i++ )
1137  {
1138  for( int j = 1; j < aCoupled.PointCount() - 1; j++ )
1139  {
1140  int delta = std::abs ( vStartIdx[i] - j );
1141 
1142  if( delta > 1 )
1143  {
1144  const VECTOR2I& vs = aCoupled.CPoint( vStartIdx[i] );
1145  SHAPE_LINE_CHAIN bypass = dir.BuildInitialTrace( vs, aCoupled.CPoint(j), dir.IsDiagonal() );
1146 
1147  int64_t coupledLength = aPair->CoupledLength( aRef, bypass );
1148 
1149  SHAPE_LINE_CHAIN newCoupled = aCoupled;
1150 
1151  si = vStartIdx[i];
1152  ei = j;
1153 
1154  if(si < ei)
1155  newCoupled.Replace( si, ei, bypass );
1156  else
1157  newCoupled.Replace( ei, si, bypass.Reverse() );
1158 
1159  if(coupledLength > bestLength && verifyDpBypass( aNode, aPair, aRefIsP, aRef, newCoupled) )
1160  {
1161  bestBypass = newCoupled;
1162  bestLength = coupledLength;
1163  found = true;
1164  }
1165  }
1166  }
1167  }
1168 
1169 
1170  if( found )
1171  aNewCoupled = bestBypass;
1172 
1173  return found;
1174 }
1175 
1176 
1177 bool checkDpColliding( NODE* aNode, DIFF_PAIR* aPair, bool aIsP, const SHAPE_LINE_CHAIN& aPath )
1178 {
1179  LINE tmp ( aIsP ? aPair->PLine() : aPair->NLine(), aPath );
1180 
1181  return static_cast<bool>( aNode->CheckColliding( &tmp ) );
1182 }
1183 
1184 
1185 bool OPTIMIZER::mergeDpStep( DIFF_PAIR* aPair, bool aTryP, int step )
1186 {
1187  int n = 1;
1188 
1189  SHAPE_LINE_CHAIN currentPath = aTryP ? aPair->CP() : aPair->CN();
1190  SHAPE_LINE_CHAIN coupledPath = aTryP ? aPair->CN() : aPair->CP();
1191 
1192  int n_segs = currentPath.SegmentCount() - 1;
1193 
1194  int64_t clenPre = aPair->CoupledLength( currentPath, coupledPath );
1195  int64_t budget = clenPre / 10; // fixme: come up with somethig more intelligent here...
1196 
1197  while( n < n_segs - step )
1198  {
1199  const SEG s1 = currentPath.CSegment( n );
1200  const SEG s2 = currentPath.CSegment( n + step );
1201 
1202  DIRECTION_45 dir1( s1 );
1203  DIRECTION_45 dir2( s2 );
1204 
1205  if( dir1.IsObtuse( dir2 ) )
1206  {
1207  SHAPE_LINE_CHAIN bypass = DIRECTION_45().BuildInitialTrace( s1.A, s2.B, dir1.IsDiagonal() );
1208  SHAPE_LINE_CHAIN newRef;
1209  SHAPE_LINE_CHAIN newCoup;
1210  int64_t deltaCoupled = -1, deltaUni = -1;
1211 
1212  newRef = currentPath;
1213  newRef.Replace( s1.Index(), s2.Index(), bypass );
1214 
1215  deltaUni = aPair->CoupledLength ( newRef, coupledPath ) - clenPre + budget;
1216 
1217  if ( coupledBypass( m_world, aPair, aTryP, newRef, bypass, coupledPath, newCoup ) )
1218  {
1219  deltaCoupled = aPair->CoupledLength( newRef, newCoup ) - clenPre + budget;
1220 
1221  if( deltaCoupled >= 0 )
1222  {
1223  newRef.Simplify();
1224  newCoup.Simplify();
1225 
1226  aPair->SetShape( newRef, newCoup, !aTryP );
1227  return true;
1228  }
1229  }
1230  else if( deltaUni >= 0 && verifyDpBypass ( m_world, aPair, aTryP, newRef, coupledPath ) )
1231  {
1232  newRef.Simplify();
1233  coupledPath.Simplify();
1234 
1235  aPair->SetShape( newRef, coupledPath, !aTryP );
1236  return true;
1237  }
1238  }
1239 
1240  n++;
1241  }
1242 
1243  return false;
1244 }
1245 
1246 
1248 {
1249  int step_p = aPair->CP().SegmentCount() - 2;
1250  int step_n = aPair->CN().SegmentCount() - 2;
1251 
1252  while( 1 )
1253  {
1254  int n_segs_p = aPair->CP().SegmentCount();
1255  int n_segs_n = aPair->CN().SegmentCount();
1256 
1257  int max_step_p = n_segs_p - 2;
1258  int max_step_n = n_segs_n - 2;
1259 
1260  if( step_p > max_step_p )
1261  step_p = max_step_p;
1262 
1263  if( step_n > max_step_n )
1264  step_n = max_step_n;
1265 
1266  if( step_p < 1 && step_n < 1)
1267  break;
1268 
1269  bool found_anything_p = false;
1270  bool found_anything_n = false;
1271 
1272  if( step_p > 1 )
1273  found_anything_p = mergeDpStep( aPair, true, step_p );
1274 
1275  if( step_n > 1 )
1276  found_anything_n = mergeDpStep( aPair, false, step_n );
1277 
1278  if( !found_anything_n && !found_anything_p )
1279  {
1280  step_n--;
1281  step_p--;
1282  }
1283  }
1284  return true;
1285 }
1286 
1287 
1289 {
1290  return mergeDpSegments( aPair );
1291 }
1292 
1293 static int64_t shovedArea( const SHAPE_LINE_CHAIN& aOld, const SHAPE_LINE_CHAIN& aNew )
1294 {
1295  int64_t area = 0;
1296  const int oc = aOld.PointCount();
1297  const int nc = aNew.PointCount();
1298  const int total = oc + nc;
1299 
1300  for(int i = 0; i < total; i++)
1301  {
1302  int i_next = (i + 1 == total ? 0 : i + 1);
1303 
1304  const VECTOR2I &v0 = ( i < oc ? aOld.CPoint(i) : aNew.CPoint( nc - 1 - (i - oc) ) );
1305  const VECTOR2I &v1 = ( i_next < oc ? aOld.CPoint ( i_next ) : aNew.CPoint( nc - 1 - (i_next - oc) ) );
1306  area += -(int64_t) v0.y * v1.x + (int64_t) v0.x * v1.y;
1307  }
1308 
1309  return std::abs(area / 2);
1310 }
1311 
1312 bool tightenSegment( bool dir, NODE *aNode, const LINE& cur,
1313  const SHAPE_LINE_CHAIN& in, SHAPE_LINE_CHAIN& out )
1314 {
1315  SEG a = in.CSegment(0);
1316  SEG center = in.CSegment(1);
1317  SEG b = in.CSegment(2);
1318 
1319  DIRECTION_45 dirA ( a );
1320  DIRECTION_45 dirCenter ( center );
1321  DIRECTION_45 dirB ( b );
1322 
1323  if (!dirA.IsObtuse( dirCenter) || !dirCenter.IsObtuse(dirB))
1324  return false;
1325 
1326  //VECTOR2I perp = (center.B - center.A).Perpendicular();
1327  VECTOR2I guideA, guideB ;
1328 
1329  SEG guide;
1330  int initial;
1331 
1332  //auto dbg = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
1333  if ( dirA.Angle ( dirB ) != DIRECTION_45::ANG_RIGHT )
1334  return false;
1335 
1336  {
1337  //auto rC = *a.IntersectLines( b );
1338  // dbg->AddSegment ( SEG( center.A, rC ), 1 );
1339  // dbg->AddSegment ( SEG( center.B, rC ), 2 );
1340  /*
1341  auto perp = dirCenter.Left().Left();
1342 
1343  SEG sperp ( center.A, center.A + perp.ToVector() );
1344 
1345  auto vpc = sperp.LineProject( rC );
1346  auto vpa = sperp.LineProject( a.A );
1347  auto vpb = sperp.LineProject( b.B );
1348 
1349  auto da = (vpc - vpa).EuclideanNorm();
1350  auto db = (vpc - vpb).EuclideanNorm();
1351 
1352  auto vp = (da < db) ? vpa : vpb;
1353  dbg->AddSegment ( SEG( vpc, vp ), 5 );
1354 
1355 
1356  guide = SEG ( vpc, vp );*/
1357 
1358 
1359  }
1360 
1361  int da = a.Length();
1362  int db = b.Length();
1363 
1364  if ( da < db )
1365  guide = a;
1366  else
1367  guide = b;
1368 
1369 
1370  initial = guide.Length();
1371 
1372  int step = initial;
1373  int current = step;
1374  SHAPE_LINE_CHAIN snew;
1375 
1376  while (step > 1)
1377  {
1378  LINE l ( cur );
1379 
1380  snew.Clear();
1381  snew.Append( a.A );
1382  snew.Append( a.B + (a.A - a.B).Resize( current ) );
1383  snew.Append( b.A + (b.B - b.A).Resize( current ) );
1384  snew.Append( b.B );
1385 
1386  step /= 2;
1387 
1388  l.SetShape(snew);
1389  if( aNode->CheckColliding(&l) )
1390  {
1391  current -= step;
1392  } else if ( current + step >= initial ) {
1393  current = initial;
1394  } else {
1395  current += step;
1396  }
1397 
1398 
1399  //dbg->AddSegment ( SEG( center.A , a.LineProject( center.A + gr ) ), 3 );
1400  //dbg->AddSegment ( SEG( center.A , center.A + guideA ), 3 );
1401  //dbg->AddSegment ( SEG( center.B , center.B + guideB ), 4 );
1402 
1403 
1404  if ( current == initial )
1405  break;
1406 
1407 
1408  }
1409  out = snew;
1410 
1411  //dbg->AddLine ( snew, 3, 100000 );
1412 
1413  return true;
1414 }
1415 
1416 void Tighten( NODE *aNode, SHAPE_LINE_CHAIN& aOldLine, LINE& aNewLine, LINE& aOptimized )
1417 {
1418  LINE tmp;
1419 
1420 
1421 
1422  if ( aNewLine.SegmentCount() < 3 )
1423  return;
1424 
1425  SHAPE_LINE_CHAIN current ( aNewLine.CLine() );
1426 
1427  for (int step = 0; step < 3; step++)
1428  {
1429  current.Simplify();
1430 
1431  for ( int i = 0; i <= current.SegmentCount() - 3; i++)
1432  {
1433  SHAPE_LINE_CHAIN l_in, l_out;
1434 
1435  l_in = current.Slice(i, i+3);
1436  for (int dir = 0; dir < 1; dir++)
1437  {
1438  if( tightenSegment( dir ? true : false, aNode, aNewLine, l_in, l_out ) )
1439  {
1440  SHAPE_LINE_CHAIN opt = current;
1441  opt.Replace(i, i+3, l_out);
1442  auto optArea = std::abs(shovedArea( aOldLine, opt ));
1443  auto prevArea = std::abs(shovedArea( aOldLine, current ));
1444 
1445  if( optArea < prevArea )
1446  {
1447  current = opt;
1448  }
1449  break;
1450  }
1451 
1452  }
1453  }
1454 
1455  }
1456 
1457  aOptimized = LINE(aNewLine, current);
1458 
1459  //auto dbg = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
1460  //dbg->AddLine ( current, 4, 100000 );
1461 }
1462 
1463 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:133
int Length() const
Function Length()
Definition: seg.h:319
const SHAPE_LINE_CHAIN & CLine() const
Const accessor to the underlying shape
Definition: pns_line.h:149
static bool pointInside2(const SHAPE_LINE_CHAIN &aL, const VECTOR2I &aP)
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:337
const SHAPE * Shape() const override
Function Shape()
Definition: pns_solid.h:74
long long int Length() const
Function Length()
void CacheStaticItem(ITEM *aItem)
bool isArc(size_t aSegment) const
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:207
SHAPE_SIMPLE.
Definition: shape_simple.h:43
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
std::vector< INTERSECTION > INTERSECTIONS
virtual int Layer() const
Definition: pns_item.h:155
BREAKOUT_LIST circleBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
VECTOR2I Offset() const
Definition: pns_solid.h:122
NODE.
Definition: pns_node.h:145
void CacheRemove(ITEM *aItem)
void removeCachedSegments(LINE *aLine, int aStartVertex=0, int aEndVertex=-1)
int GetRadius() const
Definition: shape_circle.h:94
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:155
int Mask() const
Definition: direction45.h:287
const SEG CSegment(int aIdx) const
Returns the aIdx-th segment of the line
Definition: pns_line.h:179
void Replace(LINE &aOldLine, LINE &aNewLine)
JOINT_CACHE(NODE *aWorld, int aLayer, int aMaxJoints)
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Function Slice()
int Width() const
const SHAPE_LINE_CHAIN & CN() const
bool mergeStep(LINE *aLine, SHAPE_LINE_CHAIN &aCurrentLine, int step)
virtual bool Check(int aVertex1, int aVertex2, LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
ITEM * findPadOrVia(int aLayer, int aNet, const VECTOR2I &aP) const
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:74
int QueryJoints(const BOX2I &aBox, std::vector< JOINT * > &aJoints, int aLayerMask=-1, int aKindMask=ITEM::ANY_T)
Definition: pns_node.cpp:1408
double CoupledLength() const
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Function IntersectLines()
Definition: seg.h:191
const VECTOR2I GetCenter() const
Definition: shape_circle.h:99
BREAKOUT_LIST rectBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
const BOX2I BBox(int aClearance=0) const override
Function BBox()
Definition: shape_simple.h:82
void Tighten(NODE *aNode, SHAPE_LINE_CHAIN &aOldLine, LINE &aNewLine, LINE &aOptimized)
bool runSmartPads(LINE *aLine)
VECTOR2< int > VECTOR2I
Definition: vector2d.h:594
bool mergeFull(LINE *aLine)
int PointCount() const
Function PointCount()
const RANGED_NUM< int > GapConstraint() const
const SHAPE * Shape() const override
Function Shape()
Definition: pns_via.h:143
bool checkConstraints(int aVertex1, int aVertex2, LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement)
int PointCount() const
Returns the number of points in the line
Definition: pns_line.h:161
bool EndsWithVia() const
Definition: pns_line.h:234
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
int Start() const
Definition: pns_layerset.h:83
const VECTOR2I & CPoint(int aIdx) const
Returns the aIdx-th point of the line
Definition: pns_line.h:173
void SetCollisionMask(int aMask)
const VECTOR2I GetSize() const
Function GetSize()
Definition: shape_rect.h:121
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:130
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
AngleType Angle(const DIRECTION_45 &aOther) const
Function Angle() Returns the type of angle between directions (this) and aOther.
Definition: direction45.h:153
const VECTOR2I & CPoint(int aIndex) const
Function Point()
void AddConstraint(OPT_CONSTRAINT *aConstraint)
void SetClosed(bool aClosed)
Function SetClosed()
JOINT.
Definition: pns_joint.h:43
static int64_t shovedArea(const SHAPE_LINE_CHAIN &aOld, const SHAPE_LINE_CHAIN &aNew)
BREAKOUT_LIST customBreakouts(int aWidth, const ITEM *aItem, bool aPermitDiagonal) const
VECTOR2I LineProject(const VECTOR2I &aP) const
Function LineProject()
Definition: seg.h:362
virtual bool Check(int aVertex1, int aVertex2, LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
int GetClearance(const ITEM *aA, const ITEM *aB) const
Returns the expected clearance between items a and b.
Definition: pns_node.cpp:97
const BOX2I BBox(int aClearance=0) const override
Function BBox()
#define NULL
bool IsClosed() const override
Function IsClosed()
bool ApproxParallel(const SEG &aSeg) const
Definition: seg.h:265
virtual const SHAPE * Shape() const
Function Shape()
Definition: pns_item.h:214
int Net() const
Definition: pns_item.h:149
DIRECTION_45.
Definition: direction45.h:37
const VECTOR2I & GetPosition() const
Function GetPosition()
Definition: shape_rect.h:111
bool Contains(const Vec &aPoint) const
Function Contains.
Definition: box2.h:151
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I aV=VECTOR2I(0, 0))
a quick shortcut to optmize a line without creating and setting up an optimizer
bool mergeDpSegments(DIFF_PAIR *aPair)
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)
bool IsDiagonal() const
Function IsDiagonal() Returns true if the direction is diagonal (e.g.
Definition: direction45.h:186
const SHAPE_LINE_CHAIN & Vertices() const
Function Vertices()
Definition: shape_simple.h:133
bool mergeObtuse(LINE *aLine)
SHAPE.
Definition: shape.h:120
const LINKED_ITEMS & LinkList() const
Definition: pns_joint.h:196
virtual bool Check(int aVertex1, int aVertex2, LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
static DEBUG_DECORATOR * g_dbg
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:45
CachedItemTags m_cacheTags
std::vector< OPT_CONSTRAINT * > m_constraints
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:1031
SHAPE_LINE_CHAIN & Line()
Modifiable accessor to the underlying shape
Definition: pns_line.h:143
bool tightenSegment(bool dir, NODE *aNode, const LINE &cur, const SHAPE_LINE_CHAIN &in, SHAPE_LINE_CHAIN &out)
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false, int aMaxRadius=0) const
Function BuildInitialTrace()
Definition: seg.h:39
OPTIMIZER(NODE *aWorld)
Optimizer.
DIFF_PAIR.
void cacheAdd(ITEM *aItem, bool aIsStatic)
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
bool operator()(ITEM *aOtherItem)
const SHAPE_LINE_CHAIN & CP() const
VECTOR2< T > Resize(T aNewLength) const
Function Resize returns a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:392
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)
const SEG CSegment(int aIndex) const
Function CSegment()
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr) const
Function Collide()
Definition: shape.h:172
bool fanoutCleanup(LINE *aLine)
SHAPE_LINE_CHAIN.
SHAPE_RECT ApproximateSegmentAsRect(const SHAPE_SEGMENT &aSeg)
Definition: pns_utils.cpp:216
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:427
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:133
bool checkColliding(ITEM *aItem, bool aUpdateCache=true)
void Add(LINE &aLine)
int Width() const
Returns line width
Definition: pns_line.h:192
static int CornerCost(const SEG &aA, const SEG &aB)
Cost Estimator Methods.
PnsKind Kind() const
Function Kind()
Definition: pns_item.h:123
OPTIMIZER.
Definition: pns_optimizer.h:95
void Clear()
Function Clear() Removes all points from the line chain.
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
bool CheckInside(const VECTOR2I &aPos) const
void SetEffortLevel(int aEffort)
virtual bool Check(int aVertex1, int aVertex2, LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
Definition: shape.h:42
std::vector< SHAPE_LINE_CHAIN > BREAKOUT_LIST
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Function Replace()
COST_ESTIMATOR.
Definition: pns_optimizer.h:48
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:46
SHAPE_TYPE Type() const
Function Type()
Definition: shape.h:96
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:234
void ClearCache(bool aStaticOnly=false)
static ROUTER * GetInstance()
Definition: pns_router.cpp:85
const LAYER_RANGE & Layers() const
Definition: pns_item.h:151
bool IsObtuse(const DIRECTION_45 &aOther) const
Function IsObtuse()
Definition: direction45.h:176
bool IsBetter(COST_ESTIMATOR &aOther, double aLengthTolerance, double aCornerTollerace) const
axis-aligned rectangle
Definition: shape.h:43
int CountCorners(int aAngles) const
Returns the number of corners of angles specified by mask aAngles.
Definition: pns_line.cpp:134
VECTOR2I B
Definition: seg.h:48