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