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 
32 #include <geometry/shape_rect.h>
33 
34 namespace PNS {
35 
36 LINE::LINE( const LINE& aOther )
37  : LINK_HOLDER( aOther ),
38  m_line( aOther.m_line ),
39  m_width( aOther.m_width ),
40  m_snapThreshhold( aOther.m_snapThreshhold )
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;
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;
74 
75  copyLinks( &aOther );
76 
77  return *this;
78 }
79 
80 
81 LINE* LINE::Clone() const
82 {
83  LINE* l = new LINE( *this );
84 
85  return l;
86 }
87 
88 
89 void LINE::Mark( int aMarker ) const
90 {
91  m_marker = aMarker;
92 
93  for( const LINKED_ITEM* s : m_links )
94  s->Mark( aMarker );
95 
96 }
97 
98 
99 void LINE::Unmark( int aMarker ) const
100 {
101  for( const LINKED_ITEM* s : m_links )
102  s->Unmark( aMarker );
103 
104  m_marker = 0;
105 }
106 
107 
108 int LINE::Marker() const
109 {
110  int marker = m_marker;
111 
112  for( auto s : m_links )
113  {
114  marker |= s->Marker();
115  }
116 
117  return marker;
118 }
119 
120 
122 {
123  SEGMENT* s = new SEGMENT;
124 
125  s->m_seg = m_seg;
126  s->m_net = m_net;
127  s->m_layers = m_layers;
128  s->m_marker = m_marker;
129  s->m_rank = m_rank;
130 
131  return s;
132 }
133 
134 
135 int LINE::CountCorners( int aAngles ) const
136 {
137  int count = 0;
138 
139  for( int i = 0; i < m_line.SegmentCount() - 1; i++ )
140  {
141  const SEG seg1 = m_line.CSegment( i );
142  const SEG seg2 = m_line.CSegment( i + 1 );
143 
144  const DIRECTION_45 dir1( seg1 );
145  const DIRECTION_45 dir2( seg2 );
146 
147  DIRECTION_45::AngleType a = dir1.Angle( dir2 );
148 
149  if( a & aAngles )
150  count++;
151  }
152 
153  return count;
154 }
155 
156 bool LINE::Walkaround( const SHAPE_LINE_CHAIN& aObstacle, SHAPE_LINE_CHAIN& aPath, bool aCw ) const
157 {
158  const SHAPE_LINE_CHAIN& line( CLine() );
159 
160  if( line.SegmentCount() < 1 )
161  {
162  return false;
163  }
164 
165  const auto pFirst = line.CPoint(0);
166  const auto pLast = line.CPoint(-1);
167 
168  bool inFirst = aObstacle.PointInside( pFirst ) && !aObstacle.PointOnEdge( pFirst );
169  bool inLast = aObstacle.PointInside( pLast ) && !aObstacle.PointOnEdge( pLast );
170 
171  // We can't really walk around if the beginning or the end of the path lies inside the obstacle hull.
172  // Double check if it's not on the hull itself as this triggers many unroutable corner cases.
173  if( inFirst || inLast )
174  {
175  return false;
176  }
177 
178  enum VERTEX_TYPE { INSIDE = 0, OUTSIDE, ON_EDGE };
179 
180  // Represents an entry in directed graph of hull/path vertices. Scanning this graph
181  // starting from the path's first point results (if possible) with a correct walkaround path
182  struct VERTEX
183  {
184  // vertex classification (inside/outside/exactly on the hull)
185  VERTEX_TYPE type;
186  // true = vertex coming from the hull primitive
187  bool isHull;
188  // position
189  VECTOR2I pos;
190  // list of neighboring vertices
191  std::vector<VERTEX*> neighbours;
192  // index of this vertex in path (pnew)
193  int indexp = -1;
194  // index of this vertex in the hull (hnew)
195  int indexh = -1;
196  // visited indicator (for BFS search)
197  bool visited = false;
198  };
199 
201 
202  line.Intersect( aObstacle, ips );
203 
204  SHAPE_LINE_CHAIN pnew( CLine() ), hnew( aObstacle );
205 
206  std::vector<VERTEX> vts;
207 
208  auto findVertex = [&]( VECTOR2I pos) -> VERTEX*
209  {
210  for( VERTEX& v : vts )
211  {
212  if(v.pos == pos )
213  return &v;
214  }
215 
216  return nullptr;
217  };
218 
219  // make sure all points that lie on the edge of the hull also exist as vertices in the path
220  for( int i = 0; i < pnew.PointCount(); i++ )
221  {
222  const VECTOR2I &p = pnew.CPoint(i);
223 
224  if( hnew.PointOnEdge( p ) )
225  {
227  ip.p = p;
228  ips.push_back( ip );
229  }
230  }
231 
232  // insert all intersections found into the new hull/path SLCs
233  for( auto& ip : ips )
234  {
235  if( pnew.Find( ip.p ) < 0 )
236  {
237  pnew.Split(ip.p);
238  }
239 
240  if( hnew.Find( ip.p ) < 0 )
241  {
242  hnew.Split(ip.p);
243  }
244  }
245 
246  // we assume the default orientation of the hulls is clockwise, so just reverse the vertex
247  // order if the caller wants a counter-clockwise walkaround
248  if ( !aCw )
249  hnew = hnew.Reverse();
250 
251  vts.reserve( 2 * ( hnew.PointCount() + pnew.PointCount() ) );
252 
253  // create a graph of hull/path vertices and classify them (inside/on edge/outside the hull)
254  for( int i = 0; i < pnew.PointCount(); i++ )
255  {
256  auto p = pnew.CPoint(i);
257  bool onEdge = hnew.PointOnEdge( p );
258  bool inside = hnew.PointInside( p );
259 
260  VERTEX v;
261 
262  v.indexp = i;
263  v.isHull = false;
264  v.pos = p;
265  v.type = inside && !onEdge ? INSIDE : onEdge ? ON_EDGE : OUTSIDE;
266  vts.push_back( v );
267  }
268 
269  // each path vertex neighbour list points for sure to the next vertex in the path
270  for( int i = 0; i < pnew.PointCount() - 1; i++ )
271  {
272  vts[i].neighbours.push_back( &vts[ i+1 ] );
273  }
274 
275  // insert hull vertices into the graph
276  for( int i = 0; i < hnew.PointCount(); i++ )
277  {
278  auto hp = hnew.CPoint( i );
279  auto vn = findVertex( hp );
280 
281  // if vertex already present (it's very likely that in recursive shoving hull and path vertices will overlap)
282  // just mark it as a path vertex that also belongs to the hull
283  if( vn )
284  {
285  vn->isHull = true;
286  vn->indexh = i;
287  }
288  else // new hull vertex
289  {
290  VERTEX v;
291  v.pos = hp;
292  v.type = ON_EDGE;
293  v.indexh = i;
294  v.isHull = true;
295  vts.push_back( v );
296  }
297  }
298 
299  // go around the hull and fix up the neighbour link lists
300  for( int i = 0; i < hnew.PointCount(); i++ )
301  {
302  auto vc = findVertex( hnew.CPoint(i ) );
303  auto vnext = findVertex( hnew.CPoint( i+1 ) );
304 
305  if(vc && vnext)
306  vc->neighbours.push_back(vnext);
307  }
308 
309  // vts[0] = start point
310  VERTEX* v = &vts[0];
311  SHAPE_LINE_CHAIN out;
312 
313  int iterLimit = 1000;
314 
315  // keep scanning the graph until we reach the end point of the path
316  while ( v->indexp != (pnew.PointCount() - 1) )
317  {
318  iterLimit--;
319 
320  // I'm not 100% sure this algorithm doesn't have bugs that may cause it to freeze,
321  // so here's a temporary iteration limit
322  if( iterLimit == 0 )
323  {
324  return false;
325  }
326 
327  if(v->visited)
328  {
329  // loop found? clip to beginning of the loop
330  out = out.Slice(0, out.Find( v->pos ) );
331  break;
332  }
333 
334  out.Append( v->pos );
335 
336  VERTEX* v_next = nullptr;
337 
338  if (v->type == OUTSIDE)
339  {
340  // current vertex is outside? first look for any vertex further down the path
341  // that is not inside the hull
342  out.Append(v->pos);
343  for( auto vn : v->neighbours )
344  {
345  if( (vn->indexp > v->indexp) && vn->type != INSIDE )
346  {
347  v_next = vn;
348  break;
349  }
350  }
351 
352  // such a vertex must always be present, if not, bummer.
353  if (!v_next)
354  return false;
355 
356  }
357  else if (v->type == ON_EDGE)
358  {
359  // current vertex lies on the hull? first look for the hull/path vertex with the index (N+1)
360  for( VERTEX* vn: v->neighbours)
361  {
362  if( vn->type == ON_EDGE &&
363  ( vn->indexp == ( v->indexp + 1 ) ) &&
364  ( vn->indexh == ( ( v->indexh + 1 ) % hnew.PointCount() ) ) )
365  {
366  v_next = vn;
367  break;
368  }
369  }
370 
371  // nothing found? look for the first vertex outside the hull then
372  if( !v_next )
373  {
374  for( VERTEX* vn: v->neighbours)
375  {
376  if( vn->type == OUTSIDE )
377  {
378  v_next = vn;
379  break;
380  }
381  }
382  }
383 
384  // still nothing found? try to find the next (index-wise) point on the hull. I guess
385  // we should never reach this part of the code, but who really knows?
386  if( !v_next )
387  {
388  for( VERTEX* vn: v->neighbours)
389  {
390  if ( vn->type == ON_EDGE )
391  {
392  if( vn->indexh == ( (v->indexh + 1) % hnew.PointCount() ) )
393  {
394  v_next = vn;
395 
396  break;
397  }
398  }
399  }
400  }
401  }
402 
403  v->visited = true;
404  v = v_next;
405 
406  if( !v )
407  return false;
408  }
409 
410  out.Append( v->pos );
411  out.Simplify();
412 
413  aPath = out;
414 
415  return true;
416 }
417 
418 
419 const SHAPE_LINE_CHAIN SEGMENT::Hull( int aClearance, int aWalkaroundThickness, int aLayer ) const
420 {
421  return SegmentHull( m_seg, aClearance, aWalkaroundThickness );
422 }
423 
424 
425 bool LINE::Is45Degree() const
426 {
427  for( int i = 0; i < m_line.SegmentCount(); i++ )
428  {
429  const SEG& s = m_line.CSegment( i );
430 
431  if( m_line.isArc( i ) )
432  continue;
433 
434  if( s.Length() < 10 )
435  continue;
436 
437  double angle = 180.0 / M_PI *
438  atan2( (double) s.B.y - (double) s.A.y,
439  (double) s.B.x - (double) s.A.x );
440 
441  if( angle < 0 )
442  angle += 360.0;
443 
444  double angle_a = fabs( fmod( angle, 45.0 ) );
445 
446  if( angle_a > 1.0 && angle_a < 44.0 )
447  return false;
448  }
449 
450  return true;
451 }
452 
453 
454 const LINE LINE::ClipToNearestObstacle( NODE* aNode ) const
455 {
456  const int IterationLimit = 5;
457  int i;
458  LINE l( *this );
459 
460  for( i = 0; i < IterationLimit; i++ )
461  {
462  NODE::OPT_OBSTACLE obs = aNode->NearestObstacle( &l );
463 
464  if( obs )
465  {
466  l.RemoveVia();
467  int p = l.Line().Split( obs->m_ipFirst );
468  l.Line().Remove( p + 1, -1 );
469  } else
470  break;
471  }
472 
473  if( i == IterationLimit )
474  l.Line().Clear();
475 
476  return l;
477 }
478 
479 
480 
482 {
483  OPT<SHAPE_LINE_CHAIN> picked;
484  int i;
485  int d = 2;
486 
487  wxASSERT( aOrigin.PointCount() > 0 );
488 
489  if( aOrigin.PointCount() == 1 )
490  {
491  return DIRECTION_45().BuildInitialTrace( aOrigin.CPoint( 0 ), aP );
492  }
493  else if( aOrigin.SegmentCount() == 1 )
494  {
495  DIRECTION_45 dir( aOrigin.CPoint( 0 ) - aOrigin.CPoint( 1 ) );
496 
497  return DIRECTION_45().BuildInitialTrace( aOrigin.CPoint( 0 ), aP, dir.IsDiagonal() );
498  }
499 
500  if( aOrigin.CSegment( -1 ).Length() > 100000 * 30 ) // fixme: constant/parameter?
501  d = 1;
502 
503  for( i = aOrigin.SegmentCount() - d; i >= 0; i-- )
504  {
505  DIRECTION_45 d_start( aOrigin.CSegment( i ) );
506  VECTOR2I p_start = aOrigin.CPoint( i );
507  SHAPE_LINE_CHAIN paths[2];
508  DIRECTION_45 dirs[2];
509  DIRECTION_45 d_prev = ( i > 0 ? DIRECTION_45( aOrigin.CSegment( i-1 ) ) : DIRECTION_45() );
510  int dirCount = 0;
511 
512  for( int j = 0; j < 2; j++ )
513  {
514  paths[j] = d_start.BuildInitialTrace( p_start, aP, j );
515 
516  if( paths[j].SegmentCount() < 1 )
517  continue;
518 
519  assert( dirCount < int( sizeof( dirs ) / sizeof( dirs[0] ) ) );
520 
521  dirs[dirCount] = DIRECTION_45( paths[j].CSegment( 0 ) );
522  ++dirCount;
523  }
524 
525  for( int j = 0; j < dirCount; j++ )
526  {
527  if( dirs[j] == d_start )
528  {
529  picked = paths[j];
530  break;
531  }
532  }
533 
534  if( picked )
535  break;
536 
537  for( int j = 0; j < dirCount; j++ )
538  {
539  if( dirs[j].IsObtuse( d_prev ) )
540  {
541  picked = paths[j];
542  break;
543  }
544  }
545 
546  if( picked )
547  break;
548  }
549 
550  if( picked )
551  {
552  SHAPE_LINE_CHAIN path = aOrigin.Slice( 0, i );
553  path.Append( *picked );
554 
555  return path;
556  }
557 
558  DIRECTION_45 dir( aOrigin.CPoint( -1 ) - aOrigin.CPoint( -2 ) );
559 
560  return DIRECTION_45().BuildInitialTrace( aOrigin.CPoint( 0 ), aP, dir.IsDiagonal() );
561 }
562 
563 
564 void LINE::dragCorner45( const VECTOR2I& aP, int aIndex )
565 {
567 
568  int width = m_line.Width();
569  VECTOR2I snapped = snapDraggedCorner( m_line, aP, aIndex );
570 
571  if( aIndex == 0 )
572  path = dragCornerInternal( m_line.Reverse(), snapped ).Reverse();
573  else if( aIndex == m_line.SegmentCount() )
574  path = dragCornerInternal( m_line, snapped );
575  else
576  {
577  // Are we next to an arc? Insert a new point so we slice correctly
578  if( m_line.CShapes()[aIndex + 1] >= 0 )
579  m_line.Insert( aIndex + 1, m_line.CPoint( aIndex + 1 ) );
580 
581  // fixme: awkward behaviour for "outwards" drags
582  path = dragCornerInternal( m_line.Slice( 0, aIndex ), snapped );
583  SHAPE_LINE_CHAIN path_rev =
584  dragCornerInternal( m_line.Slice( aIndex + 1, -1 ).Reverse(), snapped ).Reverse();
585  path.Append( path_rev );
586  }
587 
588  path.Simplify();
589  path.SetWidth( width );
590  m_line = path;
591 }
592 
593 
594 void LINE::dragCornerFree( const VECTOR2I& aP, int aIndex )
595 {
596  const std::vector<ssize_t>& shapes = m_line.CShapes();
597 
598  // If we're asked to drag the end of an arc, insert a new vertex to drag instead
599  if( shapes[aIndex] >= 0 )
600  {
601  if( aIndex > 0 && shapes[aIndex - 1] == -1 )
602  m_line.Insert( aIndex, m_line.GetPoint( aIndex ) );
603  else if( aIndex < shapes.size() - 1 && shapes[aIndex + 1] != shapes[aIndex] )
604  {
605  aIndex++;
606  m_line.Insert( aIndex, m_line.GetPoint( aIndex ) );
607  }
608  else
609  wxASSERT_MSG( false, "Attempt to dragCornerFree in the middle of an arc!" );
610  }
611 
612  m_line.SetPoint( aIndex, aP );
613  m_line.Simplify();
614 }
615 
616 void LINE::DragCorner( const VECTOR2I& aP, int aIndex, bool aFreeAngle )
617 {
618  wxCHECK_RET( aIndex >= 0, "Negative index passed to LINE::DragCorner" );
619 
620  if( aFreeAngle )
621  {
622  dragCornerFree( aP, aIndex );
623  }
624  else
625  {
626  dragCorner45( aP, aIndex );
627  }
628 }
629 
630 void LINE::DragSegment( const VECTOR2I& aP, int aIndex, bool aFreeAngle )
631 {
632  if( aFreeAngle )
633  {
634  assert( false );
635  }
636  else
637  {
638  dragSegment45( aP, aIndex );
639  }
640 }
641 
643  const SHAPE_LINE_CHAIN& aPath, const VECTOR2I& aP, int aIndex ) const
644 {
645  int s_start = std::max( aIndex - 2, 0 );
646  int s_end = std::min( aIndex + 2, aPath.SegmentCount() - 1 );
647 
648  int i, j;
649  int best_dist = INT_MAX;
650  VECTOR2I best_snap = aP;
651 
652  if( m_snapThreshhold <= 0 )
653  return aP;
654 
655  for( i = s_start; i <= s_end; i++ )
656  {
657  const SEG& a = aPath.CSegment( i );
658 
659  for( j = s_start; j < i; j++ )
660  {
661  const SEG& b = aPath.CSegment( j );
662 
663  if( !( DIRECTION_45( a ).IsObtuse( DIRECTION_45( b ) ) ) )
664  continue;
665 
666  OPT_VECTOR2I ip = a.IntersectLines( b );
667 
668  if( ip )
669  {
670  int dist = ( *ip - aP ).EuclideanNorm();
671 
672  if( dist < m_snapThreshhold && dist < best_dist )
673  {
674  best_dist = dist;
675  best_snap = *ip;
676  }
677  }
678  }
679  }
680 
681  return best_snap;
682 }
683 
685  const SHAPE_LINE_CHAIN& aPath, const VECTOR2I& aP, int aIndex ) const
686 {
687  VECTOR2I snap_p[2];
688  DIRECTION_45 dragDir( aPath.CSegment( aIndex ) );
689  int snap_d[2] = { -1, -1 };
690 
691  if( m_snapThreshhold == 0 )
692  return aP;
693 
694  if( aIndex >= 2 )
695  {
696  SEG s = aPath.CSegment( aIndex - 2 );
697 
698  if( DIRECTION_45( s ) == dragDir )
699  snap_d[0] = s.LineDistance( aP );
700 
701  snap_p[0] = s.A;
702  }
703 
704  if( aIndex < aPath.SegmentCount() - 2 )
705  {
706  SEG s = aPath.CSegment( aIndex + 2 );
707 
708  if( DIRECTION_45( s ) == dragDir )
709  snap_d[1] = s.LineDistance( aP );
710 
711  snap_p[1] = s.A;
712  }
713 
714  VECTOR2I best = aP;
715  int minDist = INT_MAX;
716 
717  for( int i = 0; i < 2; i++ )
718  {
719  if( snap_d[i] >= 0 && snap_d[i] < minDist && snap_d[i] <= m_snapThreshhold )
720  {
721  minDist = snap_d[i];
722  best = snap_p[i];
723  }
724  }
725 
726  return best;
727 }
728 
729 void LINE::dragSegment45( const VECTOR2I& aP, int aIndex )
730 {
732  VECTOR2I target( aP );
733 
734  wxASSERT( aIndex < m_line.PointCount() );
735 
736  SEG guideA[2], guideB[2];
737  int index = aIndex;
738 
739  target = snapToNeighbourSegments( path, aP, aIndex );
740 
741  const std::vector<ssize_t>& shapes = path.CShapes();
742 
743  // We require a valid s_prev and s_next. If we are at the start or end of the line, we insert
744  // a new point at the start or end so there is a zero-length segment for prev or next (we will
745  // resize it as part of the drag operation). If we are next to an arc, we do this also, as we
746  // cannot drag away one of the arc's points.
747 
748  if( index == 0 || shapes[index] >= 0 )
749  {
750  path.Insert( index > 0 ? index + 1 : 0, path.CPoint( index ) );
751  index++;
752  }
753 
754  if( index == path.SegmentCount() - 1 )
755  {
756  path.Insert( path.PointCount() - 1, path.CPoint( -1 ) );
757  }
758  else if( shapes[index + 1] >= 0 )
759  {
760  path.Insert( index + 1, path.CPoint( index + 1 ) );
761  }
762 
763  SEG dragged = path.CSegment( index );
764  DIRECTION_45 drag_dir( dragged );
765 
766  SEG s_prev = path.CSegment( index - 1 );
767  SEG s_next = path.CSegment( index + 1 );
768 
769  DIRECTION_45 dir_prev( s_prev );
770  DIRECTION_45 dir_next( s_next );
771 
772  if( dir_prev == drag_dir )
773  {
774  dir_prev = dir_prev.Left();
775  path.Insert( index, path.CPoint( index ) );
776  index++;
777  }
778  else if( dir_prev == DIRECTION_45::UNDEFINED )
779  {
780  dir_prev = drag_dir.Left();
781  }
782 
783  if( dir_next == drag_dir )
784  {
785  dir_next = dir_next.Right();
786  path.Insert( index + 1, path.CPoint( index + 1 ) );
787  }
788  else if( dir_next == DIRECTION_45::UNDEFINED )
789  {
790  dir_next = drag_dir.Right();
791  }
792 
793  s_prev = path.CSegment( index - 1 );
794  s_next = path.CSegment( index + 1 );
795  dragged = path.CSegment( index );
796 
797  if( aIndex == 0 )
798  {
799  guideA[0] = SEG( dragged.A, dragged.A + drag_dir.Right().ToVector() );
800  guideA[1] = SEG( dragged.A, dragged.A + drag_dir.Left().ToVector() );
801  }
802  else
803  {
804  if( dir_prev.Angle( drag_dir )
806  {
807  guideA[0] = SEG( s_prev.A, s_prev.A + drag_dir.Left().ToVector() );
808  guideA[1] = SEG( s_prev.A, s_prev.A + drag_dir.Right().ToVector() );
809  }
810  else
811  guideA[0] = guideA[1] = SEG( dragged.A, dragged.A + dir_prev.ToVector() );
812  }
813 
814  if( aIndex == m_line.SegmentCount() - 1 )
815  {
816  guideB[0] = SEG( dragged.B, dragged.B + drag_dir.Right().ToVector() );
817  guideB[1] = SEG( dragged.B, dragged.B + drag_dir.Left().ToVector() );
818  }
819  else
820  {
821  if( dir_next.Angle( drag_dir )
823  {
824  guideB[0] = SEG( s_next.B, s_next.B + drag_dir.Left().ToVector() );
825  guideB[1] = SEG( s_next.B, s_next.B + drag_dir.Right().ToVector() );
826  }
827  else
828  guideB[0] = guideB[1] = SEG( dragged.B, dragged.B + dir_next.ToVector() );
829  }
830 
831  SEG s_current( target, target + drag_dir.ToVector() );
832 
833  int best_len = INT_MAX;
834  SHAPE_LINE_CHAIN best;
835 
836  for( int i = 0; i < 2; i++ )
837  {
838  for( int j = 0; j < 2; j++ )
839  {
840  OPT_VECTOR2I ip1 = s_current.IntersectLines( guideA[i] );
841  OPT_VECTOR2I ip2 = s_current.IntersectLines( guideB[j] );
842 
843  SHAPE_LINE_CHAIN np;
844 
845  if( !ip1 || !ip2 )
846  continue;
847 
848  SEG s1( s_prev.A, *ip1 );
849  SEG s2( *ip1, *ip2 );
850  SEG s3( *ip2, s_next.B );
851 
852  OPT_VECTOR2I ip;
853 
854  if( ( ip = s1.Intersect( s_next ) ) )
855  {
856  np.Append( s1.A );
857  np.Append( *ip );
858  np.Append( s_next.B );
859  }
860  else if( ( ip = s3.Intersect( s_prev ) ) )
861  {
862  np.Append( s_prev.A );
863  np.Append( *ip );
864  np.Append( s3.B );
865  }
866  else if( ( ip = s1.Intersect( s3 ) ) )
867  {
868  np.Append( s_prev.A );
869  np.Append( *ip );
870  np.Append( s_next.B );
871  }
872  else
873  {
874  np.Append( s_prev.A );
875  np.Append( *ip1 );
876  np.Append( *ip2 );
877  np.Append( s_next.B );
878  }
879 
880  if( np.Length() < best_len )
881  {
882  best_len = np.Length();
883  best = np;
884  }
885  }
886  }
887 
888  if( m_line.PointCount() == 1 )
889  m_line = best;
890  else if( aIndex == 0 )
891  m_line.Replace( 0, 1, best );
892  else if( aIndex == m_line.SegmentCount() - 1 )
893  m_line.Replace( -2, -1, best );
894  else
895  m_line.Replace( aIndex, aIndex + 1, best );
896 
897  m_line.Simplify();
898 }
899 
900 
901 bool LINE::CompareGeometry( const LINE& aOther )
902 {
903  return m_line.CompareGeometry( aOther.m_line );
904 }
905 
906 
908 {
909  m_line = m_line.Reverse();
910 
911  std::reverse( m_links.begin(), m_links.end() );
912 }
913 
914 
915 void LINE::AppendVia( const VIA& aVia )
916 {
917  if( m_line.PointCount() > 1 && aVia.Pos() == m_line.CPoint( 0 ) )
918  {
919  Reverse();
920  }
921 
922  m_hasVia = true;
923  m_via = aVia;
924  m_via.SetNet( m_net );
925 }
926 
927 
928 void LINE::SetRank( int aRank )
929 {
930  m_rank = aRank;
931 
932  for( auto s : m_links )
933  s->SetRank( aRank );
934 
935 }
936 
937 
938 int LINE::Rank() const
939 {
940  int min_rank = INT_MAX;
941 
942  if( IsLinked() ) {
943  for( auto s : m_links )
944  {
945  min_rank = std::min( min_rank, s->Rank() );
946  }
947  } else {
948  min_rank = m_rank;
949  }
950 
951  int rank = ( min_rank == INT_MAX ) ? -1 : min_rank;
952 
953  return rank;
954 }
955 
956 
957 void LINE::ClipVertexRange( int aStart, int aEnd )
958 {
965  int firstLink = 0;
966  int lastLink = std::max( 0, static_cast<int>( m_links.size() ) - 1 );
967  int arcIdx = -1;
968  int linkIdx = 0;
969 
970  auto shapes = m_line.CShapes();
971  int numPoints = static_cast<int>( shapes.size() );
972 
973  for( int i = 0; i < m_line.PointCount(); i++ )
974  {
975  if( i <= aStart )
976  firstLink = linkIdx;
977 
978  if( shapes[i] >= 0 )
979  {
980  // Account for "hidden segments" between two arcs
981  if( i > aStart && ( shapes[i - 1] >= 0 ) && ( shapes[i - 1] != shapes[i] ) )
982  linkIdx++;
983 
984  arcIdx = shapes[i];
985 
986  // Skip over the rest of the arc vertices
987  while( i < numPoints && shapes[i] == arcIdx )
988  i++;
989 
990  // Back up two vertices to restart at the segment coincident with the end of the arc
991  i -= 2;
992  }
993 
994  if( i >= aEnd - 1 || linkIdx >= lastLink )
995  {
996  lastLink = linkIdx;
997  break;
998  }
999 
1000  linkIdx++;
1001  }
1002 
1003  wxASSERT( lastLink >= firstLink );
1004 
1005  m_line = m_line.Slice( aStart, aEnd );
1006 
1007  if( IsLinked() )
1008  {
1009  wxASSERT( m_links.size() < INT_MAX );
1010  wxASSERT( static_cast<int>( m_links.size() ) >= ( lastLink - firstLink ) );
1011 
1012  // Note: The range includes aEnd, but we have n-1 segments.
1013  std::rotate(
1014  m_links.begin(),
1015  m_links.begin() + firstLink,
1016  m_links.begin() + lastLink
1017  );
1018 
1019  m_links.resize( lastLink - firstLink + 1 );
1020  }
1021 }
1022 
1023 
1024 bool LINE::HasLoops() const
1025 {
1026  for( int i = 0; i < PointCount(); i++ )
1027  {
1028  for( int j = i + 2; j < PointCount(); j++ )
1029  {
1030  if( CPoint( i ) == CPoint( j ) )
1031  return true;
1032  }
1033  }
1034 
1035  return false;
1036 }
1037 
1038 
1039 static void extendBox( BOX2I& aBox, bool& aDefined, const VECTOR2I& aP )
1040 {
1041  if( aDefined )
1042  {
1043  aBox.Merge( aP );
1044  }
1045  else
1046  {
1047  aBox = BOX2I( aP, VECTOR2I( 0, 0 ) );
1048  aDefined = true;
1049  }
1050 }
1051 
1052 
1053 OPT_BOX2I LINE::ChangedArea( const LINE* aOther ) const
1054 {
1055  BOX2I area;
1056  bool areaDefined = false;
1057 
1058  int i_start = -1;
1059  int i_end_self = -1, i_end_other = -1;
1060 
1061  SHAPE_LINE_CHAIN self( m_line );
1062  self.Simplify();
1063  SHAPE_LINE_CHAIN other( aOther->m_line );
1064  other.Simplify();
1065 
1066  int np_self = self.PointCount();
1067  int np_other = other.PointCount();
1068 
1069  int n = std::min( np_self, np_other );
1070 
1071  for( int i = 0; i < n; i++ )
1072  {
1073  const VECTOR2I p1 = self.CPoint( i );
1074  const VECTOR2I p2 = other.CPoint( i );
1075 
1076  if( p1 != p2 )
1077  {
1078  if( i != n - 1 )
1079  {
1080  SEG s = self.CSegment( i );
1081 
1082  if( !s.Contains( p2 ) )
1083  {
1084  i_start = i;
1085  break;
1086  }
1087  }
1088  else
1089  {
1090  i_start = i;
1091  break;
1092  }
1093  }
1094  }
1095 
1096  for( int i = 0; i < n; i++ )
1097  {
1098  const VECTOR2I p1 = self.CPoint( np_self - 1 - i );
1099  const VECTOR2I p2 = other.CPoint( np_other - 1 - i );
1100 
1101  if( p1 != p2 )
1102  {
1103  i_end_self = np_self - 1 - i;
1104  i_end_other = np_other - 1 - i;
1105  break;
1106  }
1107  }
1108 
1109  if( i_start < 0 )
1110  i_start = n;
1111 
1112  if( i_end_self < 0 )
1113  i_end_self = np_self - 1;
1114 
1115  if( i_end_other < 0 )
1116  i_end_other = np_other - 1;
1117 
1118  for( int i = i_start; i <= i_end_self; i++ )
1119  extendBox( area, areaDefined, self.CPoint( i ) );
1120 
1121  for( int i = i_start; i <= i_end_other; i++ )
1122  extendBox( area, areaDefined, other.CPoint( i ) );
1123 
1124  if( areaDefined )
1125  {
1126  area.Inflate( std::max( Width(), aOther->Width() ) );
1127  return area;
1128  }
1129 
1130  return OPT_BOX2I();
1131 }
1132 
1133 
1135 {
1136  for( const auto seg : m_links )
1137  {
1138  if( seg->Marker() & MK_LOCKED )
1139  return true;
1140  }
1141  return false;
1142 }
1143 
1145 {
1146  m_hasVia = false;
1147  m_line.Clear();
1148 }
1149 
1150 
1151 }
1152 
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:148
int Length() const
Return the length (this).
Definition: seg.h:355
int Find(const VECTOR2I &aP) const
Function Find()
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:137
OPT_OBSTACLE NearestObstacle(const LINE *aLine, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=NULL)
Follow the line in search of an obstacle that is nearest to the starting to the line's starting point...
Definition: pns_node.cpp:278
long long int Length() const
Function Length()
int Split(const VECTOR2I &aP)
Function Split()
BOX2< VECTOR2I > BOX2I
Definition: box2.h:522
bool isArc(size_t aSegment) const
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
std::vector< INTERSECTION > INTERSECTIONS
Keep the router "world" - i.e.
Definition: pns_node.h:144
SHAPE_SEGMENT m_seg
Definition: pns_segment.h:121
OPT_BOX2I ChangedArea(const LINE *aOther) const
Definition: pns_line.cpp:1053
bool Walkaround(SHAPE_LINE_CHAIN aObstacle, SHAPE_LINE_CHAIN &aPre, SHAPE_LINE_CHAIN &aWalk, SHAPE_LINE_CHAIN &aPost, bool aCw) const
Calculate a line tightly wrapping a convex hull of an obstacle object (aObstacle).
LINE()
Makes an empty line.
Definition: pns_line.h:66
VIA m_via
Definition: pns_line.h:250
void DragSegment(const VECTOR2I &aP, int aIndex, bool aFreeAngle=false)
Definition: pns_line.cpp:630
LINE & operator=(const LINE &aOther)
Definition: pns_line.cpp:60
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Function Simplify()
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:684
bool Is45Degree() const
Print out all linked segments.
Definition: pns_line.cpp:425
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Compute intersection point of segment (this) with segment aSeg.
Definition: seg.cpp:119
int Rank() const override
Definition: pns_line.cpp:938
const VECTOR2I ToVector() const
Definition: direction45.h:274
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Function Slice()
VECTOR2I p
point of intersection between our and their.
int Width() const
Gets the current width of the segments in the chain.
SEGMENT * Clone() const override
Return a deep copy of the item.
Definition: pns_line.cpp:121
const DIRECTION_45 Left() const
Return the direction on the left side of this (i.e.
Definition: direction45.h:256
NODE * m_owner
Definition: pns_item.h:238
void RemoveVia()
Definition: pns_line.h:194
LAYER_RANGE m_layers
Definition: pns_item.h:239
int m_rank
Definition: pns_item.h:244
bool PointOnEdge(const VECTOR2I &aP, int aAccuracy=0) const
Check if point aP lies on an edge or vertex of the line chain.
void AppendVia(const VIA &aVia)
Definition: pns_line.cpp:915
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
Definition: seg.h:208
static std::pair< bool, SHAPE_POLY_SET::VERTEX_INDEX > findVertex(SHAPE_POLY_SET &aPolySet, const EDIT_POINT &aPoint)
int LineDistance(const VECTOR2I &aP, bool aDetermineSide=false) const
Return the closest Euclidean distance between point aP and the line defined by the ends of segment (t...
Definition: seg.h:420
bool m_movable
Definition: pns_item.h:241
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:60
const DIRECTION_45 Right() const
Return the direction on the right side of this (i.e.
Definition: direction45.h:238
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
int PointCount() const
Function PointCount()
const VECTOR2I & Pos() const
Definition: pns_via.h:96
const SHAPE_LINE_CHAIN Hull(int aClearance, int aWalkaroundThickness, int aLayer=-1) const override
Definition: pns_line.cpp:419
int PointCount() const
Definition: pns_line.h:140
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 m_marker
Definition: pns_item.h:243
ITEM * m_blockingObstacle
For mark obstacle mode.
Definition: pns_line.h:252
SHAPE_LINE_CHAIN dragCornerInternal(const SHAPE_LINE_CHAIN &aOrigin, const VECTOR2I &aP)
Definition: pns_line.cpp:481
void SetNet(int aNet)
Definition: pns_item.h:147
const VECTOR2I & CPoint(int aIdx) const
Definition: pns_line.h:145
SHAPE_LINE_CHAIN m_line
The actual shape of the line.
Definition: pns_line.h:243
void Insert(size_t aVertex, const VECTOR2I &aP)
const std::vector< ssize_t > & CShapes() const
AngleType Angle(const DIRECTION_45 &aOther) const
Return the type of angle between directions (this) and aOther.
Definition: direction45.h:169
const VECTOR2I & CPoint(int aIndex) const
Function Point()
void Reverse()
Clip the line to the nearest obstacle, traversing from the line's start vertex (0).
Definition: pns_line.cpp:907
OPT< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:39
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:36
void ClipVertexRange(int aStart, int aEnd)
Return the number of corners of angles specified by mask aAngles.
Definition: pns_line.cpp:957
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const
Check if point aP lies inside a polygon (any type) defined by the line chain.
const LINE ClipToNearestObstacle(NODE *aNode) const
Clip the line to a given range of vertices.
Definition: pns_line.cpp:454
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false, bool aFillet=false) const
Build a 2-segment line chain between points aP0 and aP1 and following 45-degree routing regime.
Text appears outside the dimension line (default)
bool m_hasVia
Optional via at the end point.
Definition: pns_line.h:249
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:386
void SetRank(int aRank) override
Definition: pns_line.cpp:928
int SegmentCount() const
Function SegmentCount()
virtual const VECTOR2I GetPoint(int aIndex) const override
int m_net
Definition: pns_item.h:242
void dragCorner45(const VECTOR2I &aP, int aIndex)
Definition: pns_line.cpp:564
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:136
void DragCorner(const VECTOR2I &aP, int aIndex, bool aFreeAngle=false)
Definition: pns_line.cpp:616
Definition: seg.h:41
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:302
AngleType
Represent kind of angle formed by vectors heading in two DIRECTION_45s.
Definition: direction45.h:65
virtual int Marker() const override
Definition: pns_line.cpp:108
const SEG CSegment(int aIndex) const
Function CSegment()
SHAPE_LINE_CHAIN.
int m_snapThreshhold
Width to smooth out jagged segments.
Definition: pns_line.h:247
static void extendBox(BOX2I &aBox, bool &aDefined, const VECTOR2I &aP)
Definition: pns_line.cpp:1039
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
bool HasLoops() const
Definition: pns_line.cpp:1024
VECTOR2I A
Definition: seg.h:49
int Width() const
Return true if the line is geometrically identical as line aOther.
Definition: pns_line.h:156
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:525
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:147
void dragSegment45(const VECTOR2I &aP, int aIndex)
Definition: pns_line.cpp:729
void Clear()
Definition: pns_line.cpp:1144
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Function Replace()
bool CompareGeometry(const LINE &aOther)
Reverse the point/vertex order.
Definition: pns_line.cpp:901
Push and Shove diff pair dimensions (gap) settings dialog.
void dragCornerFree(const VECTOR2I &aP, int aIndex)
Definition: pns_line.cpp:594
virtual LINE * Clone() const override
Return a deep copy of the item.
Definition: pns_line.cpp:81
int m_width
Our width.
Definition: pns_line.h:244
virtual void Unmark(int aMarker=-1) const override
Definition: pns_line.cpp:99
bool CompareGeometry(const SHAPE_LINE_CHAIN &aOther) const
bool HasLockedSegments() const
Definition: pns_line.cpp:1134
int CountCorners(int aAngles) const
Definition: pns_line.cpp:135
virtual void Mark(int aMarker) const override
Definition: pns_line.cpp:89
bool Contains(const SEG &aSeg) const
Definition: seg.h:336
VECTOR2I B
Definition: seg.h:50
VECTOR2I snapDraggedCorner(const SHAPE_LINE_CHAIN &aPath, const VECTOR2I &aP, int aIndex) const
Definition: pns_line.cpp:642