KiCad PCB EDA Suite
pns_line.cpp
Go to the documentation of this file.
1 /*
2  * KiRouter - a push-and-(sometimes-)shove PCB router
3  *
4  * Copyright (C) 2013-2017 CERN
5  * Copyright (C) 2016-2020 KiCad Developers, see AUTHORS.txt for contributors.
6  * Author: Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
7  *
8  * This program is free software: you can redistribute it and/or modify it
9  * under the terms of the GNU General Public License as published by the
10  * Free Software Foundation, either version 3 of the License, or (at your
11  * option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful, but
14  * WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16  * General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License along
19  * with this program. If not, see <http://www.gnu.org/licenses/>.
20  */
21 
22 #include <core/optional.h>
23 
24 #include <math/box2.h>
25 #include <math/vector2d.h>
26 
27 #include "pns_line.h"
28 #include "pns_node.h"
29 #include "pns_via.h"
30 #include "pns_utils.h"
31 #include "pns_router.h"
32 
33 #include <geometry/shape_rect.h>
34 
35 namespace PNS {
36 
37 LINE::LINE( const LINE& aOther )
38  : LINK_HOLDER( aOther ),
39  m_line( aOther.m_line ),
40  m_width( aOther.m_width ),
41  m_snapThreshhold( aOther.m_snapThreshhold )
42 {
43  m_net = aOther.m_net;
44  m_movable = aOther.m_movable;
45  m_layers = aOther.m_layers;
46  m_via = aOther.m_via;
47  m_hasVia = aOther.m_hasVia;
48  m_marker = aOther.m_marker;
49  m_rank = aOther.m_rank;
51 
52  copyLinks( &aOther );
53 }
54 
55 
57 {
58 }
59 
60 
61 LINE& LINE::operator=( const LINE& aOther )
62 {
63  m_line = aOther.m_line;
64  m_width = aOther.m_width;
65  m_net = aOther.m_net;
66  m_movable = aOther.m_movable;
67  m_layers = aOther.m_layers;
68  m_via = aOther.m_via;
69  m_hasVia = aOther.m_hasVia;
70  m_marker = aOther.m_marker;
71  m_rank = aOther.m_rank;
72  m_owner = aOther.m_owner;
75 
76  copyLinks( &aOther );
77 
78  return *this;
79 }
80 
81 
82 LINE* LINE::Clone() const
83 {
84  LINE* l = new LINE( *this );
85 
86  return l;
87 }
88 
89 
90 void LINE::Mark( int aMarker ) const
91 {
92  m_marker = aMarker;
93 
94  for( const LINKED_ITEM* s : m_links )
95  s->Mark( aMarker );
96 
97 }
98 
99 
100 void LINE::Unmark( int aMarker ) const
101 {
102  for( const LINKED_ITEM* s : m_links )
103  s->Unmark( aMarker );
104 
105  m_marker = 0;
106 }
107 
108 
109 int LINE::Marker() const
110 {
111  int marker = m_marker;
112 
113  for( auto s : m_links )
114  {
115  marker |= s->Marker();
116  }
117 
118  return marker;
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 bool LINE::Walkaround( const SHAPE_LINE_CHAIN& aObstacle, SHAPE_LINE_CHAIN& aPath, bool aCw ) const
158 {
159  const SHAPE_LINE_CHAIN& line( CLine() );
160 
161  if( line.SegmentCount() < 1 )
162  {
163  return false;
164  }
165 
166  const auto pFirst = line.CPoint(0);
167  const auto pLast = line.CPoint(-1);
168 
169  bool inFirst = aObstacle.PointInside( pFirst ) && !aObstacle.PointOnEdge( pFirst );
170  bool inLast = aObstacle.PointInside( pLast ) && !aObstacle.PointOnEdge( pLast );
171 
172  // We can't really walk around if the beginning or the end of the path lies inside the obstacle hull.
173  // Double check if it's not on the hull itself as this triggers many unroutable corner cases.
174  if( inFirst || inLast )
175  {
176  return false;
177  }
178 
179  enum VERTEX_TYPE { INSIDE = 0, OUTSIDE, ON_EDGE };
180 
181  // Represents an entry in directed graph of hull/path vertices. Scanning this graph
182  // starting from the path's first point results (if possible) with a correct walkaround path
183  struct VERTEX
184  {
185  // vertex classification (inside/outside/exactly on the hull)
186  VERTEX_TYPE type;
187  // true = vertex coming from the hull primitive
188  bool isHull;
189  // position
190  VECTOR2I pos;
191  // list of neighboring vertices
192  std::vector<VERTEX*> neighbours;
193  // index of this vertex in path (pnew)
194  int indexp = -1;
195  // index of this vertex in the hull (hnew)
196  int indexh = -1;
197  // visited indicator (for BFS search)
198  bool visited = false;
199  };
200 
202 
203  line.Intersect( aObstacle, ips );
204 
205  SHAPE_LINE_CHAIN pnew( CLine() ), hnew( aObstacle );
206 
207  std::vector<VERTEX> vts;
208 
209  auto findVertex = [&]( VECTOR2I pos) -> VERTEX*
210  {
211  for( VERTEX& v : vts )
212  {
213  if(v.pos == pos )
214  return &v;
215  }
216 
217  return nullptr;
218  };
219 
220  // make sure all points that lie on the edge of the hull also exist as vertices in the path
221  for( int i = 0; i < pnew.PointCount(); i++ )
222  {
223  const VECTOR2I &p = pnew.CPoint(i);
224 
225  if( hnew.PointOnEdge( p ) )
226  {
228  ip.p = p;
229  ips.push_back( ip );
230  }
231  }
232 
233  // insert all intersections found into the new hull/path SLCs
234  for( auto ip : ips )
235  {
236  bool isNewP, isNewH;
237 
238  if( pnew.Find( ip.p ) < 0 )
239  {
240  pnew.Split(ip.p);
241  }
242 
243  if( hnew.Find( ip.p ) < 0 )
244  {
245  hnew.Split(ip.p);
246  }
247  }
248 
249  // we assume the default orientation of the hulls is clockwise, so just reverse the vertex
250  // order if the caller wants a counter-clockwise walkaround
251  if ( !aCw )
252  hnew = hnew.Reverse();
253 
254  vts.reserve( 2 * ( hnew.PointCount() + pnew.PointCount() ) );
255 
256  // create a graph of hull/path vertices and classify them (inside/on edge/outside the hull)
257  for( int i = 0; i < pnew.PointCount(); i++ )
258  {
259  auto p = pnew.CPoint(i);
260  bool onEdge = hnew.PointOnEdge( p );
261  bool inside = hnew.PointInside( p );
262 
263  VERTEX v;
264 
265  v.indexp = i;
266  v.isHull = false;
267  v.pos = p;
268  v.type = inside && !onEdge ? INSIDE : onEdge ? ON_EDGE : OUTSIDE;
269  vts.push_back( v );
270  }
271 
272  // each path vertex neighbour list points for sure to the next vertex in the path
273  for( int i = 0; i < pnew.PointCount() - 1; i++ )
274  {
275  vts[i].neighbours.push_back( &vts[ i+1 ] );
276  }
277 
278  // insert hull vertices into the graph
279  for( int i = 0; i < hnew.PointCount(); i++ )
280  {
281  auto hp = hnew.CPoint( i );
282  auto vn = findVertex( hp );
283 
284  // if vertex already present (it's very likely that in recursive shoving hull and path vertices will overlap)
285  // just mark it as a path vertex that also belongs to the hull
286  if( vn )
287  {
288  vn->isHull = true;
289  vn->indexh = i;
290  }
291  else // new hull vertex
292  {
293  VERTEX v;
294  v.pos = hp;
295  v.type = ON_EDGE;
296  v.indexh = i;
297  v.isHull = true;
298  vts.push_back( v );
299  }
300  }
301 
302  // go around the hull and fix up the neighbour link lists
303  for( int i = 0; i < hnew.PointCount(); i++ )
304  {
305  auto vc = findVertex( hnew.CPoint(i ) );
306  auto vnext = findVertex( hnew.CPoint( i+1 ) );
307 
308  if(vc && vnext)
309  vc->neighbours.push_back(vnext);
310  }
311 
312  // vts[0] = start point
313  VERTEX* v = &vts[0];
314  SHAPE_LINE_CHAIN out;
315 
316  int iterLimit = 1000;
317 
318  // keep scanning the graph until we reach the end point of the path
319  while ( v->indexp != (pnew.PointCount() - 1) )
320  {
321  iterLimit--;
322 
323  // I'm not 100% sure this algorithm doesn't have bugs that may cause it to freeze,
324  // so here's a temporary iteration limit
325  if( iterLimit == 0 )
326  {
327  return false;
328  }
329 
330  if(v->visited)
331  {
332  // loop found? clip to beginning of the loop
333  out = out.Slice(0, out.Find( v->pos ) );
334  break;
335  }
336 
337  out.Append( v->pos );
338 
339  VERTEX* v_next = nullptr;
340 
341  if (v->type == OUTSIDE)
342  {
343  // current vertex is outside? first look for any vertex further down the path
344  // that is not inside the hull
345  out.Append(v->pos);
346  for( auto vn : v->neighbours )
347  {
348  if( (vn->indexp > v->indexp) && vn->type != INSIDE )
349  {
350  v_next = vn;
351  break;
352  }
353  }
354 
355  // such a vertex must always be present, if not, bummer.
356  if (!v_next)
357  return false;
358 
359  }
360  else if (v->type == ON_EDGE)
361  {
362  // current vertex lies on the hull? first look for the hull/path vertex with the index (N+1)
363  for( VERTEX* vn: v->neighbours)
364  {
365 
366  if( vn->type == ON_EDGE && (vn->indexp == (v->indexp + 1) ) && ( (vn->indexh == (v->indexh + 1) ) % hnew.PointCount() ) )
367  {
368  v_next = vn;
369  break;
370  }
371  }
372 
373  // nothing found? look for the first vertex outside the hull then
374  if( !v_next )
375  {
376  for( VERTEX* vn: v->neighbours)
377  {
378  if( vn->type == OUTSIDE )
379  {
380  v_next = vn;
381  break;
382  }
383  }
384  }
385 
386  // still nothing found? try to find the next (index-wise) point on the hull. I guess
387  // we should never reach this part of the code, but who really knows?
388  if( !v_next )
389  {
390  for( VERTEX* vn: v->neighbours)
391  {
392  if ( v->type == ON_EDGE )
393  {
394  if( vn->indexh == ( (v->indexh + 1) % hnew.PointCount() ) )
395  {
396  v_next = vn;
397 
398  break;
399  }
400  }
401  }
402  }
403  }
404 
405  v->visited = true;
406  v = v_next;
407 
408  if( !v )
409  return false;
410  }
411 
412  out.Append( v->pos );
413  out.Simplify();
414 
415  aPath = out;
416 
417  return true;
418 }
419 
420 
421 const SHAPE_LINE_CHAIN SEGMENT::Hull( int aClearance, int aWalkaroundThickness, int aLayer ) const
422 {
423  return SegmentHull( m_seg, aClearance, aWalkaroundThickness );
424 }
425 
426 
427 bool LINE::Is45Degree() const
428 {
429  for( int i = 0; i < m_line.SegmentCount(); i++ )
430  {
431  const SEG& s = m_line.CSegment( i );
432 
433  if( m_line.isArc( i ) )
434  continue;
435 
436  if( s.Length() < 10 )
437  continue;
438 
439  double angle = 180.0 / M_PI *
440  atan2( (double) s.B.y - (double) s.A.y,
441  (double) s.B.x - (double) s.A.x );
442 
443  if( angle < 0 )
444  angle += 360.0;
445 
446  double angle_a = fabs( fmod( angle, 45.0 ) );
447 
448  if( angle_a > 1.0 && angle_a < 44.0 )
449  return false;
450  }
451 
452  return true;
453 }
454 
455 
456 const LINE LINE::ClipToNearestObstacle( NODE* aNode ) const
457 {
458  const int IterationLimit = 5;
459  int i;
460  LINE l( *this );
461 
462  for( i = 0; i < IterationLimit; i++ )
463  {
464  NODE::OPT_OBSTACLE obs = aNode->NearestObstacle( &l );
465 
466  if( obs )
467  {
468  l.RemoveVia();
469  int p = l.Line().Split( obs->m_ipFirst );
470  l.Line().Remove( p + 1, -1 );
471  } else
472  break;
473  }
474 
475  if( i == IterationLimit )
476  l.Line().Clear();
477 
478  return l;
479 }
480 
481 
482 
484 {
485  OPT<SHAPE_LINE_CHAIN> picked;
486  int i;
487  int d = 2;
488 
489  wxASSERT( aOrigin.PointCount() > 0 );
490 
491  if( aOrigin.PointCount() == 1 )
492  {
493  return DIRECTION_45().BuildInitialTrace( aOrigin.CPoint( 0 ), aP );
494  }
495  else if( aOrigin.SegmentCount() == 1 )
496  {
497  DIRECTION_45 dir( aOrigin.CPoint( 0 ) - aOrigin.CPoint( 1 ) );
498 
499  return DIRECTION_45().BuildInitialTrace( aOrigin.CPoint( 0 ), aP, dir.IsDiagonal() );
500  }
501 
502  if( aOrigin.CSegment( -1 ).Length() > 100000 * 30 ) // fixme: constant/parameter?
503  d = 1;
504 
505  for( i = aOrigin.SegmentCount() - d; i >= 0; i-- )
506  {
507  DIRECTION_45 d_start( aOrigin.CSegment( i ) );
508  VECTOR2I p_start = aOrigin.CPoint( i );
509  SHAPE_LINE_CHAIN paths[2];
510  DIRECTION_45 dirs[2];
511  DIRECTION_45 d_prev = ( i > 0 ? DIRECTION_45( aOrigin.CSegment( i-1 ) ) : DIRECTION_45() );
512  int dirCount = 0;
513 
514  for( int j = 0; j < 2; j++ )
515  {
516  paths[j] = d_start.BuildInitialTrace( p_start, aP, j );
517 
518  if( paths[j].SegmentCount() < 1 )
519  continue;
520 
521  assert( dirCount < int( sizeof( dirs ) / sizeof( dirs[0] ) ) );
522 
523  dirs[dirCount] = DIRECTION_45( paths[j].CSegment( 0 ) );
524  ++dirCount;
525  }
526 
527  for( int j = 0; j < dirCount; j++ )
528  {
529  if( dirs[j] == d_start )
530  {
531  picked = paths[j];
532  break;
533  }
534  }
535 
536  if( picked )
537  break;
538 
539  for( int j = 0; j < dirCount; j++ )
540  {
541  if( dirs[j].IsObtuse( d_prev ) )
542  {
543  picked = paths[j];
544  break;
545  }
546  }
547 
548  if( picked )
549  break;
550  }
551 
552  if( picked )
553  {
554  SHAPE_LINE_CHAIN path = aOrigin.Slice( 0, i );
555  path.Append( *picked );
556 
557  return path;
558  }
559 
560  DIRECTION_45 dir( aOrigin.CPoint( -1 ) - aOrigin.CPoint( -2 ) );
561 
562  return DIRECTION_45().BuildInitialTrace( aOrigin.CPoint( 0 ), aP, dir.IsDiagonal() );
563 }
564 
565 void LINE::dragCorner45( const VECTOR2I& aP, int aIndex )
566 {
567  SHAPE_LINE_CHAIN path;
568 
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  // fixme: awkward behaviour for "outwards" drags
578  path = dragCornerInternal( m_line.Slice( 0, aIndex ), snapped );
579  SHAPE_LINE_CHAIN path_rev =
580  dragCornerInternal( m_line.Slice( aIndex + 1, -1 ).Reverse(), snapped ).Reverse();
581  path.Append( path_rev );
582  }
583 
584  path.Simplify();
585  m_line = path;
586 }
587 
588 void LINE::dragCornerFree( const VECTOR2I& aP, int aIndex )
589 {
590  m_line.SetPoint( aIndex, aP );
591  m_line.Simplify();
592 }
593 
594 void LINE::DragCorner( const VECTOR2I& aP, int aIndex, bool aFreeAngle )
595 {
596  if( aFreeAngle )
597  {
598  dragCornerFree( aP, aIndex );
599  }
600  else
601  {
602  dragCorner45( aP, aIndex );
603  }
604 }
605 
606 void LINE::DragSegment( const VECTOR2I& aP, int aIndex, bool aFreeAngle )
607 {
608  if( aFreeAngle )
609  {
610  assert( false );
611  }
612  else
613  {
614  dragSegment45( aP, aIndex );
615  }
616 }
617 
619  const SHAPE_LINE_CHAIN& aPath, const VECTOR2I& aP, int aIndex ) const
620 {
621  int s_start = std::max( aIndex - 2, 0 );
622  int s_end = std::min( aIndex + 2, aPath.SegmentCount() - 1 );
623 
624  int i, j;
625  int best_dist = INT_MAX;
626  VECTOR2I best_snap = aP;
627 
628  if( m_snapThreshhold <= 0 )
629  return aP;
630 
631  for( i = s_start; i <= s_end; i++ )
632  {
633  const SEG& a = aPath.CSegment( i );
634 
635  for( j = s_start; j < i; j++ )
636  {
637  const SEG& b = aPath.CSegment( j );
638 
639  if( !( DIRECTION_45( a ).IsObtuse( DIRECTION_45( b ) ) ) )
640  continue;
641 
642  OPT_VECTOR2I ip = a.IntersectLines( b );
643 
644  if( ip )
645  {
646  int dist = ( *ip - aP ).EuclideanNorm();
647 
648  if( dist < m_snapThreshhold && dist < best_dist )
649  {
650  best_dist = dist;
651  best_snap = *ip;
652  }
653  }
654  }
655  }
656 
657  return best_snap;
658 }
659 
661  const SHAPE_LINE_CHAIN& aPath, const VECTOR2I& aP, int aIndex ) const
662 {
663  VECTOR2I snap_p[2];
664  DIRECTION_45 dragDir( aPath.CSegment( aIndex ) );
665  int snap_d[2] = { -1, -1 };
666 
667  if( m_snapThreshhold == 0 )
668  return aP;
669 
670  if( aIndex >= 2 )
671  {
672  SEG s = aPath.CSegment( aIndex - 2 );
673 
674  if( DIRECTION_45( s ) == dragDir )
675  snap_d[0] = s.LineDistance( aP );
676 
677  snap_p[0] = s.A;
678  }
679 
680  if( aIndex < aPath.SegmentCount() - 2 )
681  {
682  SEG s = aPath.CSegment( aIndex + 2 );
683 
684  if( DIRECTION_45( s ) == dragDir )
685  snap_d[1] = s.LineDistance( aP );
686 
687  snap_p[1] = s.A;
688  }
689 
690  VECTOR2I best = aP;
691  int minDist = INT_MAX;
692 
693  for( int i = 0; i < 2; i++ )
694  {
695  if( snap_d[i] >= 0 && snap_d[i] < minDist && snap_d[i] <= m_snapThreshhold )
696  {
697  minDist = snap_d[i];
698  best = snap_p[i];
699  }
700  }
701 
702  return best;
703 }
704 
705 void LINE::dragSegment45( const VECTOR2I& aP, int aIndex )
706 {
707  SHAPE_LINE_CHAIN path( m_line );
708  VECTOR2I target( aP );
709 
710  SEG guideA[2], guideB[2];
711  int index = aIndex;
712 
713  target = snapToNeighbourSegments( path, aP, aIndex );
714 
715  if( index == 0 )
716  {
717  path.Insert( 0, path.CPoint( 0 ) );
718  index++;
719  }
720 
721  if( index == path.SegmentCount() - 1 )
722  {
723  path.Insert( path.PointCount() - 1, path.CPoint( -1 ) );
724  }
725 
726  SEG dragged = path.CSegment( index );
727  DIRECTION_45 drag_dir( dragged );
728 
729  SEG s_prev = path.CSegment( index - 1 );
730  SEG s_next = path.CSegment( index + 1 );
731 
732  DIRECTION_45 dir_prev( s_prev );
733  DIRECTION_45 dir_next( s_next );
734 
735  if( dir_prev == drag_dir )
736  {
737  dir_prev = dir_prev.Left();
738  path.Insert( index, path.CPoint( index ) );
739  index++;
740  }
741 
742  if( dir_next == drag_dir )
743  {
744  dir_next = dir_next.Right();
745  path.Insert( index + 1, path.CPoint( index + 1 ) );
746  }
747 
748  s_prev = path.CSegment( index - 1 );
749  s_next = path.CSegment( index + 1 );
750  dragged = path.CSegment( index );
751 
752  if( aIndex == 0 )
753  {
754  guideA[0] = SEG( dragged.A, dragged.A + drag_dir.Right().ToVector() );
755  guideA[1] = SEG( dragged.A, dragged.A + drag_dir.Left().ToVector() );
756  }
757  else
758  {
759  if( dir_prev.Angle( drag_dir )
761  {
762  guideA[0] = SEG( s_prev.A, s_prev.A + drag_dir.Left().ToVector() );
763  guideA[1] = SEG( s_prev.A, s_prev.A + drag_dir.Right().ToVector() );
764  }
765  else
766  guideA[0] = guideA[1] = SEG( dragged.A, dragged.A + dir_prev.ToVector() );
767  }
768 
769  if( aIndex == m_line.SegmentCount() - 1 )
770  {
771  guideB[0] = SEG( dragged.B, dragged.B + drag_dir.Right().ToVector() );
772  guideB[1] = SEG( dragged.B, dragged.B + drag_dir.Left().ToVector() );
773  }
774  else
775  {
776  if( dir_next.Angle( drag_dir )
778  {
779  guideB[0] = SEG( s_next.B, s_next.B + drag_dir.Left().ToVector() );
780  guideB[1] = SEG( s_next.B, s_next.B + drag_dir.Right().ToVector() );
781  }
782  else
783  guideB[0] = guideB[1] = SEG( dragged.B, dragged.B + dir_next.ToVector() );
784  }
785 
786  SEG s_current( target, target + drag_dir.ToVector() );
787 
788  int best_len = INT_MAX;
789  SHAPE_LINE_CHAIN best;
790 
791  for( int i = 0; i < 2; i++ )
792  {
793  for( int j = 0; j < 2; j++ )
794  {
795  OPT_VECTOR2I ip1 = s_current.IntersectLines( guideA[i] );
796  OPT_VECTOR2I ip2 = s_current.IntersectLines( guideB[j] );
797 
798  SHAPE_LINE_CHAIN np;
799 
800  if( !ip1 || !ip2 )
801  continue;
802 
803  SEG s1( s_prev.A, *ip1 );
804  SEG s2( *ip1, *ip2 );
805  SEG s3( *ip2, s_next.B );
806 
807  OPT_VECTOR2I ip;
808 
809  if( ( ip = s1.Intersect( s_next ) ) )
810  {
811  np.Append( s1.A );
812  np.Append( *ip );
813  np.Append( s_next.B );
814  }
815  else if( ( ip = s3.Intersect( s_prev ) ) )
816  {
817  np.Append( s_prev.A );
818  np.Append( *ip );
819  np.Append( s3.B );
820  }
821  else if( ( ip = s1.Intersect( s3 ) ) )
822  {
823  np.Append( s_prev.A );
824  np.Append( *ip );
825  np.Append( s_next.B );
826  }
827  else
828  {
829  np.Append( s_prev.A );
830  np.Append( *ip1 );
831  np.Append( *ip2 );
832  np.Append( s_next.B );
833  }
834 
835  if( np.Length() < best_len )
836  {
837  best_len = np.Length();
838  best = np;
839  }
840  }
841  }
842 
843  if( m_line.PointCount() == 1 )
844  m_line = best;
845  else if( aIndex == 0 )
846  m_line.Replace( 0, 1, best );
847  else if( aIndex == m_line.SegmentCount() - 1 )
848  m_line.Replace( -2, -1, best );
849  else
850  m_line.Replace( aIndex, aIndex + 1, best );
851 
852  m_line.Simplify();
853 }
854 
855 
856 bool LINE::CompareGeometry( const LINE& aOther )
857 {
858  return m_line.CompareGeometry( aOther.m_line );
859 }
860 
861 
863 {
864  m_line = m_line.Reverse();
865 
866  std::reverse( m_links.begin(), m_links.end() );
867 }
868 
869 
870 void LINE::AppendVia( const VIA& aVia )
871 {
872  if( m_line.PointCount() > 1 && aVia.Pos() == m_line.CPoint( 0 ) )
873  {
874  Reverse();
875  }
876 
877  m_hasVia = true;
878  m_via = aVia;
879  m_via.SetNet( m_net );
880 }
881 
882 
883 void LINE::SetRank( int aRank )
884 {
885  m_rank = aRank;
886 
887  for( auto s : m_links )
888  s->SetRank( aRank );
889 
890 }
891 
892 
893 int LINE::Rank() const
894 {
895  int min_rank = INT_MAX;
896 
897  if( IsLinked() ) {
898  for( auto s : m_links )
899  {
900  min_rank = std::min( min_rank, s->Rank() );
901  }
902  } else {
903  min_rank = m_rank;
904  }
905 
906  int rank = ( min_rank == INT_MAX ) ? -1 : min_rank;
907 
908  return rank;
909 }
910 
911 
912 void LINE::ClipVertexRange( int aStart, int aEnd )
913 {
920  int firstLink = 0;
921  int lastLink = std::max( 0, static_cast<int>( m_links.size() ) - 1 );
922  int arcIdx = -1;
923  int linkIdx = 0;
924 
925  auto shapes = m_line.CShapes();
926  int numPoints = static_cast<int>( shapes.size() );
927 
928  for( int i = 0; i < m_line.PointCount(); i++ )
929  {
930  if( i <= aStart )
931  firstLink = linkIdx;
932 
933  if( shapes[i] >= 0 )
934  {
935  // Account for "hidden segments" between two arcs
936  if( i > aStart && ( shapes[i - 1] >= 0 ) && ( shapes[i - 1] != shapes[i] ) )
937  linkIdx++;
938 
939  arcIdx = shapes[i];
940 
941  // Skip over the rest of the arc vertices
942  while( i < numPoints && shapes[i] == arcIdx )
943  i++;
944 
945  // Back up two vertices to restart at the segment coincident with the end of the arc
946  i -= 2;
947  }
948 
949  if( i >= aEnd - 1 || linkIdx >= lastLink )
950  {
951  lastLink = linkIdx;
952  break;
953  }
954 
955  linkIdx++;
956  }
957 
958  wxASSERT( lastLink >= firstLink );
959 
960  m_line = m_line.Slice( aStart, aEnd );
961 
962  if( IsLinked() )
963  {
964  wxASSERT( m_links.size() < INT_MAX );
965  wxASSERT( static_cast<int>( m_links.size() ) >= ( lastLink - firstLink ) );
966 
967  // Note: The range includes aEnd, but we have n-1 segments.
968  std::rotate(
969  m_links.begin(),
970  m_links.begin() + firstLink,
971  m_links.begin() + lastLink
972  );
973 
974  m_links.resize( lastLink - firstLink + 1 );
975  }
976 }
977 
978 
979 bool LINE::HasLoops() const
980 {
981  for( int i = 0; i < PointCount(); i++ )
982  {
983  for( int j = i + 2; j < PointCount(); j++ )
984  {
985  if( CPoint( i ) == CPoint( j ) )
986  return true;
987  }
988  }
989 
990  return false;
991 }
992 
993 
994 static void extendBox( BOX2I& aBox, bool& aDefined, const VECTOR2I& aP )
995 {
996  if( aDefined )
997  {
998  aBox.Merge( aP );
999  }
1000  else
1001  {
1002  aBox = BOX2I( aP, VECTOR2I( 0, 0 ) );
1003  aDefined = true;
1004  }
1005 }
1006 
1007 
1008 OPT_BOX2I LINE::ChangedArea( const LINE* aOther ) const
1009 {
1010  BOX2I area;
1011  bool areaDefined = false;
1012 
1013  int i_start = -1;
1014  int i_end_self = -1, i_end_other = -1;
1015 
1016  SHAPE_LINE_CHAIN self( m_line );
1017  self.Simplify();
1018  SHAPE_LINE_CHAIN other( aOther->m_line );
1019  other.Simplify();
1020 
1021  int np_self = self.PointCount();
1022  int np_other = other.PointCount();
1023 
1024  int n = std::min( np_self, np_other );
1025 
1026  for( int i = 0; i < n; i++ )
1027  {
1028  const VECTOR2I p1 = self.CPoint( i );
1029  const VECTOR2I p2 = other.CPoint( i );
1030 
1031  if( p1 != p2 )
1032  {
1033  if( i != n - 1 )
1034  {
1035  SEG s = self.CSegment( i );
1036 
1037  if( !s.Contains( p2 ) )
1038  {
1039  i_start = i;
1040  break;
1041  }
1042  }
1043  else
1044  {
1045  i_start = i;
1046  break;
1047  }
1048  }
1049  }
1050 
1051  for( int i = 0; i < n; i++ )
1052  {
1053  const VECTOR2I p1 = self.CPoint( np_self - 1 - i );
1054  const VECTOR2I p2 = other.CPoint( np_other - 1 - i );
1055 
1056  if( p1 != p2 )
1057  {
1058  i_end_self = np_self - 1 - i;
1059  i_end_other = np_other - 1 - i;
1060  break;
1061  }
1062  }
1063 
1064  if( i_start < 0 )
1065  i_start = n;
1066 
1067  if( i_end_self < 0 )
1068  i_end_self = np_self - 1;
1069 
1070  if( i_end_other < 0 )
1071  i_end_other = np_other - 1;
1072 
1073  for( int i = i_start; i <= i_end_self; i++ )
1074  extendBox( area, areaDefined, self.CPoint( i ) );
1075 
1076  for( int i = i_start; i <= i_end_other; i++ )
1077  extendBox( area, areaDefined, other.CPoint( i ) );
1078 
1079  if( areaDefined )
1080  {
1081  area.Inflate( std::max( Width(), aOther->Width() ) );
1082  return area;
1083  }
1084 
1085  return OPT_BOX2I();
1086 }
1087 
1088 
1090 {
1091  for( const auto seg : m_links )
1092  {
1093  if( seg->Marker() & MK_LOCKED )
1094  return true;
1095  }
1096  return false;
1097 }
1098 
1100 {
1101  m_hasVia = false;
1102  m_line.Clear();
1103 }
1104 
1105 
1106 }
1107 
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:340
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:285
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:149
SHAPE_SEGMENT m_seg
Definition: pns_segment.h:121
OPT_BOX2I ChangedArea(const LINE *aOther) const
Definition: pns_line.cpp:1008
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:606
LINE & operator=(const LINE &aOther)
Definition: pns_line.cpp:61
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:660
bool Is45Degree() const
Print out all linked segments.
Definition: pns_line.cpp:427
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:105
int Rank() const override
Definition: pns_line.cpp:893
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.
SEGMENT * Clone() const override
Return a deep copy of the item.
Definition: pns_line.cpp:122
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:870
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
Definition: seg.h:193
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:405
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:421
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:483
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:862
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:912
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:456
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:883
int SegmentCount() const
Function SegmentCount()
int m_net
Definition: pns_item.h:242
void dragCorner45(const VECTOR2I &aP, int aIndex)
Definition: pns_line.cpp:565
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:136
void DragCorner(const VECTOR2I &aP, int aIndex, bool aFreeAngle=false)
Definition: pns_line.cpp:594
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:109
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:994
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
bool HasLoops() const
Definition: pns_line.cpp:979
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:152
void dragSegment45(const VECTOR2I &aP, int aIndex)
Definition: pns_line.cpp:705
void Clear()
Definition: pns_line.cpp:1099
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:856
Push and Shove diff pair dimensions (gap) settings dialog.
void dragCornerFree(const VECTOR2I &aP, int aIndex)
Definition: pns_line.cpp:588
virtual LINE * Clone() const override
Return a deep copy of the item.
Definition: pns_line.cpp:82
int m_width
Our width.
Definition: pns_line.h:244
virtual void Unmark(int aMarker=-1) const override
Definition: pns_line.cpp:100
bool CompareGeometry(const SHAPE_LINE_CHAIN &aOther) const
bool HasLockedSegments() const
Definition: pns_line.cpp:1089
int CountCorners(int aAngles) const
Definition: pns_line.cpp:136
virtual void Mark(int aMarker) const override
Definition: pns_line.cpp:90
bool Contains(const SEG &aSeg) const
Definition: seg.h:321
VECTOR2I B
Definition: seg.h:50
VECTOR2I snapDraggedCorner(const SHAPE_LINE_CHAIN &aPath, const VECTOR2I &aP, int aIndex) const
Definition: pns_line.cpp:618