KiCad PCB EDA Suite
shape_line_chain.cpp
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2013-2017 CERN
5  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * as published by the Free Software Foundation; either version 2
10  * of the License, or (at your option) any later version.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, you may find one here:
19  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
20  * or you may search the http://www.gnu.org website for the version 2 license,
21  * or you may write to the Free Software Foundation, Inc.,
22  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
23  */
24 
25 #include <algorithm>
26 #include <limits.h> // for INT_MAX
27 #include <math.h> // for hypot
28 #include <string> // for basic_string
29 
30 #include <clipper.hpp>
31 #include <geometry/seg.h> // for SEG, OPT_VECTOR2I
33 #include <math/box2.h> // for BOX2I
34 #include <math/util.h> // for rescale
35 #include <math/vector2d.h> // for VECTOR2, VECTOR2I
36 
37 class SHAPE;
38 
39 SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN( const std::vector<int>& aV)
40  : SHAPE_LINE_CHAIN_BASE( SH_LINE_CHAIN ), m_closed( false ), m_width( 0 )
41 {
42  for(size_t i = 0; i < aV.size(); i+= 2 )
43  {
44  Append( aV[i], aV[i+1] );
45  }
46 }
47 
48 ClipperLib::Path SHAPE_LINE_CHAIN::convertToClipper( bool aRequiredOrientation ) const
49 {
50  ClipperLib::Path c_path;
51 
52  for( int i = 0; i < PointCount(); i++ )
53  {
54  const VECTOR2I& vertex = CPoint( i );
55  c_path.push_back( ClipperLib::IntPoint( vertex.x, vertex.y ) );
56  }
57 
58  if( Orientation( c_path ) != aRequiredOrientation )
59  ReversePath( c_path );
60 
61  return c_path;
62 }
63 
64 
65 //TODO(SH): Adjust this into two functions: one to convert and one to split the arc into two arcs
66 void SHAPE_LINE_CHAIN::convertArc( ssize_t aArcIndex )
67 {
68  if( aArcIndex < 0 )
69  aArcIndex += m_arcs.size();
70 
71  if( aArcIndex >= static_cast<ssize_t>( m_arcs.size() ) )
72  return;
73 
74  // Clear the shapes references
75  for( auto& sh : m_shapes )
76  {
77  if( sh == aArcIndex )
78  sh = SHAPE_IS_PT;
79 
80  if( sh > aArcIndex )
81  --sh;
82  }
83 
84  m_arcs.erase( m_arcs.begin() + aArcIndex );
85 }
86 
87 
88 bool SHAPE_LINE_CHAIN_BASE::Collide( const VECTOR2I& aP, int aClearance, int* aActual,
89  VECTOR2I* aLocation ) const
90 {
91  if( IsClosed() && PointInside( aP, aClearance ) )
92  {
93  if( aLocation )
94  *aLocation = aP;
95 
96  if( aActual )
97  *aActual = 0;
98 
99  return true;
100  }
101 
102  SEG::ecoord closest_dist_sq = VECTOR2I::ECOORD_MAX;
103  SEG::ecoord clearance_sq = SEG::Square( aClearance );
104  VECTOR2I nearest;
105 
106  for( size_t i = 0; i < GetSegmentCount(); i++ )
107  {
108  const SEG& s = GetSegment( i );
109  VECTOR2I pn = s.NearestPoint( aP );
110  SEG::ecoord dist_sq = ( pn - aP ).SquaredEuclideanNorm();
111 
112  if( dist_sq < closest_dist_sq )
113  {
114  nearest = pn;
115  closest_dist_sq = dist_sq;
116 
117  if( closest_dist_sq == 0 )
118  break;
119 
120  // If we're not looking for aActual then any collision will do
121  if( closest_dist_sq < clearance_sq && !aActual )
122  break;
123  }
124  }
125 
126  if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
127  {
128  if( aLocation )
129  *aLocation = nearest;
130 
131  if( aActual )
132  *aActual = sqrt( closest_dist_sq );
133 
134  return true;
135  }
136 
137  return false;
138 }
139 
140 
141 void SHAPE_LINE_CHAIN::Rotate( double aAngle, const VECTOR2I& aCenter )
142 {
143  for( auto& pt : m_points )
144  {
145  pt -= aCenter;
146  pt = pt.Rotate( aAngle );
147  pt += aCenter;
148  }
149 
150  for( auto& arc : m_arcs )
151  arc.Rotate( aAngle, aCenter );
152 }
153 
154 
155 bool SHAPE_LINE_CHAIN_BASE::Collide( const SEG& aSeg, int aClearance, int* aActual,
156  VECTOR2I* aLocation ) const
157 {
158  if( IsClosed() && PointInside( aSeg.A ) )
159  {
160  if( aLocation )
161  *aLocation = aSeg.A;
162 
163  if( aActual )
164  *aActual = 0;
165 
166  return true;
167  }
168 
169  SEG::ecoord closest_dist_sq = VECTOR2I::ECOORD_MAX;
170  SEG::ecoord clearance_sq = SEG::Square( aClearance );
171  VECTOR2I nearest;
172 
173  for( size_t i = 0; i < GetSegmentCount(); i++ )
174  {
175  const SEG& s = GetSegment( i );
176  SEG::ecoord dist_sq =s.SquaredDistance( aSeg );
177 
178  if( dist_sq < closest_dist_sq )
179  {
180  if( aLocation )
181  nearest = s.NearestPoint( aSeg );
182 
183  closest_dist_sq = dist_sq;
184 
185  if( closest_dist_sq == 0)
186  break;
187 
188  // If we're not looking for aActual then any collision will do
189  if( closest_dist_sq < clearance_sq && !aActual )
190  break;
191  }
192  }
193 
194  if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
195  {
196  if( aLocation )
197  *aLocation = nearest;
198 
199  if( aActual )
200  *aActual = sqrt( closest_dist_sq );
201 
202  return true;
203  }
204 
205  return false;
206 }
207 
208 
210 {
211  SHAPE_LINE_CHAIN a( *this );
212 
213  reverse( a.m_points.begin(), a.m_points.end() );
214  reverse( a.m_shapes.begin(), a.m_shapes.end() );
215  reverse( a.m_arcs.begin(), a.m_arcs.end() );
216 
217  for( auto& sh : a.m_shapes )
218  {
219  if( sh != SHAPE_IS_PT )
220  sh = a.m_arcs.size() - sh - 1;
221  }
222 
223  for( SHAPE_ARC& arc : a.m_arcs )
224  arc.Reverse();
225 
226  a.m_closed = m_closed;
227 
228  return a;
229 }
230 
231 
232 long long int SHAPE_LINE_CHAIN::Length() const
233 {
234  long long int l = 0;
235 
236  for( int i = 0; i < SegmentCount(); i++ )
237  l += CSegment( i ).Length();
238 
239  return l;
240 }
241 
242 
243 void SHAPE_LINE_CHAIN::Mirror( bool aX, bool aY, const VECTOR2I& aRef )
244 {
245  for( auto& pt : m_points )
246  {
247  if( aX )
248  pt.x = -pt.x + 2 * aRef.x;
249 
250  if( aY )
251  pt.y = -pt.y + 2 * aRef.y;
252  }
253 
254  for( auto& arc : m_arcs )
255  arc.Mirror( aX, aY, aRef );
256 }
257 
258 
259 void SHAPE_LINE_CHAIN::Replace( int aStartIndex, int aEndIndex, const VECTOR2I& aP )
260 {
261  if( aEndIndex < 0 )
262  aEndIndex += PointCount();
263 
264  if( aStartIndex < 0 )
265  aStartIndex += PointCount();
266 
267  aEndIndex = std::min( aEndIndex, PointCount() - 1 );
268 
269  // N.B. This works because convertArc changes m_shapes on the first run
270  for( int ind = aStartIndex; ind <= aEndIndex; ind++ )
271  {
272  if( m_shapes[ind] != SHAPE_IS_PT )
273  convertArc( ind );
274  }
275 
276  if( aStartIndex == aEndIndex )
277  m_points[aStartIndex] = aP;
278  else
279  {
280  m_points.erase( m_points.begin() + aStartIndex + 1, m_points.begin() + aEndIndex + 1 );
281  m_points[aStartIndex] = aP;
282 
283  m_shapes.erase( m_shapes.begin() + aStartIndex + 1, m_shapes.begin() + aEndIndex + 1 );
284  }
285 
286  assert( m_shapes.size() == m_points.size() );
287 }
288 
289 
290 void SHAPE_LINE_CHAIN::Replace( int aStartIndex, int aEndIndex, const SHAPE_LINE_CHAIN& aLine )
291 {
292  if( aEndIndex < 0 )
293  aEndIndex += PointCount();
294 
295  if( aStartIndex < 0 )
296  aStartIndex += PointCount();
297 
298  Remove( aStartIndex, aEndIndex );
299 
300  // The total new arcs index is added to the new arc indices
301  size_t prev_arc_count = m_arcs.size();
302  auto new_shapes = aLine.m_shapes;
303 
304  for( auto& shape : new_shapes )
305  shape += prev_arc_count;
306 
307  m_shapes.insert( m_shapes.begin() + aStartIndex, new_shapes.begin(), new_shapes.end() );
308  m_points.insert( m_points.begin() + aStartIndex, aLine.m_points.begin(), aLine.m_points.end() );
309  m_arcs.insert( m_arcs.end(), aLine.m_arcs.begin(), aLine.m_arcs.end() );
310 
311  assert( m_shapes.size() == m_points.size() );
312 }
313 
314 
315 void SHAPE_LINE_CHAIN::Remove( int aStartIndex, int aEndIndex )
316 {
317  assert( m_shapes.size() == m_points.size() );
318  if( aEndIndex < 0 )
319  aEndIndex += PointCount();
320 
321  if( aStartIndex < 0 )
322  aStartIndex += PointCount();
323 
324  if( aStartIndex >= PointCount() )
325  return;
326 
327  aEndIndex = std::min( aEndIndex, PointCount() );
328  std::set<size_t> extra_arcs;
329 
330  // Remove any overlapping arcs in the point range
331  for( int i = aStartIndex; i < aEndIndex; i++ )
332  {
333  if( m_shapes[i] != SHAPE_IS_PT )
334  extra_arcs.insert( m_shapes[i] );
335  }
336 
337  for( auto arc : extra_arcs )
338  convertArc( arc );
339 
340  m_shapes.erase( m_shapes.begin() + aStartIndex, m_shapes.begin() + aEndIndex + 1 );
341  m_points.erase( m_points.begin() + aStartIndex, m_points.begin() + aEndIndex + 1 );
342  assert( m_shapes.size() == m_points.size() );
343 }
344 
345 
346 int SHAPE_LINE_CHAIN::Distance( const VECTOR2I& aP, bool aOutlineOnly ) const
347 {
348  return sqrt( SquaredDistance( aP, aOutlineOnly ) );
349 }
350 
351 
352 SEG::ecoord SHAPE_LINE_CHAIN_BASE::SquaredDistance( const VECTOR2I& aP, bool aOutlineOnly ) const
353 {
355 
356  if( IsClosed() && PointInside( aP ) && !aOutlineOnly )
357  return 0;
358 
359  for( size_t s = 0; s < GetSegmentCount(); s++ )
360  d = std::min( d, GetSegment( s ).SquaredDistance( aP ) );
361 
362  return d;
363 }
364 
365 
367 {
368  int ii = -1;
369  int min_dist = 2;
370 
371  int found_index = Find( aP );
372 
373  for( int s = 0; s < SegmentCount(); s++ )
374  {
375  const SEG seg = CSegment( s );
376  int dist = seg.Distance( aP );
377 
378  // make sure we are not producing a 'slightly concave' primitive. This might happen
379  // if aP lies very close to one of already existing points.
380  if( dist < min_dist && seg.A != aP && seg.B != aP )
381  {
382  min_dist = dist;
383  if( found_index < 0 )
384  ii = s;
385  else if( s < found_index )
386  ii = s;
387  }
388  }
389 
390  if( ii < 0 )
391  ii = found_index;
392 
393  if( ii >= 0 )
394  {
395  // Are we splitting at the beginning of an arc? If so, let's split right before so that
396  // the shape is preserved
397  if( ii < PointCount() - 1 && m_shapes[ii] >= 0 && m_shapes[ii] == m_shapes[ii + 1] )
398  ii--;
399 
400  m_points.insert( m_points.begin() + ii + 1, aP );
401  m_shapes.insert( m_shapes.begin() + ii + 1, ssize_t( SHAPE_IS_PT ) );
402 
403  return ii + 1;
404  }
405 
406  return -1;
407 }
408 
409 
410 int SHAPE_LINE_CHAIN::Find( const VECTOR2I& aP ) const
411 {
412  for( int s = 0; s < PointCount(); s++ )
413  if( CPoint( s ) == aP )
414  return s;
415 
416  return -1;
417 }
418 
419 
421 {
422  for( int s = 0; s < SegmentCount(); s++ )
423  if( CSegment( s ).Distance( aP ) <= 1 )
424  return s;
425 
426  return -1;
427 }
428 
429 
431 {
432  if( m_points.empty() )
433  return 0;
434 
435  int numPoints = static_cast<int>( m_shapes.size() );
436  int numShapes = 0;
437  int arcIdx = -1;
438 
439  for( int i = 0; i < m_points.size() - 1; i++ )
440  {
441  if( m_shapes[i] == SHAPE_IS_PT )
442  {
443  numShapes++;
444  }
445  else
446  {
447  arcIdx = m_shapes[i];
448  numShapes++;
449 
450  // Now skip the rest of the arc
451  while( i < numPoints && m_shapes[i] == arcIdx )
452  i++;
453 
454  // Is there another arc right after? Add the "hidden" segment
455  if( i < numPoints &&
456  m_shapes[i] != SHAPE_IS_PT &&
457  m_shapes[i] != arcIdx &&
458  m_points[i] != m_points[i - 1] )
459  {
460  numShapes++;
461  }
462 
463  i--;
464  }
465  }
466 
467  return numShapes;
468 }
469 
470 
471 int SHAPE_LINE_CHAIN::NextShape( int aPointIndex, bool aForwards ) const
472 {
473  if( aPointIndex < 0 )
474  aPointIndex += PointCount();
475 
476  // First or last point?
477  if( ( aForwards && aPointIndex == PointCount() - 1 ) ||
478  ( !aForwards && aPointIndex == 0 ) )
479  {
480  return -1;
481  }
482 
483  int delta = aForwards ? 1 : -1;
484 
485  if( m_shapes[aPointIndex] == SHAPE_IS_PT )
486  return aPointIndex + delta;
487 
488  int arcIndex = m_shapes[aPointIndex];
489  int arcStart = aPointIndex;
490 
491  while( aPointIndex < static_cast<int>( m_shapes.size() ) && m_shapes[aPointIndex] == arcIndex )
492  aPointIndex += delta;
493 
494  // We want the last vertex of the arc if the initial point was the start of one
495  // Well-formed arcs should generate more than one point to travel above
496  if( aPointIndex - arcStart > 1 )
497  aPointIndex -= delta;
498 
499  return aPointIndex;
500 }
501 
502 
503 void SHAPE_LINE_CHAIN::RemoveShape( int aPointIndex )
504 {
505  if( aPointIndex < 0 )
506  aPointIndex += PointCount();
507 
508  if( m_shapes[aPointIndex] == SHAPE_IS_PT )
509  {
510  Remove( aPointIndex );
511  return;
512  }
513 
514  int start = aPointIndex;
515  int end = aPointIndex;
516  int arcIdx = m_shapes[aPointIndex];
517 
518  while( start >= 0 && m_shapes[start] == arcIdx )
519  start--;
520 
521  while( end < static_cast<int>( m_shapes.size() ) - 1 && m_shapes[end] == arcIdx )
522  end++;
523 
524  Remove( start, end );
525 }
526 
527 
528 const SHAPE_LINE_CHAIN SHAPE_LINE_CHAIN::Slice( int aStartIndex, int aEndIndex ) const
529 {
530  SHAPE_LINE_CHAIN rv;
531 
532  if( aEndIndex < 0 )
533  aEndIndex += PointCount();
534 
535  if( aStartIndex < 0 )
536  aStartIndex += PointCount();
537 
538  int numPoints = static_cast<int>( m_points.size() );
539 
540  for( int i = aStartIndex; i <= aEndIndex && i < numPoints; i++ )
541  {
542  if( m_shapes[i] != SHAPE_IS_PT )
543  {
544  int arcIdx = m_shapes[i];
545  bool wholeArc = true;
546  int arcStart = i;
547 
548  if( i > 0 && m_shapes[i - 1] >= 0 && m_shapes[i - 1] != arcIdx )
549  wholeArc = false;
550 
551  while( i < numPoints && m_shapes[i] == arcIdx )
552  i++;
553 
554  i--;
555 
556  if( i > aEndIndex )
557  wholeArc = false;
558 
559  if( wholeArc )
560  {
561  rv.Append( m_arcs[arcIdx] );
562  }
563  else
564  {
565  rv.Append( m_points[arcStart] );
566  i = arcStart;
567  }
568  }
569  else
570  {
571  rv.Append( m_points[i] );
572  }
573  }
574 
575  return rv;
576 }
577 
578 
580 {
581  assert( m_shapes.size() == m_points.size() );
582 
583  if( aOtherLine.PointCount() == 0 )
584  return;
585 
586  else if( PointCount() == 0 || aOtherLine.CPoint( 0 ) != CPoint( -1 ) )
587  {
588  const VECTOR2I p = aOtherLine.CPoint( 0 );
589  m_points.push_back( p );
590  m_shapes.push_back( aOtherLine.CShapes()[0] );
591  m_bbox.Merge( p );
592  }
593 
594  size_t num_arcs = m_arcs.size();
595  m_arcs.insert( m_arcs.end(), aOtherLine.m_arcs.begin(), aOtherLine.m_arcs.end() );
596 
597  for( int i = 1; i < aOtherLine.PointCount(); i++ )
598  {
599  const VECTOR2I p = aOtherLine.CPoint( i );
600  m_points.push_back( p );
601 
602  ssize_t arcIndex = aOtherLine.ArcIndex( i );
603 
604  if( arcIndex != ssize_t( SHAPE_IS_PT ) )
605  m_shapes.push_back( num_arcs + arcIndex );
606  else
607  m_shapes.push_back( ssize_t( SHAPE_IS_PT ) );
608 
609  m_bbox.Merge( p );
610  }
611 
612  assert( m_shapes.size() == m_points.size() );
613 }
614 
615 
617 {
618  auto& chain = aArc.ConvertToPolyline();
619 
620  for( auto& pt : chain.CPoints() )
621  {
622  m_points.push_back( pt );
623  m_shapes.push_back( m_arcs.size() );
624  }
625 
626  m_arcs.push_back( aArc );
627 
628  assert( m_shapes.size() == m_points.size() );
629 }
630 
631 
632 void SHAPE_LINE_CHAIN::Insert( size_t aVertex, const VECTOR2I& aP )
633 {
634  if( m_shapes[aVertex] != SHAPE_IS_PT )
635  convertArc( aVertex );
636 
637  m_points.insert( m_points.begin() + aVertex, aP );
638  m_shapes.insert( m_shapes.begin() + aVertex, ssize_t( SHAPE_IS_PT ) );
639 
640  assert( m_shapes.size() == m_points.size() );
641 }
642 
643 
644 void SHAPE_LINE_CHAIN::Insert( size_t aVertex, const SHAPE_ARC& aArc )
645 {
646  if( m_shapes[aVertex] != SHAPE_IS_PT )
647  convertArc( aVertex );
648 
650  size_t arc_pos = m_arcs.size();
651 
652  for( auto arc_it = m_shapes.rbegin() ;
653  arc_it != m_shapes.rend() + aVertex;
654  arc_it++ )
655  {
656  if( *arc_it != SHAPE_IS_PT )
657  arc_pos = ( *arc_it )++;
658  }
659 
660  m_arcs.insert( m_arcs.begin() + arc_pos, aArc );
661 
663  auto& chain = aArc.ConvertToPolyline();
664  m_points.insert( m_points.begin() + aVertex,
665  chain.CPoints().begin(), chain.CPoints().end() );
666 
668  std::vector<size_t> new_points( chain.PointCount(), arc_pos );
669  m_shapes.insert( m_shapes.begin() + aVertex, new_points.begin(), new_points.end() );
670  assert( m_shapes.size() == m_points.size() );
671 }
672 
673 
675 {
676  compareOriginDistance( const VECTOR2I& aOrigin ) :
677  m_origin( aOrigin ) {};
678 
680  const SHAPE_LINE_CHAIN::INTERSECTION& aB ) const
681  {
682  return ( m_origin - aA.p ).EuclideanNorm() < ( m_origin - aB.p ).EuclideanNorm();
683  }
684 
686 };
687 
688 
689 int SHAPE_LINE_CHAIN::Intersect( const SEG& aSeg, INTERSECTIONS& aIp ) const
690 {
691  for( int s = 0; s < SegmentCount(); s++ )
692  {
693  OPT_VECTOR2I p = CSegment( s ).Intersect( aSeg );
694 
695  if( p )
696  {
697  INTERSECTION is;
698  is.our = CSegment( s );
699  is.their = aSeg;
700  is.p = *p;
701  aIp.push_back( is );
702  }
703  }
704 
705  compareOriginDistance comp( aSeg.A );
706  sort( aIp.begin(), aIp.end(), comp );
707 
708  return aIp.size();
709 }
710 
712 {
713  if( aIps.size() == 0 )
714  {
715  aIps.push_back( aP );
716  return;
717  }
718 
719  const auto& last = aIps.back();
720 
721  if( ( (last.our.Index() + 1) % aPc) == aP.our.Index() && last.p == aP.p )
722  return;
723 
724  if( last.our.Index() == aP.our.Index() && last.p == aP.p )
725  return;
726 
727  aIps.push_back( aP );
728 }
729 
731 {
732  BOX2I bb_other = aChain.BBox();
733 
734  for( int s1 = 0; s1 < SegmentCount(); s1++ )
735  {
736  const SEG& a = CSegment( s1 );
737  const BOX2I bb_cur( a.A, a.B - a.A );
738 
739  if( !bb_other.Intersects( bb_cur ) )
740  continue;
741 
742  for( int s2 = 0; s2 < aChain.SegmentCount(); s2++ )
743  {
744  const SEG& b = aChain.CSegment( s2 );
745  INTERSECTION is;
746 
747  if( a.Collinear( b ) )
748  {
749  is.our = a;
750  is.their = b;
751 
752  if( a.Contains( b.A ) ) { is.p = b.A; addIntersection(aIp, PointCount(), is); }
753  if( a.Contains( b.B ) ) { is.p = b.B; addIntersection(aIp, PointCount(), is); }
754  if( b.Contains( a.A ) ) { is.p = a.A; addIntersection(aIp, PointCount(), is); }
755  if( b.Contains( a.B ) ) { is.p = a.B; addIntersection(aIp, PointCount(), is); }
756  }
757  else
758  {
759  OPT_VECTOR2I p = a.Intersect( b );
760 
761  if( p )
762  {
763  is.p = *p;
764  is.our = a;
765  is.their = b;
766  addIntersection(aIp, PointCount(), is);
767  }
768  }
769  }
770  }
771 
772  return aIp.size();
773 }
774 
775 
777 {
778  int sum = 0;
779 
780  for( int i = 0; i < SegmentCount(); i++ )
781  {
782  const SEG seg = CSegment( i );
783  int d = seg.Distance( aP );
784 
785  if( d <= 1 )
786  {
787  sum += ( aP - seg.A ).EuclideanNorm();
788  return sum;
789  }
790  else
791  sum += seg.Length();
792  }
793 
794  return -1;
795 }
796 
797 
798 bool SHAPE_LINE_CHAIN_BASE::PointInside( const VECTOR2I& aPt, int aAccuracy,
799  bool aUseBBoxCache ) const
800 {
801  /*
802  * Don't check the bounding box unless it's cached. Building it is about the same speed as
803  * the rigorous test below and so just slows things down by doing potentially two tests.
804  */
805  //if( aUseBBoxCache && !m_bbox.Contains( aPt ) )
806  //return false;
807 
808  // fixme: bbox cache...
809 
810  if( !IsClosed() || GetPointCount() < 3 )
811  return false;
812 
813  bool inside = false;
814 
826  int pointCount = GetPointCount();
827 
828  for( int i = 0; i < pointCount; )
829  {
830  const auto p1 = GetPoint( i++ );
831  const auto p2 = GetPoint( i == pointCount ? 0 : i );
832  const auto diff = p2 - p1;
833 
834  if( diff.y != 0 )
835  {
836  const int d = rescale( diff.x, ( aPt.y - p1.y ), diff.y );
837 
838  if( ( ( p1.y > aPt.y ) != ( p2.y > aPt.y ) ) && ( aPt.x - p1.x < d ) )
839  inside = !inside;
840  }
841  }
842 
843  // If accuracy is <= 1 (nm) then we skip the accuracy test for performance. Otherwise
844  // we use "OnEdge(accuracy)" as a proxy for "Inside(accuracy)".
845  if( aAccuracy <= 1 )
846  return inside;
847  else
848  return inside || PointOnEdge( aPt, aAccuracy );
849 }
850 
851 
852 bool SHAPE_LINE_CHAIN_BASE::PointOnEdge( const VECTOR2I& aPt, int aAccuracy ) const
853 {
854  return EdgeContainingPoint( aPt, aAccuracy ) >= 0;
855 }
856 
857 int SHAPE_LINE_CHAIN_BASE::EdgeContainingPoint( const VECTOR2I& aPt, int aAccuracy ) const
858 {
859  if( !GetPointCount() )
860  return -1;
861 
862  else if( GetPointCount() == 1 )
863  {
864  VECTOR2I dist = GetPoint(0) - aPt;
865  return ( hypot( dist.x, dist.y ) <= aAccuracy + 1 ) ? 0 : -1;
866  }
867 
868  for( size_t i = 0; i < GetSegmentCount(); i++ )
869  {
870  const SEG s = GetSegment( i );
871 
872  if( s.A == aPt || s.B == aPt )
873  return i;
874 
875  if( s.Distance( aPt ) <= aAccuracy + 1 )
876  return i;
877  }
878 
879  return -1;
880 }
881 
882 
883 bool SHAPE_LINE_CHAIN::CheckClearance( const VECTOR2I& aP, const int aDist) const
884 {
885  if( !PointCount() )
886  return false;
887 
888  else if( PointCount() == 1 )
889  return m_points[0] == aP;
890 
891  for( int i = 0; i < SegmentCount(); i++ )
892  {
893  const SEG s = CSegment( i );
894 
895  if( s.A == aP || s.B == aP )
896  return true;
897 
898  if( s.Distance( aP ) <= aDist )
899  return true;
900  }
901 
902  return false;
903 }
904 
905 
907 {
908  for( int s1 = 0; s1 < SegmentCount(); s1++ )
909  {
910  for( int s2 = s1 + 1; s2 < SegmentCount(); s2++ )
911  {
912  const VECTOR2I s2a = CSegment( s2 ).A, s2b = CSegment( s2 ).B;
913 
914  if( s1 + 1 != s2 && CSegment( s1 ).Contains( s2a ) )
915  {
916  INTERSECTION is;
917  is.our = CSegment( s1 );
918  is.their = CSegment( s2 );
919  is.p = s2a;
920  return is;
921  }
922  else if( CSegment( s1 ).Contains( s2b ) &&
923  // for closed polylines, the ending point of the
924  // last segment == starting point of the first segment
925  // this is a normal case, not self intersecting case
926  !( IsClosed() && s1 == 0 && s2 == SegmentCount()-1 ) )
927  {
928  INTERSECTION is;
929  is.our = CSegment( s1 );
930  is.their = CSegment( s2 );
931  is.p = s2b;
932  return is;
933  }
934  else
935  {
936  OPT_VECTOR2I p = CSegment( s1 ).Intersect( CSegment( s2 ), true );
937 
938  if( p )
939  {
940  INTERSECTION is;
941  is.our = CSegment( s1 );
942  is.their = CSegment( s2 );
943  is.p = *p;
944  return is;
945  }
946  }
947  }
948  }
949 
951 }
952 
953 
955 {
956  std::vector<VECTOR2I> pts_unique;
957  std::vector<ssize_t> shapes_unique;
958 
959  if( PointCount() < 2 )
960  {
961  return *this;
962  }
963  else if( PointCount() == 2 )
964  {
965  if( m_points[0] == m_points[1] )
966  m_points.pop_back();
967 
968  return *this;
969  }
970 
971  int i = 0;
972  int np = PointCount();
973 
974  // stage 1: eliminate duplicate vertices
975  while( i < np )
976  {
977  int j = i + 1;
978 
979  // We can eliminate duplicate vertices as long as they are part of the same shape, OR if
980  // one of them is part of a shape and one is not.
981  while( j < np && m_points[i] == m_points[j] &&
982  ( m_shapes[i] == m_shapes[j] ||
983  m_shapes[i] == SHAPE_IS_PT ||
984  m_shapes[j] == SHAPE_IS_PT ) )
985  {
986  j++;
987  }
988 
989  int shapeToKeep = m_shapes[i];
990 
991  if( shapeToKeep == SHAPE_IS_PT )
992  shapeToKeep = m_shapes[j - 1];
993 
994  wxASSERT( shapeToKeep < static_cast<int>( m_arcs.size() ) );
995 
996  pts_unique.push_back( CPoint( i ) );
997  shapes_unique.push_back( shapeToKeep );
998 
999  i = j;
1000  }
1001 
1002  m_points.clear();
1003  m_shapes.clear();
1004  np = pts_unique.size();
1005 
1006  i = 0;
1007 
1008  // stage 2: eliminate colinear segments
1009  while( i < np - 2 )
1010  {
1011  const VECTOR2I p0 = pts_unique[i];
1012  const VECTOR2I p1 = pts_unique[i + 1];
1013  int n = i;
1014 
1015  if( aRemoveColinear )
1016  {
1017  while( n < np - 2
1018  && ( SEG( p0, p1 ).LineDistance( pts_unique[n + 2] ) <= 1
1019  || SEG( p0, p1 ).Collinear( SEG( p1, pts_unique[n + 2] ) ) ) )
1020  n++;
1021  }
1022 
1023  m_points.push_back( p0 );
1024  m_shapes.push_back( shapes_unique[i] );
1025 
1026  if( n > i )
1027  i = n;
1028 
1029  if( n == np - 2 )
1030  {
1031  m_points.push_back( pts_unique[np - 1] );
1032  m_shapes.push_back( shapes_unique[np - 1] );
1033  return *this;
1034  }
1035 
1036  i++;
1037  }
1038 
1039  if( np > 1 )
1040  {
1041  m_points.push_back( pts_unique[np - 2] );
1042  m_shapes.push_back( shapes_unique[np - 2] );
1043  }
1044 
1045  m_points.push_back( pts_unique[np - 1] );
1046  m_shapes.push_back( shapes_unique[np - 1] );
1047 
1048  assert( m_points.size() == m_shapes.size() );
1049 
1050  return *this;
1051 }
1052 
1053 
1055  bool aAllowInternalShapePoints ) const
1056 {
1057  int min_d = INT_MAX;
1058  int nearest = 0;
1059 
1060  for( int i = 0; i < SegmentCount(); i++ )
1061  {
1062  int d = CSegment( i ).Distance( aP );
1063 
1064  bool isInternalShapePoint = false;
1065 
1066  // An internal shape point here is everything after the start of an arc and before the
1067  // second-to-last vertex of the arc, because we are looking at segments here!
1068  if( i > 0 && i < SegmentCount() - 1 && m_shapes[i] >= 0 &&
1069  ( ( m_shapes[i - 1] >= 0 && m_shapes[i - 1] == m_shapes[i] ) &&
1070  ( m_shapes[i + 2] >= 0 && m_shapes[i + 2] == m_shapes[i] ) ) )
1071  {
1072  isInternalShapePoint = true;
1073  }
1074 
1075  if( ( d < min_d ) && ( aAllowInternalShapePoints || !isInternalShapePoint ) )
1076  {
1077  min_d = d;
1078  nearest = i;
1079  }
1080  }
1081 
1082  // Is this the start of an arc? If so, return it directly
1083  if( !aAllowInternalShapePoints &&
1084  ( ( nearest == 0 && m_shapes[nearest] >= 0 ) ||
1085  ( m_shapes[nearest] >= 0 && m_shapes[nearest] != m_shapes[nearest - 1] ) ) )
1086  {
1087  return m_points[nearest];
1088  }
1089  else if( !aAllowInternalShapePoints && nearest < SegmentCount() &&
1090  m_shapes[nearest] >= 0 && m_shapes[nearest + 1] == m_shapes[nearest] )
1091  {
1092  // If the nearest segment is the last of the arc, just return the arc endpoint
1093  return m_points[nearest + 1];
1094  }
1095 
1096  return CSegment( nearest ).NearestPoint( aP );
1097 }
1098 
1099 
1100 const VECTOR2I SHAPE_LINE_CHAIN::NearestPoint( const SEG& aSeg, int& dist ) const
1101 {
1102  int nearest = 0;
1103 
1104  dist = INT_MAX;
1105  for( int i = 0; i < PointCount(); i++ )
1106  {
1107  int d = aSeg.LineDistance( CPoint( i ) );
1108 
1109  if( d < dist )
1110  {
1111  dist = d;
1112  nearest = i;
1113  }
1114  }
1115 
1116  return CPoint( nearest );
1117 }
1118 
1119 
1121 {
1122  int min_d = INT_MAX;
1123  int nearest = 0;
1124 
1125  for( int i = 0; i < SegmentCount(); i++ )
1126  {
1127  int d = CSegment( i ).Distance( aP );
1128 
1129  if( d < min_d )
1130  {
1131  min_d = d;
1132  nearest = i;
1133  }
1134  }
1135 
1136  return nearest;
1137 }
1138 
1139 
1140 const std::string SHAPE_LINE_CHAIN::Format() const
1141 {
1142  std::stringstream ss;
1143 
1144 
1145  ss << "SHAPE_LINE_CHAIN( { ";
1146  for( int i = 0; i < PointCount(); i++ )
1147  {
1148  ss << "VECTOR2I( " << m_points[i].x << ", " << m_points[i].y << ")";
1149  if( i != PointCount() -1 )
1150  ss << ", ";
1151  }
1152 
1153  ss << "}, " << ( m_closed ? "true" : "false" );
1154  ss << " );";
1155 
1156 
1157 
1158  return ss.str();
1159 
1160 
1161  /* fixme: arcs
1162  for( size_t i = 0; i < m_arcs.size(); i++ )
1163  ss << m_arcs[i].GetCenter().x << " " << m_arcs[i].GetCenter().y << " "
1164  << m_arcs[i].GetP0().x << " " << m_arcs[i].GetP0().y << " "
1165  << m_arcs[i].GetCentralAngle();
1166 
1167  return ss.str();*/
1168 }
1169 
1170 
1172 {
1173  SHAPE_LINE_CHAIN a(*this), b( aOther );
1174  a.Simplify();
1175  b.Simplify();
1176 
1177  if( a.m_points.size() != b.m_points.size() )
1178  return false;
1179 
1180  for( int i = 0; i < a.PointCount(); i++)
1181  if( a.CPoint( i ) != b.CPoint( i ) )
1182  return false;
1183  return true;
1184 }
1185 
1186 
1188 {
1190  return Intersect( aChain, dummy ) != 0;
1191 }
1192 
1193 
1195 {
1196  return new SHAPE_LINE_CHAIN( *this );
1197 }
1198 
1199 bool SHAPE_LINE_CHAIN::Parse( std::stringstream& aStream )
1200 {
1201  size_t n_pts;
1202  size_t n_arcs;
1203 
1204  m_points.clear();
1205  aStream >> n_pts;
1206 
1207  // Rough sanity check, just make sure the loop bounds aren't absolutely outlandish
1208  if( n_pts > aStream.str().size() )
1209  return false;
1210 
1211  aStream >> m_closed;
1212  aStream >> n_arcs;
1213 
1214  if( n_arcs > aStream.str().size() )
1215  return false;
1216 
1217  for( size_t i = 0; i < n_pts; i++ )
1218  {
1219  int x, y;
1220  ssize_t ind;
1221  aStream >> x;
1222  aStream >> y;
1223  m_points.emplace_back( x, y );
1224 
1225  aStream >> ind;
1226  m_shapes.push_back( ind );
1227  }
1228 
1229  for( size_t i = 0; i < n_arcs; i++ )
1230  {
1231  VECTOR2I p0, pc;
1232  double angle;
1233 
1234  aStream >> pc.x;
1235  aStream >> pc.y;
1236  aStream >> p0.x;
1237  aStream >> p0.y;
1238  aStream >> angle;
1239 
1240  m_arcs.emplace_back( pc, p0, angle );
1241  }
1242 
1243  return true;
1244 }
1245 
1246 
1247 const VECTOR2I SHAPE_LINE_CHAIN::PointAlong( int aPathLength ) const
1248 {
1249  int total = 0;
1250 
1251  if( aPathLength == 0 )
1252  return CPoint( 0 );
1253 
1254  for( int i = 0; i < SegmentCount(); i++ )
1255  {
1256  const SEG& s = CSegment( i );
1257  int l = s.Length();
1258 
1259  if( total + l >= aPathLength )
1260  {
1261  VECTOR2I d( s.B - s.A );
1262  return s.A + d.Resize( aPathLength - total );
1263  }
1264 
1265  total += l;
1266  }
1267 
1268  return CPoint( -1 );
1269 }
1270 
1272 {
1273  // see https://www.mathopenref.com/coordpolygonarea2.html
1274 
1275  if( !m_closed )
1276  return 0.0;
1277 
1278  double area = 0.0;
1279  int size = m_points.size();
1280 
1281  for( int i = 0, j = size - 1; i < size; ++i )
1282  {
1283  area += ( (double) m_points[j].x + m_points[i].x ) * ( (double) m_points[j].y - m_points[i].y );
1284  j = i;
1285  }
1286 
1287  return -area * 0.5;
1288 }
1289 
1290 
1292  m_point( aPoint ),
1293  m_finished( false ),
1294  m_state( 0 ),
1295  m_count( 0 )
1296 {
1297 }
1298 
1299 
1301  const VECTOR2I& ip, const VECTOR2I& ipNext )
1302 {
1303  if( ipNext.y == m_point.y )
1304  {
1305  if( ( ipNext.x == m_point.x )
1306  || ( ip.y == m_point.y && ( ( ipNext.x > m_point.x ) == ( ip.x < m_point.x ) ) ) )
1307  {
1308  m_finished = true;
1309  m_state = -1;
1310  return false;
1311  }
1312  }
1313 
1314  if( ( ip.y < m_point.y ) != ( ipNext.y < m_point.y ) )
1315  {
1316  if( ip.x >= m_point.x )
1317  {
1318  if( ipNext.x > m_point.x )
1319  {
1320  m_state = 1 - m_state;
1321  }
1322  else
1323  {
1324  double d = (double) ( ip.x - m_point.x ) * ( ipNext.y - m_point.y )
1325  - (double) ( ipNext.x - m_point.x ) * ( ip.y - m_point.y );
1326 
1327  if( !d )
1328  {
1329  m_finished = true;
1330  m_state = -1;
1331  return false;
1332  }
1333 
1334  if( ( d > 0 ) == ( ipNext.y > ip.y ) )
1335  m_state = 1 - m_state;
1336  }
1337  }
1338  else
1339  {
1340  if( ipNext.x > m_point.x )
1341  {
1342  double d = (double) ( ip.x - m_point.x ) * ( ipNext.y - m_point.y )
1343  - (double) ( ipNext.x - m_point.x ) * ( ip.y - m_point.y );
1344 
1345  if( !d )
1346  {
1347  m_finished = true;
1348  m_state = -1;
1349  return false;
1350  }
1351 
1352  if( ( d > 0 ) == ( ipNext.y > ip.y ) )
1353  m_state = 1 - m_state;
1354  }
1355  }
1356  }
1357  return true;
1358 }
1359 
1360 
1362 {
1363  if( !m_count )
1364  {
1365  m_lastPoint = aPolyline.CPoint( 0 );
1366  m_firstPoint = aPolyline.CPoint( 0 );
1367  }
1368 
1369  m_count += aPolyline.PointCount();
1370 
1371  for( int i = 1; i < aPolyline.PointCount(); i++ )
1372  {
1373  auto p = aPolyline.CPoint( i );
1374 
1375  if( !processVertex( m_lastPoint, p ) )
1376  return;
1377 
1378  m_lastPoint = p;
1379  }
1380 
1381 }
1382 
1383 
1385 {
1386  processVertex( m_lastPoint, m_firstPoint );
1387  return m_state > 0;
1388 }
1389 
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()
BOX2I m_bbox
cached bounding box
int Index() const
Return the index of this segment in its parent shape (applicable only to non-local segments).
Definition: seg.h:358
int FindSegment(const VECTOR2I &aP) const
Function FindSegment()
long long int Length() const
Function Length()
int Split(const VECTOR2I &aP)
Function Split()
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.h:224
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
std::vector< INTERSECTION > INTERSECTIONS
void RemoveShape(int aPointIndex)
Removes the shape at the given index from the line chain.
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Function Simplify()
SEG::ecoord SquaredDistance(const VECTOR2I &aP, bool aOutlineOnly=false) const
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
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Function Slice()
virtual bool IsClosed() const =0
VECTOR2I p
point of intersection between our and their.
VECTOR2I::extended_type ecoord
Definition: seg.h:44
Define a general 2D-vector/point.
Definition: vector2d.h:61
virtual size_t GetPointCount() const =0
static LIB_PART * dummy()
Used to draw a dummy shape when a LIB_PART is not found in library.
Definition: sch_symbol.cpp:69
compareOriginDistance(const VECTOR2I &aOrigin)
int Distance(const VECTOR2I &aP, bool aOutlineOnly=false) const
Function Distance()
bool PointOnEdge(const VECTOR2I &aP, int aAccuracy=0) const
Check if point aP lies on an edge or vertex of the line chain.
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:38
void AddPolyline(const SHAPE_LINE_CHAIN &aPolyline)
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
virtual size_t GetSegmentCount() const =0
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
void convertArc(ssize_t aArcIndex)
Converts an arc to only a point chain by removing the arc and references.
int PointCount() const
Function PointCount()
static SEG::ecoord Square(int a)
Definition: seg.h:123
const OPT< INTERSECTION > SelfIntersecting() const
Function SelfIntersecting()
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
std::vector< SHAPE_ARC > m_arcs
const VECTOR2I NearestPoint(const VECTOR2I &aP, bool aAllowInternalShapePoints=true) const
Finds a point on the line chain that is closest to point aP.
int PathLength(const VECTOR2I &aP) const
Function PathLength()
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if point aP lies closer to us than aClearance.
ClipperLib::Path convertToClipper(bool aRequiredOrientation) const
Creates a new Clipper path from the SHAPE_LINE_CHAIN in a given orientation.
bool Parse(std::stringstream &aStream) override
bool operator()(const SHAPE_LINE_CHAIN::INTERSECTION &aA, const SHAPE_LINE_CHAIN::INTERSECTION &aB) const
void Insert(size_t aVertex, const VECTOR2I &aP)
const std::vector< ssize_t > & CShapes() const
ssize_t ArcIndex(size_t aSegment) const
bool Intersects(const BOX2< Vec > &aRect) const
Function Intersects.
Definition: box2.h:236
const VECTOR2I & CPoint(int aIndex) const
Function Point()
bool m_closed
is the line chain closed?
SHAPE_LINE_CHAIN()
Constructor Initializes an empty line chain.
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:79
SEG their
segment belonging from the aOther argument of Intersect()
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=0.005 *PCB_IU_PER_MM) const
Constructs a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:388
bool IsClosed() const override
Function IsClosed()
OPT< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:39
std::vector< VECTOR2I > m_points
array of vertices
bool CheckClearance(const VECTOR2I &aP, const int aDist) const
Function CheckClearance()
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.
bool Intersects(const SHAPE_LINE_CHAIN &aChain) const
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
Definition: seg.h:422
int ShapeCount() const
Returns the number of shapes (line segments or arcs) in this line chain.
An abstract shape on 2D plane.
Definition: shape.h:116
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
const std::string Format() const override
int SegmentCount() const
Function SegmentCount()
void Reverse()
Definition: shape_arc.cpp:477
void Rotate(double aAngle, const VECTOR2I &aCenter=VECTOR2I(0, 0)) override
Function Rotate rotates all vertices by a given angle.
bool Collinear(const SEG &aSeg) const
Check if segment aSeg lies on the same line as (this).
Definition: seg.h:258
Definition: seg.h:41
virtual const SEG GetSegment(int aIndex) const =0
int NearestSegment(const VECTOR2I &aP) const
Find the segment nearest the given point.
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:404
VECTOR2< T > Rotate(double aAngle) const
Rotate the vector by a given angle.
Definition: vector2d.h:371
std::vector< ssize_t > m_shapes
Array of indices that refer to the index of the shape if the point is part of a larger shape,...
const SEG CSegment(int aIndex) const
Function CSegment()
static constexpr ssize_t SHAPE_IS_PT
VECTOR2I::extended_type ecoord
Definition: shape.h:236
SHAPE_LINE_CHAIN.
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
VECTOR2I A
Definition: seg.h:49
T rescale(T aNumerator, T aValue, T aDenominator)
Function rescale()
Definition: util.h:95
line chain (polyline)
Definition: shape.h:45
boost::optional< T > OPT
Definition: optional.h:7
SHAPE * Clone() const override
Return a dynamically allocated copy of the shape.
int EdgeContainingPoint(const VECTOR2I &aP, int aAccuracy=0) const
Check if point aP lies on an edge or vertex of the line chain.
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Function Replace()
int NextShape(int aPointIndex, bool aForwards=true) const
Returns the vertex index of the next shape in the chain, or -1 if aPoint is in the last shape If aPoi...
virtual const VECTOR2I GetPoint(int aIndex) const =0
SEG our
segment belonging from the (this) argument of Intersect()
static void addIntersection(SHAPE_LINE_CHAIN::INTERSECTIONS &aIps, int aPc, const SHAPE_LINE_CHAIN::INTERSECTION &aP)
const VECTOR2I PointAlong(int aPathLength) const
bool processVertex(const VECTOR2I &ip, const VECTOR2I &ipNext)
void Mirror(bool aX=true, bool aY=false, const VECTOR2I &aRef={ 0, 0 })
Mirrors the line points about y or x (or both)
bool CompareGeometry(const SHAPE_LINE_CHAIN &aOther) const
bool Contains(const SEG &aSeg) const
Definition: seg.h:321
VECTOR2I B
Definition: seg.h:50