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