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