KiCad PCB EDA Suite
pns_line.cpp
Go to the documentation of this file.
1 /*
2  * KiRouter - a push-and-(sometimes-)shove PCB router
3  *
4  * Copyright (C) 2013-2017 CERN
5  * Copyright (C) 2016-2020 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 <core/optional.h>
23 
24 #include <math/box2.h>
25 #include <math/vector2d.h>
26 
27 #include "pns_line.h"
28 #include "pns_node.h"
29 #include "pns_via.h"
30 #include "pns_utils.h"
31 #include "pns_router.h"
32 
33 #include <geometry/shape_rect.h>
34 
35 namespace PNS {
36 
37 LINE::LINE( const LINE& aOther )
38  : ITEM( aOther ),
39  m_line( aOther.m_line ),
40  m_width( aOther.m_width ),
41  m_snapThreshhold( aOther.m_snapThreshhold )
42 {
43  m_net = aOther.m_net;
44  m_movable = aOther.m_movable;
45  m_layers = aOther.m_layers;
46  m_via = aOther.m_via;
47  m_hasVia = aOther.m_hasVia;
48  m_marker = aOther.m_marker;
49  m_rank = aOther.m_rank;
50 
51  copyLinks( &aOther );
52 }
53 
54 
56 {
57 }
58 
59 
60 LINE& LINE::operator=( const LINE& aOther )
61 {
62  m_line = aOther.m_line;
63  m_width = aOther.m_width;
64  m_net = aOther.m_net;
65  m_movable = aOther.m_movable;
66  m_layers = aOther.m_layers;
67  m_via = aOther.m_via;
68  m_hasVia = aOther.m_hasVia;
69  m_marker = aOther.m_marker;
70  m_rank = aOther.m_rank;
71  m_owner = aOther.m_owner;
73 
74  copyLinks( &aOther );
75 
76  return *this;
77 }
78 
79 
80 LINE* LINE::Clone() const
81 {
82  LINE* l = new LINE( *this );
83 
84  return l;
85 }
86 
87 
88 void LINE::Mark( int aMarker )
89 {
90  m_marker = aMarker;
91 
92  for( auto s : m_segmentRefs )
93  s->Mark( aMarker );
94 
95 }
96 
97 
98 void LINE::Unmark( int aMarker )
99 {
100  for( auto s : m_segmentRefs )
101  s->Unmark( aMarker );
102 
103  m_marker = 0;
104 }
105 
106 
107 int LINE::Marker() const
108 {
109  int marker = m_marker;
110 
111  for( auto s : m_segmentRefs )
112  {
113  marker |= s->Marker();
114  }
115 
116  return marker;
117 }
118 
119 
120 void LINE::copyLinks( const LINE* aParent )
121 {
122  m_segmentRefs = aParent->m_segmentRefs;
123 }
124 
125 
127 {
128  SEGMENT* s = new SEGMENT;
129 
130  s->m_seg = m_seg;
131  s->m_net = m_net;
132  s->m_layers = m_layers;
133  s->m_marker = m_marker;
134  s->m_rank = m_rank;
135 
136  return s;
137 }
138 
139 
140 int LINE::CountCorners( int aAngles ) const
141 {
142  int count = 0;
143 
144  for( int i = 0; i < m_line.SegmentCount() - 1; i++ )
145  {
146  const SEG seg1 = m_line.CSegment( i );
147  const SEG seg2 = m_line.CSegment( i + 1 );
148 
149  const DIRECTION_45 dir1( seg1 );
150  const DIRECTION_45 dir2( seg2 );
151 
152  DIRECTION_45::AngleType a = dir1.Angle( dir2 );
153 
154  if( a & aAngles )
155  count++;
156  }
157 
158  return count;
159 }
160 
161 
163  SHAPE_LINE_CHAIN& aWalk, SHAPE_LINE_CHAIN& aPost, bool aCw ) const
164 {
165  const SHAPE_LINE_CHAIN& line( CLine() );
166 
167  if( line.SegmentCount() < 1 )
168  return false;
169 
170  const auto pFirst = line.CPoint(0);
171  const auto pLast = line.CPoint(-1);
172 
173  if( aObstacle.PointInside( line.CPoint( 0 ) ) || aObstacle.PointInside( line.CPoint( -1 ) ) )
174  {
175  return false;
176  }
177 
179 
180  line.Intersect( aObstacle, ips );
181 
182 
183  /* for( auto p : ips )
184  {
185  printf("gif %d %d our %d their %d\n", p.p.x, p.p.y, p.our.Index(), p.their.Index() );
186  }*/
187 
188  for( int i = 0; i < line.SegmentCount(); i++ )
189  {
190  const SEG& a = line.CSegment(i);
191  bool over = false;
192 
193 
194  for( int j = 0; j < aObstacle.SegmentCount(); j++ )
195  {
196  const SEG& so = aObstacle.CSegment(j);
197  if( so.Contains( a ) )
198  {
199  // printf("discard seg %d\n", i );
200  over = true;
201  break;
202  }
203  }
204 
205  if(over)
206  continue;
207 
208 
209  bool a_in = aObstacle.PointInside( a.A );// && !aObstacle.PointOnEdge( a.A );
210  bool b_in = aObstacle.PointInside( a.B );// && !aObstacle.PointOnEdge( a.B );
211 
212 // printf("i %d a %d %d %d %d [%d %d] a_in %d b_in %d\n", i, a.A.x, a.A.y, a.B.x, a.B.y, a.A.x- a.B.x, a.A.y - a.B.y, !!a_in, !!b_in );
213 
214 
215  if( a_in ^ b_in ) // segment crosses hull boundary
216  {
217  for( int j = 0; j < aObstacle.SegmentCount(); j++ )
218  {
219  OPT_VECTOR2I p;
220 
221  bool cont_a = aObstacle.CSegment(j).Contains( a.A );
222  bool cont_b = aObstacle.CSegment(j).Contains( a.B );
223 
224  if(cont_a)
225  p = a.A;
226  else if (cont_b)
227  p = a.B;
228  else
229  p = aObstacle.CSegment(j).Intersect( a );
230 
231  //printf("- cont_a %d cont_b %d p %d\n", !!cont_a, !!cont_b, p ? 1 : 0 );
232 
233 
234  if ( p )
235  {
237  ip.our = a;
238  ip.their = aObstacle.CSegment(j);
239  ip.p = *p;
240  ips.push_back(ip);
241  //printf("chb %d %d\n", p->x, p->y);
242  }
243  }
244  }
245  else if ( !a_in && !b_in )
246  {
247  int min_idx = INT_MAX;
248  int max_idx = INT_MIN;
249 
250  for( int j = 0; j < aObstacle.SegmentCount(); j++ )
251  {
252  const SEG& os = aObstacle.CSegment(j);
253 
254  if (os.Intersect(a))
255  {
256  min_idx = std::min(min_idx, j);
257  max_idx = std::max(max_idx, j);
258  }
259 
260  }
261 
262  if (min_idx != max_idx && min_idx != INT_MAX )
263  {
264  // genuine interesection found
265  for( int j = 0; j < aObstacle.SegmentCount(); j++ )
266  {
267  const SEG& os = aObstacle.CSegment(j);
268 
269  auto p = os.Intersect(a);
270  if(p)
271  {
273  ip.our = a;
274  ip.their = aObstacle.CSegment(j);
275  ip.p = *p;
276  ips.push_back(ip);
277  // printf("gif %d %d\n", p->x, p->y);
278  }
279 
280  }
281  }
282  }
283  }
284 
285  auto eFirst = aObstacle.EdgeContainingPoint( pFirst );
286  auto eLast = aObstacle.EdgeContainingPoint( pLast );
287 
288  aWalk.Clear();
289  aPost.Clear();
290 
291  int nearest_dist = INT_MAX;
292  int farthest_dist = 0;
293 
294  SHAPE_LINE_CHAIN::INTERSECTION nearest, farthest;
296 
297  if( eFirst >= 0 )
298  {
299  is.our = line.CSegment(0);
300  is.their = aObstacle.CSegment( eFirst );
301  is.p = pFirst;
302  ips.push_back(is);
303  }
304 
305  if ( eLast >= 0 )
306  {
307  is.our = line.CSegment(-1);
308  is.their = aObstacle.CSegment( eLast );
309  is.p = pLast;
310  ips.push_back(is);
311  }
312 
313  for( int i = 0; i < (int) ips.size(); i++ )
314  {
315  const VECTOR2I p = ips[i].p;
316  int dist = line.PathLength( p );
317 
318  if( dist < 0 )
319  return false;
320 
321  if( dist <= nearest_dist )
322  {
323  nearest_dist = dist;
324  nearest = ips[i];
325  }
326 
327  if( dist >= farthest_dist )
328  {
329  farthest_dist = dist;
330  farthest = ips[i];
331  }
332  }
333 
334  if( ips.size() <= 1 || nearest.p == farthest.p )
335  {
336  aPre = line;
337  return true;
338  }
339 
340  aPre = line.Slice( 0, nearest.our.Index() );
341  aPre.Append( nearest.p );
342  aPre.Simplify();
343 
344  aWalk.Clear();
345  aWalk.SetClosed( false );
346  aWalk.Append( nearest.p );
347 
348  assert( nearest.their.Index() >= 0 );
349  assert( farthest.their.Index() >= 0 );
350 
351  assert( nearest_dist <= farthest_dist );
352 
353  aObstacle.Split( nearest.p );
354  aObstacle.Split( farthest.p );
355 
356  int i_first = aObstacle.Find( nearest.p );
357  int i_last = aObstacle.Find( farthest.p );
358 
359  int i = i_first;
360 
361  if( i_first < 0 || i_last < 0 )
362  return false;
363 
364  while( i != i_last )
365  {
366  aWalk.Append( aObstacle.CPoint( i ) );
367  i += ( aCw ? 1 : -1 );
368 
369  if( i < 0 )
370  i = aObstacle.PointCount() - 1;
371  else if( i == aObstacle.PointCount() )
372  i = 0;
373  }
374 
375  aWalk.Append( farthest.p );
376  aWalk.Simplify();
377 
378  aPost.Clear();
379  aPost.Append( farthest.p );
380  aPost.Append( line.Slice( farthest.our.Index() + 1, -1 ) );
381  aPost.Simplify();
382 
383  return true;
384 }
385 
386 
387 bool LINE::Walkaround( const SHAPE_LINE_CHAIN& aObstacle, SHAPE_LINE_CHAIN& aPath, bool aCw ) const
388 {
389  SHAPE_LINE_CHAIN walk, post;
390 
391  if( ! Walkaround( aObstacle, aPath, walk, post, aCw ) )
392  return false;
393 
394  aPath.Append( walk );
395  aPath.Append( post );
396  aPath.Simplify();
397 
398  return true;
399 }
400 
401 
402 const SHAPE_LINE_CHAIN SEGMENT::Hull( int aClearance, int aWalkaroundThickness ) const
403 {
404  return SegmentHull( m_seg, aClearance, aWalkaroundThickness );
405 }
406 
407 
408 bool LINE::Is45Degree() const
409 {
410  for( int i = 0; i < m_line.SegmentCount(); i++ )
411  {
412  const SEG& s = m_line.CSegment( i );
413 
414  if( m_line.isArc( i ) )
415  continue;
416 
417  if( s.Length() < 10 )
418  continue;
419 
420  double angle = 180.0 / M_PI *
421  atan2( (double) s.B.y - (double) s.A.y,
422  (double) s.B.x - (double) s.A.x );
423 
424  if( angle < 0 )
425  angle += 360.0;
426 
427  double angle_a = fabs( fmod( angle, 45.0 ) );
428 
429  if( angle_a > 1.0 && angle_a < 44.0 )
430  return false;
431  }
432 
433  return true;
434 }
435 
436 
437 const LINE LINE::ClipToNearestObstacle( NODE* aNode ) const
438 {
439  const int IterationLimit = 5;
440  int i;
441  LINE l( *this );
442 
443  for( i = 0; i < IterationLimit; i++ )
444  {
445  NODE::OPT_OBSTACLE obs = aNode->NearestObstacle( &l );
446 
447  if( obs )
448  {
449  l.RemoveVia();
450  int p = l.Line().Split( obs->m_ipFirst );
451  l.Line().Remove( p + 1, -1 );
452  } else
453  break;
454  }
455 
456  if( i == IterationLimit )
457  l.Line().Clear();
458 
459  return l;
460 }
461 
462 
463 void LINE::ShowLinks() const
464 {
465  if( !IsLinked() )
466  {
467  wxLogTrace( "PNS", "line %p: no links", this );
468  return;
469  }
470 
471  wxLogTrace( "PNS", "line %p: %d linked segs", this, (int) m_segmentRefs.size() );
472 
473  for( int i = 0; i < (int) m_segmentRefs.size(); i++ )
474  wxLogTrace( "PNS", "seg %d: %p\n", i, m_segmentRefs[i] );
475 }
476 
477 
479 {
480  OPT<SHAPE_LINE_CHAIN> picked;
481  int i;
482  int d = 2;
483 
484  if( aOrigin.SegmentCount() == 1)
485  {
486  DIRECTION_45 dir( aOrigin.CPoint( 0 ) - aOrigin.CPoint( 1 ) );
487 
488  return DIRECTION_45().BuildInitialTrace( aOrigin.CPoint( 0 ), aP, dir.IsDiagonal() );
489  }
490 
491  if( aOrigin.CSegment( -1 ).Length() > 100000 * 30 ) // fixme: constant/parameter?
492  d = 1;
493 
494  for( i = aOrigin.SegmentCount() - d; i >= 0; i-- )
495  {
496  DIRECTION_45 d_start( aOrigin.CSegment( i ) );
497  VECTOR2I p_start = aOrigin.CPoint( i );
498  SHAPE_LINE_CHAIN paths[2];
499  DIRECTION_45 dirs[2];
500  DIRECTION_45 d_prev = ( i > 0 ? DIRECTION_45( aOrigin.CSegment( i-1 ) ) : DIRECTION_45() );
501  int dirCount = 0;
502 
503  for( int j = 0; j < 2; j++ )
504  {
505  paths[j] = d_start.BuildInitialTrace( p_start, aP, j );
506 
507  if( paths[j].SegmentCount() < 1 )
508  continue;
509 
510  assert( dirCount < int( sizeof( dirs ) / sizeof( dirs[0] ) ) );
511 
512  dirs[dirCount] = DIRECTION_45( paths[j].CSegment( 0 ) );
513  ++dirCount;
514  }
515 
516  for( int j = 0; j < dirCount; j++ )
517  {
518  if( dirs[j] == d_start )
519  {
520  picked = paths[j];
521  break;
522  }
523  }
524 
525  if( picked )
526  break;
527 
528  for( int j = 0; j < dirCount; j++ )
529  {
530  if( dirs[j].IsObtuse( d_prev ) )
531  {
532  picked = paths[j];
533  break;
534  }
535  }
536 
537  if( picked )
538  break;
539  }
540 
541  if( picked )
542  {
543  SHAPE_LINE_CHAIN path = aOrigin.Slice( 0, i );
544  path.Append( *picked );
545 
546  return path;
547  }
548 
549  DIRECTION_45 dir( aOrigin.CPoint( -1 ) - aOrigin.CPoint( -2 ) );
550 
551  return DIRECTION_45().BuildInitialTrace( aOrigin.CPoint( 0 ), aP, dir.IsDiagonal() );
552 }
553 
554 void LINE::dragCorner45( const VECTOR2I& aP, int aIndex )
555 {
556  SHAPE_LINE_CHAIN path;
557 
558  VECTOR2I snapped = snapDraggedCorner( m_line, aP, aIndex );
559 
560  if( aIndex == 0 )
561  path = dragCornerInternal( m_line.Reverse(), snapped ).Reverse();
562  else if( aIndex == m_line.SegmentCount() )
563  path = dragCornerInternal( m_line, snapped );
564  else
565  {
566  // fixme: awkward behaviour for "outwards" drags
567  path = dragCornerInternal( m_line.Slice( 0, aIndex ), snapped );
568  SHAPE_LINE_CHAIN path_rev =
569  dragCornerInternal( m_line.Slice( aIndex, -1 ).Reverse(), snapped ).Reverse();
570  path.Append( path_rev );
571  }
572 
573  path.Simplify();
574  m_line = path;
575 }
576 
577 void LINE::dragCornerFree( const VECTOR2I& aP, int aIndex )
578 {
579  m_line.SetPoint( aIndex, aP );
580  m_line.Simplify();
581 }
582 
583 void LINE::DragCorner( const VECTOR2I& aP, int aIndex, bool aFreeAngle )
584 {
585  if( aFreeAngle )
586  {
587  dragCornerFree( aP, aIndex );
588  }
589  else
590  {
591  dragCorner45( aP, aIndex );
592  }
593 }
594 
595 void LINE::DragSegment( const VECTOR2I& aP, int aIndex, bool aFreeAngle )
596 {
597  if( aFreeAngle )
598  {
599  assert( false );
600  }
601  else
602  {
603  dragSegment45( aP, aIndex );
604  }
605 }
606 
608  const SHAPE_LINE_CHAIN& aPath, const VECTOR2I& aP, int aIndex ) const
609 {
610  int s_start = std::max( aIndex - 2, 0 );
611  int s_end = std::min( aIndex + 2, aPath.SegmentCount() - 1 );
612 
613  int i, j;
614  int best_dist = INT_MAX;
615  VECTOR2I best_snap = aP;
616 
617  if( m_snapThreshhold <= 0 )
618  return aP;
619 
620  for( i = s_start; i <= s_end; i++ )
621  {
622  const SEG& a = aPath.CSegment( i );
623 
624  for( j = s_start; j < i; j++ )
625  {
626  const SEG& b = aPath.CSegment( j );
627 
628  if( !( DIRECTION_45( a ).IsObtuse( DIRECTION_45( b ) ) ) )
629  continue;
630 
631  OPT_VECTOR2I ip = a.IntersectLines( b );
632 
633  if( ip )
634  {
635  int dist = ( *ip - aP ).EuclideanNorm();
636 
637  if( dist < m_snapThreshhold && dist < best_dist )
638  {
639  best_dist = dist;
640  best_snap = *ip;
641  }
642  }
643  }
644  }
645 
646  return best_snap;
647 }
648 
650  const SHAPE_LINE_CHAIN& aPath, const VECTOR2I& aP, int aIndex ) const
651 {
652  VECTOR2I snap_p[2];
653  DIRECTION_45 dragDir( aPath.CSegment( aIndex ) );
654  int snap_d[2] = { -1, -1 };
655 
656  if( m_snapThreshhold == 0 )
657  return aP;
658 
659  if( aIndex >= 2 )
660  {
661  SEG s = aPath.CSegment( aIndex - 2 );
662 
663  if( DIRECTION_45( s ) == dragDir )
664  snap_d[0] = s.LineDistance( aP );
665 
666  snap_p[0] = s.A;
667  }
668 
669  if( aIndex < aPath.SegmentCount() - 2 )
670  {
671  SEG s = aPath.CSegment( aIndex + 2 );
672 
673  if( DIRECTION_45( s ) == dragDir )
674  snap_d[1] = s.LineDistance( aP );
675 
676  snap_p[1] = s.A;
677  }
678 
679  VECTOR2I best = aP;
680  int minDist = INT_MAX;
681 
682  for( int i = 0; i < 2; i++ )
683  {
684  if( snap_d[i] >= 0 && snap_d[i] < minDist && snap_d[i] <= m_snapThreshhold )
685  {
686  minDist = snap_d[i];
687  best = snap_p[i];
688  }
689  }
690 
691  return best;
692 }
693 
694 void LINE::dragSegment45( const VECTOR2I& aP, int aIndex )
695 {
696  SHAPE_LINE_CHAIN path( m_line );
697  VECTOR2I target( aP );
698 
699  SEG guideA[2], guideB[2];
700  int index = aIndex;
701 
702  target = snapToNeighbourSegments( path, aP, aIndex );
703 
704  if( index == 0 )
705  {
706  path.Insert( 0, path.CPoint( 0 ) );
707  index++;
708  }
709 
710  if( index == path.SegmentCount() - 1 )
711  {
712  path.Insert( path.PointCount() - 1, path.CPoint( -1 ) );
713  }
714 
715  SEG dragged = path.CSegment( index );
716  DIRECTION_45 drag_dir( dragged );
717 
718  SEG s_prev = path.CSegment( index - 1 );
719  SEG s_next = path.CSegment( index + 1 );
720 
721  DIRECTION_45 dir_prev( s_prev );
722  DIRECTION_45 dir_next( s_next );
723 
724  if( dir_prev == drag_dir )
725  {
726  dir_prev = dir_prev.Left();
727  path.Insert( index, path.CPoint( index ) );
728  index++;
729  }
730 
731  if( dir_next == drag_dir )
732  {
733  dir_next = dir_next.Right();
734  path.Insert( index + 1, path.CPoint( index + 1 ) );
735  }
736 
737  s_prev = path.CSegment( index - 1 );
738  s_next = path.CSegment( index + 1 );
739  dragged = path.CSegment( index );
740 
741  if( aIndex == 0 )
742  {
743  guideA[0] = SEG( dragged.A, dragged.A + drag_dir.Right().ToVector() );
744  guideA[1] = SEG( dragged.A, dragged.A + drag_dir.Left().ToVector() );
745  }
746  else
747  {
748  if( dir_prev.Angle( drag_dir )
750  {
751  guideA[0] = SEG( s_prev.A, s_prev.A + drag_dir.Left().ToVector() );
752  guideA[1] = SEG( s_prev.A, s_prev.A + drag_dir.Right().ToVector() );
753  }
754  else
755  guideA[0] = guideA[1] = SEG( dragged.A, dragged.A + dir_prev.ToVector() );
756  }
757 
758  if( aIndex == m_line.SegmentCount() - 1 )
759  {
760  guideB[0] = SEG( dragged.B, dragged.B + drag_dir.Right().ToVector() );
761  guideB[1] = SEG( dragged.B, dragged.B + drag_dir.Left().ToVector() );
762  }
763  else
764  {
765  if( dir_next.Angle( drag_dir )
767  {
768  guideB[0] = SEG( s_next.B, s_next.B + drag_dir.Left().ToVector() );
769  guideB[1] = SEG( s_next.B, s_next.B + drag_dir.Right().ToVector() );
770  }
771  else
772  guideB[0] = guideB[1] = SEG( dragged.B, dragged.B + dir_next.ToVector() );
773  }
774 
775  SEG s_current( target, target + drag_dir.ToVector() );
776 
777  int best_len = INT_MAX;
778  SHAPE_LINE_CHAIN best;
779 
780  for( int i = 0; i < 2; i++ )
781  {
782  for( int j = 0; j < 2; j++ )
783  {
784  OPT_VECTOR2I ip1 = s_current.IntersectLines( guideA[i] );
785  OPT_VECTOR2I ip2 = s_current.IntersectLines( guideB[j] );
786 
787  SHAPE_LINE_CHAIN np;
788 
789  if( !ip1 || !ip2 )
790  continue;
791 
792  SEG s1( s_prev.A, *ip1 );
793  SEG s2( *ip1, *ip2 );
794  SEG s3( *ip2, s_next.B );
795 
796  OPT_VECTOR2I ip;
797 
798  if( ( ip = s1.Intersect( s_next ) ) )
799  {
800  np.Append( s1.A );
801  np.Append( *ip );
802  np.Append( s_next.B );
803  }
804  else if( ( ip = s3.Intersect( s_prev ) ) )
805  {
806  np.Append( s_prev.A );
807  np.Append( *ip );
808  np.Append( s3.B );
809  }
810  else if( ( ip = s1.Intersect( s3 ) ) )
811  {
812  np.Append( s_prev.A );
813  np.Append( *ip );
814  np.Append( s_next.B );
815  }
816  else
817  {
818  np.Append( s_prev.A );
819  np.Append( *ip1 );
820  np.Append( *ip2 );
821  np.Append( s_next.B );
822  }
823 
824  if( np.Length() < best_len )
825  {
826  best_len = np.Length();
827  best = np;
828  }
829  }
830  }
831 
832  if( m_line.PointCount() == 1 )
833  m_line = best;
834  else if( aIndex == 0 )
835  m_line.Replace( 0, 1, best );
836  else if( aIndex == m_line.SegmentCount() - 1 )
837  m_line.Replace( -2, -1, best );
838  else
839  m_line.Replace( aIndex, aIndex + 1, best );
840 
841  m_line.Simplify();
842 }
843 
844 
845 bool LINE::CompareGeometry( const LINE& aOther )
846 {
847  return m_line.CompareGeometry( aOther.m_line );
848 }
849 
850 
852 {
853  m_line = m_line.Reverse();
854 
855  std::reverse( m_segmentRefs.begin(), m_segmentRefs.end() );
856 }
857 
858 
859 void LINE::AppendVia( const VIA& aVia )
860 {
861  if( m_line.PointCount() > 1 && aVia.Pos() == m_line.CPoint( 0 ) )
862  {
863  Reverse();
864  }
865 
866  m_hasVia = true;
867  m_via = aVia;
868  m_via.SetNet( m_net );
869 }
870 
871 
872 void LINE::SetRank( int aRank )
873 {
874  m_rank = aRank;
875 
876  for( auto s : m_segmentRefs )
877  s->SetRank( aRank );
878 
879 }
880 
881 
882 int LINE::Rank() const
883 {
884  int min_rank = INT_MAX;
885 
886  if( IsLinked() ) {
887  for( auto s : m_segmentRefs )
888  {
889  min_rank = std::min( min_rank, s->Rank() );
890  }
891  } else {
892  min_rank = m_rank;
893  }
894 
895  int rank = ( min_rank == INT_MAX ) ? -1 : min_rank;
896 
897  return rank;
898 }
899 
900 
901 void LINE::ClipVertexRange( int aStart, int aEnd )
902 {
903  m_line = m_line.Slice( aStart, aEnd );
904 
905  if( IsLinked() ) {
906  assert( m_segmentRefs.size() < INT_MAX );
907  assert( (int) m_segmentRefs.size() >= (aEnd - aStart) );
908 
909  // Note: The range includes aEnd, but we have n-1 segments.
910  std::rotate(
911  m_segmentRefs.begin(),
912  m_segmentRefs.begin() + aStart,
913  m_segmentRefs.begin() + aEnd
914  );
915 
916  m_segmentRefs.resize( aEnd - aStart );
917  }
918 }
919 
920 
921 bool LINE::HasLoops() const
922 {
923  for( int i = 0; i < PointCount(); i++ )
924  {
925  for( int j = i + 2; j < PointCount(); j++ )
926  {
927  if( CPoint( i ) == CPoint( j ) )
928  return true;
929  }
930  }
931 
932  return false;
933 }
934 
935 
937 {
938  m_segmentRefs.clear();
939 }
940 
941 
942 static void extendBox( BOX2I& aBox, bool& aDefined, const VECTOR2I& aP )
943 {
944  if( aDefined )
945  {
946  aBox.Merge( aP );
947  }
948  else
949  {
950  aBox = BOX2I( aP, VECTOR2I( 0, 0 ) );
951  aDefined = true;
952  }
953 }
954 
955 
956 OPT_BOX2I LINE::ChangedArea( const LINE* aOther ) const
957 {
958  BOX2I area;
959  bool areaDefined = false;
960 
961  int i_start = -1;
962  int i_end_self = -1, i_end_other = -1;
963 
964  SHAPE_LINE_CHAIN self( m_line );
965  self.Simplify();
966  SHAPE_LINE_CHAIN other( aOther->m_line );
967  other.Simplify();
968 
969  int np_self = self.PointCount();
970  int np_other = other.PointCount();
971 
972  int n = std::min( np_self, np_other );
973 
974  for( int i = 0; i < n; i++ )
975  {
976  const VECTOR2I p1 = self.CPoint( i );
977  const VECTOR2I p2 = other.CPoint( i );
978 
979  if( p1 != p2 )
980  {
981  if( i != n - 1 )
982  {
983  SEG s = self.CSegment( i );
984 
985  if( !s.Contains( p2 ) )
986  {
987  i_start = i;
988  break;
989  }
990  }
991  else
992  {
993  i_start = i;
994  break;
995  }
996  }
997  }
998 
999  for( int i = 0; i < n; i++ )
1000  {
1001  const VECTOR2I p1 = self.CPoint( np_self - 1 - i );
1002  const VECTOR2I p2 = other.CPoint( np_other - 1 - i );
1003 
1004  if( p1 != p2 )
1005  {
1006  i_end_self = np_self - 1 - i;
1007  i_end_other = np_other - 1 - i;
1008  break;
1009  }
1010  }
1011 
1012  if( i_start < 0 )
1013  i_start = n;
1014 
1015  if( i_end_self < 0 )
1016  i_end_self = np_self - 1;
1017 
1018  if( i_end_other < 0 )
1019  i_end_other = np_other - 1;
1020 
1021  for( int i = i_start; i <= i_end_self; i++ )
1022  extendBox( area, areaDefined, self.CPoint( i ) );
1023 
1024  for( int i = i_start; i <= i_end_other; i++ )
1025  extendBox( area, areaDefined, other.CPoint( i ) );
1026 
1027  if( areaDefined )
1028  {
1029  area.Inflate( std::max( Width(), aOther->Width() ) );
1030  return area;
1031  }
1032 
1033  return OPT_BOX2I();
1034 }
1035 
1036 
1038 {
1039  for( const auto seg : m_segmentRefs )
1040  {
1041  if( seg->Marker() & MK_LOCKED )
1042  return true;
1043  }
1044  return false;
1045 }
1046 
1048 {
1049  m_hasVia = false;
1050  m_line.Clear();
1051 }
1052 
1053 
1054 }
1055 
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:128
int Length() const
Function Length()
Definition: seg.h:319
int Find(const VECTOR2I &aP) const
Function Find()
const SHAPE_LINE_CHAIN & CLine() const
Const accessor to the underlying shape
Definition: pns_line.h:144
ITEM.
Definition: pns_item.h:53
int Index() const
Function Index()
Definition: seg.h:337
const SHAPE_LINE_CHAIN Hull(int aClearance, int aWalkaroundThickness) const override
Definition: pns_line.cpp:402
long long int Length() const
Function Length()
int Split(const VECTOR2I &aP)
Function Split()
int EdgeContainingPoint(const VECTOR2I &aP, int aAccuracy=0) const
Function EdgeContainingPoint()
BOX2< VECTOR2I > BOX2I
Definition: box2.h:521
bool isArc(size_t aSegment) const
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
std::vector< INTERSECTION > INTERSECTIONS
NODE.
Definition: pns_node.h:145
SHAPE_SEGMENT m_seg
Definition: pns_segment.h:120
static const int dist[10][10]
Definition: ar_matrix.cpp:326
OPT_BOX2I ChangedArea(const LINE *aOther) const
Definition: pns_line.cpp:956
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 Walkaround(SHAPE_LINE_CHAIN aObstacle, SHAPE_LINE_CHAIN &aPre, SHAPE_LINE_CHAIN &aWalk, SHAPE_LINE_CHAIN &aPost, bool aCw) const
Calculates a line thightly wrapping a convex hull of an obstacle object (aObstacle).
Definition: pns_line.cpp:162
LINE()
Constructor Makes an empty line.
Definition: pns_line.h:70
VIA m_via
Via at the end point, if m_hasVia == true
Definition: pns_line.h:343
void DragSegment(const VECTOR2I &aP, int aIndex, bool aFreeAngle=false)
Definition: pns_line.cpp:595
LINE & operator=(const LINE &aOther)
Definition: pns_line.cpp:60
void SetPoint(int aIndex, const VECTOR2I &aPos)
Accessor Function to move a point to a specific location.
VECTOR2I snapToNeighbourSegments(const SHAPE_LINE_CHAIN &aPath, const VECTOR2I &aP, int aIndex) const
Definition: pns_line.cpp:649
bool Is45Degree() const
Definition: pns_line.cpp:408
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Function Intersect()
Definition: seg.cpp:144
int Rank() const override
Definition: pns_line.cpp:882
const VECTOR2I ToVector() const
Function ToVector()
Definition: direction45.h:269
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Function Slice()
VECTOR2I p
point of intersection between our and their.
SEGMENT * Clone() const override
Function Clone()
Definition: pns_line.cpp:126
const DIRECTION_45 Left() const
Function Left()
Definition: direction45.h:249
NODE * m_owner
Definition: pns_item.h:252
void RemoveVia()
Definition: pns_line.h:279
LAYER_RANGE m_layers
Definition: pns_item.h:253
int m_rank
Definition: pns_item.h:258
void AppendVia(const VIA &aVia)
Definition: pns_line.cpp:859
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Function IntersectLines()
Definition: seg.h:191
int LineDistance(const VECTOR2I &aP, bool aDetermineSide=false) const
Function LineDistance()
Definition: seg.h:380
bool m_movable
Definition: pns_item.h:255
const DIRECTION_45 Right() const
Function Right()
Definition: direction45.h:228
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
VECTOR2< int > VECTOR2I
Definition: vector2d.h:594
int PointCount() const
Function PointCount()
const VECTOR2I & Pos() const
Definition: pns_via.h:100
int PointCount() const
Returns the number of points in the line
Definition: pns_line.h:156
const SHAPE_LINE_CHAIN SegmentHull(const SHAPE_SEGMENT &aSeg, int aClearance, int aWalkaroundThickness)
Definition: pns_utils.cpp:112
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
int PathLength(const VECTOR2I &aP) const
Function PathLength()
int m_marker
Definition: pns_item.h:257
SHAPE_LINE_CHAIN dragCornerInternal(const SHAPE_LINE_CHAIN &aOrigin, const VECTOR2I &aP)
Definition: pns_line.cpp:478
void SetNet(int aNet)
Definition: pns_item.h:148
const VECTOR2I & CPoint(int aIdx) const
Returns the aIdx-th point of the line
Definition: pns_line.h:168
SHAPE_LINE_CHAIN m_line
The actual shape of the line
Definition: pns_line.h:331
void Insert(size_t aVertex, const VECTOR2I &aP)
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 SetClosed(bool aClosed)
Function SetClosed()
SEG their
segment belonging from the aOther argument of Intersect()
void Reverse()
Reverses the point/vertex order
Definition: pns_line.cpp:851
OPT< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:37
DIRECTION_45.
Definition: direction45.h:37
void ClipVertexRange(int aStart, int aEnd)
Clips the line to a given range of vertices.
Definition: pns_line.cpp:901
void copyLinks(const LINE *aParent)
Copies m_segmentRefs from the line aParent.
Definition: pns_line.cpp:120
const LINE ClipToNearestObstacle(NODE *aNode) const
Clips the line to the nearest obstacle, traversing from the line's start vertex (0).
Definition: pns_line.cpp:437
bool m_hasVia
If true, the line ends with a via
Definition: pns_line.h:337
void Remove(int aStartIndex, int aEndIndex)
Function Remove()
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Function Merge modifies the position and size of the rectangle in order to contain aRect.
Definition: box2.h:385
void SetRank(int aRank) override
Definition: pns_line.cpp:872
virtual void Mark(int aMarker) override
Definition: pns_line.cpp:88
int SegmentCount() const
Function SegmentCount()
int m_net
Definition: pns_item.h:256
void dragCorner45(const VECTOR2I &aP, int aIndex)
Definition: pns_line.cpp:554
SHAPE_LINE_CHAIN & Line()
Modifiable accessor to the underlying shape
Definition: pns_line.h:138
void DragCorner(const VECTOR2I &aP, int aIndex, bool aFreeAngle=false)
Definition: pns_line.cpp:583
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false, int aMaxRadius=0) const
Function BuildInitialTrace()
Definition: seg.h:39
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:301
AngleType
Enum AngleType Represents kind of angle formed by vectors heading in two DIRECTION_45s.
Definition: direction45.h:64
virtual int Marker() const override
Definition: pns_line.cpp:107
void ClearSegmentLinks()
Erases the linking information. Used to detach the line from the owning node.
Definition: pns_line.cpp:936
SEGMENT_REFS m_segmentRefs
List of segments in the owning NODE (ITEM::m_owner) that constitute this line, or NULL if the line is...
Definition: pns_line.h:328
const SEG CSegment(int aIndex) const
Function CSegment()
SHAPE_LINE_CHAIN.
int m_snapThreshhold
Width to smooth out jagged segments
Definition: pns_line.h:340
static void extendBox(BOX2I &aBox, bool &aDefined, const VECTOR2I &aP)
Definition: pns_line.cpp:942
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
bool HasLoops() const
Definition: pns_line.cpp:921
VECTOR2I A
Definition: seg.h:47
int Width() const
Returns line width
Definition: pns_line.h:187
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:524
boost::optional< T > OPT
Definition: optional.h:7
void Clear()
Function Clear() Removes all points from the line chain.
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:148
void dragSegment45(const VECTOR2I &aP, int aIndex)
Definition: pns_line.cpp:694
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const
Function PointInside()
void Clear()
Definition: pns_line.cpp:1047
bool IsLinked() const
Definition: pns_line.h:214
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Function Replace()
bool CompareGeometry(const LINE &aOther)
Returns true if the line is geometrically identical as line aOther
Definition: pns_line.cpp:845
SEG our
segment belonging from the (this) argument of Intersect()
Push and Shove diff pair dimensions (gap) settings dialog.
void dragCornerFree(const VECTOR2I &aP, int aIndex)
Definition: pns_line.cpp:577
virtual LINE * Clone() const override
Function Clone()
Definition: pns_line.cpp:80
virtual void Unmark(int aMarker=-1) override
Definition: pns_line.cpp:98
void ShowLinks() const
Prints out all linked segments
Definition: pns_line.cpp:463
int m_width
our width
Definition: pns_line.h:334
bool CompareGeometry(const SHAPE_LINE_CHAIN &aOther) const
bool HasLockedSegments() const
Definition: pns_line.cpp:1037
int CountCorners(int aAngles) const
Returns the number of corners of angles specified by mask aAngles.
Definition: pns_line.cpp:140
bool Contains(const SEG &aSeg) const
Definition: seg.h:299
VECTOR2I B
Definition: seg.h:48
VECTOR2I snapDraggedCorner(const SHAPE_LINE_CHAIN &aPath, const VECTOR2I &aP, int aIndex) const
Definition: pns_line.cpp:607