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