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