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( 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::Collide( const VECTOR2I& aP, int aClearance, int* aActual ) const
89 {
91  SEG::ecoord clearance_sq = SEG::Square( aClearance );
92 
93  for( int i = 0; i < SegmentCount(); i++ )
94  {
95  const SEG& s = CSegment( i );
96  dist_sq = std::min( dist_sq, s.SquaredDistance( aP ) );
97 
98  if( ( dist_sq == 0 || dist_sq < clearance_sq ) && !aActual )
99  return true;
100  }
101 
102  if( dist_sq == 0 || dist_sq < clearance_sq )
103  {
104  if( aActual )
105  *aActual = sqrt( dist_sq );
106 
107  return true;
108  }
109 
110  return false;
111 }
112 
113 
114 void SHAPE_LINE_CHAIN::Rotate( double aAngle, const VECTOR2I& aCenter )
115 {
116  for( auto& pt : m_points )
117  {
118  pt -= aCenter;
119  pt = pt.Rotate( aAngle );
120  pt += aCenter;
121  }
122 
123  for( auto& arc : m_arcs )
124  arc.Rotate( aAngle, aCenter );
125 }
126 
127 
128 bool SHAPE_LINE_CHAIN::Collide( const SEG& aSeg, int aClearance, int* aActual ) const
129 {
131  SEG::ecoord clearance_sq = SEG::Square( aClearance );
132 
133  for( int i = 0; i < SegmentCount(); i++ )
134  {
135  const SEG& s = CSegment( i );
136  dist_sq = std::min( dist_sq, s.SquaredDistance( aSeg ) );
137 
138  if( ( dist_sq == 0 || dist_sq < clearance_sq ) && !aActual )
139  return true;
140  }
141 
142  if( dist_sq == 0 || dist_sq < clearance_sq )
143  {
144  if( aActual )
145  *aActual = sqrt( dist_sq );
146 
147  return true;
148  }
149 
150  return false;
151 }
152 
153 
155 {
156  SHAPE_LINE_CHAIN a( *this );
157 
158  reverse( a.m_points.begin(), a.m_points.end() );
159  reverse( a.m_shapes.begin(), a.m_shapes.end() );
160  reverse( a.m_arcs.begin(), a.m_arcs.end() );
161 
162  for( auto& sh : a.m_shapes )
163  {
164  if( sh != SHAPE_IS_PT )
165  sh = a.m_arcs.size() - sh - 1;
166  }
167 
168 
169  a.m_closed = m_closed;
170 
171  return a;
172 }
173 
174 
175 long long int SHAPE_LINE_CHAIN::Length() const
176 {
177  long long int l = 0;
178 
179  for( int i = 0; i < SegmentCount(); i++ )
180  l += CSegment( i ).Length();
181 
182  return l;
183 }
184 
185 
186 void SHAPE_LINE_CHAIN::Mirror( bool aX, bool aY, const VECTOR2I& aRef )
187 {
188  for( auto& pt : m_points )
189  {
190  if( aX )
191  pt.x = -pt.x + 2 * aRef.x;
192 
193  if( aY )
194  pt.y = -pt.y + 2 * aRef.y;
195  }
196 
197  for( auto& arc : m_arcs )
198  arc.Mirror( aX, aY, aRef );
199 }
200 
201 
202 void SHAPE_LINE_CHAIN::Replace( int aStartIndex, int aEndIndex, const VECTOR2I& aP )
203 {
204  if( aEndIndex < 0 )
205  aEndIndex += PointCount();
206 
207  if( aStartIndex < 0 )
208  aStartIndex += PointCount();
209 
210  aEndIndex = std::min( aEndIndex, PointCount() - 1 );
211 
212  // N.B. This works because convertArc changes m_shapes on the first run
213  for( int ind = aStartIndex; ind <= aEndIndex; ind++ )
214  {
215  if( m_shapes[ind] != SHAPE_IS_PT )
216  convertArc( ind );
217  }
218 
219  if( aStartIndex == aEndIndex )
220  m_points[aStartIndex] = aP;
221  else
222  {
223  m_points.erase( m_points.begin() + aStartIndex + 1, m_points.begin() + aEndIndex + 1 );
224  m_points[aStartIndex] = aP;
225 
226  m_shapes.erase( m_shapes.begin() + aStartIndex + 1, m_shapes.begin() + aEndIndex + 1 );
227  }
228 
229  assert( m_shapes.size() == m_points.size() );
230 }
231 
232 
233 void SHAPE_LINE_CHAIN::Replace( int aStartIndex, int aEndIndex, const SHAPE_LINE_CHAIN& aLine )
234 {
235  if( aEndIndex < 0 )
236  aEndIndex += PointCount();
237 
238  if( aStartIndex < 0 )
239  aStartIndex += PointCount();
240 
241  Remove( aStartIndex, aEndIndex );
242 
243  // The total new arcs index is added to the new arc indices
244  size_t prev_arc_count = m_arcs.size();
245  auto new_shapes = aLine.m_shapes;
246 
247  for( auto& shape : new_shapes )
248  shape += prev_arc_count;
249 
250  m_shapes.insert( m_shapes.begin() + aStartIndex, new_shapes.begin(), new_shapes.end() );
251  m_points.insert( m_points.begin() + aStartIndex, aLine.m_points.begin(), aLine.m_points.end() );
252  m_arcs.insert( m_arcs.end(), aLine.m_arcs.begin(), aLine.m_arcs.end() );
253 
254  assert( m_shapes.size() == m_points.size() );
255 }
256 
257 
258 void SHAPE_LINE_CHAIN::Remove( int aStartIndex, int aEndIndex )
259 {
260  assert( m_shapes.size() == m_points.size() );
261  if( aEndIndex < 0 )
262  aEndIndex += PointCount();
263 
264  if( aStartIndex < 0 )
265  aStartIndex += PointCount();
266 
267  if( aStartIndex >= PointCount() )
268  return;
269 
270  aEndIndex = std::min( aEndIndex, PointCount() );
271  std::set<size_t> extra_arcs;
272 
273  // Remove any overlapping arcs in the point range
274  for( int i = aStartIndex; i < aEndIndex; i++ )
275  {
276  if( m_shapes[i] != SHAPE_IS_PT )
277  extra_arcs.insert( m_shapes[i] );
278  }
279 
280  for( auto arc : extra_arcs )
281  convertArc( arc );
282 
283  m_shapes.erase( m_shapes.begin() + aStartIndex, m_shapes.begin() + aEndIndex + 1 );
284  m_points.erase( m_points.begin() + aStartIndex, m_points.begin() + aEndIndex + 1 );
285  assert( m_shapes.size() == m_points.size() );
286 }
287 
288 
289 int SHAPE_LINE_CHAIN::Distance( const VECTOR2I& aP, bool aOutlineOnly ) const
290 {
291  return sqrt( SquaredDistance( aP, aOutlineOnly ) );
292 }
293 
294 
295 SEG::ecoord SHAPE_LINE_CHAIN::SquaredDistance( const VECTOR2I& aP, bool aOutlineOnly ) const
296 {
298 
299  if( IsClosed() && PointInside( aP ) && !aOutlineOnly )
300  return 0;
301 
302  for( int s = 0; s < SegmentCount(); s++ )
303  d = std::min( d, CSegment( s ).SquaredDistance( aP ) );
304 
305  return d;
306 }
307 
308 
310 {
311  int ii = -1;
312  int min_dist = 2;
313 
314  int found_index = Find( aP );
315 
316  for( int s = 0; s < SegmentCount(); s++ )
317  {
318  const SEG seg = CSegment( s );
319  int dist = seg.Distance( aP );
320 
321  // make sure we are not producing a 'slightly concave' primitive. This might happen
322  // if aP lies very close to one of already existing points.
323  if( dist < min_dist && seg.A != aP && seg.B != aP )
324  {
325  min_dist = dist;
326  if( found_index < 0 )
327  ii = s;
328  else if( s < found_index )
329  ii = s;
330  }
331  }
332 
333  if( ii < 0 )
334  ii = found_index;
335 
336  if( ii >= 0 )
337  {
338  m_points.insert( m_points.begin() + ii + 1, aP );
339  m_shapes.insert( m_shapes.begin() + ii + 1, ssize_t( SHAPE_IS_PT ) );
340 
341  return ii + 1;
342  }
343 
344  return -1;
345 }
346 
347 
348 int SHAPE_LINE_CHAIN::Find( const VECTOR2I& aP ) const
349 {
350  for( int s = 0; s < PointCount(); s++ )
351  if( CPoint( s ) == aP )
352  return s;
353 
354  return -1;
355 }
356 
357 
359 {
360  for( int s = 0; s < SegmentCount(); s++ )
361  if( CSegment( s ).Distance( aP ) <= 1 )
362  return s;
363 
364  return -1;
365 }
366 
367 
368 const SHAPE_LINE_CHAIN SHAPE_LINE_CHAIN::Slice( int aStartIndex, int aEndIndex ) const
369 {
370  SHAPE_LINE_CHAIN rv;
371 
372  if( aEndIndex < 0 )
373  aEndIndex += PointCount();
374 
375  if( aStartIndex < 0 )
376  aStartIndex += PointCount();
377 
378  for( int i = aStartIndex; i <= aEndIndex && static_cast<size_t>( i ) < m_points.size(); i++ )
379  rv.Append( m_points[i] );
380 
381  return rv;
382 }
383 
384 
386 {
387  assert( m_shapes.size() == m_points.size() );
388 
389  if( aOtherLine.PointCount() == 0 )
390  return;
391 
392  else if( PointCount() == 0 || aOtherLine.CPoint( 0 ) != CPoint( -1 ) )
393  {
394  const VECTOR2I p = aOtherLine.CPoint( 0 );
395  m_points.push_back( p );
396  m_shapes.push_back( ssize_t( SHAPE_IS_PT ) );
397  m_bbox.Merge( p );
398  }
399 
400  size_t num_arcs = m_arcs.size();
401  m_arcs.insert( m_arcs.end(), aOtherLine.m_arcs.begin(), aOtherLine.m_arcs.end() );
402 
403  for( int i = 1; i < aOtherLine.PointCount(); i++ )
404  {
405  const VECTOR2I p = aOtherLine.CPoint( i );
406  m_points.push_back( p );
407 
408  ssize_t arcIndex = aOtherLine.ArcIndex( i );
409 
410  if( arcIndex != ssize_t( SHAPE_IS_PT ) )
411  m_shapes.push_back( num_arcs + arcIndex );
412  else
413  m_shapes.push_back( ssize_t( SHAPE_IS_PT ) );
414 
415  m_bbox.Merge( p );
416  }
417 
418  assert( m_shapes.size() == m_points.size() );
419 }
420 
421 
423 {
424  auto& chain = aArc.ConvertToPolyline();
425 
426  for( auto& pt : chain.CPoints() )
427  {
428  m_points.push_back( pt );
429  m_shapes.push_back( m_arcs.size() );
430  }
431 
432  m_arcs.push_back( aArc );
433 
434  assert( m_shapes.size() == m_points.size() );
435 }
436 
437 
438 void SHAPE_LINE_CHAIN::Insert( size_t aVertex, const VECTOR2I& aP )
439 {
440  if( m_shapes[aVertex] != SHAPE_IS_PT )
441  convertArc( aVertex );
442 
443  m_points.insert( m_points.begin() + aVertex, aP );
444  m_shapes.insert( m_shapes.begin() + aVertex, ssize_t( SHAPE_IS_PT ) );
445 
446  assert( m_shapes.size() == m_points.size() );
447 }
448 
449 
450 void SHAPE_LINE_CHAIN::Insert( size_t aVertex, const SHAPE_ARC& aArc )
451 {
452  if( m_shapes[aVertex] != SHAPE_IS_PT )
453  convertArc( aVertex );
454 
456  size_t arc_pos = m_arcs.size();
457 
458  for( auto arc_it = m_shapes.rbegin() ;
459  arc_it != m_shapes.rend() + aVertex;
460  arc_it++ )
461  {
462  if( *arc_it != SHAPE_IS_PT )
463  arc_pos = ( *arc_it )++;
464  }
465 
466  m_arcs.insert( m_arcs.begin() + arc_pos, aArc );
467 
469  auto& chain = aArc.ConvertToPolyline();
470  m_points.insert( m_points.begin() + aVertex,
471  chain.CPoints().begin(), chain.CPoints().end() );
472 
474  std::vector<size_t> new_points( chain.PointCount(), arc_pos );
475  m_shapes.insert( m_shapes.begin() + aVertex, new_points.begin(), new_points.end() );
476  assert( m_shapes.size() == m_points.size() );
477 }
478 
479 
481 {
483  m_origin( aOrigin ) {};
484 
487  {
488  return ( m_origin - aA.p ).EuclideanNorm() < ( m_origin - aB.p ).EuclideanNorm();
489  }
490 
492 };
493 
494 
495 int SHAPE_LINE_CHAIN::Intersect( const SEG& aSeg, INTERSECTIONS& aIp ) const
496 {
497  for( int s = 0; s < SegmentCount(); s++ )
498  {
499  OPT_VECTOR2I p = CSegment( s ).Intersect( aSeg );
500 
501  if( p )
502  {
503  INTERSECTION is;
504  is.our = CSegment( s );
505  is.their = aSeg;
506  is.p = *p;
507  aIp.push_back( is );
508  }
509  }
510 
511  compareOriginDistance comp( aSeg.A );
512  sort( aIp.begin(), aIp.end(), comp );
513 
514  return aIp.size();
515 }
516 
518 {
519  if( aIps.size() == 0 )
520  {
521  aIps.push_back( aP );
522  return;
523  }
524 
525  const auto& last = aIps.back();
526 
527  if( ( (last.our.Index() + 1) % aPc) == aP.our.Index() && last.p == aP.p )
528  return;
529 
530  if( last.our.Index() == aP.our.Index() && last.p == aP.p )
531  return;
532 
533  aIps.push_back( aP );
534 }
535 
537 {
538  BOX2I bb_other = aChain.BBox();
539 
540  for( int s1 = 0; s1 < SegmentCount(); s1++ )
541  {
542  const SEG& a = CSegment( s1 );
543  const BOX2I bb_cur( a.A, a.B - a.A );
544 
545  if( !bb_other.Intersects( bb_cur ) )
546  continue;
547 
548  for( int s2 = 0; s2 < aChain.SegmentCount(); s2++ )
549  {
550  const SEG& b = aChain.CSegment( s2 );
551  INTERSECTION is;
552 
553  if( a.Collinear( b ) )
554  {
555  is.our = a;
556  is.their = b;
557 
558  if( a.Contains( b.A ) ) { is.p = b.A; addIntersection(aIp, PointCount(), is); }
559  if( a.Contains( b.B ) ) { is.p = b.B; addIntersection(aIp, PointCount(), is); }
560  if( b.Contains( a.A ) ) { is.p = a.A; addIntersection(aIp, PointCount(), is); }
561  if( b.Contains( a.B ) ) { is.p = a.B; addIntersection(aIp, PointCount(), is); }
562  }
563  else
564  {
565  OPT_VECTOR2I p = a.Intersect( b );
566 
567  if( p )
568  {
569  is.p = *p;
570  is.our = a;
571  is.their = b;
572  addIntersection(aIp, PointCount(), is);
573  }
574  }
575  }
576  }
577 
578  return aIp.size();
579 }
580 
581 
583 {
584  int sum = 0;
585 
586  for( int i = 0; i < SegmentCount(); i++ )
587  {
588  const SEG seg = CSegment( i );
589  int d = seg.Distance( aP );
590 
591  if( d <= 1 )
592  {
593  sum += ( aP - seg.A ).EuclideanNorm();
594  return sum;
595  }
596  else
597  sum += seg.Length();
598  }
599 
600  return -1;
601 }
602 
603 
604 bool SHAPE_LINE_CHAIN::PointInside( const VECTOR2I& aPt, int aAccuracy, bool aUseBBoxCache ) const
605 {
606  /*
607  * Don't check the bounding box unless it's cached. Building it is about the same speed as
608  * the rigorous test below and so just slows things down by doing potentially two tests.
609  */
610  if( aUseBBoxCache && !m_bbox.Contains( aPt ) )
611  return false;
612 
613  if( !m_closed || PointCount() < 3 )
614  return false;
615 
616  bool inside = false;
617 
629  const std::vector<VECTOR2I>& points = CPoints();
630  int pointCount = points.size();
631 
632  for( int i = 0; i < pointCount; )
633  {
634  const auto p1 = points[ i++ ];
635  const auto p2 = points[ i == pointCount ? 0 : i ];
636  const auto diff = p2 - p1;
637 
638  if( diff.y != 0 )
639  {
640  const int d = rescale( diff.x, ( aPt.y - p1.y ), diff.y );
641 
642  if( ( ( p1.y > aPt.y ) != ( p2.y > aPt.y ) ) && ( aPt.x - p1.x < d ) )
643  inside = !inside;
644  }
645  }
646 
647  // If accuracy is <= 1 (nm) then we skip the accuracy test for performance. Otherwise
648  // we use "OnEdge(accuracy)" as a proxy for "Inside(accuracy)".
649  if( aAccuracy <= 1 )
650  return inside;
651  else
652  return inside || PointOnEdge( aPt, aAccuracy );
653 }
654 
655 
656 bool SHAPE_LINE_CHAIN::PointOnEdge( const VECTOR2I& aPt, int aAccuracy ) const
657 {
658  return EdgeContainingPoint( aPt, aAccuracy ) >= 0;
659 }
660 
661 int SHAPE_LINE_CHAIN::EdgeContainingPoint( const VECTOR2I& aPt, int aAccuracy ) const
662 {
663  if( !PointCount() )
664  return -1;
665 
666  else if( PointCount() == 1 )
667  {
668  VECTOR2I dist = m_points[0] - aPt;
669  return ( hypot( dist.x, dist.y ) <= aAccuracy + 1 ) ? 0 : -1;
670  }
671 
672  for( int i = 0; i < SegmentCount(); i++ )
673  {
674  const SEG s = CSegment( i );
675 
676  if( s.A == aPt || s.B == aPt )
677  return i;
678 
679  if( s.Distance( aPt ) <= aAccuracy + 1 )
680  return i;
681  }
682 
683  return -1;
684 }
685 
686 
687 bool SHAPE_LINE_CHAIN::CheckClearance( const VECTOR2I& aP, const int aDist) const
688 {
689  if( !PointCount() )
690  return false;
691 
692  else if( PointCount() == 1 )
693  return m_points[0] == aP;
694 
695  for( int i = 0; i < SegmentCount(); i++ )
696  {
697  const SEG s = CSegment( i );
698 
699  if( s.A == aP || s.B == aP )
700  return true;
701 
702  if( s.Distance( aP ) <= aDist )
703  return true;
704  }
705 
706  return false;
707 }
708 
709 
711 {
712  for( int s1 = 0; s1 < SegmentCount(); s1++ )
713  {
714  for( int s2 = s1 + 1; s2 < SegmentCount(); s2++ )
715  {
716  const VECTOR2I s2a = CSegment( s2 ).A, s2b = CSegment( s2 ).B;
717 
718  if( s1 + 1 != s2 && CSegment( s1 ).Contains( s2a ) )
719  {
720  INTERSECTION is;
721  is.our = CSegment( s1 );
722  is.their = CSegment( s2 );
723  is.p = s2a;
724  return is;
725  }
726  else if( CSegment( s1 ).Contains( s2b ) &&
727  // for closed polylines, the ending point of the
728  // last segment == starting point of the first segment
729  // this is a normal case, not self intersecting case
730  !( IsClosed() && s1 == 0 && s2 == SegmentCount()-1 ) )
731  {
732  INTERSECTION is;
733  is.our = CSegment( s1 );
734  is.their = CSegment( s2 );
735  is.p = s2b;
736  return is;
737  }
738  else
739  {
740  OPT_VECTOR2I p = CSegment( s1 ).Intersect( CSegment( s2 ), true );
741 
742  if( p )
743  {
744  INTERSECTION is;
745  is.our = CSegment( s1 );
746  is.their = CSegment( s2 );
747  is.p = *p;
748  return is;
749  }
750  }
751  }
752  }
753 
755 }
756 
757 
759 {
760  std::vector<VECTOR2I> pts_unique;
761  std::vector<ssize_t> shapes_unique;
762 
763  if( PointCount() < 2 )
764  {
765  return *this;
766  }
767  else if( PointCount() == 2 )
768  {
769  if( m_points[0] == m_points[1] )
770  m_points.pop_back();
771 
772  return *this;
773  }
774 
775  int i = 0;
776  int np = PointCount();
777 
778  // stage 1: eliminate duplicate vertices
779  while( i < np )
780  {
781  int j = i + 1;
782 
783  while( j < np && m_points[i] == m_points[j] && m_shapes[i] == m_shapes[j] )
784  j++;
785 
786  pts_unique.push_back( CPoint( i ) );
787  shapes_unique.push_back( m_shapes[i] );
788 
789  i = j;
790  }
791 
792  m_points.clear();
793  m_shapes.clear();
794  np = pts_unique.size();
795 
796  i = 0;
797 
798  // stage 1: eliminate collinear segments
799  while( i < np - 2 )
800  {
801  const VECTOR2I p0 = pts_unique[i];
802  const VECTOR2I p1 = pts_unique[i + 1];
803  int n = i;
804 
805  while( n < np - 2
806  && ( SEG( p0, p1 ).LineDistance( pts_unique[n + 2] ) <= 1
807  || SEG( p0, p1 ).Collinear( SEG( p1, pts_unique[n + 2] ) ) ) )
808  n++;
809 
810  m_points.push_back( p0 );
811  m_shapes.push_back( shapes_unique[i] );
812 
813  if( n > i )
814  i = n;
815 
816  if( n == np )
817  {
818  m_points.push_back( pts_unique[n - 1] );
819  m_shapes.push_back( shapes_unique[n - 1] );
820  return *this;
821  }
822 
823  i++;
824  }
825 
826  if( np > 1 )
827  {
828  m_points.push_back( pts_unique[np - 2] );
829  m_shapes.push_back( shapes_unique[np - 2] );
830  }
831 
832  m_points.push_back( pts_unique[np - 1] );
833  m_shapes.push_back( shapes_unique[np - 1] );
834 
835  assert( m_points.size() == m_shapes.size() );
836 
837  return *this;
838 }
839 
840 
842 {
843  int min_d = INT_MAX;
844  int nearest = 0;
845 
846  for( int i = 0; i < SegmentCount(); i++ )
847  {
848  int d = CSegment( i ).Distance( aP );
849 
850  if( d < min_d )
851  {
852  min_d = d;
853  nearest = i;
854  }
855  }
856 
857  return CSegment( nearest ).NearestPoint( aP );
858 }
859 
860 
861 const VECTOR2I SHAPE_LINE_CHAIN::NearestPoint( const SEG& aSeg, int& dist ) const
862 {
863  int nearest = 0;
864 
865  dist = INT_MAX;
866  for( int i = 0; i < PointCount(); i++ )
867  {
868  int d = aSeg.LineDistance( CPoint( i ) );
869 
870  if( d < dist )
871  {
872  dist = d;
873  nearest = i;
874  }
875  }
876 
877  return CPoint( nearest );
878 }
879 
880 
882 {
883  int min_d = INT_MAX;
884  int nearest = 0;
885 
886  for( int i = 0; i < SegmentCount(); i++ )
887  {
888  int d = CSegment( i ).Distance( aP );
889 
890  if( d < min_d )
891  {
892  min_d = d;
893  nearest = i;
894  }
895  }
896 
897  return nearest;
898 }
899 
900 
901 const std::string SHAPE_LINE_CHAIN::Format() const
902 {
903  std::stringstream ss;
904 
905  ss << m_points.size() << " " << ( m_closed ? 1 : 0 ) << " " << m_arcs.size() << " ";
906 
907  for( int i = 0; i < PointCount(); i++ )
908  ss << m_points[i].x << " " << m_points[i].y << " " << m_shapes[i];
909 
910  for( size_t i = 0; i < m_arcs.size(); i++ )
911  ss << m_arcs[i].GetCenter().x << " " << m_arcs[i].GetCenter().y << " "
912  << m_arcs[i].GetP0().x << " " << m_arcs[i].GetP0().y << " "
913  << m_arcs[i].GetCentralAngle();
914 
915  return ss.str();
916 }
917 
918 
920 {
921  SHAPE_LINE_CHAIN a(*this), b( aOther );
922  a.Simplify();
923  b.Simplify();
924 
925  if( a.m_points.size() != b.m_points.size() )
926  return false;
927 
928  for( int i = 0; i < a.PointCount(); i++)
929  if( a.CPoint( i ) != b.CPoint( i ) )
930  return false;
931  return true;
932 }
933 
934 
936 {
938  return Intersect( aChain, dummy ) != 0;
939 }
940 
941 
943 {
944  return new SHAPE_LINE_CHAIN( *this );
945 }
946 
947 bool SHAPE_LINE_CHAIN::Parse( std::stringstream& aStream )
948 {
949  size_t n_pts;
950  size_t n_arcs;
951 
952  m_points.clear();
953  aStream >> n_pts;
954 
955  // Rough sanity check, just make sure the loop bounds aren't absolutely outlandish
956  if( n_pts > aStream.str().size() )
957  return false;
958 
959  aStream >> m_closed;
960  aStream >> n_arcs;
961 
962  if( n_arcs > aStream.str().size() )
963  return false;
964 
965  for( size_t i = 0; i < n_pts; i++ )
966  {
967  int x, y;
968  ssize_t ind;
969  aStream >> x;
970  aStream >> y;
971  m_points.emplace_back( x, y );
972 
973  aStream >> ind;
974  m_shapes.push_back( ind );
975  }
976 
977  for( size_t i = 0; i < n_arcs; i++ )
978  {
979  VECTOR2I p0, pc;
980  double angle;
981 
982  aStream >> pc.x;
983  aStream >> pc.y;
984  aStream >> p0.x;
985  aStream >> p0.y;
986  aStream >> angle;
987 
988  m_arcs.emplace_back( pc, p0, angle );
989  }
990 
991  return true;
992 }
993 
994 
995 const VECTOR2I SHAPE_LINE_CHAIN::PointAlong( int aPathLength ) const
996 {
997  int total = 0;
998 
999  if( aPathLength == 0 )
1000  return CPoint( 0 );
1001 
1002  for( int i = 0; i < SegmentCount(); i++ )
1003  {
1004  const SEG& s = CSegment( i );
1005  int l = s.Length();
1006 
1007  if( total + l >= aPathLength )
1008  {
1009  VECTOR2I d( s.B - s.A );
1010  return s.A + d.Resize( aPathLength - total );
1011  }
1012 
1013  total += l;
1014  }
1015 
1016  return CPoint( -1 );
1017 }
1018 
1020 {
1021  // see https://www.mathopenref.com/coordpolygonarea2.html
1022 
1023  if( !m_closed )
1024  return 0.0;
1025 
1026  double area = 0.0;
1027  int size = m_points.size();
1028 
1029  for( int i = 0, j = size - 1; i < size; ++i )
1030  {
1031  area += ( (double) m_points[j].x + m_points[i].x ) * ( (double) m_points[j].y - m_points[i].y );
1032  j = i;
1033  }
1034 
1035  return -area * 0.5;
1036 }
1037 
1038 
1040  m_point( aPoint ),
1041  m_finished( false ),
1042  m_state( 0 ),
1043  m_count( 0 )
1044 {
1045 }
1046 
1047 
1049  const VECTOR2I& ip, const VECTOR2I& ipNext )
1050 {
1051  if( ipNext.y == m_point.y )
1052  {
1053  if( ( ipNext.x == m_point.x )
1054  || ( ip.y == m_point.y && ( ( ipNext.x > m_point.x ) == ( ip.x < m_point.x ) ) ) )
1055  {
1056  m_finished = true;
1057  m_state = -1;
1058  return false;
1059  }
1060  }
1061 
1062  if( ( ip.y < m_point.y ) != ( ipNext.y < m_point.y ) )
1063  {
1064  if( ip.x >= m_point.x )
1065  {
1066  if( ipNext.x > m_point.x )
1067  {
1068  m_state = 1 - m_state;
1069  }
1070  else
1071  {
1072  double d = (double) ( ip.x - m_point.x ) * ( ipNext.y - m_point.y )
1073  - (double) ( ipNext.x - m_point.x ) * ( ip.y - m_point.y );
1074 
1075  if( !d )
1076  {
1077  m_finished = true;
1078  m_state = -1;
1079  return false;
1080  }
1081 
1082  if( ( d > 0 ) == ( ipNext.y > ip.y ) )
1083  m_state = 1 - m_state;
1084  }
1085  }
1086  else
1087  {
1088  if( ipNext.x > m_point.x )
1089  {
1090  double d = (double) ( ip.x - m_point.x ) * ( ipNext.y - m_point.y )
1091  - (double) ( ipNext.x - m_point.x ) * ( ip.y - m_point.y );
1092 
1093  if( !d )
1094  {
1095  m_finished = true;
1096  m_state = -1;
1097  return false;
1098  }
1099 
1100  if( ( d > 0 ) == ( ipNext.y > ip.y ) )
1101  m_state = 1 - m_state;
1102  }
1103  }
1104  }
1105  return true;
1106 }
1107 
1108 
1110 {
1111  if( !m_count )
1112  {
1113  m_lastPoint = aPolyline.CPoint(0);
1114  m_firstPoint = aPolyline.CPoint(0);
1115  }
1116 
1117  m_count += aPolyline.PointCount();
1118 
1119  for (int i = 1; i < aPolyline.PointCount(); i++ )
1120  {
1121  auto p = aPolyline.CPoint( i );
1122  if( !processVertex( m_lastPoint, p ))
1123  return;
1124 
1125  m_lastPoint = p;
1126  }
1127 
1128 }
1129 
1130 
1132 {
1133  processVertex( m_lastPoint, m_firstPoint );
1134  return m_state > 0;
1135 }
1136 
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:128
int Length() const
Function Length()
Definition: seg.h:319
int Find(const VECTOR2I &aP) const
Function Find()
BOX2I m_bbox
cached bounding box
int Index() const
Function Index()
Definition: seg.h:337
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
int FindSegment(const VECTOR2I &aP) const
Function FindSegment()
long long int Length() const
Function Length()
int Split(const VECTOR2I &aP)
Function Split()
int EdgeContainingPoint(const VECTOR2I &aP, int aAccuracy=0) const
Function EdgeContainingPoint()
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:207
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
std::vector< INTERSECTION > INTERSECTIONS
bool PointOnEdge(const VECTOR2I &aP, int aAccuracy=0) const
Function PointOnEdge()
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Function Intersect()
Definition: seg.cpp:93
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Function Slice()
VECTOR2I p
point of intersection between our and their.
VECTOR2I::extended_type ecoord
Definition: seg.h:42
VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:61
int Distance(const VECTOR2I &aP, bool aOutlineOnly=false) const
Function Distance()
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:37
void AddPolyline(const SHAPE_LINE_CHAIN &aPolyline)
int LineDistance(const VECTOR2I &aP, bool aDetermineSide=false) const
Function LineDistance()
Definition: seg.h:378
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
void convertArc(ssize_t aArcIndex)
Converts an arc to only a point chain by removing the arc and references.
int PointCount() const
Function PointCount()
static SEG::ecoord Square(int a)
Definition: seg.h:116
const OPT< INTERSECTION > SelfIntersecting() const
Function SelfIntersecting()
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
std::vector< SHAPE_ARC > m_arcs
int PathLength(const VECTOR2I &aP) const
Function PathLength()
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
void Insert(size_t aVertex, const VECTOR2I &aP)
ssize_t ArcIndex(size_t aSegment) const
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
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:80
SEG their
segment belonging from the aOther argument of Intersect()
const BOX2I BBox(int aClearance=0) const override
Function BBox()
const std::vector< VECTOR2I > & CPoints() const
OPT< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:37
std::vector< VECTOR2I > m_points
array of vertices
bool CheckClearance(const VECTOR2I &aP, const int aDist) const
Function CheckClearance()
bool Contains(const Vec &aPoint) const
Function Contains.
Definition: box2.h:151
bool Intersects(const SHAPE_LINE_CHAIN &aChain) const
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
Definition: seg.h:395
SHAPE.
Definition: shape.h:74
SEG::ecoord SquaredDistance(const VECTOR2I &aP, bool aOutlineOnly=false) const
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 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
Function Collinear()
Definition: seg.h:243
Definition: seg.h:39
int NearestSegment(const VECTOR2I &aP) const
Find the segment nearest the given point.
VECTOR2< T > Resize(T aNewLength) const
Function Resize returns a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:392
bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr) const override
Function Collide()
VECTOR2< T > Rotate(double aAngle) const
Function Rotate rotates the vector by a given angle.
Definition: vector2d.h:377
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
static LIB_PART * dummy()
Used to draw a dummy shape when a LIB_PART is not found in library.
VECTOR2I::extended_type ecoord
Definition: shape.h:77
SHAPE_LINE_CHAIN.
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
VECTOR2I A
Definition: seg.h:47
T rescale(T aNumerator, T aValue, T aDenominator)
Function rescale()
Definition: util.h:95
line segment
Definition: shape.h:43
boost::optional< T > OPT
Definition: optional.h:7
bool operator()(const SHAPE_LINE_CHAIN::INTERSECTION &aA, const SHAPE_LINE_CHAIN::INTERSECTION &aB)
SHAPE * Clone() const override
Function Clone()
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const
Function PointInside()
bool IsClosed() const
Function IsClosed()
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Function Replace()
SEG our
segment belonging from the (this) argument of Intersect()
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=500.0) const
Constructs a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:231
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
compareOriginDistance(VECTOR2I &aOrigin)
bool Contains(const SEG &aSeg) const
Definition: seg.h:299
VECTOR2I B
Definition: seg.h:48