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