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 
28 #include <geometry/shape_circle.h>
29 #include "clipper.hpp"
30 
31 
32 ClipperLib::Path SHAPE_LINE_CHAIN::convertToClipper( bool aRequiredOrientation ) const
33 {
34  ClipperLib::Path c_path;
35 
36  for( int i = 0; i < PointCount(); i++ )
37  {
38  const VECTOR2I& vertex = CPoint( i );
39  c_path.push_back( ClipperLib::IntPoint( vertex.x, vertex.y ) );
40  }
41 
42  if( Orientation( c_path ) != aRequiredOrientation )
43  ReversePath( c_path );
44 
45  return c_path;
46 }
47 
48 
49 bool SHAPE_LINE_CHAIN::Collide( const VECTOR2I& aP, int aClearance ) const
50 {
51  // fixme: ugly!
52  SEG s( aP, aP );
53  return this->Collide( s, aClearance );
54 }
55 
56 
57 void SHAPE_LINE_CHAIN::Rotate( double aAngle, const VECTOR2I& aCenter )
58 {
59  for( std::vector<VECTOR2I>::iterator i = m_points.begin(); i != m_points.end(); ++i )
60  {
61  (*i) -= aCenter;
62  (*i) = (*i).Rotate( aAngle );
63  (*i) += aCenter;
64  }
65 }
66 
67 
68 bool SHAPE_LINE_CHAIN::Collide( const SEG& aSeg, int aClearance ) const
69 {
70  BOX2I box_a( aSeg.A, aSeg.B - aSeg.A );
71  BOX2I::ecoord_type dist_sq = (BOX2I::ecoord_type) aClearance * aClearance;
72 
73  for( int i = 0; i < SegmentCount(); i++ )
74  {
75  const SEG& s = CSegment( i );
76  BOX2I box_b( s.A, s.B - s.A );
77 
78  BOX2I::ecoord_type d = box_a.SquaredDistance( box_b );
79 
80  if( d < dist_sq )
81  {
82  if( s.Collide( aSeg, aClearance ) )
83  return true;
84  }
85  }
86 
87  return false;
88 }
89 
90 
92 {
93  SHAPE_LINE_CHAIN a( *this );
94 
95  reverse( a.m_points.begin(), a.m_points.end() );
96  a.m_closed = m_closed;
97 
98  return a;
99 }
100 
101 
103 {
104  int l = 0;
105 
106  for( int i = 0; i < SegmentCount(); i++ )
107  l += CSegment( i ).Length();
108 
109  return l;
110 }
111 
112 
113 void SHAPE_LINE_CHAIN::Replace( int aStartIndex, int aEndIndex, const VECTOR2I& aP )
114 {
115  if( aEndIndex < 0 )
116  aEndIndex += PointCount();
117 
118  if( aStartIndex < 0 )
119  aStartIndex += PointCount();
120 
121  if( aStartIndex == aEndIndex )
122  m_points[aStartIndex] = aP;
123  else
124  {
125  m_points.erase( m_points.begin() + aStartIndex + 1, m_points.begin() + aEndIndex + 1 );
126  m_points[aStartIndex] = aP;
127  }
128 }
129 
130 
131 void SHAPE_LINE_CHAIN::Replace( int aStartIndex, int aEndIndex, const SHAPE_LINE_CHAIN& aLine )
132 {
133  if( aEndIndex < 0 )
134  aEndIndex += PointCount();
135 
136  if( aStartIndex < 0 )
137  aStartIndex += PointCount();
138 
139  m_points.erase( m_points.begin() + aStartIndex, m_points.begin() + aEndIndex + 1 );
140  m_points.insert( m_points.begin() + aStartIndex, aLine.m_points.begin(), aLine.m_points.end() );
141 }
142 
143 
144 void SHAPE_LINE_CHAIN::Remove( int aStartIndex, int aEndIndex )
145 {
146  if( aEndIndex < 0 )
147  aEndIndex += PointCount();
148 
149  if( aStartIndex < 0 )
150  aStartIndex += PointCount();
151 
152  m_points.erase( m_points.begin() + aStartIndex, m_points.begin() + aEndIndex + 1 );
153 }
154 
155 
156 int SHAPE_LINE_CHAIN::Distance( const VECTOR2I& aP, bool aOutlineOnly ) const
157 {
158  int d = INT_MAX;
159 
160  if( IsClosed() && PointInside( aP ) && !aOutlineOnly )
161  return 0;
162 
163  for( int s = 0; s < SegmentCount(); s++ )
164  d = std::min( d, CSegment( s ).Distance( aP ) );
165 
166  return d;
167 }
168 
169 
171 {
172  int ii = -1;
173  int min_dist = 2;
174 
175  int found_index = Find( aP );
176 
177  for( int s = 0; s < SegmentCount(); s++ )
178  {
179  const SEG seg = CSegment( s );
180  int dist = seg.Distance( aP );
181 
182  // make sure we are not producing a 'slightly concave' primitive. This might happen
183  // if aP lies very close to one of already existing points.
184  if( dist < min_dist && seg.A != aP && seg.B != aP )
185  {
186  min_dist = dist;
187  if( found_index < 0 )
188  ii = s;
189  else if( s < found_index )
190  ii = s;
191  }
192  }
193 
194  if( ii < 0 )
195  ii = found_index;
196 
197  if( ii >= 0 )
198  {
199  m_points.insert( m_points.begin() + ii + 1, aP );
200 
201  return ii + 1;
202  }
203 
204  return -1;
205 }
206 
207 
208 int SHAPE_LINE_CHAIN::Find( const VECTOR2I& aP ) const
209 {
210  for( int s = 0; s < PointCount(); s++ )
211  if( CPoint( s ) == aP )
212  return s;
213 
214  return -1;
215 }
216 
217 
219 {
220  for( int s = 0; s < SegmentCount(); s++ )
221  if( CSegment( s ).Distance( aP ) <= 1 )
222  return s;
223 
224  return -1;
225 }
226 
227 
228 const SHAPE_LINE_CHAIN SHAPE_LINE_CHAIN::Slice( int aStartIndex, int aEndIndex ) const
229 {
230  SHAPE_LINE_CHAIN rv;
231 
232  if( aEndIndex < 0 )
233  aEndIndex += PointCount();
234 
235  if( aStartIndex < 0 )
236  aStartIndex += PointCount();
237 
238  for( int i = aStartIndex; i <= aEndIndex; i++ )
239  rv.Append( m_points[i] );
240 
241  return rv;
242 }
243 
244 
246 {
248  m_origin( aOrigin ) {};
249 
252  {
253  return ( m_origin - aA.p ).EuclideanNorm() < ( m_origin - aB.p ).EuclideanNorm();
254  }
255 
257 };
258 
259 
260 int SHAPE_LINE_CHAIN::Intersect( const SEG& aSeg, INTERSECTIONS& aIp ) const
261 {
262  for( int s = 0; s < SegmentCount(); s++ )
263  {
264  OPT_VECTOR2I p = CSegment( s ).Intersect( aSeg );
265 
266  if( p )
267  {
268  INTERSECTION is;
269  is.our = CSegment( s );
270  is.their = aSeg;
271  is.p = *p;
272  aIp.push_back( is );
273  }
274  }
275 
276  compareOriginDistance comp( aSeg.A );
277  sort( aIp.begin(), aIp.end(), comp );
278 
279  return aIp.size();
280 }
281 
282 
284 {
285  BOX2I bb_other = aChain.BBox();
286 
287  for( int s1 = 0; s1 < SegmentCount(); s1++ )
288  {
289  const SEG& a = CSegment( s1 );
290  const BOX2I bb_cur( a.A, a.B - a.A );
291 
292  if( !bb_other.Intersects( bb_cur ) )
293  continue;
294 
295  for( int s2 = 0; s2 < aChain.SegmentCount(); s2++ )
296  {
297  const SEG& b = aChain.CSegment( s2 );
298  INTERSECTION is;
299 
300  if( a.Collinear( b ) )
301  {
302  is.our = a;
303  is.their = b;
304 
305  if( a.Contains( b.A ) ) { is.p = b.A; aIp.push_back( is ); }
306  if( a.Contains( b.B ) ) { is.p = b.B; aIp.push_back( is ); }
307  if( b.Contains( a.A ) ) { is.p = a.A; aIp.push_back( is ); }
308  if( b.Contains( a.B ) ) { is.p = a.B; aIp.push_back( is ); }
309  }
310  else
311  {
312  OPT_VECTOR2I p = a.Intersect( b );
313 
314  if( p )
315  {
316  is.p = *p;
317  is.our = a;
318  is.their = b;
319  aIp.push_back( is );
320  }
321  }
322  }
323  }
324 
325  return aIp.size();
326 }
327 
328 
330 {
331  int sum = 0;
332 
333  for( int i = 0; i < SegmentCount(); i++ )
334  {
335  const SEG seg = CSegment( i );
336  int d = seg.Distance( aP );
337 
338  if( d <= 1 )
339  {
340  sum += ( aP - seg.A ).EuclideanNorm();
341  return sum;
342  }
343  else
344  sum += seg.Length();
345  }
346 
347  return -1;
348 }
349 
350 
352 {
353  if( !m_closed || PointCount() < 3 || !BBox().Contains( aP ) )
354  return false;
355 
356  bool inside = false;
357 
366  for( int i = 0; i < PointCount(); i++ )
367  {
368  const auto p1 = CPoint( i );
369  const auto p2 = CPoint( i + 1 ); // CPoint wraps, so ignore counts
370  const auto diff = p2 - p1;
371 
372  if( diff.y != 0 )
373  {
374  const int d = rescale( diff.x, ( aP.y - p1.y ), diff.y );
375 
376  if( ( ( p1.y > aP.y ) != ( p2.y > aP.y ) ) && ( aP.x - p1.x < d ) )
377  inside = !inside;
378  }
379  }
380  return inside && !PointOnEdge( aP );
381 }
382 
383 
385 {
386  return EdgeContainingPoint( aP ) >= 0;
387 }
388 
390 {
391  if( !PointCount() )
392  return -1;
393 
394  else if( PointCount() == 1 )
395  return m_points[0] == aP ? 0 : -1;
396 
397  for( int i = 0; i < SegmentCount(); i++ )
398  {
399  const SEG s = CSegment( i );
400 
401  if( s.A == aP || s.B == aP )
402  return i;
403 
404  if( s.Distance( aP ) <= 1 )
405  return i;
406  }
407 
408  return -1;
409 }
410 
411 
412 bool SHAPE_LINE_CHAIN::CheckClearance( const VECTOR2I& aP, const int aDist) const
413 {
414  if( !PointCount() )
415  return false;
416 
417  else if( PointCount() == 1 )
418  return m_points[0] == aP;
419 
420  for( int i = 0; i < SegmentCount(); i++ )
421  {
422  const SEG s = CSegment( i );
423 
424  if( s.A == aP || s.B == aP )
425  return true;
426 
427  if( s.Distance( aP ) <= aDist )
428  return true;
429  }
430 
431  return false;
432 }
433 
434 
436 {
437  for( int s1 = 0; s1 < SegmentCount(); s1++ )
438  {
439  for( int s2 = s1 + 1; s2 < SegmentCount(); s2++ )
440  {
441  const VECTOR2I s2a = CSegment( s2 ).A, s2b = CSegment( s2 ).B;
442 
443  if( s1 + 1 != s2 && CSegment( s1 ).Contains( s2a ) )
444  {
445  INTERSECTION is;
446  is.our = CSegment( s1 );
447  is.their = CSegment( s2 );
448  is.p = s2a;
449  return is;
450  }
451  else if( CSegment( s1 ).Contains( s2b ) &&
452  // for closed polylines, the ending point of the
453  // last segment == starting point of the first segment
454  // this is a normal case, not self intersecting case
455  !( IsClosed() && s1 == 0 && s2 == SegmentCount()-1 ) )
456  {
457  INTERSECTION is;
458  is.our = CSegment( s1 );
459  is.their = CSegment( s2 );
460  is.p = s2b;
461  return is;
462  }
463  else
464  {
465  OPT_VECTOR2I p = CSegment( s1 ).Intersect( CSegment( s2 ), true );
466 
467  if( p )
468  {
469  INTERSECTION is;
470  is.our = CSegment( s1 );
471  is.their = CSegment( s2 );
472  is.p = *p;
473  return is;
474  }
475  }
476  }
477  }
478 
480 }
481 
482 
484 {
485  std::vector<VECTOR2I> pts_unique;
486 
487  if( PointCount() < 2 )
488  {
489  return *this;
490  }
491  else if( PointCount() == 2 )
492  {
493  if( m_points[0] == m_points[1] )
494  m_points.pop_back();
495 
496  return *this;
497  }
498 
499  int i = 0;
500  int np = PointCount();
501 
502  // stage 1: eliminate duplicate vertices
503  while( i < np )
504  {
505  int j = i + 1;
506 
507  while( j < np && CPoint( i ) == CPoint( j ) )
508  j++;
509 
510  pts_unique.push_back( CPoint( i ) );
511  i = j;
512  }
513 
514  m_points.clear();
515  np = pts_unique.size();
516 
517  i = 0;
518 
519  // stage 1: eliminate collinear segments
520  while( i < np - 2 )
521  {
522  const VECTOR2I p0 = pts_unique[i];
523  const VECTOR2I p1 = pts_unique[i + 1];
524  int n = i;
525 
526  while( n < np - 2 && SEG( p0, p1 ).LineDistance( pts_unique[n + 2] ) <= 1 )
527  n++;
528 
529  m_points.push_back( p0 );
530 
531  if( n > i )
532  i = n;
533 
534  if( n == np )
535  {
536  m_points.push_back( pts_unique[n - 1] );
537  return *this;
538  }
539 
540  i++;
541  }
542 
543  if( np > 1 )
544  m_points.push_back( pts_unique[np - 2] );
545 
546  m_points.push_back( pts_unique[np - 1] );
547 
548  return *this;
549 }
550 
551 
553 {
554  int min_d = INT_MAX;
555  int nearest = 0;
556 
557  for( int i = 0; i < SegmentCount(); i++ )
558  {
559  int d = CSegment( i ).Distance( aP );
560 
561  if( d < min_d )
562  {
563  min_d = d;
564  nearest = i;
565  }
566  }
567 
568  return CSegment( nearest ).NearestPoint( aP );
569 }
570 
571 
572 const VECTOR2I SHAPE_LINE_CHAIN::NearestPoint( const SEG& aSeg, int& dist ) const
573 {
574  int nearest = 0;
575 
576  dist = INT_MAX;
577  for( int i = 0; i < PointCount(); i++ )
578  {
579  int d = aSeg.LineDistance( CPoint( i ) );
580 
581  if( d < dist )
582  {
583  dist = d;
584  nearest = i;
585  }
586  }
587 
588  return CPoint( nearest );
589 }
590 
591 
592 const std::string SHAPE_LINE_CHAIN::Format() const
593 {
594  std::stringstream ss;
595 
596  ss << m_points.size() << " " << ( m_closed ? 1 : 0 ) << " ";
597 
598  for( int i = 0; i < PointCount(); i++ )
599  ss << m_points[i].x << " " << m_points[i].y << " "; // Format() << " ";
600 
601  return ss.str();
602 }
603 
604 
606 {
607  SHAPE_LINE_CHAIN a(*this), b( aOther );
608  a.Simplify();
609  b.Simplify();
610 
611  if( a.m_points.size() != b.m_points.size() )
612  return false;
613 
614  for( int i = 0; i < a.PointCount(); i++)
615  if( a.CPoint( i ) != b.CPoint( i ) )
616  return false;
617  return true;
618 }
619 
620 
622 {
624  return Intersect( aChain, dummy ) != 0;
625 }
626 
627 
629 {
630  return new SHAPE_LINE_CHAIN( *this );
631 }
632 
633 bool SHAPE_LINE_CHAIN::Parse( std::stringstream& aStream )
634 {
635  int n_pts;
636 
637  m_points.clear();
638  aStream >> n_pts;
639 
640  // Rough sanity check, just make sure the loop bounds aren't absolutely outlandish
641  if( n_pts < 0 || n_pts > int( aStream.str().size() ) )
642  return false;
643 
644  aStream >> m_closed;
645 
646  for( int i = 0; i < n_pts; i++ )
647  {
648  int x, y;
649  aStream >> x;
650  aStream >> y;
651  m_points.push_back( VECTOR2I( x, y ) );
652  }
653 
654  return true;
655 }
656 
657 
658 const VECTOR2I SHAPE_LINE_CHAIN::PointAlong( int aPathLength ) const
659 {
660  int total = 0;
661 
662  if( aPathLength == 0 )
663  return CPoint( 0 );
664 
665  for( int i = 0; i < SegmentCount(); i++ )
666  {
667  const SEG& s = CSegment( i );
668  int l = s.Length();
669 
670  if( total + l >= aPathLength )
671  {
672  VECTOR2I d( s.B - s.A );
673  return s.A + d.Resize( aPathLength - total );
674  }
675 
676  total += l;
677  }
678 
679  return CPoint( -1 );
680 }
681 
683 {
684  // see https://www.mathopenref.com/coordpolygonarea2.html
685 
686  if( !m_closed )
687  return 0.0;
688 
689  double area = 0.0;
690  int size = m_points.size();
691 
692  for( int i = 0, j = size - 1; i < size; ++i )
693  {
694  area += ( (double) m_points[j].x + m_points[i].x ) * ( (double) m_points[j].y - m_points[i].y );
695  j = i;
696  }
697 
698  return -area * 0.5;
699 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:112
int Length() const
Function Length()
Definition: seg.h:296
int Find(const VECTOR2I &aP) const
Function Find()
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
int FindSegment(const VECTOR2I &aP) const
Function FindSegment()
int Split(const VECTOR2I &aP)
Function Split()
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:199
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
std::vector< INTERSECTION > INTERSECTIONS
static const int dist[10][10]
Definition: ar_matrix.cpp:320
bool PointInside(const VECTOR2I &aP) const
Function PointInside()
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Function Intersect()
Definition: seg.cpp:132
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Function Slice()
VECTOR2I p
point of intersection between our and their.
ecoord_type SquaredDistance(const Vec &aP) const
Definition: box2.h:440
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:357
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
VECTOR2< int > VECTOR2I
Definition: vector2d.h:587
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()
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
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
bool Intersects(const BOX2< Vec > &aRect) const
Function Intersects.
Definition: box2.h:234
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
bool m_closed
is the line chain closed?
SHAPE_LINE_CHAIN()
Constructor Initializes an empty line chain.
void Rotate(double aAngle, const VECTOR2I &aCenter)
Function Rotate rotates all vertices by a given angle.
int EdgeContainingPoint(const VECTOR2I &aP) const
Function EdgeContainingPoint()
SEG their
segment belonging from the aOther argument of Intersect()
const BOX2I BBox(int aClearance=0) const override
Function BBox()
OPT< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:34
VECTOR2I ::extended_type ecoord_type
Definition: box2.h:49
std::vector< VECTOR2I > m_points
array of vertices
bool CheckClearance(const VECTOR2I &aP, const int aDist) const
Function CheckClearance()
bool Contains(const VECTOR2I &aP) const
Definition: seg.cpp:188
bool PointOnEdge(const VECTOR2I &aP) const
Function PointOnEdge()
bool Intersects(const SHAPE_LINE_CHAIN &aChain) const
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
Definition: seg.h:374
Class SHAPE.
Definition: shape.h:58
void Remove(int aStartIndex, int aEndIndex)
Function Remove()
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:235
Definition: seg.h:36
VECTOR2< T > Resize(T aNewLength) const
Function Resize returns a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:385
VECTOR2< T > Rotate(double aAngle) const
Function Rotate rotates the vector by a given angle.
Definition: vector2d.h:370
const SEG CSegment(int aIndex) const
Function CSegment()
static LIB_PART * dummy()
Used when a LIB_PART is not found in library to draw a dummy shape This component is a 400 mils squar...
T rescale(T aNumerator, T aValue, T aDenominator)
Function rescale()
Class SHAPE_LINE_CHAIN.
size_t i
Definition: json11.cpp:597
VECTOR2I A
Definition: seg.h:44
int Length() const
Function Length()
static void reverse(privcurve_t *curve)
Definition: trace.cpp:1025
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:167
SHAPE * Clone() const override
Function Clone()
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 VECTOR2I PointAlong(int aPathLength) const
bool CompareGeometry(const SHAPE_LINE_CHAIN &aOther) const
compareOriginDistance(VECTOR2I &aOrigin)
#define min(a, b)
Definition: auxiliary.h:85
VECTOR2I B
Definition: seg.h:45