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  * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors.
6  *
7  * @author Tomasz Wlostowski <[email protected]>
8  * Copyright (C) 2013-2021 KiCad Developers, see AUTHORS.txt for contributors.
9  *
10  * This program is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU General Public License
12  * as published by the Free Software Foundation; either version 2
13  * of the License, or (at your option) any later version.
14  *
15  * This program is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18  * GNU General Public License for more details.
19  *
20  * You should have received a copy of the GNU General Public License
21  * along with this program; if not, you may find one here:
22  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
23  * or you may search the http://www.gnu.org website for the version 2 license,
24  * or you may write to the Free Software Foundation, Inc.,
25  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
26  */
27 
28 #include <limits.h> // for INT_MAX
29 #include <math.h> // for hypot
30 #include <map>
31 #include <string> // for basic_string
32 
33 #include <clipper.hpp>
34 #include <core/kicad_algo.h> // for alg::run_on_pair
35 #include <geometry/seg.h> // for SEG, OPT_VECTOR2I
36 #include <geometry/circle.h> // for CIRCLE
38 #include <math/box2.h> // for BOX2I
39 #include <math/util.h> // for rescale
40 #include <math/vector2d.h> // for VECTOR2, VECTOR2I
41 #include <trigo.h> // for RAD2DECIDEG, CalcArcAngle
42 
43 class SHAPE;
44 
45 const ssize_t SHAPE_LINE_CHAIN::SHAPE_IS_PT = -1;
46 const std::pair<ssize_t, ssize_t> SHAPE_LINE_CHAIN::SHAPES_ARE_PT = { SHAPE_IS_PT, SHAPE_IS_PT };
47 
48 SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN( const std::vector<int>& aV)
49  : SHAPE_LINE_CHAIN_BASE( SH_LINE_CHAIN ), m_closed( false ), m_width( 0 )
50 {
51  for(size_t i = 0; i < aV.size(); i+= 2 )
52  {
53  Append( aV[i], aV[i+1] );
54  }
55 }
56 
57 SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN( const ClipperLib::Path& aPath,
58  const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
59  const std::vector<SHAPE_ARC>& aArcBuffer ) :
61  m_closed( true ), m_width( 0 )
62 {
63  std::map<ssize_t, ssize_t> loadedArcs;
64  m_points.reserve( aPath.size() );
65  m_shapes.reserve( aPath.size() );
66 
67  auto loadArc =
68  [&]( ssize_t aArcIndex ) -> ssize_t
69  {
70  if( aArcIndex == SHAPE_IS_PT )
71  {
72  return SHAPE_IS_PT;
73  }
74  else if( loadedArcs.count( aArcIndex ) == 0 )
75  {
76  loadedArcs.insert( { aArcIndex, m_arcs.size() } );
77  m_arcs.push_back( aArcBuffer.at( aArcIndex ) );
78  }
79 
80  return loadedArcs.at(aArcIndex);
81  };
82 
83  for( size_t ii = 0; ii < aPath.size(); ++ii )
84  {
85  Append( aPath[ii].X, aPath[ii].Y );
86 
87  m_shapes[ii].first = loadArc( aZValueBuffer[aPath[ii].Z].m_FirstArcIdx );
88  m_shapes[ii].second = loadArc( aZValueBuffer[aPath[ii].Z].m_SecondArcIdx );
89  }
90 }
91 
92 ClipperLib::Path SHAPE_LINE_CHAIN::convertToClipper( bool aRequiredOrientation,
93  std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
94  std::vector<SHAPE_ARC>& aArcBuffer ) const
95 {
96  ClipperLib::Path c_path;
97  SHAPE_LINE_CHAIN input;
98  bool orientation = Area( false ) >= 0;
99  ssize_t shape_offset = aArcBuffer.size();
100 
101  if( orientation != aRequiredOrientation )
102  input = Reverse();
103  else
104  input = *this;
105 
106  for( int i = 0; i < input.PointCount(); i++ )
107  {
108  const VECTOR2I& vertex = input.CPoint( i );
109 
110  CLIPPER_Z_VALUE z_value( input.m_shapes[i], shape_offset );
111  size_t z_value_ptr = aZValueBuffer.size();
112  aZValueBuffer.push_back( z_value );
113 
114  c_path.push_back( ClipperLib::IntPoint( vertex.x, vertex.y, z_value_ptr ) );
115  }
116 
117  aArcBuffer.insert( aArcBuffer.end(), input.m_arcs.begin(), input.m_arcs.end() );
118 
119  return c_path;
120 }
121 
122 
123 void SHAPE_LINE_CHAIN::convertArc( ssize_t aArcIndex )
124 {
125  if( aArcIndex < 0 )
126  aArcIndex += m_arcs.size();
127 
128  if( aArcIndex >= static_cast<ssize_t>( m_arcs.size() ) )
129  return;
130 
131  // Clear the shapes references
132  for( auto& sh : m_shapes )
133  {
134  alg::run_on_pair( sh,
135  [&]( ssize_t& aShapeIndex )
136  {
137  if( aShapeIndex == aArcIndex )
138  aShapeIndex = SHAPE_IS_PT;
139 
140  if( aShapeIndex > aArcIndex )
141  --aShapeIndex;
142  } );
143 
144  if( sh.second != SHAPE_IS_PT && sh.first == SHAPE_IS_PT )
145  std::swap( sh.first, sh.second );
146  }
147 
148  m_arcs.erase( m_arcs.begin() + aArcIndex );
149 }
150 
151 
152 void SHAPE_LINE_CHAIN::amendArc( size_t aArcIndex, const VECTOR2I& aNewStart,
153  const VECTOR2I& aNewEnd )
154 {
155  wxCHECK_MSG( aArcIndex < m_arcs.size(), /* void */,
156  "Invalid arc index requested." );
157 
158  SHAPE_ARC& theArc = m_arcs[aArcIndex];
159 
160  // Try to preseve the centre of the original arc
161  SHAPE_ARC newArc;
162  newArc.ConstructFromStartEndCenter( aNewStart, aNewEnd, theArc.GetCenter(),
163  theArc.IsClockwise() );
164 
165  m_arcs[aArcIndex] = newArc;
166 }
167 
168 
169 void SHAPE_LINE_CHAIN::splitArc( ssize_t aPtIndex, bool aCoincident )
170 {
171  if( aPtIndex < 0 )
172  aPtIndex += m_shapes.size();
173 
174  if( !IsSharedPt( aPtIndex ) && IsArcStart( aPtIndex ) )
175  return; // Nothing to do
176 
177  if( !IsPtOnArc( aPtIndex ) )
178  return; // Nothing to do
179 
180  wxCHECK_MSG( aPtIndex < static_cast<ssize_t>( m_shapes.size() ), /* void */,
181  "Invalid point index requested." );
182 
183  if( IsSharedPt( aPtIndex ) || IsArcEnd( aPtIndex ) )
184  {
185  if( aCoincident || aPtIndex == 0 )
186  return; // nothing to do
187 
188  ssize_t firstArcIndex = m_shapes[aPtIndex].first;
189 
190  const VECTOR2I& newStart = m_arcs[firstArcIndex].GetP0(); // don't amend the start
191  const VECTOR2I& newEnd = m_points[aPtIndex - 1];
192  amendArc( firstArcIndex, newStart, newEnd );
193 
194  if( IsSharedPt( aPtIndex ) )
195  {
196  m_shapes[aPtIndex].first = m_shapes[aPtIndex].second;
197  m_shapes[aPtIndex].second = SHAPE_IS_PT;
198  }
199  else
200  {
201  m_shapes[aPtIndex] = SHAPES_ARE_PT;
202  }
203 
204  return;
205  }
206 
207  ssize_t currArcIdx = ArcIndex( aPtIndex );
208  SHAPE_ARC& currentArc = m_arcs[currArcIdx];
209 
210  SHAPE_ARC newArc1;
211  SHAPE_ARC newArc2;
212 
213  VECTOR2I arc1End = ( aCoincident ) ? m_points[aPtIndex] : m_points[aPtIndex - 1];
214  VECTOR2I arc2Start = m_points[aPtIndex];
215 
216  newArc1.ConstructFromStartEndCenter( currentArc.GetP0(), arc1End, currentArc.GetCenter(),
217  currentArc.IsClockwise() );
218 
219  newArc2.ConstructFromStartEndCenter( arc2Start, currentArc.GetP1(), currentArc.GetCenter(),
220  currentArc.IsClockwise() );
221 
222  if( !aCoincident && ArcIndex( aPtIndex - 1 ) != currArcIdx )
223  {
224  //Ignore newArc1 as it has zero points
225  m_arcs[currArcIdx] = newArc2;
226  }
227  else
228  {
229  m_arcs[currArcIdx] = newArc1;
230  m_arcs.insert( m_arcs.begin() + currArcIdx + 1, newArc2 );
231 
232  if( aCoincident )
233  {
234  m_shapes[aPtIndex].second = currArcIdx + 1;
235  aPtIndex++;
236  }
237 
238  // Only change the arc indices for the second half of the point range
239  for( int i = aPtIndex; i < PointCount(); i++ )
240  {
241  alg::run_on_pair( m_shapes[i], [&]( ssize_t& aIndex ) {
242  if( aIndex != SHAPE_IS_PT )
243  aIndex++;
244  } );
245  }
246  }
247 }
248 
249 
250 bool SHAPE_LINE_CHAIN_BASE::Collide( const VECTOR2I& aP, int aClearance, int* aActual,
251  VECTOR2I* aLocation ) const
252 {
253  if( IsClosed() && PointInside( aP, aClearance ) )
254  {
255  if( aLocation )
256  *aLocation = aP;
257 
258  if( aActual )
259  *aActual = 0;
260 
261  return true;
262  }
263 
264  SEG::ecoord closest_dist_sq = VECTOR2I::ECOORD_MAX;
265  SEG::ecoord clearance_sq = SEG::Square( aClearance );
266  VECTOR2I nearest;
267 
268  for( size_t i = 0; i < GetSegmentCount(); i++ )
269  {
270  const SEG& s = GetSegment( i );
271  VECTOR2I pn = s.NearestPoint( aP );
272  SEG::ecoord dist_sq = ( pn - aP ).SquaredEuclideanNorm();
273 
274  if( dist_sq < closest_dist_sq )
275  {
276  nearest = pn;
277  closest_dist_sq = dist_sq;
278 
279  if( closest_dist_sq == 0 )
280  break;
281 
282  // If we're not looking for aActual then any collision will do
283  if( closest_dist_sq < clearance_sq && !aActual )
284  break;
285  }
286  }
287 
288  if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
289  {
290  if( aLocation )
291  *aLocation = nearest;
292 
293  if( aActual )
294  *aActual = sqrt( closest_dist_sq );
295 
296  return true;
297  }
298 
299  return false;
300 }
301 
302 
303 void SHAPE_LINE_CHAIN::Rotate( double aAngle, const VECTOR2I& aCenter )
304 {
305  for( auto& pt : m_points )
306  {
307  pt -= aCenter;
308  pt = pt.Rotate( aAngle );
309  pt += aCenter;
310  }
311 
312  for( auto& arc : m_arcs )
313  arc.Rotate( aAngle, aCenter );
314 }
315 
316 
317 bool SHAPE_LINE_CHAIN_BASE::Collide( const SEG& aSeg, int aClearance, int* aActual,
318  VECTOR2I* aLocation ) const
319 {
320  if( IsClosed() && PointInside( aSeg.A ) )
321  {
322  if( aLocation )
323  *aLocation = aSeg.A;
324 
325  if( aActual )
326  *aActual = 0;
327 
328  return true;
329  }
330 
331  SEG::ecoord closest_dist_sq = VECTOR2I::ECOORD_MAX;
332  SEG::ecoord clearance_sq = SEG::Square( aClearance );
333  VECTOR2I nearest;
334 
335  for( size_t i = 0; i < GetSegmentCount(); i++ )
336  {
337  const SEG& s = GetSegment( i );
338  SEG::ecoord dist_sq = s.SquaredDistance( aSeg );
339 
340  if( dist_sq < closest_dist_sq )
341  {
342  if( aLocation )
343  nearest = s.NearestPoint( aSeg );
344 
345  closest_dist_sq = dist_sq;
346 
347  if( closest_dist_sq == 0)
348  break;
349 
350  // If we're not looking for aActual then any collision will do
351  if( closest_dist_sq < clearance_sq && !aActual )
352  break;
353  }
354  }
355 
356  if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
357  {
358  if( aLocation )
359  *aLocation = nearest;
360 
361  if( aActual )
362  *aActual = sqrt( closest_dist_sq );
363 
364  return true;
365  }
366 
367  return false;
368 }
369 
370 
372 {
373  SHAPE_LINE_CHAIN a( *this );
374 
375  reverse( a.m_points.begin(), a.m_points.end() );
376  reverse( a.m_shapes.begin(), a.m_shapes.end() );
377  reverse( a.m_arcs.begin(), a.m_arcs.end() );
378 
379  for( auto& sh : a.m_shapes )
380  {
381  if( sh != SHAPES_ARE_PT )
382  {
383  alg::run_on_pair( sh,
384  [&]( ssize_t& aShapeIndex )
385  {
386  if( aShapeIndex != SHAPE_IS_PT )
387  aShapeIndex = a.m_arcs.size() - aShapeIndex - 1;
388  } );
389 
390  if( sh.second != SHAPE_IS_PT )
391  {
392  // If the second element is populated, the first one should be too!
393  assert( sh.first != SHAPE_IS_PT );
394 
395  // Switch round first and second in shared points, as part of reversing the chain
396  std::swap( sh.first, sh.second );
397  }
398  }
399  }
400 
401  for( SHAPE_ARC& arc : a.m_arcs )
402  arc.Reverse();
403 
404  a.m_closed = m_closed;
405 
406  return a;
407 }
408 
409 
411 {
412  for( ssize_t arcIndex = m_arcs.size() - 1; arcIndex >= 0; --arcIndex )
413  convertArc( arcIndex );
414 }
415 
416 
417 long long int SHAPE_LINE_CHAIN::Length() const
418 {
419  long long int l = 0;
420 
421  for( int i = 0; i < SegmentCount(); i++ )
422  {
423  // Only include segments that aren't part of arc shapes
424  if( !IsArcSegment(i) )
425  l += CSegment( i ).Length();
426  }
427 
428  for( int i = 0; i < ArcCount(); i++ )
429  l += CArcs()[i].GetLength();
430 
431  return l;
432 }
433 
434 
435 void SHAPE_LINE_CHAIN::Mirror( bool aX, bool aY, const VECTOR2I& aRef )
436 {
437  for( auto& pt : m_points )
438  {
439  if( aX )
440  pt.x = -pt.x + 2 * aRef.x;
441 
442  if( aY )
443  pt.y = -pt.y + 2 * aRef.y;
444  }
445 
446  for( auto& arc : m_arcs )
447  arc.Mirror( aX, aY, aRef );
448 }
449 
450 
451 void SHAPE_LINE_CHAIN::Mirror( const SEG& axis )
452 {
453  for( auto& pt : m_points )
454  pt = axis.ReflectPoint( pt );
455 
456  for( auto& arc : m_arcs )
457  arc.Mirror( axis );
458 }
459 
460 
461 void SHAPE_LINE_CHAIN::Replace( int aStartIndex, int aEndIndex, const VECTOR2I& aP )
462 {
463  Remove( aStartIndex, aEndIndex );
464  Insert( aStartIndex, aP );
465  assert( m_shapes.size() == m_points.size() );
466 }
467 
468 
469 void SHAPE_LINE_CHAIN::Replace( int aStartIndex, int aEndIndex, const SHAPE_LINE_CHAIN& aLine )
470 {
471  if( aEndIndex < 0 )
472  aEndIndex += PointCount();
473 
474  if( aStartIndex < 0 )
475  aStartIndex += PointCount();
476 
477  // We only process lines in order in this house
478  wxASSERT( aStartIndex <= aEndIndex );
479  wxASSERT( aEndIndex < m_points.size() );
480 
481  SHAPE_LINE_CHAIN newLine = aLine;
482 
483  // Zero points to add?
484  if( newLine.PointCount() == 0 )
485  {
486  Remove( aStartIndex, aEndIndex );
487  return;
488  }
489 
490  // Remove coincident points in the new line
491  if( newLine.m_points.front() == m_points[aStartIndex] )
492  {
493  aStartIndex++;
494  newLine.Remove( 0 );
495 
496  // Zero points to add?
497  if( newLine.PointCount() == 0 )
498  {
499  Remove( aStartIndex, aEndIndex );
500  return;
501  }
502  }
503 
504  if( newLine.m_points.back() == m_points[aEndIndex] && aEndIndex > 0 )
505  {
506  aEndIndex--;
507  newLine.Remove( -1 );
508  }
509 
510  Remove( aStartIndex, aEndIndex );
511 
512  // Zero points to add?
513  if( newLine.PointCount() == 0 )
514  return;
515 
516  // The total new arcs index is added to the new arc indices
517  size_t prev_arc_count = m_arcs.size();
518  std::vector<std::pair<ssize_t, ssize_t>> new_shapes = newLine.m_shapes;
519 
520  for( std::pair<ssize_t, ssize_t>& shape_pair : new_shapes )
521  {
522  alg::run_on_pair( shape_pair,
523  [&]( ssize_t& aShape )
524  {
525  if( aShape != SHAPE_IS_PT )
526  aShape += prev_arc_count;
527  } );
528  }
529 
530  m_shapes.insert( m_shapes.begin() + aStartIndex, new_shapes.begin(), new_shapes.end() );
531  m_points.insert( m_points.begin() + aStartIndex, newLine.m_points.begin(),
532  newLine.m_points.end() );
533  m_arcs.insert( m_arcs.end(), newLine.m_arcs.begin(), newLine.m_arcs.end() );
534 
535  assert( m_shapes.size() == m_points.size() );
536 }
537 
538 
539 void SHAPE_LINE_CHAIN::Remove( int aStartIndex, int aEndIndex )
540 {
541  assert( m_shapes.size() == m_points.size() );
542 
543  if( aEndIndex < 0 )
544  aEndIndex += PointCount();
545 
546  if( aStartIndex < 0 )
547  aStartIndex += PointCount();
548 
549  if( aStartIndex >= PointCount() )
550  return;
551 
552  aEndIndex = std::min( aEndIndex, PointCount() - 1 );
553 
554  // Split arcs at start index and end just after the end index
555  if( IsPtOnArc( aStartIndex ) )
556  splitArc( aStartIndex );
557 
558  size_t nextIndex = static_cast<size_t>( aEndIndex ) + 1;
559 
560  if( IsPtOnArc( nextIndex ) )
561  splitArc( nextIndex );
562 
563  std::set<size_t> extra_arcs;
564  auto logArcIdxRemoval = [&]( ssize_t& aShapeIndex )
565  {
566  if( aShapeIndex != SHAPE_IS_PT )
567  extra_arcs.insert( aShapeIndex );
568  };
569 
570  // Remove any overlapping arcs in the point range
571  for( int i = aStartIndex; i <= aEndIndex; i++ )
572  {
573  if( IsSharedPt( i ) )
574  {
575  if( i == aStartIndex )
576  {
577  logArcIdxRemoval( m_shapes[i].second ); // Only remove the arc on the second index
578 
579  // Ensure that m_shapes has been built correctly.
580  assert( i < aEndIndex || m_shapes[i + 1].first == m_shapes[i].second );
581 
582  continue;
583  }
584  else if( i == aEndIndex )
585  {
586  logArcIdxRemoval( m_shapes[i].first ); // Only remove the arc on the first index
587 
588  // Ensure that m_shapes has been built correctly.
589  assert( i > aStartIndex || IsSharedPt( i - 1 )
590  ? m_shapes[i - 1].second == m_shapes[i].first
591  : m_shapes[i - 1].first == m_shapes[i].first );
592  continue;
593  }
594  }
595 
596  alg::run_on_pair( m_shapes[i], logArcIdxRemoval );
597  }
598 
599  for( auto arc : extra_arcs )
600  convertArc( arc );
601 
602  m_shapes.erase( m_shapes.begin() + aStartIndex, m_shapes.begin() + aEndIndex + 1 );
603  m_points.erase( m_points.begin() + aStartIndex, m_points.begin() + aEndIndex + 1 );
604  assert( m_shapes.size() == m_points.size() );
605 }
606 
607 
608 int SHAPE_LINE_CHAIN::Distance( const VECTOR2I& aP, bool aOutlineOnly ) const
609 {
610  return sqrt( SquaredDistance( aP, aOutlineOnly ) );
611 }
612 
613 
614 SEG::ecoord SHAPE_LINE_CHAIN_BASE::SquaredDistance( const VECTOR2I& aP, bool aOutlineOnly ) const
615 {
617 
618  if( IsClosed() && PointInside( aP ) && !aOutlineOnly )
619  return 0;
620 
621  for( size_t s = 0; s < GetSegmentCount(); s++ )
622  d = std::min( d, GetSegment( s ).SquaredDistance( aP ) );
623 
624  return d;
625 }
626 
627 
629 {
630  int ii = -1;
631  int min_dist = 2;
632 
633  int found_index = Find( aP );
634 
635  for( int s = 0; s < SegmentCount(); s++ )
636  {
637  const SEG seg = CSegment( s );
638  int dist = seg.Distance( aP );
639 
640  // make sure we are not producing a 'slightly concave' primitive. This might happen
641  // if aP lies very close to one of already existing points.
642  if( dist < min_dist && seg.A != aP && seg.B != aP )
643  {
644  min_dist = dist;
645  if( found_index < 0 )
646  ii = s;
647  else if( s < found_index )
648  ii = s;
649  }
650  }
651 
652  if( ii < 0 )
653  ii = found_index;
654 
655  if( ii >= 0 )
656  {
657  // Don't create duplicate points
658  if( GetPoint( ii ) == aP )
659  return ii;
660 
661  size_t newIndex = static_cast<size_t>( ii ) + 1;
662 
663  if( IsArcSegment( ii ) )
664  {
665  m_points.insert( m_points.begin() + newIndex, aP );
666  m_shapes.insert( m_shapes.begin() + newIndex, { ArcIndex( ii ), SHAPE_IS_PT } );
667  splitArc( newIndex, true ); // Make the inserted point a shared point
668  }
669  else
670  {
671  Insert( newIndex, aP );
672  }
673 
674  return newIndex;
675  }
676 
677  return -1;
678 }
679 
680 
681 int SHAPE_LINE_CHAIN::Find( const VECTOR2I& aP, int aThreshold ) const
682 {
683  for( int s = 0; s < PointCount(); s++ )
684  {
685  if( aThreshold == 0 )
686  {
687  if( CPoint( s ) == aP )
688  return s;
689  }
690  else
691  {
692  if( (CPoint( s ) - aP).EuclideanNorm() <= aThreshold )
693  return s;
694  }
695  }
696 
697  return -1;
698 }
699 
700 
701 int SHAPE_LINE_CHAIN::FindSegment( const VECTOR2I& aP, int aThreshold ) const
702 {
703  for( int s = 0; s < SegmentCount(); s++ )
704  {
705  if( CSegment( s ).Distance( aP ) <= aThreshold )
706  return s;
707  }
708 
709  return -1;
710 }
711 
712 
714 {
715  if( m_points.empty() )
716  return 0;
717 
718  int numPoints = static_cast<int>( m_shapes.size() );
719  int numShapes = 0;
720  int arcIdx = -1;
721 
722  for( int i = 0; i < m_points.size() - 1; i++ )
723  {
724  if( m_shapes[i] == SHAPES_ARE_PT )
725  {
726  numShapes++;
727  }
728  else
729  {
730  // Expect that the second index only gets populated when the point is shared between
731  // two shapes. Otherwise, the shape index should always go on the first element of
732  // the pair.
733  assert( m_shapes[i].first != SHAPE_IS_PT );
734 
735  // Start assuming the point is shared with the previous arc
736  // If so, the new/next arc index should be located at the second
737  // element in the pair
738  arcIdx = m_shapes[i].second;
739 
740  if( arcIdx == SHAPE_IS_PT )
741  arcIdx = m_shapes[i].first; // Not a shared point
742 
743  numShapes++;
744 
745  // Now skip the rest of the arc
746  while( i < numPoints && m_shapes[i].first == arcIdx )
747  i++;
748 
749  // Add the "hidden" segment at the end of the arc, if it exists
750  if( i < numPoints && m_points[i] != m_points[i - 1] )
751  {
752  numShapes++;
753  }
754 
755  i--;
756  }
757  }
758 
759  return numShapes;
760 }
761 
762 
763 int SHAPE_LINE_CHAIN::NextShape( int aPointIndex, bool aForwards ) const
764 {
765  if( aPointIndex < 0 )
766  aPointIndex += PointCount();
767 
768  int lastIndex = PointCount() - 1;
769 
770  // First or last point?
771  if( ( aForwards && aPointIndex == lastIndex ) ||
772  ( !aForwards && aPointIndex == 0 ) )
773  {
774  return -1; // we don't want to wrap around
775  }
776 
777  int delta = aForwards ? 1 : -1;
778 
779  if( m_shapes[aPointIndex] == SHAPES_ARE_PT )
780  return aPointIndex + delta;
781 
782  int arcStart = aPointIndex;
783 
784  // The second element should only get populated when the point is shared between two shapes.
785  // If not a shared point, then the index should always go on the first element.
786  assert( m_shapes[aPointIndex].first != SHAPE_IS_PT );
787 
788  // Start with the assumption the point is shared
789  auto arcIndex = [&]( int aIndex ) -> ssize_t
790  {
791  if( aForwards )
792  return ArcIndex( aIndex );
793  else
794  return reversedArcIndex( aIndex );
795  };
796 
797  ssize_t currentArcIdx = arcIndex( aPointIndex );
798 
799  // Now skip the rest of the arc
800  while( aPointIndex < lastIndex && aPointIndex >= 0 && arcIndex( aPointIndex ) == currentArcIdx )
801  aPointIndex += delta;
802 
803  if( aPointIndex == lastIndex )
804  {
805  if( !m_closed )
806  return -1;
807  else
808  return lastIndex; // Segment between last point and the start
809  }
810 
811  bool indexStillOnArc = alg::pair_contains( m_shapes[aPointIndex], currentArcIdx );
812 
813  // We want the last vertex of the arc if the initial point was the start of one
814  // Well-formed arcs should generate more than one point to travel above
815  if( aPointIndex - arcStart > 1 && !indexStillOnArc )
816  aPointIndex -= delta;
817 
818  return aPointIndex;
819 }
820 
821 
822 void SHAPE_LINE_CHAIN::SetPoint( int aIndex, const VECTOR2I& aPos )
823 {
824  if( aIndex < 0 )
825  aIndex += PointCount();
826  else if( aIndex >= PointCount() )
827  aIndex -= PointCount();
828 
829  m_points[aIndex] = aPos;
830 
831  alg::run_on_pair( m_shapes[aIndex],
832  [&]( ssize_t& aIdx )
833  {
834  if( aIdx != SHAPE_IS_PT )
835  convertArc( aIdx );
836  } );
837 }
838 
839 
840 void SHAPE_LINE_CHAIN::RemoveShape( int aPointIndex )
841 {
842  if( aPointIndex < 0 )
843  aPointIndex += PointCount();
844 
845  if( m_shapes[aPointIndex] == SHAPES_ARE_PT )
846  {
847  Remove( aPointIndex );
848  return;
849  }
850 
851  //@todo should this be replaced to use NextShape() / PrevShape()?
852  int start = aPointIndex;
853  int end = aPointIndex;
854  int arcIdx = ArcIndex( aPointIndex );
855 
856  if( !IsSharedPt( aPointIndex ) )
857  {
858  // aPointIndex is not a shared point, so iterate backwards to find the start of the arc
859  while( start >= 0 && m_shapes[start].first == arcIdx )
860  start--;
861 
862  // Check if the previous point might be a shared point and decrement 'start' if so
863  if( start >= 1 && m_shapes[static_cast<ssize_t>( start ) - 1].second == arcIdx )
864  start--;
865  }
866 
867  // For the end point we only need to check the first element in m_shapes (the second one is only
868  // populated if there is an arc after the current one sharing the same point).
869  while( end < static_cast<int>( m_shapes.size() ) - 1 && m_shapes[end].first == arcIdx )
870  end++;
871 
872  Remove( start, end );
873 }
874 
875 
876 const SHAPE_LINE_CHAIN SHAPE_LINE_CHAIN::Slice( int aStartIndex, int aEndIndex ) const
877 {
878  SHAPE_LINE_CHAIN rv;
879 
880  if( aEndIndex < 0 )
881  aEndIndex += PointCount();
882 
883  if( aStartIndex < 0 )
884  aStartIndex += PointCount();
885 
886  int numPoints = static_cast<int>( m_points.size() );
887 
888 
889  if( IsArcSegment( aStartIndex ) && !IsArcStart( aStartIndex ) )
890  {
891  // Cutting in middle of an arc, lets split it
892  ssize_t arcIndex = ArcIndex( aStartIndex );
893  const SHAPE_ARC& currentArc = Arc( arcIndex );
894 
895  // Copy the points as arc points
896  for( size_t i = aStartIndex; arcIndex == ArcIndex( i ); i++ )
897  {
898  rv.m_points.push_back( m_points[i] );
899  rv.m_shapes.push_back( { rv.m_arcs.size(), SHAPE_IS_PT } );
900  rv.m_bbox.Merge( m_points[i] );
901  }
902 
903  // Create a new arc from the existing one, with different start point.
904  SHAPE_ARC newArc;
905 
906  VECTOR2I newArcStart = m_points[aStartIndex];
907 
908  newArc.ConstructFromStartEndCenter( newArcStart, currentArc.GetP1(),
909  currentArc.GetCenter(),
910  currentArc.IsClockwise() );
911 
912 
913  rv.m_arcs.push_back( newArc );
914 
915  aStartIndex += rv.PointCount();
916  }
917 
918  for( int i = aStartIndex; i <= aEndIndex && i < numPoints; i = NextShape( i ) )
919  {
920  if( i == -1 )
921  return rv; // NextShape reached the end
922 
923  if( IsArcStart( i ) )
924  {
925  const SHAPE_ARC &currentArc = Arc( ArcIndex( i ) );
926  int nextShape = NextShape( i );
927  bool isLastShape = nextShape < 0;
928 
929  if( ( isLastShape && aEndIndex != ( numPoints - 1 ) )
930  || ( nextShape > aEndIndex ) )
931  {
932  if( i == aEndIndex )
933  {
934  // Single point on an arc, just append the single point
935  rv.Append( m_points[i] );
936  return rv;
937  }
938 
939  // Cutting in middle of an arc, lets split it
940  ssize_t arcIndex = ArcIndex( i );
941  const SHAPE_ARC& currentArc = Arc( arcIndex );
942 
943  // Copy the points as arc points
944  for( ; i <= aEndIndex && i < numPoints; i++ )
945  {
946  if( arcIndex != ArcIndex( i ) )
947  break;
948 
949  rv.m_points.push_back( m_points[i] );
950  rv.m_shapes.push_back( { rv.m_arcs.size(), SHAPE_IS_PT } );
951  rv.m_bbox.Merge( m_points[i] );
952  }
953 
954  // Create a new arc from the existing one, with different end point.
955  SHAPE_ARC newArc;
956 
957  VECTOR2I newArcEnd = m_points[aEndIndex];
958 
959  newArc.ConstructFromStartEndCenter( currentArc.GetP0(), newArcEnd,
960  currentArc.GetCenter(),
961  currentArc.IsClockwise() );
962 
963 
964  rv.m_arcs.push_back( newArc );
965 
966  return rv;
967  }
968  else
969  {
970  // append the whole arc
971  rv.Append( currentArc );
972  }
973 
974  if( isLastShape )
975  return rv;
976  }
977  else
978  {
979  wxASSERT_MSG( !IsArcSegment( i ), "Still on an arc segment, we missed something..." );
980 
981  rv.Append( m_points[i] );
982  }
983  }
984 
985  return rv;
986 }
987 
988 
990 {
991  assert( m_shapes.size() == m_points.size() );
992 
993  if( aOtherLine.PointCount() == 0 )
994  {
995  return;
996  }
997 
998  size_t num_arcs = m_arcs.size();
999  m_arcs.insert( m_arcs.end(), aOtherLine.m_arcs.begin(), aOtherLine.m_arcs.end() );
1000 
1001  auto fixShapeIndices =
1002  [&]( const std::pair<ssize_t, ssize_t>& aShapeIndices ) -> std::pair<ssize_t, ssize_t>
1003  {
1004  std::pair<ssize_t, ssize_t> retval = aShapeIndices;
1005 
1006  alg::run_on_pair( retval, [&]( ssize_t& aIndex )
1007  {
1008  if( aIndex != SHAPE_IS_PT )
1009  aIndex = aIndex + num_arcs;
1010  } );
1011 
1012  return retval;
1013  };
1014 
1015  if( PointCount() == 0 || aOtherLine.CPoint( 0 ) != CPoint( -1 ) )
1016  {
1017  const VECTOR2I p = aOtherLine.CPoint( 0 );
1018  m_points.push_back( p );
1019  m_shapes.push_back( fixShapeIndices( aOtherLine.CShapes()[0] ) );
1020  m_bbox.Merge( p );
1021  }
1022  else if( aOtherLine.IsArcSegment( 0 ) )
1023  {
1024  // Associate the new arc shape with the last point of this chain
1025  if( m_shapes.back() == SHAPES_ARE_PT )
1026  m_shapes.back().first = aOtherLine.CShapes()[0].first + num_arcs;
1027  else
1028  m_shapes.back().second = aOtherLine.CShapes()[0].first + num_arcs;
1029  }
1030 
1031 
1032  for( int i = 1; i < aOtherLine.PointCount(); i++ )
1033  {
1034  const VECTOR2I p = aOtherLine.CPoint( i );
1035  m_points.push_back( p );
1036 
1037  ssize_t arcIndex = aOtherLine.ArcIndex( i );
1038 
1039  if( arcIndex != ssize_t( SHAPE_IS_PT ) )
1040  {
1041  m_shapes.push_back( fixShapeIndices( aOtherLine.m_shapes[i] ) );
1042  }
1043  else
1044  m_shapes.push_back( SHAPES_ARE_PT );
1045 
1046  m_bbox.Merge( p );
1047  }
1048 
1049  assert( m_shapes.size() == m_points.size() );
1050 }
1051 
1052 
1054 {
1055  SEG startToEnd( aArc.GetP0(), aArc.GetP1() );
1056 
1057  if( startToEnd.Distance( aArc.GetArcMid() ) < 1 )
1058  {
1059  // Not really a valid arc. Add as a straight line segment instead
1060  Append( aArc.GetP0() );
1061  Append( aArc.GetP1() );
1062  }
1063  else
1064  {
1065  SHAPE_LINE_CHAIN chain = aArc.ConvertToPolyline();
1066 
1067  // @todo should the below 4 LOC be moved to SHAPE_ARC::ConvertToPolyline ?
1068  chain.m_arcs.push_back( aArc );
1069 
1070  for( auto& sh : chain.m_shapes )
1071  sh.first = 0;
1072 
1073  Append( chain );
1074  }
1075 
1076  assert( m_shapes.size() == m_points.size() );
1077 }
1078 
1079 
1080 void SHAPE_LINE_CHAIN::Insert( size_t aVertex, const VECTOR2I& aP )
1081 {
1082  if( aVertex == m_points.size() )
1083  {
1084  Append( aP );
1085  return;
1086  }
1087 
1088  wxCHECK( aVertex < m_points.size(), /* void */ );
1089 
1090  if( aVertex > 0 && IsPtOnArc( aVertex ) )
1091  splitArc( aVertex );
1092 
1093  //@todo need to check we aren't creating duplicate points
1094  m_points.insert( m_points.begin() + aVertex, aP );
1095  m_shapes.insert( m_shapes.begin() + aVertex, SHAPES_ARE_PT );
1096 
1097  assert( m_shapes.size() == m_points.size() );
1098 }
1099 
1100 
1101 void SHAPE_LINE_CHAIN::Insert( size_t aVertex, const SHAPE_ARC& aArc )
1102 {
1103  wxCHECK( aVertex < m_points.size(), /* void */ );
1104 
1105  if( aVertex > 0 && IsPtOnArc( aVertex ) )
1106  splitArc( aVertex );
1107 
1109  ssize_t arc_pos = m_arcs.size();
1110 
1111  for( auto arc_it = m_shapes.rbegin() ;
1112  arc_it != m_shapes.rend() + aVertex;
1113  arc_it++ )
1114  {
1115  if( *arc_it != SHAPES_ARE_PT )
1116  {
1117  arc_pos = std::max( ( *arc_it ).first, ( *arc_it ).second );
1118  arc_pos++;
1119  }
1120  }
1121 
1122  //Increment all arc indices before inserting the new arc
1123  for( auto& sh : m_shapes )
1124  {
1125  alg::run_on_pair( sh,
1126  [&]( ssize_t& aIndex )
1127  {
1128  if( aIndex >= arc_pos )
1129  aIndex++;
1130  } );
1131  }
1132 
1133  m_arcs.insert( m_arcs.begin() + arc_pos, aArc );
1134 
1136  //@todo need to check we aren't creating duplicate points at start or end
1137  auto& chain = aArc.ConvertToPolyline();
1138  m_points.insert( m_points.begin() + aVertex, chain.CPoints().begin(), chain.CPoints().end() );
1139 
1141  //@todo need to check we aren't creating duplicate points at start or end
1142  std::vector<std::pair<ssize_t, ssize_t>> new_points( chain.PointCount(),
1143  { arc_pos, SHAPE_IS_PT } );
1144 
1145  m_shapes.insert( m_shapes.begin() + aVertex, new_points.begin(), new_points.end() );
1146  assert( m_shapes.size() == m_points.size() );
1147 }
1148 
1149 
1151 {
1152  compareOriginDistance( const VECTOR2I& aOrigin ) :
1153  m_origin( aOrigin ) {};
1154 
1156  const SHAPE_LINE_CHAIN::INTERSECTION& aB ) const
1157  {
1158  return ( m_origin - aA.p ).EuclideanNorm() < ( m_origin - aB.p ).EuclideanNorm();
1159  }
1160 
1162 };
1163 
1164 
1165 int SHAPE_LINE_CHAIN::Intersect( const SEG& aSeg, INTERSECTIONS& aIp ) const
1166 {
1167  for( int s = 0; s < SegmentCount(); s++ )
1168  {
1169  OPT_VECTOR2I p = CSegment( s ).Intersect( aSeg );
1170 
1171  if( p )
1172  {
1173  INTERSECTION is;
1174  is.valid = true;
1175  is.index_our = s;
1176  is.index_their = -1;
1177  is.is_corner_our = is.is_corner_their = false;
1178  is.p = *p;
1179  aIp.push_back( is );
1180  }
1181  }
1182 
1183  compareOriginDistance comp( aSeg.A );
1184  sort( aIp.begin(), aIp.end(), comp );
1185 
1186  return aIp.size();
1187 }
1188 
1189 
1190 static inline void addIntersection( SHAPE_LINE_CHAIN::INTERSECTIONS& aIps, int aPc,
1191  const SHAPE_LINE_CHAIN::INTERSECTION& aP )
1192 {
1193  if( aIps.size() == 0 )
1194  {
1195  aIps.push_back( aP );
1196  return;
1197  }
1198 
1199  const auto& last = aIps.back();
1200 
1201  aIps.push_back( aP );
1202 }
1203 
1204 
1206  bool aExcludeColinearAndTouching ) const
1207 {
1208  BOX2I bb_other = aChain.BBox();
1209 
1210  for( int s1 = 0; s1 < SegmentCount(); s1++ )
1211  {
1212  const SEG& a = CSegment( s1 );
1213  const BOX2I bb_cur( a.A, a.B - a.A );
1214 
1215  if( !bb_other.Intersects( bb_cur ) )
1216  continue;
1217 
1218  for( int s2 = 0; s2 < aChain.SegmentCount(); s2++ )
1219  {
1220  const SEG& b = aChain.CSegment( s2 );
1221  INTERSECTION is;
1222 
1223  is.index_our = s1;
1224  is.index_their = s2;
1225  is.is_corner_our = false;
1226  is.is_corner_their = false;
1227  is.valid = true;
1228 
1229  OPT_VECTOR2I p = a.Intersect( b );
1230 
1231  bool coll = a.Collinear( b );
1232 
1233  if( coll && ! aExcludeColinearAndTouching )
1234  {
1235  if( a.Contains( b.A ) )
1236  {
1237  is.p = b.A;
1238  is.is_corner_their = true;
1239  addIntersection(aIp, PointCount(), is);
1240  }
1241 
1242  if( a.Contains( b.B ) )
1243  {
1244  is.p = b.B;
1245  is.index_their++;
1246  is.is_corner_their = true;
1247  addIntersection( aIp, PointCount(), is );
1248  }
1249 
1250  if( b.Contains( a.A ) )
1251  {
1252  is.p = a.A;
1253  is.is_corner_our = true;
1254  addIntersection( aIp, PointCount(), is );
1255  }
1256 
1257  if( b.Contains( a.B ) )
1258  {
1259  is.p = a.B;
1260  is.index_our++;
1261  is.is_corner_our = true;
1262  addIntersection( aIp, PointCount(), is );
1263  }
1264  }
1265  else if( p )
1266  {
1267  is.p = *p;
1268  is.is_corner_our = false;
1269  is.is_corner_their = false;
1270 
1271  int distA = ( b.A - *p ).EuclideanNorm();
1272  int distB = ( b.B - *p ).EuclideanNorm();
1273 
1274  if( p == a.A )
1275  {
1276  is.is_corner_our = true;
1277  }
1278 
1279  if( p == a.B )
1280  {
1281  is.is_corner_our = true;
1282  is.index_our++;
1283  }
1284 
1285  if( p == b.A )
1286  {
1287  is.is_corner_their = true;
1288  }
1289 
1290  if( p == b.B )
1291  {
1292  is.is_corner_their = true;
1293  is.index_their++;
1294  }
1295 
1296  addIntersection( aIp, PointCount(), is );
1297  }
1298  }
1299  }
1300 
1301  return aIp.size();
1302 }
1303 
1304 
1305 int SHAPE_LINE_CHAIN::PathLength( const VECTOR2I& aP, int aIndex ) const
1306 {
1307  int sum = 0;
1308 
1309  for( int i = 0; i < SegmentCount(); i++ )
1310  {
1311  const SEG seg = CSegment( i );
1312  int d = seg.Distance( aP );
1313 
1314  bool indexMatch = true;
1315 
1316  if( aIndex >= 0 )
1317  {
1318  if( aIndex == SegmentCount() )
1319  {
1320  indexMatch = ( i == SegmentCount() - 1 );
1321  }
1322  else
1323  {
1324  indexMatch = ( i == aIndex );
1325  }
1326  }
1327 
1328  if( indexMatch )
1329  {
1330  sum += ( aP - seg.A ).EuclideanNorm();
1331  return sum;
1332  }
1333  else
1334  sum += seg.Length();
1335  }
1336 
1337  return -1;
1338 }
1339 
1340 
1341 bool SHAPE_LINE_CHAIN_BASE::PointInside( const VECTOR2I& aPt, int aAccuracy,
1342  bool aUseBBoxCache ) const
1343 {
1344  /*
1345  * Don't check the bounding box unless it's cached. Building it is about the same speed as
1346  * the rigorous test below and so just slows things down by doing potentially two tests.
1347  */
1348  if( aUseBBoxCache && GetCachedBBox() && !GetCachedBBox()->Contains( aPt ) )
1349  return false;
1350 
1351  if( !IsClosed() || GetPointCount() < 3 )
1352  return false;
1353 
1354  bool inside = false;
1355 
1356  /*
1357  * To check for interior points, we draw a line in the positive x direction from
1358  * the point. If it intersects an even number of segments, the point is outside the
1359  * line chain (it had to first enter and then exit). Otherwise, it is inside the chain.
1360  *
1361  * Note: slope might be denormal here in the case of a horizontal line but we require our
1362  * y to move from above to below the point (or vice versa)
1363  *
1364  * Note: we open-code CPoint() here so that we don't end up calculating the size of the
1365  * vector number-of-points times. This has a non-trivial impact on zone fill times.
1366  */
1367  int pointCount = GetPointCount();
1368 
1369  for( int i = 0; i < pointCount; )
1370  {
1371  const auto p1 = GetPoint( i++ );
1372  const auto p2 = GetPoint( i == pointCount ? 0 : i );
1373  const auto diff = p2 - p1;
1374 
1375  if( diff.y != 0 )
1376  {
1377  const int d = rescale( diff.x, ( aPt.y - p1.y ), diff.y );
1378 
1379  if( ( ( p1.y > aPt.y ) != ( p2.y > aPt.y ) ) && ( aPt.x - p1.x < d ) )
1380  inside = !inside;
1381  }
1382  }
1383 
1384  // If accuracy is <= 1 (nm) then we skip the accuracy test for performance. Otherwise
1385  // we use "OnEdge(accuracy)" as a proxy for "Inside(accuracy)".
1386  if( aAccuracy <= 1 )
1387  return inside;
1388  else
1389  return inside || PointOnEdge( aPt, aAccuracy );
1390 }
1391 
1392 
1393 bool SHAPE_LINE_CHAIN_BASE::PointOnEdge( const VECTOR2I& aPt, int aAccuracy ) const
1394 {
1395  return EdgeContainingPoint( aPt, aAccuracy ) >= 0;
1396 }
1397 
1398 
1399 int SHAPE_LINE_CHAIN_BASE::EdgeContainingPoint( const VECTOR2I& aPt, int aAccuracy ) const
1400 {
1401  if( !GetPointCount() )
1402  {
1403  return -1;
1404  }
1405  else if( GetPointCount() == 1 )
1406  {
1407  VECTOR2I dist = GetPoint(0) - aPt;
1408  return ( hypot( dist.x, dist.y ) <= aAccuracy + 1 ) ? 0 : -1;
1409  }
1410 
1411  for( size_t i = 0; i < GetSegmentCount(); i++ )
1412  {
1413  const SEG s = GetSegment( i );
1414 
1415  if( s.A == aPt || s.B == aPt )
1416  return i;
1417 
1418  if( s.Distance( aPt ) <= aAccuracy + 1 )
1419  return i;
1420  }
1421 
1422  return -1;
1423 }
1424 
1425 
1426 bool SHAPE_LINE_CHAIN::CheckClearance( const VECTOR2I& aP, const int aDist ) const
1427 {
1428  if( !PointCount() )
1429  return false;
1430  else if( PointCount() == 1 )
1431  return m_points[0] == aP;
1432 
1433  for( int i = 0; i < SegmentCount(); i++ )
1434  {
1435  const SEG s = CSegment( i );
1436 
1437  if( s.A == aP || s.B == aP )
1438  return true;
1439 
1440  if( s.Distance( aP ) <= aDist )
1441  return true;
1442  }
1443 
1444  return false;
1445 }
1446 
1447 
1449 {
1450  for( int s1 = 0; s1 < SegmentCount(); s1++ )
1451  {
1452  for( int s2 = s1 + 1; s2 < SegmentCount(); s2++ )
1453  {
1454  const VECTOR2I s2a = CSegment( s2 ).A, s2b = CSegment( s2 ).B;
1455 
1456  if( s1 + 1 != s2 && CSegment( s1 ).Contains( s2a ) )
1457  {
1458  INTERSECTION is;
1459  is.index_our = s1;
1460  is.index_their = s2;
1461  is.p = s2a;
1462  return is;
1463  }
1464  else if( CSegment( s1 ).Contains( s2b ) &&
1465  // for closed polylines, the ending point of the
1466  // last segment == starting point of the first segment
1467  // this is a normal case, not self intersecting case
1468  !( IsClosed() && s1 == 0 && s2 == SegmentCount()-1 ) )
1469  {
1470  INTERSECTION is;
1471  is.index_our = s1;
1472  is.index_their = s2;
1473  is.p = s2b;
1474  return is;
1475  }
1476  else
1477  {
1478  OPT_VECTOR2I p = CSegment( s1 ).Intersect( CSegment( s2 ), true );
1479 
1480  if( p )
1481  {
1482  INTERSECTION is;
1483  is.index_our = s1;
1484  is.index_their = s2;
1485  is.p = *p;
1486  return is;
1487  }
1488  }
1489  }
1490  }
1491 
1493 }
1494 
1495 
1497 {
1498  std::vector<VECTOR2I> pts_unique;
1499  std::vector<std::pair<ssize_t, ssize_t>> shapes_unique;
1500 
1501  if( PointCount() < 2 )
1502  {
1503  return *this;
1504  }
1505  else if( PointCount() == 2 )
1506  {
1507  if( m_points[0] == m_points[1] )
1508  m_points.pop_back();
1509 
1510  return *this;
1511  }
1512 
1513  int i = 0;
1514  int np = PointCount();
1515 
1516  // stage 1: eliminate duplicate vertices
1517  while( i < np )
1518  {
1519  int j = i + 1;
1520 
1521  // We can eliminate duplicate vertices as long as they are part of the same shape, OR if
1522  // one of them is part of a shape and one is not.
1523  while( j < np && m_points[i] == m_points[j] &&
1524  ( m_shapes[i] == m_shapes[j] ||
1525  m_shapes[i] == SHAPES_ARE_PT ||
1526  m_shapes[j] == SHAPES_ARE_PT ) )
1527  {
1528  j++;
1529  }
1530 
1531  std::pair<ssize_t,ssize_t> shapeToKeep = m_shapes[i];
1532 
1533  if( shapeToKeep == SHAPES_ARE_PT )
1534  shapeToKeep = m_shapes[j - 1];
1535 
1536  assert( shapeToKeep.first < static_cast<int>( m_arcs.size() ) );
1537  assert( shapeToKeep.second < static_cast<int>( m_arcs.size() ) );
1538 
1539  pts_unique.push_back( CPoint( i ) );
1540  shapes_unique.push_back( shapeToKeep );
1541 
1542  i = j;
1543  }
1544 
1545  m_points.clear();
1546  m_shapes.clear();
1547  np = pts_unique.size();
1548 
1549  i = 0;
1550 
1551  // stage 2: eliminate colinear segments
1552  while( i < np - 2 )
1553  {
1554  const VECTOR2I p0 = pts_unique[i];
1555  const VECTOR2I p1 = pts_unique[i + 1];
1556  int n = i;
1557 
1558  if( aRemoveColinear && shapes_unique[i] == SHAPES_ARE_PT
1559  && shapes_unique[i + 1] == SHAPES_ARE_PT )
1560  {
1561  while( n < np - 2
1562  && ( SEG( p0, p1 ).LineDistance( pts_unique[n + 2] ) <= 1
1563  || SEG( p0, p1 ).Collinear( SEG( p1, pts_unique[n + 2] ) ) ) )
1564  n++;
1565  }
1566 
1567  m_points.push_back( p0 );
1568  m_shapes.push_back( shapes_unique[i] );
1569 
1570  if( n > i )
1571  i = n;
1572 
1573  if( n == np - 2 )
1574  {
1575  m_points.push_back( pts_unique[np - 1] );
1576  m_shapes.push_back( shapes_unique[np - 1] );
1577  return *this;
1578  }
1579 
1580  i++;
1581  }
1582 
1583  if( np > 1 )
1584  {
1585  m_points.push_back( pts_unique[np - 2] );
1586  m_shapes.push_back( shapes_unique[np - 2] );
1587  }
1588 
1589  m_points.push_back( pts_unique[np - 1] );
1590  m_shapes.push_back( shapes_unique[np - 1] );
1591 
1592  assert( m_points.size() == m_shapes.size() );
1593 
1594  return *this;
1595 }
1596 
1597 
1599  bool aAllowInternalShapePoints ) const
1600 {
1601  int min_d = INT_MAX;
1602  int nearest = 0;
1603 
1604  for( int i = 0; i < SegmentCount(); i++ )
1605  {
1606  int d = CSegment( i ).Distance( aP );
1607 
1608  if( d < min_d )
1609  {
1610  min_d = d;
1611  nearest = i;
1612  }
1613  }
1614 
1615  if( !aAllowInternalShapePoints )
1616  {
1617  //Snap to arc end points if the closest found segment is part of an arc segment
1618  if( nearest > 0 && nearest < PointCount() && IsArcSegment( nearest ) )
1619  {
1620  VECTOR2I ptToSegStart = CSegment( nearest ).A - aP;
1621  VECTOR2I ptToSegEnd = CSegment( nearest ).B - aP;
1622 
1623  if( ptToSegStart.EuclideanNorm() > ptToSegEnd.EuclideanNorm() )
1624  nearest++;
1625 
1626  // Is this the start or end of an arc? If so, return it directly
1627  if( IsArcStart( nearest ) || IsArcEnd( nearest ) )
1628  {
1629  return m_points[nearest];
1630  }
1631  else
1632  {
1633  const SHAPE_ARC& nearestArc = Arc( ArcIndex( nearest ) );
1634  VECTOR2I ptToArcStart = nearestArc.GetP0() - aP;
1635  VECTOR2I ptToArcEnd = nearestArc.GetP1() - aP;
1636 
1637  if( ptToArcStart.EuclideanNorm() > ptToArcEnd.EuclideanNorm() )
1638  return nearestArc.GetP1();
1639  else
1640  return nearestArc.GetP0();
1641  }
1642 
1643  }
1644  }
1645 
1646  return CSegment( nearest ).NearestPoint( aP );
1647 }
1648 
1649 
1650 const VECTOR2I SHAPE_LINE_CHAIN::NearestPoint( const SEG& aSeg, int& dist ) const
1651 {
1652  int nearest = 0;
1653 
1654  dist = INT_MAX;
1655 
1656  for( int i = 0; i < PointCount(); i++ )
1657  {
1658  int d = aSeg.LineDistance( CPoint( i ) );
1659 
1660  if( d < dist )
1661  {
1662  dist = d;
1663  nearest = i;
1664  }
1665  }
1666 
1667  return CPoint( nearest );
1668 }
1669 
1670 
1672 {
1673  int min_d = INT_MAX;
1674  int nearest = 0;
1675 
1676  for( int i = 0; i < SegmentCount(); i++ )
1677  {
1678  int d = CSegment( i ).Distance( aP );
1679 
1680  if( d < min_d )
1681  {
1682  min_d = d;
1683  nearest = i;
1684  }
1685  }
1686 
1687  return nearest;
1688 }
1689 
1690 
1691 const std::string SHAPE_LINE_CHAIN::Format() const
1692 {
1693  std::stringstream ss;
1694 
1695  ss << "SHAPE_LINE_CHAIN( { ";
1696 
1697  for( int i = 0; i < PointCount(); i++ )
1698  {
1699  ss << "VECTOR2I( " << m_points[i].x << ", " << m_points[i].y << ")";
1700 
1701  if( i != PointCount() -1 )
1702  ss << ", ";
1703  }
1704 
1705  ss << "}, " << ( m_closed ? "true" : "false" );
1706  ss << " );";
1707 
1708  return ss.str();
1709 
1710  /* fixme: arcs
1711  for( size_t i = 0; i < m_arcs.size(); i++ )
1712  ss << m_arcs[i].GetCenter().x << " " << m_arcs[i].GetCenter().y << " "
1713  << m_arcs[i].GetP0().x << " " << m_arcs[i].GetP0().y << " "
1714  << m_arcs[i].GetCentralAngle();
1715 
1716  return ss.str();*/
1717 }
1718 
1719 
1721 {
1722  SHAPE_LINE_CHAIN a(*this), b( aOther );
1723  a.Simplify();
1724  b.Simplify();
1725 
1726  if( a.m_points.size() != b.m_points.size() )
1727  return false;
1728 
1729  for( int i = 0; i < a.PointCount(); i++ )
1730  {
1731  if( a.CPoint( i ) != b.CPoint( i ) )
1732  return false;
1733  }
1734 
1735  return true;
1736 }
1737 
1738 
1740 {
1742  return Intersect( aChain, dummy ) != 0;
1743 }
1744 
1745 
1747 {
1748  return new SHAPE_LINE_CHAIN( *this );
1749 }
1750 
1751 
1752 bool SHAPE_LINE_CHAIN::Parse( std::stringstream& aStream )
1753 {
1754  size_t n_pts;
1755  size_t n_arcs;
1756 
1757  m_points.clear();
1758  aStream >> n_pts;
1759 
1760  // Rough sanity check, just make sure the loop bounds aren't absolutely outlandish
1761  if( n_pts > aStream.str().size() )
1762  return false;
1763 
1764  aStream >> m_closed;
1765  aStream >> n_arcs;
1766 
1767  if( n_arcs > aStream.str().size() )
1768  return false;
1769 
1770  for( size_t i = 0; i < n_pts; i++ )
1771  {
1772  int x, y;
1773  ssize_t ind;
1774  aStream >> x;
1775  aStream >> y;
1776  m_points.emplace_back( x, y );
1777 
1778  aStream >> ind;
1779  m_shapes.emplace_back( std::make_pair( ind, SHAPE_IS_PT ) );
1780  }
1781 
1782  for( size_t i = 0; i < n_arcs; i++ )
1783  {
1784  VECTOR2I p0, pc;
1785  double angle;
1786 
1787  aStream >> pc.x;
1788  aStream >> pc.y;
1789  aStream >> p0.x;
1790  aStream >> p0.y;
1791  aStream >> angle;
1792 
1793  m_arcs.emplace_back( pc, p0, angle );
1794  }
1795 
1796  return true;
1797 }
1798 
1799 
1800 const VECTOR2I SHAPE_LINE_CHAIN::PointAlong( int aPathLength ) const
1801 {
1802  int total = 0;
1803 
1804  if( aPathLength == 0 )
1805  return CPoint( 0 );
1806 
1807  for( int i = 0; i < SegmentCount(); i++ )
1808  {
1809  const SEG& s = CSegment( i );
1810  int l = s.Length();
1811 
1812  if( total + l >= aPathLength )
1813  {
1814  VECTOR2I d( s.B - s.A );
1815  return s.A + d.Resize( aPathLength - total );
1816  }
1817 
1818  total += l;
1819  }
1820 
1821  return CPoint( -1 );
1822 }
1823 
1824 
1825 double SHAPE_LINE_CHAIN::Area( bool aAbsolute ) const
1826 {
1827  // see https://www.mathopenref.com/coordpolygonarea2.html
1828 
1829  if( !m_closed )
1830  return 0.0;
1831 
1832  double area = 0.0;
1833  int size = m_points.size();
1834 
1835  for( int i = 0, j = size - 1; i < size; ++i )
1836  {
1837  area += ( (double) m_points[j].x + m_points[i].x ) *
1838  ( (double) m_points[j].y - m_points[i].y );
1839  j = i;
1840  }
1841 
1842  if( aAbsolute )
1843  return std::fabs( area * 0.5 ); // The result would be negative if points are anti-clockwise
1844  else
1845  return -area * 0.5; // The result would be negative if points are anti-clockwise
1846 }
1847 
1848 
1850  m_point( aPoint ),
1851  m_finished( false ),
1852  m_state( 0 ),
1853  m_count( 0 )
1854 {
1855 }
1856 
1857 
1859  const VECTOR2I& ip, const VECTOR2I& ipNext )
1860 {
1861  if( ipNext.y == m_point.y )
1862  {
1863  if( ( ipNext.x == m_point.x )
1864  || ( ip.y == m_point.y && ( ( ipNext.x > m_point.x ) == ( ip.x < m_point.x ) ) ) )
1865  {
1866  m_finished = true;
1867  m_state = -1;
1868  return false;
1869  }
1870  }
1871 
1872  if( ( ip.y < m_point.y ) != ( ipNext.y < m_point.y ) )
1873  {
1874  if( ip.x >= m_point.x )
1875  {
1876  if( ipNext.x > m_point.x )
1877  {
1878  m_state = 1 - m_state;
1879  }
1880  else
1881  {
1882  double d = (double) ( ip.x - m_point.x ) * ( ipNext.y - m_point.y )
1883  - (double) ( ipNext.x - m_point.x ) * ( ip.y - m_point.y );
1884 
1885  if( !d )
1886  {
1887  m_finished = true;
1888  m_state = -1;
1889  return false;
1890  }
1891 
1892  if( ( d > 0 ) == ( ipNext.y > ip.y ) )
1893  m_state = 1 - m_state;
1894  }
1895  }
1896  else
1897  {
1898  if( ipNext.x > m_point.x )
1899  {
1900  double d = (double) ( ip.x - m_point.x ) * ( ipNext.y - m_point.y )
1901  - (double) ( ipNext.x - m_point.x ) * ( ip.y - m_point.y );
1902 
1903  if( !d )
1904  {
1905  m_finished = true;
1906  m_state = -1;
1907  return false;
1908  }
1909 
1910  if( ( d > 0 ) == ( ipNext.y > ip.y ) )
1911  m_state = 1 - m_state;
1912  }
1913  }
1914  }
1915 
1916  return true;
1917 }
1918 
1919 
1921 {
1922  if( !m_count )
1923  {
1924  m_lastPoint = aPolyline.CPoint( 0 );
1925  m_firstPoint = aPolyline.CPoint( 0 );
1926  }
1927 
1928  m_count += aPolyline.PointCount();
1929 
1930  for( int i = 1; i < aPolyline.PointCount(); i++ )
1931  {
1932  auto p = aPolyline.CPoint( i );
1933 
1934  if( !processVertex( m_lastPoint, p ) )
1935  return;
1936 
1937  m_lastPoint = p;
1938  }
1939 
1940 }
1941 
1942 
1944 {
1945  processVertex( m_lastPoint, m_firstPoint );
1946  return m_state > 0;
1947 }
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
Represent an intersection between two line segments.
const std::vector< std::pair< ssize_t, ssize_t > > & CShapes() const
BOX2I m_bbox
cached bounding box
const SHAPE_ARC & Arc(size_t aArc) const
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.
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.cpp:285
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Find all intersection points between our line chain and the segment aSeg.
ClipperLib::Path convertToClipper(bool aRequiredOrientation, std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, std::vector< SHAPE_ARC > &aArcBuffer) const
Create a new Clipper path from the SHAPE_LINE_CHAIN in a given orientation.
std::vector< INTERSECTION > INTERSECTIONS
bool IsSharedPt(size_t aIndex) const
Test if a point is shared between multiple shapes.
void RemoveShape(int aPointIndex)
Remove the shape at the given index from the line chain.
virtual BOX2I * GetCachedBBox() const
Definition: shape.h:312
bool IsClockwise() const
Definition: shape_arc.cpp:391
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.
SEG::ecoord SquaredDistance(const VECTOR2I &aP, bool aOutlineOnly=false) const
static const ssize_t SHAPE_IS_PT
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
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.
virtual bool IsClosed() const =0
VECTOR2I p
< Point of intersection between our and their.
VECTOR2I::extended_type ecoord
Definition: seg.h:43
Define a general 2D-vector/point.
Definition: vector2d.h:61
const VECTOR2I ReflectPoint(const VECTOR2I &aP) const
Reflect a point using this segment as axis.
Definition: seg.cpp:249
virtual size_t GetPointCount() const =0
compareOriginDistance(const VECTOR2I &aOrigin)
int Distance(const VECTOR2I &aP, bool aOutlineOnly=false) const
Compute the minimum distance between the line chain and a point aP.
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:39
size_t ArcCount() const
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.cpp:297
double Area(bool aAbsolute=true) const
Return the area of this chain.
virtual size_t GetSegmentCount() const =0
const SHAPE_LINE_CHAIN Reverse() const
Reverse point order in the line chain.
const std::vector< SHAPE_ARC > & CArcs() const
void convertArc(ssize_t aArcIndex)
Convert an arc to only a point chain by removing the arc and references.
int PointCount() const
Return the number of points (vertices) in this line chain.
static SEG::ecoord Square(int a)
Definition: seg.h:122
int FindSegment(const VECTOR2I &aP, int aThreshold=1) const
Search for segment containing point aP.
void splitArc(ssize_t aPtIndex, bool aCoincident=false)
Splits an arc into two arcs at aPtIndex.
const OPT< INTERSECTION > SelfIntersecting() const
Check if the line chain is self-intersecting.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
std::vector< SHAPE_ARC > m_arcs
const VECTOR2I NearestPoint(const VECTOR2I &aP, bool aAllowInternalShapePoints=true) const
Find a point on the line chain that is closest to point aP.
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.
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)
static LIB_SYMBOL * dummy()
Used to draw a dummy shape when a LIB_SYMBOL is not found in library.
Definition: sch_symbol.cpp:72
ssize_t ArcIndex(size_t aSegment) const
Return the arc index for the given segment index.
bool Intersects(const BOX2< Vec > &aRect) const
Definition: box2.h:217
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
bool IsArcStart(size_t aIndex) const
bool m_closed
is the line chain closed?
SHAPE_LINE_CHAIN()
Initialize an empty line chain.
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:79
int PathLength(const VECTOR2I &aP, int aIndex=-1) const
Compute the walk path length from the beginning of the line chain and the point aP belonging to our l...
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
bool IsArcSegment(size_t aSegment) const
bool IsClosed() const override
OPT< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:38
bool is_corner_their
Auxiliary flag to avoid copying intersection info to intersection refining code, used by the refining...
int Find(const VECTOR2I &aP, int aThreshold=0) const
Search for point aP.
void ClearArcs()
Remove all arc references in the line chain, resulting in a chain formed only of straight segments.
std::vector< VECTOR2I > m_points
array of vertices
void run_on_pair(std::pair< _Type, _Type > &__pair, _Function __f)
Apply a function to the first and second element of a std::pair.
Definition: kicad_algo.h:44
bool CheckClearance(const VECTOR2I &aP, const int aDist) const
Check if point aP is closer to (or on) an edge or vertex of the line chain.
const VECTOR2I & GetP0() const
Definition: shape_arc.h:111
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 VECTOR2I & GetArcMid() const
Definition: shape_arc.h:113
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.cpp:227
int ShapeCount() const
Return 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)
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 amendArc(size_t aArcIndex, const VECTOR2I &aNewStart, const VECTOR2I &aNewEnd)
const std::string Format() const override
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
void Reverse()
Definition: shape_arc.cpp:618
void Rotate(double aAngle, const VECTOR2I &aCenter=VECTOR2I(0, 0)) override
Rotate 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:268
Definition: seg.h:40
std::vector< std::pair< ssize_t, ssize_t > > m_shapes
Array of indices that refer to the index of the shape if the point is part of a larger shape,...
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
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=DefaultAccuracyForPCB(), double *aEffectiveAccuracy=nullptr) const
Construct a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:498
int index_their
When true, the corner [index_our] of the 'our' line lies exactly on 'their' line.
bool is_corner_our
When true, the corner [index_their] of the 'their' line lies exactly on 'our' line.
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
ssize_t reversedArcIndex(size_t aSegment) const
Return the arc index for the given segment index, looking backwards.
SHAPE_ARC & ConstructFromStartEndCenter(const VECTOR2I &aStart, const VECTOR2I &aEnd, const VECTOR2I &aCenter, bool aClockwise=false, double aWidth=0)
Constructs this arc from the given start, end and center.
Definition: shape_arc.cpp:201
VECTOR2I::extended_type ecoord
Definition: shape.h:236
Represent a polyline (an zero-thickness chain of connected line segments).
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
bool pair_contains(const std::pair< _Type, _Type > __pair, _Value __value)
Returns true if either of the elements in an std::pair contains the given value.
Definition: kicad_algo.h:112
VECTOR2I A
Definition: seg.h:48
bool IsArcEnd(size_t aIndex) const
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
Definition: util.h:98
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.
constexpr int delta
Holds information on each point of a SHAPE_LINE_CHAIN that is retrievable after an operation with Cli...
int EdgeContainingPoint(const VECTOR2I &aP, int aAccuracy=0) const
Check if point aP lies on an edge or vertex of the line chain.
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition: vector2d.h:293
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.
virtual const VECTOR2I GetPoint(int aIndex) const =0
static const std::pair< ssize_t, ssize_t > SHAPES_ARE_PT
static void addIntersection(SHAPE_LINE_CHAIN::INTERSECTIONS &aIps, int aPc, const SHAPE_LINE_CHAIN::INTERSECTION &aP)
int index_our
index of the intersecting corner/segment in the 'their' (Intersect() method parameter) line.
const VECTOR2I PointAlong(int aPathLength) const
const VECTOR2I & GetP1() const
Definition: shape_arc.h:112
VECTOR2I GetCenter() const
Definition: shape_arc.cpp:464
bool processVertex(const VECTOR2I &ip, const VECTOR2I &ipNext)
void Mirror(bool aX=true, bool aY=false, const VECTOR2I &aRef={ 0, 0 })
Mirror 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:331
VECTOR2I B
Definition: seg.h:49