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( int 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( int 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 
224  a.m_closed = m_closed;
225 
226  return a;
227 }
228 
229 
230 long long int SHAPE_LINE_CHAIN::Length() const
231 {
232  long long int l = 0;
233 
234  for( int i = 0; i < SegmentCount(); i++ )
235  l += CSegment( i ).Length();
236 
237  return l;
238 }
239 
240 
241 void SHAPE_LINE_CHAIN::Mirror( bool aX, bool aY, const VECTOR2I& aRef )
242 {
243  for( auto& pt : m_points )
244  {
245  if( aX )
246  pt.x = -pt.x + 2 * aRef.x;
247 
248  if( aY )
249  pt.y = -pt.y + 2 * aRef.y;
250  }
251 
252  for( auto& arc : m_arcs )
253  arc.Mirror( aX, aY, aRef );
254 }
255 
256 
257 void SHAPE_LINE_CHAIN::Replace( int aStartIndex, int aEndIndex, const VECTOR2I& aP )
258 {
259  if( aEndIndex < 0 )
260  aEndIndex += PointCount();
261 
262  if( aStartIndex < 0 )
263  aStartIndex += PointCount();
264 
265  aEndIndex = std::min( aEndIndex, PointCount() - 1 );
266 
267  // N.B. This works because convertArc changes m_shapes on the first run
268  for( int ind = aStartIndex; ind <= aEndIndex; ind++ )
269  {
270  if( m_shapes[ind] != SHAPE_IS_PT )
271  convertArc( ind );
272  }
273 
274  if( aStartIndex == aEndIndex )
275  m_points[aStartIndex] = aP;
276  else
277  {
278  m_points.erase( m_points.begin() + aStartIndex + 1, m_points.begin() + aEndIndex + 1 );
279  m_points[aStartIndex] = aP;
280 
281  m_shapes.erase( m_shapes.begin() + aStartIndex + 1, m_shapes.begin() + aEndIndex + 1 );
282  }
283 
284  assert( m_shapes.size() == m_points.size() );
285 }
286 
287 
288 void SHAPE_LINE_CHAIN::Replace( int aStartIndex, int aEndIndex, const SHAPE_LINE_CHAIN& aLine )
289 {
290  if( aEndIndex < 0 )
291  aEndIndex += PointCount();
292 
293  if( aStartIndex < 0 )
294  aStartIndex += PointCount();
295 
296  Remove( aStartIndex, aEndIndex );
297 
298  // The total new arcs index is added to the new arc indices
299  size_t prev_arc_count = m_arcs.size();
300  auto new_shapes = aLine.m_shapes;
301 
302  for( auto& shape : new_shapes )
303  shape += prev_arc_count;
304 
305  m_shapes.insert( m_shapes.begin() + aStartIndex, new_shapes.begin(), new_shapes.end() );
306  m_points.insert( m_points.begin() + aStartIndex, aLine.m_points.begin(), aLine.m_points.end() );
307  m_arcs.insert( m_arcs.end(), aLine.m_arcs.begin(), aLine.m_arcs.end() );
308 
309  assert( m_shapes.size() == m_points.size() );
310 }
311 
312 
313 void SHAPE_LINE_CHAIN::Remove( int aStartIndex, int aEndIndex )
314 {
315  assert( m_shapes.size() == m_points.size() );
316  if( aEndIndex < 0 )
317  aEndIndex += PointCount();
318 
319  if( aStartIndex < 0 )
320  aStartIndex += PointCount();
321 
322  if( aStartIndex >= PointCount() )
323  return;
324 
325  aEndIndex = std::min( aEndIndex, PointCount() );
326  std::set<size_t> extra_arcs;
327 
328  // Remove any overlapping arcs in the point range
329  for( int i = aStartIndex; i < aEndIndex; i++ )
330  {
331  if( m_shapes[i] != SHAPE_IS_PT )
332  extra_arcs.insert( m_shapes[i] );
333  }
334 
335  for( auto arc : extra_arcs )
336  convertArc( arc );
337 
338  m_shapes.erase( m_shapes.begin() + aStartIndex, m_shapes.begin() + aEndIndex + 1 );
339  m_points.erase( m_points.begin() + aStartIndex, m_points.begin() + aEndIndex + 1 );
340  assert( m_shapes.size() == m_points.size() );
341 }
342 
343 
344 int SHAPE_LINE_CHAIN::Distance( const VECTOR2I& aP, bool aOutlineOnly ) const
345 {
346  return sqrt( SquaredDistance( aP, aOutlineOnly ) );
347 }
348 
349 
350 SEG::ecoord SHAPE_LINE_CHAIN_BASE::SquaredDistance( const VECTOR2I& aP, bool aOutlineOnly ) const
351 {
353 
354  if( IsClosed() && PointInside( aP ) && !aOutlineOnly )
355  return 0;
356 
357  for( int s = 0; s < GetSegmentCount(); s++ )
358  d = std::min( d, GetSegment( s ).SquaredDistance( aP ) );
359 
360  return d;
361 }
362 
363 
365 {
366  int ii = -1;
367  int min_dist = 2;
368 
369  int found_index = Find( aP );
370 
371  for( int s = 0; s < SegmentCount(); s++ )
372  {
373  const SEG seg = CSegment( s );
374  int dist = seg.Distance( aP );
375 
376  // make sure we are not producing a 'slightly concave' primitive. This might happen
377  // if aP lies very close to one of already existing points.
378  if( dist < min_dist && seg.A != aP && seg.B != aP )
379  {
380  min_dist = dist;
381  if( found_index < 0 )
382  ii = s;
383  else if( s < found_index )
384  ii = s;
385  }
386  }
387 
388  if( ii < 0 )
389  ii = found_index;
390 
391  if( ii >= 0 )
392  {
393  m_points.insert( m_points.begin() + ii + 1, aP );
394  m_shapes.insert( m_shapes.begin() + ii + 1, ssize_t( SHAPE_IS_PT ) );
395 
396  return ii + 1;
397  }
398 
399  return -1;
400 }
401 
402 
403 int SHAPE_LINE_CHAIN::Find( const VECTOR2I& aP ) const
404 {
405  for( int s = 0; s < PointCount(); s++ )
406  if( CPoint( s ) == aP )
407  return s;
408 
409  return -1;
410 }
411 
412 
414 {
415  for( int s = 0; s < SegmentCount(); s++ )
416  if( CSegment( s ).Distance( aP ) <= 1 )
417  return s;
418 
419  return -1;
420 }
421 
422 
423 const SHAPE_LINE_CHAIN SHAPE_LINE_CHAIN::Slice( int aStartIndex, int aEndIndex ) const
424 {
425  SHAPE_LINE_CHAIN rv;
426 
427  if( aEndIndex < 0 )
428  aEndIndex += PointCount();
429 
430  if( aStartIndex < 0 )
431  aStartIndex += PointCount();
432 
433  for( int i = aStartIndex; i <= aEndIndex && static_cast<size_t>( i ) < m_points.size(); i++ )
434  rv.Append( m_points[i] );
435 
436  return rv;
437 }
438 
439 
441 {
442  assert( m_shapes.size() == m_points.size() );
443 
444  if( aOtherLine.PointCount() == 0 )
445  return;
446 
447  else if( PointCount() == 0 || aOtherLine.CPoint( 0 ) != CPoint( -1 ) )
448  {
449  const VECTOR2I p = aOtherLine.CPoint( 0 );
450  m_points.push_back( p );
451  m_shapes.push_back( ssize_t( SHAPE_IS_PT ) );
452  m_bbox.Merge( p );
453  }
454 
455  size_t num_arcs = m_arcs.size();
456  m_arcs.insert( m_arcs.end(), aOtherLine.m_arcs.begin(), aOtherLine.m_arcs.end() );
457 
458  for( int i = 1; i < aOtherLine.PointCount(); i++ )
459  {
460  const VECTOR2I p = aOtherLine.CPoint( i );
461  m_points.push_back( p );
462 
463  ssize_t arcIndex = aOtherLine.ArcIndex( i );
464 
465  if( arcIndex != ssize_t( SHAPE_IS_PT ) )
466  m_shapes.push_back( num_arcs + arcIndex );
467  else
468  m_shapes.push_back( ssize_t( SHAPE_IS_PT ) );
469 
470  m_bbox.Merge( p );
471  }
472 
473  assert( m_shapes.size() == m_points.size() );
474 }
475 
476 
478 {
479  auto& chain = aArc.ConvertToPolyline();
480 
481  for( auto& pt : chain.CPoints() )
482  {
483  m_points.push_back( pt );
484  m_shapes.push_back( m_arcs.size() );
485  }
486 
487  m_arcs.push_back( aArc );
488 
489  assert( m_shapes.size() == m_points.size() );
490 }
491 
492 
493 void SHAPE_LINE_CHAIN::Insert( size_t aVertex, const VECTOR2I& aP )
494 {
495  if( m_shapes[aVertex] != SHAPE_IS_PT )
496  convertArc( aVertex );
497 
498  m_points.insert( m_points.begin() + aVertex, aP );
499  m_shapes.insert( m_shapes.begin() + aVertex, ssize_t( SHAPE_IS_PT ) );
500 
501  assert( m_shapes.size() == m_points.size() );
502 }
503 
504 
505 void SHAPE_LINE_CHAIN::Insert( size_t aVertex, const SHAPE_ARC& aArc )
506 {
507  if( m_shapes[aVertex] != SHAPE_IS_PT )
508  convertArc( aVertex );
509 
511  size_t arc_pos = m_arcs.size();
512 
513  for( auto arc_it = m_shapes.rbegin() ;
514  arc_it != m_shapes.rend() + aVertex;
515  arc_it++ )
516  {
517  if( *arc_it != SHAPE_IS_PT )
518  arc_pos = ( *arc_it )++;
519  }
520 
521  m_arcs.insert( m_arcs.begin() + arc_pos, aArc );
522 
524  auto& chain = aArc.ConvertToPolyline();
525  m_points.insert( m_points.begin() + aVertex,
526  chain.CPoints().begin(), chain.CPoints().end() );
527 
529  std::vector<size_t> new_points( chain.PointCount(), arc_pos );
530  m_shapes.insert( m_shapes.begin() + aVertex, new_points.begin(), new_points.end() );
531  assert( m_shapes.size() == m_points.size() );
532 }
533 
534 
536 {
537  compareOriginDistance( const VECTOR2I& aOrigin ) :
538  m_origin( aOrigin ) {};
539 
541  const SHAPE_LINE_CHAIN::INTERSECTION& aB ) const
542  {
543  return ( m_origin - aA.p ).EuclideanNorm() < ( m_origin - aB.p ).EuclideanNorm();
544  }
545 
547 };
548 
549 
550 int SHAPE_LINE_CHAIN::Intersect( const SEG& aSeg, INTERSECTIONS& aIp ) const
551 {
552  for( int s = 0; s < SegmentCount(); s++ )
553  {
554  OPT_VECTOR2I p = CSegment( s ).Intersect( aSeg );
555 
556  if( p )
557  {
558  INTERSECTION is;
559  is.our = CSegment( s );
560  is.their = aSeg;
561  is.p = *p;
562  aIp.push_back( is );
563  }
564  }
565 
566  compareOriginDistance comp( aSeg.A );
567  sort( aIp.begin(), aIp.end(), comp );
568 
569  return aIp.size();
570 }
571 
573 {
574  if( aIps.size() == 0 )
575  {
576  aIps.push_back( aP );
577  return;
578  }
579 
580  const auto& last = aIps.back();
581 
582  if( ( (last.our.Index() + 1) % aPc) == aP.our.Index() && last.p == aP.p )
583  return;
584 
585  if( last.our.Index() == aP.our.Index() && last.p == aP.p )
586  return;
587 
588  aIps.push_back( aP );
589 }
590 
592 {
593  BOX2I bb_other = aChain.BBox();
594 
595  for( int s1 = 0; s1 < SegmentCount(); s1++ )
596  {
597  const SEG& a = CSegment( s1 );
598  const BOX2I bb_cur( a.A, a.B - a.A );
599 
600  if( !bb_other.Intersects( bb_cur ) )
601  continue;
602 
603  for( int s2 = 0; s2 < aChain.SegmentCount(); s2++ )
604  {
605  const SEG& b = aChain.CSegment( s2 );
606  INTERSECTION is;
607 
608  if( a.Collinear( b ) )
609  {
610  is.our = a;
611  is.their = b;
612 
613  if( a.Contains( b.A ) ) { is.p = b.A; addIntersection(aIp, PointCount(), is); }
614  if( a.Contains( b.B ) ) { is.p = b.B; addIntersection(aIp, PointCount(), is); }
615  if( b.Contains( a.A ) ) { is.p = a.A; addIntersection(aIp, PointCount(), is); }
616  if( b.Contains( a.B ) ) { is.p = a.B; addIntersection(aIp, PointCount(), is); }
617  }
618  else
619  {
620  OPT_VECTOR2I p = a.Intersect( b );
621 
622  if( p )
623  {
624  is.p = *p;
625  is.our = a;
626  is.their = b;
627  addIntersection(aIp, PointCount(), is);
628  }
629  }
630  }
631  }
632 
633  return aIp.size();
634 }
635 
636 
638 {
639  int sum = 0;
640 
641  for( int i = 0; i < SegmentCount(); i++ )
642  {
643  const SEG seg = CSegment( i );
644  int d = seg.Distance( aP );
645 
646  if( d <= 1 )
647  {
648  sum += ( aP - seg.A ).EuclideanNorm();
649  return sum;
650  }
651  else
652  sum += seg.Length();
653  }
654 
655  return -1;
656 }
657 
658 
659 bool SHAPE_LINE_CHAIN_BASE::PointInside( const VECTOR2I& aPt, int aAccuracy,
660  bool aUseBBoxCache ) const
661 {
662  /*
663  * Don't check the bounding box unless it's cached. Building it is about the same speed as
664  * the rigorous test below and so just slows things down by doing potentially two tests.
665  */
666  //if( aUseBBoxCache && !m_bbox.Contains( aPt ) )
667  //return false;
668 
669  // fixme: bbox cache...
670 
671  if( !IsClosed() || GetPointCount() < 3 )
672  return false;
673 
674  bool inside = false;
675 
687  int pointCount = GetPointCount();
688 
689  for( int i = 0; i < pointCount; )
690  {
691  const auto p1 = GetPoint( i++ );
692  const auto p2 = GetPoint( i == pointCount ? 0 : i );
693  const auto diff = p2 - p1;
694 
695  if( diff.y != 0 )
696  {
697  const int d = rescale( diff.x, ( aPt.y - p1.y ), diff.y );
698 
699  if( ( ( p1.y > aPt.y ) != ( p2.y > aPt.y ) ) && ( aPt.x - p1.x < d ) )
700  inside = !inside;
701  }
702  }
703 
704  // If accuracy is <= 1 (nm) then we skip the accuracy test for performance. Otherwise
705  // we use "OnEdge(accuracy)" as a proxy for "Inside(accuracy)".
706  if( aAccuracy <= 1 )
707  return inside;
708  else
709  return inside || PointOnEdge( aPt, aAccuracy );
710 }
711 
712 
713 bool SHAPE_LINE_CHAIN_BASE::PointOnEdge( const VECTOR2I& aPt, int aAccuracy ) const
714 {
715  return EdgeContainingPoint( aPt, aAccuracy ) >= 0;
716 }
717 
718 int SHAPE_LINE_CHAIN_BASE::EdgeContainingPoint( const VECTOR2I& aPt, int aAccuracy ) const
719 {
720  if( !GetPointCount() )
721  return -1;
722 
723  else if( GetPointCount() == 1 )
724  {
725  VECTOR2I dist = GetPoint(0) - aPt;
726  return ( hypot( dist.x, dist.y ) <= aAccuracy + 1 ) ? 0 : -1;
727  }
728 
729  for( int i = 0; i < GetSegmentCount(); i++ )
730  {
731  const SEG s = GetSegment( i );
732 
733  if( s.A == aPt || s.B == aPt )
734  return i;
735 
736  if( s.Distance( aPt ) <= aAccuracy + 1 )
737  return i;
738  }
739 
740  return -1;
741 }
742 
743 
744 bool SHAPE_LINE_CHAIN::CheckClearance( const VECTOR2I& aP, const int aDist) const
745 {
746  if( !PointCount() )
747  return false;
748 
749  else if( PointCount() == 1 )
750  return m_points[0] == aP;
751 
752  for( int i = 0; i < SegmentCount(); i++ )
753  {
754  const SEG s = CSegment( i );
755 
756  if( s.A == aP || s.B == aP )
757  return true;
758 
759  if( s.Distance( aP ) <= aDist )
760  return true;
761  }
762 
763  return false;
764 }
765 
766 
768 {
769  for( int s1 = 0; s1 < SegmentCount(); s1++ )
770  {
771  for( int s2 = s1 + 1; s2 < SegmentCount(); s2++ )
772  {
773  const VECTOR2I s2a = CSegment( s2 ).A, s2b = CSegment( s2 ).B;
774 
775  if( s1 + 1 != s2 && CSegment( s1 ).Contains( s2a ) )
776  {
777  INTERSECTION is;
778  is.our = CSegment( s1 );
779  is.their = CSegment( s2 );
780  is.p = s2a;
781  return is;
782  }
783  else if( CSegment( s1 ).Contains( s2b ) &&
784  // for closed polylines, the ending point of the
785  // last segment == starting point of the first segment
786  // this is a normal case, not self intersecting case
787  !( IsClosed() && s1 == 0 && s2 == SegmentCount()-1 ) )
788  {
789  INTERSECTION is;
790  is.our = CSegment( s1 );
791  is.their = CSegment( s2 );
792  is.p = s2b;
793  return is;
794  }
795  else
796  {
797  OPT_VECTOR2I p = CSegment( s1 ).Intersect( CSegment( s2 ), true );
798 
799  if( p )
800  {
801  INTERSECTION is;
802  is.our = CSegment( s1 );
803  is.their = CSegment( s2 );
804  is.p = *p;
805  return is;
806  }
807  }
808  }
809  }
810 
812 }
813 
814 
816 {
817  std::vector<VECTOR2I> pts_unique;
818  std::vector<ssize_t> shapes_unique;
819 
820  if( PointCount() < 2 )
821  {
822  return *this;
823  }
824  else if( PointCount() == 2 )
825  {
826  if( m_points[0] == m_points[1] )
827  m_points.pop_back();
828 
829  return *this;
830  }
831 
832  int i = 0;
833  int np = PointCount();
834 
835  // stage 1: eliminate duplicate vertices
836  while( i < np )
837  {
838  int j = i + 1;
839 
840  while( j < np && m_points[i] == m_points[j] && m_shapes[i] == m_shapes[j] )
841  j++;
842 
843  pts_unique.push_back( CPoint( i ) );
844  shapes_unique.push_back( m_shapes[i] );
845 
846  i = j;
847  }
848 
849  m_points.clear();
850  m_shapes.clear();
851  np = pts_unique.size();
852 
853  i = 0;
854 
855  // stage 1: eliminate collinear segments
856  while( i < np - 2 )
857  {
858  const VECTOR2I p0 = pts_unique[i];
859  const VECTOR2I p1 = pts_unique[i + 1];
860  int n = i;
861 
862  while( n < np - 2
863  && ( SEG( p0, p1 ).LineDistance( pts_unique[n + 2] ) <= 1
864  || SEG( p0, p1 ).Collinear( SEG( p1, pts_unique[n + 2] ) ) ) )
865  n++;
866 
867  m_points.push_back( p0 );
868  m_shapes.push_back( shapes_unique[i] );
869 
870  if( n > i )
871  i = n;
872 
873  if( n == np )
874  {
875  m_points.push_back( pts_unique[n - 1] );
876  m_shapes.push_back( shapes_unique[n - 1] );
877  return *this;
878  }
879 
880  i++;
881  }
882 
883  if( np > 1 )
884  {
885  m_points.push_back( pts_unique[np - 2] );
886  m_shapes.push_back( shapes_unique[np - 2] );
887  }
888 
889  m_points.push_back( pts_unique[np - 1] );
890  m_shapes.push_back( shapes_unique[np - 1] );
891 
892  assert( m_points.size() == m_shapes.size() );
893 
894  return *this;
895 }
896 
897 
899 {
900  int min_d = INT_MAX;
901  int nearest = 0;
902 
903  for( int i = 0; i < SegmentCount(); i++ )
904  {
905  int d = CSegment( i ).Distance( aP );
906 
907  if( d < min_d )
908  {
909  min_d = d;
910  nearest = i;
911  }
912  }
913 
914  return CSegment( nearest ).NearestPoint( aP );
915 }
916 
917 
918 const VECTOR2I SHAPE_LINE_CHAIN::NearestPoint( const SEG& aSeg, int& dist ) const
919 {
920  int nearest = 0;
921 
922  dist = INT_MAX;
923  for( int i = 0; i < PointCount(); i++ )
924  {
925  int d = aSeg.LineDistance( CPoint( i ) );
926 
927  if( d < dist )
928  {
929  dist = d;
930  nearest = i;
931  }
932  }
933 
934  return CPoint( nearest );
935 }
936 
937 
939 {
940  int min_d = INT_MAX;
941  int nearest = 0;
942 
943  for( int i = 0; i < SegmentCount(); i++ )
944  {
945  int d = CSegment( i ).Distance( aP );
946 
947  if( d < min_d )
948  {
949  min_d = d;
950  nearest = i;
951  }
952  }
953 
954  return nearest;
955 }
956 
957 
958 const std::string SHAPE_LINE_CHAIN::Format() const
959 {
960  std::stringstream ss;
961 
962 
963  ss << "SHAPE_LINE_CHAIN( { ";
964  for( int i = 0; i < PointCount(); i++ )
965  {
966  ss << "VECTOR2I( " << m_points[i].x << ", " << m_points[i].y << ")";
967  if( i != PointCount() -1 )
968  ss << ", ";
969  }
970 
971  ss << "}, " << ( m_closed ? "true" : "false" );
972  ss << " );";
973 
974 
975 
976  return ss.str();
977 
978 
979  /* fixme: arcs
980  for( size_t i = 0; i < m_arcs.size(); i++ )
981  ss << m_arcs[i].GetCenter().x << " " << m_arcs[i].GetCenter().y << " "
982  << m_arcs[i].GetP0().x << " " << m_arcs[i].GetP0().y << " "
983  << m_arcs[i].GetCentralAngle();
984 
985  return ss.str();*/
986 }
987 
988 
990 {
991  SHAPE_LINE_CHAIN a(*this), b( aOther );
992  a.Simplify();
993  b.Simplify();
994 
995  if( a.m_points.size() != b.m_points.size() )
996  return false;
997 
998  for( int i = 0; i < a.PointCount(); i++)
999  if( a.CPoint( i ) != b.CPoint( i ) )
1000  return false;
1001  return true;
1002 }
1003 
1004 
1006 {
1008  return Intersect( aChain, dummy ) != 0;
1009 }
1010 
1011 
1013 {
1014  return new SHAPE_LINE_CHAIN( *this );
1015 }
1016 
1017 bool SHAPE_LINE_CHAIN::Parse( std::stringstream& aStream )
1018 {
1019  size_t n_pts;
1020  size_t n_arcs;
1021 
1022  m_points.clear();
1023  aStream >> n_pts;
1024 
1025  // Rough sanity check, just make sure the loop bounds aren't absolutely outlandish
1026  if( n_pts > aStream.str().size() )
1027  return false;
1028 
1029  aStream >> m_closed;
1030  aStream >> n_arcs;
1031 
1032  if( n_arcs > aStream.str().size() )
1033  return false;
1034 
1035  for( size_t i = 0; i < n_pts; i++ )
1036  {
1037  int x, y;
1038  ssize_t ind;
1039  aStream >> x;
1040  aStream >> y;
1041  m_points.emplace_back( x, y );
1042 
1043  aStream >> ind;
1044  m_shapes.push_back( ind );
1045  }
1046 
1047  for( size_t i = 0; i < n_arcs; i++ )
1048  {
1049  VECTOR2I p0, pc;
1050  double angle;
1051 
1052  aStream >> pc.x;
1053  aStream >> pc.y;
1054  aStream >> p0.x;
1055  aStream >> p0.y;
1056  aStream >> angle;
1057 
1058  m_arcs.emplace_back( pc, p0, angle );
1059  }
1060 
1061  return true;
1062 }
1063 
1064 
1065 const VECTOR2I SHAPE_LINE_CHAIN::PointAlong( int aPathLength ) const
1066 {
1067  int total = 0;
1068 
1069  if( aPathLength == 0 )
1070  return CPoint( 0 );
1071 
1072  for( int i = 0; i < SegmentCount(); i++ )
1073  {
1074  const SEG& s = CSegment( i );
1075  int l = s.Length();
1076 
1077  if( total + l >= aPathLength )
1078  {
1079  VECTOR2I d( s.B - s.A );
1080  return s.A + d.Resize( aPathLength - total );
1081  }
1082 
1083  total += l;
1084  }
1085 
1086  return CPoint( -1 );
1087 }
1088 
1090 {
1091  // see https://www.mathopenref.com/coordpolygonarea2.html
1092 
1093  if( !m_closed )
1094  return 0.0;
1095 
1096  double area = 0.0;
1097  int size = m_points.size();
1098 
1099  for( int i = 0, j = size - 1; i < size; ++i )
1100  {
1101  area += ( (double) m_points[j].x + m_points[i].x ) * ( (double) m_points[j].y - m_points[i].y );
1102  j = i;
1103  }
1104 
1105  return -area * 0.5;
1106 }
1107 
1108 
1110  m_point( aPoint ),
1111  m_finished( false ),
1112  m_state( 0 ),
1113  m_count( 0 )
1114 {
1115 }
1116 
1117 
1119  const VECTOR2I& ip, const VECTOR2I& ipNext )
1120 {
1121  if( ipNext.y == m_point.y )
1122  {
1123  if( ( ipNext.x == m_point.x )
1124  || ( ip.y == m_point.y && ( ( ipNext.x > m_point.x ) == ( ip.x < m_point.x ) ) ) )
1125  {
1126  m_finished = true;
1127  m_state = -1;
1128  return false;
1129  }
1130  }
1131 
1132  if( ( ip.y < m_point.y ) != ( ipNext.y < m_point.y ) )
1133  {
1134  if( ip.x >= m_point.x )
1135  {
1136  if( ipNext.x > m_point.x )
1137  {
1138  m_state = 1 - m_state;
1139  }
1140  else
1141  {
1142  double d = (double) ( ip.x - m_point.x ) * ( ipNext.y - m_point.y )
1143  - (double) ( ipNext.x - m_point.x ) * ( ip.y - m_point.y );
1144 
1145  if( !d )
1146  {
1147  m_finished = true;
1148  m_state = -1;
1149  return false;
1150  }
1151 
1152  if( ( d > 0 ) == ( ipNext.y > ip.y ) )
1153  m_state = 1 - m_state;
1154  }
1155  }
1156  else
1157  {
1158  if( ipNext.x > m_point.x )
1159  {
1160  double d = (double) ( ip.x - m_point.x ) * ( ipNext.y - m_point.y )
1161  - (double) ( ipNext.x - m_point.x ) * ( ip.y - m_point.y );
1162 
1163  if( !d )
1164  {
1165  m_finished = true;
1166  m_state = -1;
1167  return false;
1168  }
1169 
1170  if( ( d > 0 ) == ( ipNext.y > ip.y ) )
1171  m_state = 1 - m_state;
1172  }
1173  }
1174  }
1175  return true;
1176 }
1177 
1178 
1180 {
1181  if( !m_count )
1182  {
1183  m_lastPoint = aPolyline.CPoint( 0 );
1184  m_firstPoint = aPolyline.CPoint( 0 );
1185  }
1186 
1187  m_count += aPolyline.PointCount();
1188 
1189  for( int i = 1; i < aPolyline.PointCount(); i++ )
1190  {
1191  auto p = aPolyline.CPoint( i );
1192 
1193  if( !processVertex( m_lastPoint, p ) )
1194  return;
1195 
1196  m_lastPoint = p;
1197  }
1198 
1199 }
1200 
1201 
1203 {
1204  processVertex( m_lastPoint, m_firstPoint );
1205  return m_state > 0;
1206 }
1207 
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:134
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 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
SEG::ecoord SquaredDistance(const VECTOR2I &aP, bool aOutlineOnly=false) const
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Function Intersect()
Definition: seg.cpp:104
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:42
VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:61
virtual size_t GetPointCount() const =0
compareOriginDistance(const VECTOR2I &aOrigin)
int Distance(const VECTOR2I &aP, bool aOutlineOnly=false) const
Function Distance()
bool PointOnEdge(const VECTOR2I &aP, int aAccuracy=0) const
Function PointOnEdge()
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
virtual size_t GetSegmentCount() const =0
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()
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Function Collide()
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)
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 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:370
bool IsClosed() const override
Function IsClosed()
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 PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const
Function PointInside()
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:122
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
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
Function Resize returns a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:392
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:125
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:45
boost::optional< T > OPT
Definition: optional.h:7
SHAPE * Clone() const override
Function Clone()
int EdgeContainingPoint(const VECTOR2I &aP, int aAccuracy=0) const
Function EdgeContainingPoint()
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Function Replace()
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:299
VECTOR2I B
Definition: seg.h:48