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 VECTOR2D p1 = CPoint( i );
369  const VECTOR2D p2 = CPoint( i + 1 ); // CPoint wraps, so ignore counts
370  const VECTOR2D diff = p2 - p1;
371 
372  if( ( ( p1.y > aP.y ) != ( p2.y > aP.y ) ) &&
373  ( aP.x - p1.x < ( diff.x / diff.y ) * ( aP.y - p1.y ) ) )
374  inside = !inside;
375  }
376 
377  return inside;
378 }
379 
380 
382 {
383  if( !PointCount() )
384  return false;
385  else if( PointCount() == 1 )
386  return m_points[0] == aP;
387 
388  for( int i = 0; i < PointCount(); i++ )
389  {
390  const VECTOR2I& p1 = CPoint( i );
391  const VECTOR2I& p2 = CPoint( i + 1 );
392 
393  if( aP == p1 )
394  return true;
395 
396  if( p1.x == p2.x && p1.x == aP.x && ( p1.y > aP.y ) != ( p2.y > aP.y ) )
397  return true;
398 
399  const VECTOR2D diff = p2 - p1;
400  if( aP.x >= p1.x && aP.x <= p2.x )
401  {
402  if( round_nearest( p1.y + ( diff.y / diff.x ) * ( aP.x - p1.x ) ) == aP.y )
403  return true;
404  }
405  }
406 
407  return false;
408 }
409 
410 
411 bool SHAPE_LINE_CHAIN::CheckClearance( const VECTOR2I& aP, const int aDist) const
412 {
413  if( !PointCount() )
414  return false;
415 
416  else if( PointCount() == 1 )
417  return m_points[0] == aP;
418 
419  for( int i = 0; i < SegmentCount(); i++ )
420  {
421  const SEG s = CSegment( i );
422 
423  if( s.A == aP || s.B == aP )
424  return true;
425 
426  if( s.Distance( aP ) <= aDist )
427  return true;
428  }
429 
430  return false;
431 }
432 
433 
435 {
436  for( int s1 = 0; s1 < SegmentCount(); s1++ )
437  {
438  for( int s2 = s1 + 1; s2 < SegmentCount(); s2++ )
439  {
440  const VECTOR2I s2a = CSegment( s2 ).A, s2b = CSegment( s2 ).B;
441 
442  if( s1 + 1 != s2 && CSegment( s1 ).Contains( s2a ) )
443  {
444  INTERSECTION is;
445  is.our = CSegment( s1 );
446  is.their = CSegment( s2 );
447  is.p = s2a;
448  return is;
449  }
450  else if( CSegment( s1 ).Contains( s2b ) &&
451  // for closed polylines, the ending point of the
452  // last segment == starting point of the first segment
453  // this is a normal case, not self intersecting case
454  !( IsClosed() && s1 == 0 && s2 == SegmentCount()-1 ) )
455  {
456  INTERSECTION is;
457  is.our = CSegment( s1 );
458  is.their = CSegment( s2 );
459  is.p = s2b;
460  return is;
461  }
462  else
463  {
464  OPT_VECTOR2I p = CSegment( s1 ).Intersect( CSegment( s2 ), true );
465 
466  if( p )
467  {
468  INTERSECTION is;
469  is.our = CSegment( s1 );
470  is.their = CSegment( s2 );
471  is.p = *p;
472  return is;
473  }
474  }
475  }
476  }
477 
479 }
480 
481 
483 {
484  std::vector<VECTOR2I> pts_unique;
485 
486  if( PointCount() < 2 )
487  {
488  return *this;
489  }
490  else if( PointCount() == 2 )
491  {
492  if( m_points[0] == m_points[1] )
493  m_points.pop_back();
494 
495  return *this;
496  }
497 
498  int i = 0;
499  int np = PointCount();
500 
501  // stage 1: eliminate duplicate vertices
502  while( i < np )
503  {
504  int j = i + 1;
505 
506  while( j < np && CPoint( i ) == CPoint( j ) )
507  j++;
508 
509  pts_unique.push_back( CPoint( i ) );
510  i = j;
511  }
512 
513  m_points.clear();
514  np = pts_unique.size();
515 
516  i = 0;
517 
518  // stage 1: eliminate collinear segments
519  while( i < np - 2 )
520  {
521  const VECTOR2I p0 = pts_unique[i];
522  const VECTOR2I p1 = pts_unique[i + 1];
523  int n = i;
524 
525  while( n < np - 2 && SEG( p0, p1 ).LineDistance( pts_unique[n + 2] ) <= 1 )
526  n++;
527 
528  m_points.push_back( p0 );
529 
530  if( n > i )
531  i = n;
532 
533  if( n == np )
534  {
535  m_points.push_back( pts_unique[n - 1] );
536  return *this;
537  }
538 
539  i++;
540  }
541 
542  if( np > 1 )
543  m_points.push_back( pts_unique[np - 2] );
544 
545  m_points.push_back( pts_unique[np - 1] );
546 
547  return *this;
548 }
549 
550 
552 {
553  int min_d = INT_MAX;
554  int nearest = 0;
555 
556  for( int i = 0; i < SegmentCount(); i++ )
557  {
558  int d = CSegment( i ).Distance( aP );
559 
560  if( d < min_d )
561  {
562  min_d = d;
563  nearest = i;
564  }
565  }
566 
567  return CSegment( nearest ).NearestPoint( aP );
568 }
569 
570 
571 const VECTOR2I SHAPE_LINE_CHAIN::NearestPoint( const SEG& aSeg, int& dist ) const
572 {
573  int nearest = 0;
574 
575  dist = INT_MAX;
576  for( int i = 0; i < PointCount(); i++ )
577  {
578  int d = aSeg.LineDistance( CPoint( i ) );
579 
580  if( d < dist )
581  {
582  dist = d;
583  nearest = i;
584  }
585  }
586 
587  return CPoint( nearest );
588 }
589 
590 
591 const std::string SHAPE_LINE_CHAIN::Format() const
592 {
593  std::stringstream ss;
594 
595  ss << m_points.size() << " " << ( m_closed ? 1 : 0 ) << " ";
596 
597  for( int i = 0; i < PointCount(); i++ )
598  ss << m_points[i].x << " " << m_points[i].y << " "; // Format() << " ";
599 
600  return ss.str();
601 }
602 
603 
605 {
606  SHAPE_LINE_CHAIN a(*this), b( aOther );
607  a.Simplify();
608  b.Simplify();
609 
610  if( a.m_points.size() != b.m_points.size() )
611  return false;
612 
613  for( int i = 0; i < a.PointCount(); i++)
614  if( a.CPoint( i ) != b.CPoint( i ) )
615  return false;
616  return true;
617 }
618 
619 
621 {
623  return Intersect( aChain, dummy ) != 0;
624 }
625 
626 
628 {
629  return new SHAPE_LINE_CHAIN( *this );
630 }
631 
632 bool SHAPE_LINE_CHAIN::Parse( std::stringstream& aStream )
633 {
634  int n_pts;
635 
636  m_points.clear();
637  aStream >> n_pts;
638 
639  // Rough sanity check, just make sure the loop bounds aren't absolutely outlandish
640  if( n_pts < 0 || n_pts > int( aStream.str().size() ) )
641  return false;
642 
643  aStream >> m_closed;
644 
645  for( int i = 0; i < n_pts; i++ )
646  {
647  int x, y;
648  aStream >> x;
649  aStream >> y;
650  m_points.push_back( VECTOR2I( x, y ) );
651  }
652 
653  return true;
654 }
655 
656 
657 const VECTOR2I SHAPE_LINE_CHAIN::PointAlong( int aPathLength ) const
658 {
659  int total = 0;
660 
661  if( aPathLength == 0 )
662  return CPoint( 0 );
663 
664  for( int i = 0; i < SegmentCount(); i++ )
665  {
666  const SEG& s = CSegment( i );
667  int l = s.Length();
668 
669  if( total + l >= aPathLength )
670  {
671  VECTOR2I d( s.B - s.A );
672  return s.A + d.Resize( aPathLength - total );
673  }
674 
675  total += l;
676  }
677 
678  return CPoint( -1 );
679 }
680 
682 {
683  // see https://www.mathopenref.com/coordpolygonarea2.html
684 
685  if( !m_closed )
686  return 0.0;
687 
688  double area = 0.0;
689  int size = m_points.size();
690 
691  for( int i = 0, j = size - 1; i < size; ++i )
692  {
693  area += ( (double) m_points[j].x + m_points[i].x ) * ( (double) m_points[j].y - m_points[i].y );
694  j = i;
695  }
696 
697  return -area * 0.5;
698 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:112
bool PointOnEdge(const VECTOR2I &aP) const
Function PointOnEdge()
bool PointInside(const VECTOR2I &aP) const
Function PointInside()
int Split(const VECTOR2I &aP)
Function Split()
std::vector< INTERSECTION > INTERSECTIONS
static const int dist[10][10]
Definition: ar_matrix.cpp:320
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
ClipperLib::Path convertToClipper(bool aRequiredOrientation) const
Creates a new Clipper path from the SHAPE_LINE_CHAIN in a given orientation.
VECTOR2< T > Resize(T aNewLength) const
Function Resize returns a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:385
int PointCount() const
Function PointCount()
int Length() const
Function Length()
Definition: seg.h:292
ecoord_type SquaredDistance(const Vec &aP) const
Definition: box2.h:440
VECTOR2I p
point of intersection between our and their.
VECTOR2< T > Rotate(double aAngle) const
Function Rotate rotates the vector by a given angle.
Definition: vector2d.h:370
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
bool CheckClearance(const VECTOR2I &aP, const int aDist) const
Function CheckClearance()
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Function Intersect()
Definition: seg.cpp:99
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Function Slice()
VECTOR2< int > VECTOR2I
Definition: vector2d.h:587
const OPT< INTERSECTION > SelfIntersecting() const
Function SelfIntersecting()
static int round_nearest(double v)
Definition: math_util.h:56
bool Collide(const VECTOR2I &aP, int aClearance=0) const override
Function Collide()
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
bool Parse(std::stringstream &aStream) override
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
const SEG CSegment(int aIndex) const
Function CSegment()
int Find(const VECTOR2I &aP) const
Function Find()
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.
SEG their
segment belonging from the aOther argument of Intersect()
const VECTOR2I PointAlong(int aPathLength) const
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
bool Intersects(const SHAPE_LINE_CHAIN &aChain) const
std::vector< VECTOR2I > m_points
array of vertices
int LineDistance(const VECTOR2I &aP, bool aDetermineSide=false) const
Function LineDistance()
Definition: seg.h:353
bool Intersects(const BOX2< Vec > &aRect) const
Function Intersects.
Definition: box2.h:234
Class SHAPE.
Definition: shape.h:58
void Remove(int aStartIndex, int aEndIndex)
Function Remove()
const std::string Format() const override
int FindSegment(const VECTOR2I &aP) const
Function FindSegment()
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
Definition: seg.h:370
Definition: seg.h:36
int PathLength(const VECTOR2I &aP) const
Function PathLength()
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...
Class SHAPE_LINE_CHAIN.
double Area() const
size_t i
Definition: json11.cpp:597
VECTOR2I A
Definition: seg.h:46
static void reverse(privcurve_t *curve)
Definition: trace.cpp:1025
boost::optional< T > OPT
Definition: optional.h:7
bool IsClosed() const
Function IsClosed()
bool operator()(const SHAPE_LINE_CHAIN::INTERSECTION &aA, const SHAPE_LINE_CHAIN::INTERSECTION &aB)
SHAPE * Clone() const override
Function Clone()
bool CompareGeometry(const SHAPE_LINE_CHAIN &aOther) const
bool Collide(const SEG &aSeg, int aClearance) const
Definition: seg.cpp:134
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Function Replace()
bool Collinear(const SEG &aSeg) const
Function Collinear()
Definition: seg.h:231
bool Contains(const VECTOR2I &aP) const
Definition: seg.cpp:155
int Distance(const VECTOR2I &aP, bool aOutlineOnly=false) const
Function Distance()
SEG our
segment belonging from the (this) argument of Intersect()
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:195
int SegmentCount() const
Function SegmentCount()
int Length() const
Function Length()
compareOriginDistance(VECTOR2I &aOrigin)
#define min(a, b)
Definition: auxiliary.h:85
VECTOR2I B
Definition: seg.h:47