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 static int areNeighbours( int x, int y, int max = 0 )
157 {
158  if( x > 0 && x - 1 == y )
159  return true;
160 
161  if( x < max - 1 && x + 1 == y )
162  return true;
163 
164  return false;
165 }
166 
167 
168 //#ifdef TOM_EXTRA_DEBUG
170 //#endif
171 
172 bool LINE::Walkaround( const SHAPE_LINE_CHAIN& aObstacle, SHAPE_LINE_CHAIN& aPath, bool aCw ) const
173 {
174  const SHAPE_LINE_CHAIN& line( CLine() );
175 
176  if( line.SegmentCount() < 1 )
177  {
178  return false;
179  }
180 
181  const auto pFirst = line.CPoint(0);
182 
183  bool inFirst = aObstacle.PointInside( pFirst ) && !aObstacle.PointOnEdge( pFirst );
184 
185  // We can't really walk around if the beginning of the path lies inside the obstacle hull.
186  // Double check if it's not on the hull itself as this triggers many unroutable corner cases.
187  if( inFirst )
188  {
189  return false;
190  }
191 
192  enum VERTEX_TYPE { INSIDE = 0, OUTSIDE, ON_EDGE };
193 
194  // Represents an entry in directed graph of hull/path vertices. Scanning this graph
195  // starting from the path's first point results (if possible) with a correct walkaround path
196  struct VERTEX
197  {
198  // vertex classification (inside/outside/exactly on the hull)
199  VERTEX_TYPE type;
200  // true = vertex coming from the hull primitive
201  bool isHull;
202  // position
203  VECTOR2I pos;
204  // list of neighboring vertices
205  std::vector<VERTEX*> neighbours;
206  // index of this vertex in path (pnew)
207  int indexp = -1;
208  // index of this vertex in the hull (hnew)
209  int indexh = -1;
210  // visited indicator (for BFS search)
211  bool visited = false;
212  };
213 
215 
216  HullIntersection( aObstacle, line, ips );
217 
218  SHAPE_LINE_CHAIN pnew( CLine() ), hnew( aObstacle );
219 
220  std::vector<VERTEX> vts;
221 
222  auto findVertex = [&]( VECTOR2I pos) -> VERTEX*
223  {
224  for( VERTEX& v : vts )
225  {
226  if(v.pos == pos )
227  return &v;
228  }
229 
230  return nullptr;
231  };
232 
233 
234  // corner case for loopy tracks: insert the end loop point back into the hull
235  if( auto isect = pnew.SelfIntersecting() )
236  {
237  if( isect->p != pnew.CPoint( -1 ) )
238  {
239  pnew.Split( isect->p );
240  }
241  }
242 
243  // insert all intersections found into the new hull/path SLCs
244  for( auto& ip : ips )
245  {
246  if( pnew.Find( ip.p, 1 ) < 0)
247  {
248  pnew.Split(ip.p);
249  }
250 
251  if( hnew.Find( ip.p, 1 ) < 0 )
252  {
253  hnew.Split(ip.p);
254  }
255  }
256 
257  for( int i = 0; i < pnew.PointCount(); i++ )
258  {
259  auto p = pnew.CPoint(i);
260  bool onEdge = hnew.PointOnEdge( p );
261 
262  if ( !onEdge )
263  continue;
264 
265  int idx = hnew.Find( p );
266 
267  if(idx < 0 )
268  {
269  hnew.Split(p);
270  }
271  }
272 
273  #ifdef TOM_EXTRA_DEBUG
274  for( auto& ip : ips )
275  {
276  printf("Chk: %d %d\n", pnew.Find( ip.p ), hnew.Find(ip.p) );
277  }
278  #endif
279 
280  // we assume the default orientation of the hulls is clockwise, so just reverse the vertex
281  // order if the caller wants a counter-clockwise walkaround
282  if ( !aCw )
283  hnew = hnew.Reverse();
284 
285  vts.reserve( 2 * ( hnew.PointCount() + pnew.PointCount() ) );
286 
287  // create a graph of hull/path vertices and classify them (inside/on edge/outside the hull)
288  for( int i = 0; i < pnew.PointCount(); i++ )
289  {
290  auto p = pnew.CPoint(i);
291  bool onEdge = hnew.PointOnEdge( p );
292  bool inside = hnew.PointInside( p );
293 
294  #ifdef TOM_EXTRA_DEBUG
295  printf("pnew %d inside %d onedge %d\n", i, !!inside, !!onEdge );
296  #endif
297 
298  VERTEX v;
299 
300  v.indexp = i;
301  v.isHull = false;
302  v.pos = p;
303  v.type = inside && !onEdge ? INSIDE : onEdge ? ON_EDGE : OUTSIDE;
304  vts.push_back( v );
305  }
306 
307  #ifdef TOM_EXTRA_DEBUG
308  g_pnew = pnew;
309  g_hnew = hnew;
310  #endif
311 
312  // each path vertex neighbour list points for sure to the next vertex in the path
313  for( int i = 0; i < pnew.PointCount() - 1; i++ )
314  {
315  vts[i].neighbours.push_back( &vts[ i+1 ] );
316  }
317 
318  // each path vertex neighbour list points for sure to the next vertex in the path
319  for( int i = 1; i < pnew.PointCount() ; i++ )
320  {
321  vts[i].neighbours.push_back( &vts[ i-1 ] );
322  }
323 
324  // insert hull vertices into the graph
325  for( int i = 0; i < hnew.PointCount(); i++ )
326  {
327  auto hp = hnew.CPoint( i );
328  auto vn = findVertex( hp );
329 
330  // if vertex already present (it's very likely that in recursive shoving hull and path vertices will overlap)
331  // just mark it as a path vertex that also belongs to the hull
332  if( vn )
333  {
334  vn->isHull = true;
335  vn->indexh = i;
336  }
337  else // new hull vertex
338  {
339  VERTEX v;
340  v.pos = hp;
341  v.type = ON_EDGE;
342  v.indexh = i;
343  v.isHull = true;
344  vts.push_back( v );
345  }
346  }
347 
348  // go around the hull and fix up the neighbour link lists
349  for( int i = 0; i < hnew.PointCount(); i++ )
350  {
351  auto vc = findVertex( hnew.CPoint(i ) );
352  auto vnext = findVertex( hnew.CPoint( i+1 ) );
353 
354  if(vc && vnext)
355  vc->neighbours.push_back(vnext);
356  }
357 
358  // In the case that the initial path ends *inside* the current obstacle (i.e. the mouse cursor
359  // is somewhere inside the hull for the current obstacle) we want to end the walkaround at the
360  // point closest to the cursor
361  bool inLast = aObstacle.PointInside( CPoint( -1 ) ) && !aObstacle.PointOnEdge( CPoint( -1 ) );
362  bool appendV = true;
363  int lastDst = INT_MAX;
364 
365  int i = 0;
366 #ifdef TOM_EXTRA_DEBUG
367  for(auto &v: vts)
368  {
369  if( v.indexh < 0 && v.type == ON_EDGE )
370  {
371  v.type = OUTSIDE; // hack
372  }
373  printf("V %d pos %d %d ip %d ih %d type %d\n", i++, v.pos.x, v.pos.y, v.indexp, v.indexh, v.type );
374  }
375 #endif
376  // vts[0] = start point
377  VERTEX* v = &vts[0], *v_prev = nullptr;
378  SHAPE_LINE_CHAIN out;
379 
380  int iterLimit = 1000;
381 
382  // keep scanning the graph until we reach the end point of the path
383  while( v->indexp != ( pnew.PointCount() - 1 ) )
384  {
385  iterLimit--;
386 
387  // I'm not 100% sure this algorithm doesn't have bugs that may cause it to freeze,
388  // so here's a temporary iteration limit
389  if( iterLimit == 0 )
390  {
391  return false;
392  }
393 
394  if( v->visited )
395  {
396  // loop found? stop walking
397  break;
398  }
399 #ifdef TOM_EXTRA_DEBUG
400  printf("---\nvisit ip %d ih %d type %d outs %d neig %d\n", v->indexp, v->indexh, v->type, out.PointCount(), v->neighbours.size() );
401 #endif
402  out.Append( v->pos );
403 
404  VERTEX* v_next = nullptr;
405 
406  if( v->type == OUTSIDE )
407  {
408  // current vertex is outside? first look for any vertex further down the path
409  // that is not inside the hull
410  out.Append( v->pos );
411  VERTEX* v_next_fallback = nullptr;
412  for( auto vn : v->neighbours )
413  {
414  if( areNeighbours( vn->indexp , v->indexp, pnew.PointCount() ) &&
415  vn->type != INSIDE )
416  {
417  if( !vn->visited )
418  {
419  v_next = vn;
420  break;
421  }
422  else if( vn != v_prev )
423  v_next_fallback = vn;
424  }
425  }
426 
427  if( !v_next )
428  v_next = v_next_fallback;
429 
430  // such a vertex must always be present, if not, bummer.
431  if( !v_next )
432  {
433  #ifdef TOM_EXTRA_DEBUG
434  printf("FAIL VN fallback %p\n", v_next_fallback );
435  #endif
436  return false;
437  }
438 
439  }
440  else if( v->type == ON_EDGE )
441  {
442  // look first for the first vertex outside the hull
443  for( VERTEX* vn : v->neighbours )
444  {
445 #ifdef TOM_EXTRA_DEBUG
446  printf( "- OUT scan ip %d ih %d type %d\n", vn->indexp, vn->indexh, vn->type );
447 #endif
448 
449  if( vn->type == OUTSIDE && !vn->visited )
450  {
451  v_next = vn;
452  break;
453  }
454  }
455 
456  // no outside vertices found? continue traversing the hull
457  if( !v_next )
458  {
459  for( VERTEX* vn : v->neighbours )
460  {
461  #ifdef TOM_EXTRA_DEBUG
462  printf("- scan ip %d ih %d type %d\n", vn->indexp, vn->indexh, vn->type );
463  #endif
464  if( vn->type == ON_EDGE && !vn->isHull &&
465  areNeighbours( vn->indexp, v->indexp, pnew.PointCount() ) &&
466  ( vn->indexh == ( ( v->indexh + 1 ) % hnew.PointCount() ) ) )
467  {
468  v_next = vn;
469  break;
470  }
471  }
472  }
473 
474  // still nothing found? try to find the next (index-wise) point on the hull. I guess
475  // we should never reach this part of the code, but who really knows?
476  if( !v_next )
477  {
478  for( VERTEX* vn : v->neighbours )
479  {
480  if( vn->type == ON_EDGE )
481  {
482  if( vn->indexh == ( ( v->indexh + 1 ) % hnew.PointCount() ) )
483  {
484  v_next = vn;
485  break;
486  }
487  }
488  }
489 
490  // Did we get the next hull point but the end of the line is inside? Instead of walking
491  // around the hull some more (which will just end up taking us back to the start), lets
492  // just project the normal of the endpoint onto this next segment and call it quits.
493  if( inLast && v_next )
494  {
495  int d = ( v_next->pos - CPoint( -1 ) ).SquaredEuclideanNorm();
496 
497  if( d < lastDst )
498  {
499  lastDst = d;
500  }
501  else
502  {
503  VECTOR2I proj = SEG( v->pos, v_next->pos ).NearestPoint( CPoint( -1 ) );
504  out.Append( proj );
505  appendV = false;
506  break;
507  }
508  }
509  }
510  }
511 
512  v->visited = true;
513  v_prev = v;
514  v = v_next;
515 
516  if( !v )
517  {
518  return false;
519  }
520  }
521 
522  if( appendV )
523  out.Append( v->pos );
524 
525  aPath = out;
526 
527  return true;
528 }
529 
530 
531 const SHAPE_LINE_CHAIN SEGMENT::Hull( int aClearance, int aWalkaroundThickness, int aLayer ) const
532 {
533  return SegmentHull( m_seg, aClearance, aWalkaroundThickness );
534 }
535 
536 
537 bool LINE::Is45Degree() const
538 {
539  for( int i = 0; i < m_line.SegmentCount(); i++ )
540  {
541  const SEG& s = m_line.CSegment( i );
542 
543  if( m_line.IsArcSegment( i ) )
544  continue;
545 
546  if( s.Length() < 10 )
547  continue;
548 
549  double angle = 180.0 / M_PI *
550  atan2( (double) s.B.y - (double) s.A.y,
551  (double) s.B.x - (double) s.A.x );
552 
553  if( angle < 0 )
554  angle += 360.0;
555 
556  double angle_a = fabs( fmod( angle, 45.0 ) );
557 
558  if( angle_a > 1.0 && angle_a < 44.0 )
559  return false;
560  }
561 
562  return true;
563 }
564 
565 
566 const LINE LINE::ClipToNearestObstacle( NODE* aNode ) const
567 {
568  const int IterationLimit = 5;
569  int i;
570  LINE l( *this );
571 
572  for( i = 0; i < IterationLimit; i++ )
573  {
574  NODE::OPT_OBSTACLE obs = aNode->NearestObstacle( &l );
575 
576  if( obs )
577  {
578  l.RemoveVia();
579  int p = l.Line().Split( obs->m_ipFirst );
580  l.Line().Remove( p + 1, -1 );
581  } else
582  break;
583  }
584 
585  if( i == IterationLimit )
586  l.Line().Clear();
587 
588  return l;
589 }
590 
591 
592 
594 {
595  OPT<SHAPE_LINE_CHAIN> picked;
596  int i;
597  int d = 2;
598 
599  wxASSERT( aOrigin.PointCount() > 0 );
600 
601  if( aOrigin.PointCount() == 1 )
602  {
603  return DIRECTION_45().BuildInitialTrace( aOrigin.CPoint( 0 ), aP );
604  }
605  else if( aOrigin.SegmentCount() == 1 )
606  {
607  DIRECTION_45 dir( aOrigin.CPoint( 0 ) - aOrigin.CPoint( 1 ) );
608 
609  return DIRECTION_45().BuildInitialTrace( aOrigin.CPoint( 0 ), aP, dir.IsDiagonal() );
610  }
611 
612  if( aOrigin.CSegment( -1 ).Length() > 100000 * 30 ) // fixme: constant/parameter?
613  d = 1;
614 
615  for( i = aOrigin.SegmentCount() - d; i >= 0; i-- )
616  {
617  DIRECTION_45 d_start( aOrigin.CSegment( i ) );
618  VECTOR2I p_start = aOrigin.CPoint( i );
619  SHAPE_LINE_CHAIN paths[2];
620  DIRECTION_45 dirs[2];
621  DIRECTION_45 d_prev = ( i > 0 ? DIRECTION_45( aOrigin.CSegment( i-1 ) ) : DIRECTION_45() );
622  int dirCount = 0;
623 
624  for( int j = 0; j < 2; j++ )
625  {
626  paths[j] = d_start.BuildInitialTrace( p_start, aP, j );
627 
628  if( paths[j].SegmentCount() < 1 )
629  continue;
630 
631  assert( dirCount < int( sizeof( dirs ) / sizeof( dirs[0] ) ) );
632 
633  dirs[dirCount] = DIRECTION_45( paths[j].CSegment( 0 ) );
634  ++dirCount;
635  }
636 
637  for( int j = 0; j < dirCount; j++ )
638  {
639  if( dirs[j] == d_start )
640  {
641  picked = paths[j];
642  break;
643  }
644  }
645 
646  if( picked )
647  break;
648 
649  for( int j = 0; j < dirCount; j++ )
650  {
651  if( dirs[j].IsObtuse( d_prev ) )
652  {
653  picked = paths[j];
654  break;
655  }
656  }
657 
658  if( picked )
659  break;
660  }
661 
662  if( picked )
663  {
664  SHAPE_LINE_CHAIN path = aOrigin.Slice( 0, i );
665  path.Append( *picked );
666 
667  return path;
668  }
669 
670  DIRECTION_45 dir( aOrigin.CPoint( -1 ) - aOrigin.CPoint( -2 ) );
671 
672  return DIRECTION_45().BuildInitialTrace( aOrigin.CPoint( 0 ), aP, dir.IsDiagonal() );
673 }
674 
675 
676 void LINE::dragCorner45( const VECTOR2I& aP, int aIndex )
677 {
679 
680  int width = m_line.Width();
681  VECTOR2I snapped = snapDraggedCorner( m_line, aP, aIndex );
682 
683  if( aIndex == 0 )
684  path = dragCornerInternal( m_line.Reverse(), snapped ).Reverse();
685  else if( aIndex == m_line.SegmentCount() )
686  path = dragCornerInternal( m_line, snapped );
687  else
688  {
689  // Are we next to an arc? Insert a new point so we slice correctly
690  if( m_line.IsPtOnArc( static_cast<size_t>( aIndex ) + 1 ) )
691  m_line.Insert( aIndex + 1, m_line.CPoint( aIndex + 1 ) );
692 
693  // fixme: awkward behaviour for "outwards" drags
694  path = dragCornerInternal( m_line.Slice( 0, aIndex ), snapped );
695  SHAPE_LINE_CHAIN path_rev =
696  dragCornerInternal( m_line.Slice( aIndex + 1, -1 ).Reverse(), snapped ).Reverse();
697  path.Append( path_rev );
698  }
699 
700  path.Simplify();
701  path.SetWidth( width );
702  m_line = path;
703 }
704 
705 
706 void LINE::dragCornerFree( const VECTOR2I& aP, int aIndex )
707 {
708  ssize_t idx = static_cast<ssize_t>( aIndex );
709  ssize_t numpts = static_cast<ssize_t>( m_line.PointCount() );
710 
711  // If we're asked to drag the end of an arc, insert a new vertex to drag instead
712  if( m_line.IsPtOnArc( idx ) )
713  {
714  if( idx == 0 || ( idx > 0 && !m_line.IsPtOnArc( idx - 1 ) ) )
715  {
716  m_line.Insert( idx, m_line.GetPoint( idx ) );
717  }
718  else if( ( idx == numpts - 1 ) || ( idx < numpts - 1 && !m_line.IsArcSegment( idx ) ) )
719  {
720  idx++;
721  m_line.Insert( idx, m_line.GetPoint( idx ) );
722  }
723  else
724  {
725  wxASSERT_MSG( false, "Attempt to dragCornerFree in the middle of an arc!" );
726  }
727  }
728 
729  m_line.SetPoint( idx, aP );
730  m_line.Simplify();
731 }
732 
733 void LINE::DragCorner( const VECTOR2I& aP, int aIndex, bool aFreeAngle )
734 {
735  wxCHECK_RET( aIndex >= 0, "Negative index passed to LINE::DragCorner" );
736 
737  if( aFreeAngle )
738  {
739  dragCornerFree( aP, aIndex );
740  }
741  else
742  {
743  dragCorner45( aP, aIndex );
744  }
745 }
746 
747 void LINE::DragSegment( const VECTOR2I& aP, int aIndex, bool aFreeAngle )
748 {
749  if( aFreeAngle )
750  {
751  assert( false );
752  }
753  else
754  {
755  dragSegment45( aP, aIndex );
756  }
757 }
758 
760  const SHAPE_LINE_CHAIN& aPath, const VECTOR2I& aP, int aIndex ) const
761 {
762  int s_start = std::max( aIndex - 2, 0 );
763  int s_end = std::min( aIndex + 2, aPath.SegmentCount() - 1 );
764 
765  int i, j;
766  int best_dist = INT_MAX;
767  VECTOR2I best_snap = aP;
768 
769  if( m_snapThreshhold <= 0 )
770  return aP;
771 
772  for( i = s_start; i <= s_end; i++ )
773  {
774  const SEG& a = aPath.CSegment( i );
775 
776  for( j = s_start; j < i; j++ )
777  {
778  const SEG& b = aPath.CSegment( j );
779 
780  if( !( DIRECTION_45( a ).IsObtuse( DIRECTION_45( b ) ) ) )
781  continue;
782 
783  OPT_VECTOR2I ip = a.IntersectLines( b );
784 
785  if( ip )
786  {
787  int dist = ( *ip - aP ).EuclideanNorm();
788 
789  if( dist < m_snapThreshhold && dist < best_dist )
790  {
791  best_dist = dist;
792  best_snap = *ip;
793  }
794  }
795  }
796  }
797 
798  return best_snap;
799 }
800 
802  const SHAPE_LINE_CHAIN& aPath, const VECTOR2I& aP, int aIndex ) const
803 {
804  VECTOR2I snap_p[2];
805  DIRECTION_45 dragDir( aPath.CSegment( aIndex ) );
806  int snap_d[2] = { -1, -1 };
807 
808  if( m_snapThreshhold == 0 )
809  return aP;
810 
811  if( aIndex >= 2 )
812  {
813  SEG s = aPath.CSegment( aIndex - 2 );
814 
815  if( DIRECTION_45( s ) == dragDir )
816  snap_d[0] = s.LineDistance( aP );
817 
818  snap_p[0] = s.A;
819  }
820 
821  if( aIndex < aPath.SegmentCount() - 2 )
822  {
823  SEG s = aPath.CSegment( aIndex + 2 );
824 
825  if( DIRECTION_45( s ) == dragDir )
826  snap_d[1] = s.LineDistance( aP );
827 
828  snap_p[1] = s.A;
829  }
830 
831  VECTOR2I best = aP;
832  int minDist = INT_MAX;
833 
834  for( int i = 0; i < 2; i++ )
835  {
836  if( snap_d[i] >= 0 && snap_d[i] < minDist && snap_d[i] <= m_snapThreshhold )
837  {
838  minDist = snap_d[i];
839  best = snap_p[i];
840  }
841  }
842 
843  return best;
844 }
845 
846 void LINE::dragSegment45( const VECTOR2I& aP, int aIndex )
847 {
849  VECTOR2I target( aP );
850 
851  wxASSERT( aIndex < m_line.PointCount() );
852 
853  SEG guideA[2], guideB[2];
854  int index = aIndex;
855 
856  target = snapToNeighbourSegments( path, aP, aIndex );
857 
858  // We require a valid s_prev and s_next. If we are at the start or end of the line, we insert
859  // a new point at the start or end so there is a zero-length segment for prev or next (we will
860  // resize it as part of the drag operation). If we are next to an arc, we do this also, as we
861  // cannot drag away one of the arc's points.
862 
863  if( index == 0 || path.IsPtOnArc( index ) )
864  {
865  path.Insert( index > 0 ? index + 1 : 0, path.CPoint( index ) );
866  index++;
867  }
868 
869  if( index == path.SegmentCount() - 1 )
870  {
871  path.Insert( path.PointCount() - 1, path.CPoint( -1 ) );
872  }
873  else if( path.IsPtOnArc( index + 1 ) )
874  {
875  path.Insert( index + 1, path.CPoint( index + 1 ) );
876  }
877 
878  SEG dragged = path.CSegment( index );
879  DIRECTION_45 drag_dir( dragged );
880 
881  SEG s_prev = path.CSegment( index - 1 );
882  SEG s_next = path.CSegment( index + 1 );
883 
884  DIRECTION_45 dir_prev( s_prev );
885  DIRECTION_45 dir_next( s_next );
886 
887  if( dir_prev == drag_dir )
888  {
889  dir_prev = dir_prev.Left();
890  path.Insert( index, path.CPoint( index ) );
891  index++;
892  }
893  else if( dir_prev == DIRECTION_45::UNDEFINED )
894  {
895  dir_prev = drag_dir.Left();
896  }
897 
898  if( dir_next == drag_dir )
899  {
900  dir_next = dir_next.Right();
901  path.Insert( index + 1, path.CPoint( index + 1 ) );
902  }
903  else if( dir_next == DIRECTION_45::UNDEFINED )
904  {
905  dir_next = drag_dir.Right();
906  }
907 
908  s_prev = path.CSegment( index - 1 );
909  s_next = path.CSegment( index + 1 );
910  dragged = path.CSegment( index );
911 
912  if( aIndex == 0 )
913  {
914  guideA[0] = SEG( dragged.A, dragged.A + drag_dir.Right().ToVector() );
915  guideA[1] = SEG( dragged.A, dragged.A + drag_dir.Left().ToVector() );
916  }
917  else
918  {
919  if( dir_prev.Angle( drag_dir )
921  {
922  guideA[0] = SEG( s_prev.A, s_prev.A + drag_dir.Left().ToVector() );
923  guideA[1] = SEG( s_prev.A, s_prev.A + drag_dir.Right().ToVector() );
924  }
925  else
926  guideA[0] = guideA[1] = SEG( dragged.A, dragged.A + dir_prev.ToVector() );
927  }
928 
929  if( aIndex == m_line.SegmentCount() - 1 )
930  {
931  guideB[0] = SEG( dragged.B, dragged.B + drag_dir.Right().ToVector() );
932  guideB[1] = SEG( dragged.B, dragged.B + drag_dir.Left().ToVector() );
933  }
934  else
935  {
936  if( dir_next.Angle( drag_dir )
938  {
939  guideB[0] = SEG( s_next.B, s_next.B + drag_dir.Left().ToVector() );
940  guideB[1] = SEG( s_next.B, s_next.B + drag_dir.Right().ToVector() );
941  }
942  else
943  guideB[0] = guideB[1] = SEG( dragged.B, dragged.B + dir_next.ToVector() );
944  }
945 
946  SEG s_current( target, target + drag_dir.ToVector() );
947 
948  int best_len = INT_MAX;
949  SHAPE_LINE_CHAIN best;
950 
951  for( int i = 0; i < 2; i++ )
952  {
953  for( int j = 0; j < 2; j++ )
954  {
955  OPT_VECTOR2I ip1 = s_current.IntersectLines( guideA[i] );
956  OPT_VECTOR2I ip2 = s_current.IntersectLines( guideB[j] );
957 
958  SHAPE_LINE_CHAIN np;
959 
960  if( !ip1 || !ip2 )
961  continue;
962 
963  SEG s1( s_prev.A, *ip1 );
964  SEG s2( *ip1, *ip2 );
965  SEG s3( *ip2, s_next.B );
966 
967  OPT_VECTOR2I ip;
968 
969  if( ( ip = s1.Intersect( s_next ) ) )
970  {
971  np.Append( s1.A );
972  np.Append( *ip );
973  np.Append( s_next.B );
974  }
975  else if( ( ip = s3.Intersect( s_prev ) ) )
976  {
977  np.Append( s_prev.A );
978  np.Append( *ip );
979  np.Append( s3.B );
980  }
981  else if( ( ip = s1.Intersect( s3 ) ) )
982  {
983  np.Append( s_prev.A );
984  np.Append( *ip );
985  np.Append( s_next.B );
986  }
987  else
988  {
989  np.Append( s_prev.A );
990  np.Append( *ip1 );
991  np.Append( *ip2 );
992  np.Append( s_next.B );
993  }
994 
995  if( np.Length() < best_len )
996  {
997  best_len = np.Length();
998  best = np;
999  }
1000  }
1001  }
1002 
1003  if( m_line.PointCount() == 1 )
1004  m_line = best;
1005  else if( aIndex == 0 )
1006  m_line.Replace( 0, 1, best );
1007  else if( aIndex == m_line.SegmentCount() - 1 )
1008  m_line.Replace( -2, -1, best );
1009  else
1010  m_line.Replace( aIndex, aIndex + 1, best );
1011 
1012  m_line.Simplify();
1013 }
1014 
1015 
1016 bool LINE::CompareGeometry( const LINE& aOther )
1017 {
1018  return m_line.CompareGeometry( aOther.m_line );
1019 }
1020 
1021 
1023 {
1024  m_line = m_line.Reverse();
1025 
1026  std::reverse( m_links.begin(), m_links.end() );
1027 }
1028 
1029 
1030 void LINE::AppendVia( const VIA& aVia )
1031 {
1032  if( m_line.PointCount() > 1 && aVia.Pos() == m_line.CPoint( 0 ) )
1033  {
1034  Reverse();
1035  }
1036 
1037  m_hasVia = true;
1038  m_via = aVia;
1039  m_via.SetNet( m_net );
1040 }
1041 
1042 
1043 void LINE::SetRank( int aRank )
1044 {
1045  m_rank = aRank;
1046 
1047  for( auto s : m_links )
1048  s->SetRank( aRank );
1049 
1050 }
1051 
1052 
1053 int LINE::Rank() const
1054 {
1055  int min_rank = INT_MAX;
1056 
1057  if( IsLinked() ) {
1058  for( auto s : m_links )
1059  {
1060  min_rank = std::min( min_rank, s->Rank() );
1061  }
1062  } else {
1063  min_rank = m_rank;
1064  }
1065 
1066  int rank = ( min_rank == INT_MAX ) ? -1 : min_rank;
1067 
1068  return rank;
1069 }
1070 
1071 
1072 void LINE::ClipVertexRange( int aStart, int aEnd )
1073 {
1080  int firstLink = 0;
1081  int lastLink = std::max( 0, static_cast<int>( m_links.size() ) - 1 );
1082  int arcIdx = -1;
1083  int linkIdx = 0;
1084 
1085  int numPoints = static_cast<int>( m_line.PointCount() );
1086 
1087  for( int i = 0; i < m_line.PointCount(); i = m_line.NextShape( i ) )
1088  {
1089  if( i <= aStart )
1090  firstLink = linkIdx;
1091 
1092  if( i < 0 || i >= aEnd - 1 || linkIdx >= lastLink )
1093  {
1094  lastLink = linkIdx;
1095  break;
1096  }
1097 
1098  linkIdx++;
1099  }
1100 
1101  wxASSERT( lastLink >= firstLink );
1102 
1103  m_line = m_line.Slice( aStart, aEnd );
1104 
1105  if( IsLinked() )
1106  {
1107  wxASSERT( m_links.size() < INT_MAX );
1108  wxASSERT( static_cast<int>( m_links.size() ) >= ( lastLink - firstLink ) );
1109 
1110  // Note: The range includes aEnd, but we have n-1 segments.
1111  std::rotate(
1112  m_links.begin(),
1113  m_links.begin() + firstLink,
1114  m_links.begin() + lastLink
1115  );
1116 
1117  m_links.resize( lastLink - firstLink + 1 );
1118  }
1119 }
1120 
1121 
1122 bool LINE::HasLoops() const
1123 {
1124  for( int i = 0; i < PointCount(); i++ )
1125  {
1126  for( int j = i + 2; j < PointCount(); j++ )
1127  {
1128  if( CPoint( i ) == CPoint( j ) )
1129  return true;
1130  }
1131  }
1132 
1133  return false;
1134 }
1135 
1136 
1137 static void extendBox( BOX2I& aBox, bool& aDefined, const VECTOR2I& aP )
1138 {
1139  if( aDefined )
1140  {
1141  aBox.Merge( aP );
1142  }
1143  else
1144  {
1145  aBox = BOX2I( aP, VECTOR2I( 0, 0 ) );
1146  aDefined = true;
1147  }
1148 }
1149 
1150 
1151 OPT_BOX2I LINE::ChangedArea( const LINE* aOther ) const
1152 {
1153  BOX2I area;
1154  bool areaDefined = false;
1155 
1156  int i_start = -1;
1157  int i_end_self = -1, i_end_other = -1;
1158 
1159  SHAPE_LINE_CHAIN self( m_line );
1160  self.Simplify();
1161  SHAPE_LINE_CHAIN other( aOther->m_line );
1162  other.Simplify();
1163 
1164  int np_self = self.PointCount();
1165  int np_other = other.PointCount();
1166 
1167  int n = std::min( np_self, np_other );
1168 
1169  for( int i = 0; i < n; i++ )
1170  {
1171  const VECTOR2I p1 = self.CPoint( i );
1172  const VECTOR2I p2 = other.CPoint( i );
1173 
1174  if( p1 != p2 )
1175  {
1176  if( i != n - 1 )
1177  {
1178  SEG s = self.CSegment( i );
1179 
1180  if( !s.Contains( p2 ) )
1181  {
1182  i_start = i;
1183  break;
1184  }
1185  }
1186  else
1187  {
1188  i_start = i;
1189  break;
1190  }
1191  }
1192  }
1193 
1194  for( int i = 0; i < n; i++ )
1195  {
1196  const VECTOR2I p1 = self.CPoint( np_self - 1 - i );
1197  const VECTOR2I p2 = other.CPoint( np_other - 1 - i );
1198 
1199  if( p1 != p2 )
1200  {
1201  i_end_self = np_self - 1 - i;
1202  i_end_other = np_other - 1 - i;
1203  break;
1204  }
1205  }
1206 
1207  if( i_start < 0 )
1208  i_start = n;
1209 
1210  if( i_end_self < 0 )
1211  i_end_self = np_self - 1;
1212 
1213  if( i_end_other < 0 )
1214  i_end_other = np_other - 1;
1215 
1216  for( int i = i_start; i <= i_end_self; i++ )
1217  extendBox( area, areaDefined, self.CPoint( i ) );
1218 
1219  for( int i = i_start; i <= i_end_other; i++ )
1220  extendBox( area, areaDefined, other.CPoint( i ) );
1221 
1222  if( areaDefined )
1223  {
1224  area.Inflate( std::max( Width(), aOther->Width() ) );
1225  return area;
1226  }
1227 
1228  return OPT_BOX2I();
1229 }
1230 
1231 
1233 {
1234  for( const auto seg : m_links )
1235  {
1236  if( seg->Marker() & MK_LOCKED )
1237  return true;
1238  }
1239  return false;
1240 }
1241 
1243 {
1244  m_hasVia = false;
1245  m_line.Clear();
1246 }
1247 
1248 
1249 }
1250 
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:146
int Length() const
Return the length (this).
Definition: seg.h:350
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:137
void HullIntersection(const SHAPE_LINE_CHAIN &hull, const SHAPE_LINE_CHAIN &line, SHAPE_LINE_CHAIN::INTERSECTIONS &ips)
Definition: pns_utils.cpp:275
long long int Length() const
Return length of the line chain in Euclidean metric.
int Split(const VECTOR2I &aP)
Insert the point aP belonging to one of the our segments, splitting the adjacent segment in two.
BOX2< VECTOR2I > BOX2I
Definition: box2.h:506
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:1151
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:747
LINE & operator=(const LINE &aOther)
Definition: pns_line.cpp:60
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
void SetPoint(int aIndex, const VECTOR2I &aPos)
Move a point to a specific location.
VECTOR2I snapToNeighbourSegments(const SHAPE_LINE_CHAIN &aPath, const VECTOR2I &aP, int aIndex) const
Definition: pns_line.cpp:801
bool Is45Degree() const
Print out all linked segments.
Definition: pns_line.cpp:537
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:154
int Rank() const override
Definition: pns_line.cpp:1053
const VECTOR2I ToVector() const
Definition: direction45.h:274
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Return a subset of this line chain containing the [start_index, end_index] range of points.
int Width() const
Get 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:245
void RemoveVia()
Definition: pns_line.h:194
LAYER_RANGE m_layers
Definition: pns_item.h:246
int m_rank
Definition: pns_item.h:251
Text appears outside the dimension line (default)
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:1030
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
Definition: seg.h:209
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.cpp:297
bool m_movable
Definition: pns_item.h:248
SHAPE_LINE_CHAIN g_pnew
Definition: pns_line.cpp:169
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
Reverse point order in the line chain.
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
int PointCount() const
Return the number of points (vertices) in this line chain.
const VECTOR2I & Pos() const
Definition: pns_via.h:99
const SHAPE_LINE_CHAIN Hull(int aClearance, int aWalkaroundThickness, int aLayer=-1) const override
Definition: pns_line.cpp:531
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:123
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
int m_marker
Definition: pns_item.h:250
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:593
void SetNet(int aNet)
Definition: pns_item.h:149
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)
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
Return a reference to a given point in the line chain.
void Reverse()
Clip the line to the nearest obstacle, traversing from the line's start vertex (0).
Definition: pns_line.cpp:1022
bool IsArcSegment(size_t aSegment) const
OPT< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:38
int Find(const VECTOR2I &aP, int aThreshold=0) const
Search for point aP.
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:1072
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:566
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
Definition: seg.cpp:227
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.
bool m_hasVia
Optional via at the end point.
Definition: pns_line.h:249
void Remove(int aStartIndex, int aEndIndex)
Remove the range of points [start_index, end_index] from the line chain.
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition: box2.h:363
void SetRank(int aRank) override
Definition: pns_line.cpp:1043
int SegmentCount() const
Return the number of segments in this line chain.
virtual const VECTOR2I GetPoint(int aIndex) const override
bool IsPtOnArc(size_t aPtIndex) const
SHAPE_LINE_CHAIN g_hnew
Definition: pns_line.cpp:169
int m_net
Definition: pns_item.h:249
void dragCorner45(const VECTOR2I &aP, int aIndex)
Definition: pns_line.cpp:676
static int areNeighbours(int x, int y, int max=0)
Definition: pns_line.cpp:156
OPT_OBSTACLE NearestObstacle(const LINE *aLine, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=nullptr)
Follow the line in search of an obstacle that is nearest to the starting to the line's starting point...
Definition: pns_node.cpp:296
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:136
void DragCorner(const VECTOR2I &aP, int aIndex, bool aFreeAngle=false)
Definition: pns_line.cpp:733
Definition: seg.h:40
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:281
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
Return a constant copy of the aIndex segment in the line chain.
Represent a polyline (an zero-thickness chain of connected line segments).
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:1137
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
bool HasLoops() const
Definition: pns_line.cpp:1122
VECTOR2I A
Definition: seg.h:48
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:509
boost::optional< T > OPT
Definition: optional.h:7
void Clear()
Remove 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:846
void Clear()
Definition: pns_line.cpp:1242
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Replace points with indices in range [start_index, end_index] with a single point aP.
int NextShape(int aPointIndex, bool aForwards=true) const
Return the vertex index of the next shape in the chain, or -1 if aPointIndex is the last shape.
bool CompareGeometry(const LINE &aOther)
Reverse the point/vertex order.
Definition: pns_line.cpp:1016
Push and Shove diff pair dimensions (gap) settings dialog.
void dragCornerFree(const VECTOR2I &aP, int aIndex)
Definition: pns_line.cpp:706
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:1232
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:331
VECTOR2I B
Definition: seg.h:49
VECTOR2I snapDraggedCorner(const SHAPE_LINE_CHAIN &aPath, const VECTOR2I &aP, int aIndex) const
Definition: pns_line.cpp:759