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