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