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 
26 #include <geometry/shape_circle.h>
27 
28 using boost::optional;
29 
30 bool SHAPE_LINE_CHAIN::Collide( const VECTOR2I& aP, int aClearance ) const
31 {
32  // fixme: ugly!
33  SEG s( aP, aP );
34  return this->Collide( s, aClearance );
35 }
36 
37 
38 bool SHAPE_LINE_CHAIN::Collide( const SEG& aSeg, int aClearance ) const
39 {
40  BOX2I box_a( aSeg.A, aSeg.B - aSeg.A );
41  BOX2I::ecoord_type dist_sq = (BOX2I::ecoord_type) aClearance * aClearance;
42 
43  for( int i = 0; i < SegmentCount(); i++ )
44  {
45  const SEG& s = CSegment( i );
46  BOX2I box_b( s.A, s.B - s.A );
47 
48  BOX2I::ecoord_type d = box_a.SquaredDistance( box_b );
49 
50  if( d < dist_sq )
51  {
52  if( s.Collide( aSeg, aClearance ) )
53  return true;
54  }
55  }
56 
57  return false;
58 }
59 
60 
62 {
63  SHAPE_LINE_CHAIN a( *this );
64 
65  reverse( a.m_points.begin(), a.m_points.end() );
66  a.m_closed = m_closed;
67 
68  return a;
69 }
70 
71 
73 {
74  int l = 0;
75 
76  for( int i = 0; i < SegmentCount(); i++ )
77  l += CSegment( i ).Length();
78 
79  return l;
80 }
81 
82 
83 void SHAPE_LINE_CHAIN::Replace( int aStartIndex, int aEndIndex, const VECTOR2I& aP )
84 {
85  if( aEndIndex < 0 )
86  aEndIndex += PointCount();
87 
88  if( aStartIndex < 0 )
89  aStartIndex += PointCount();
90 
91  if( aStartIndex == aEndIndex )
92  m_points[aStartIndex] = aP;
93  else
94  {
95  m_points.erase( m_points.begin() + aStartIndex + 1, m_points.begin() + aEndIndex + 1 );
96  m_points[aStartIndex] = aP;
97  }
98 }
99 
100 
101 void SHAPE_LINE_CHAIN::Replace( int aStartIndex, int aEndIndex, const SHAPE_LINE_CHAIN& aLine )
102 {
103  if( aEndIndex < 0 )
104  aEndIndex += PointCount();
105 
106  if( aStartIndex < 0 )
107  aStartIndex += PointCount();
108 
109  m_points.erase( m_points.begin() + aStartIndex, m_points.begin() + aEndIndex + 1 );
110  m_points.insert( m_points.begin() + aStartIndex, aLine.m_points.begin(), aLine.m_points.end() );
111 }
112 
113 
114 void SHAPE_LINE_CHAIN::Remove( int aStartIndex, int aEndIndex )
115 {
116  if( aEndIndex < 0 )
117  aEndIndex += PointCount();
118 
119  if( aStartIndex < 0 )
120  aStartIndex += PointCount();
121 
122  m_points.erase( m_points.begin() + aStartIndex, m_points.begin() + aEndIndex + 1 );
123 }
124 
125 
126 int SHAPE_LINE_CHAIN::Distance( const VECTOR2I& aP ) const
127 {
128  int d = INT_MAX;
129 
130  if( IsClosed() && PointInside( aP ) )
131  return 0;
132 
133  for( int s = 0; s < SegmentCount(); s++ )
134  d = std::min( d, CSegment( s ).Distance( aP ) );
135 
136  return d;
137 }
138 
139 
141 {
142  int ii = -1;
143  int min_dist = 2;
144 
145  int found_index = Find( aP );
146 
147  for( int s = 0; s < SegmentCount(); s++ )
148  {
149  const SEG seg = CSegment( s );
150  int dist = seg.Distance( aP );
151 
152  // make sure we are not producing a 'slightly concave' primitive. This might happen
153  // if aP lies very close to one of already existing points.
154  if( dist < min_dist && seg.A != aP && seg.B != aP )
155  {
156  min_dist = dist;
157  if( found_index < 0 )
158  ii = s;
159  else if( s < found_index )
160  ii = s;
161  }
162  }
163 
164  if( ii < 0 )
165  ii = found_index;
166 
167  if( ii >= 0 )
168  {
169  m_points.insert( m_points.begin() + ii + 1, aP );
170 
171  return ii + 1;
172  }
173 
174  return -1;
175 }
176 
177 
178 int SHAPE_LINE_CHAIN::Find( const VECTOR2I& aP ) const
179 {
180  for( int s = 0; s < PointCount(); s++ )
181  if( CPoint( s ) == aP )
182  return s;
183 
184  return -1;
185 }
186 
187 
189 {
190  for( int s = 0; s < SegmentCount(); s++ )
191  if( CSegment( s ).Distance( aP ) <= 1 )
192  return s;
193 
194  return -1;
195 }
196 
197 
198 const SHAPE_LINE_CHAIN SHAPE_LINE_CHAIN::Slice( int aStartIndex, int aEndIndex ) const
199 {
200  SHAPE_LINE_CHAIN rv;
201 
202  if( aEndIndex < 0 )
203  aEndIndex += PointCount();
204 
205  if( aStartIndex < 0 )
206  aStartIndex += PointCount();
207 
208  for( int i = aStartIndex; i <= aEndIndex; i++ )
209  rv.Append( m_points[i] );
210 
211  return rv;
212 }
213 
214 
216 {
218  m_origin( aOrigin ) {};
219 
222  {
223  return ( m_origin - aA.p ).EuclideanNorm() < ( m_origin - aB.p ).EuclideanNorm();
224  }
225 
227 };
228 
229 
230 int SHAPE_LINE_CHAIN::Intersect( const SEG& aSeg, INTERSECTIONS& aIp ) const
231 {
232  for( int s = 0; s < SegmentCount(); s++ )
233  {
234  OPT_VECTOR2I p = CSegment( s ).Intersect( aSeg );
235 
236  if( p )
237  {
238  INTERSECTION is;
239  is.our = CSegment( s );
240  is.their = aSeg;
241  is.p = *p;
242  aIp.push_back( is );
243  }
244  }
245 
246  compareOriginDistance comp( aSeg.A );
247  sort( aIp.begin(), aIp.end(), comp );
248 
249  return aIp.size();
250 }
251 
252 
254 {
255  BOX2I bb_other = aChain.BBox();
256 
257  for( int s1 = 0; s1 < SegmentCount(); s1++ )
258  {
259  const SEG& a = CSegment( s1 );
260  const BOX2I bb_cur( a.A, a.B - a.A );
261 
262  if( !bb_other.Intersects( bb_cur ) )
263  continue;
264 
265  for( int s2 = 0; s2 < aChain.SegmentCount(); s2++ )
266  {
267  const SEG& b = aChain.CSegment( s2 );
268  INTERSECTION is;
269 
270  if( a.Collinear( b ) )
271  {
272  is.our = a;
273  is.their = b;
274 
275  if( a.Contains( b.A ) ) { is.p = b.A; aIp.push_back( is ); }
276  if( a.Contains( b.B ) ) { is.p = b.B; aIp.push_back( is ); }
277  if( b.Contains( a.A ) ) { is.p = a.A; aIp.push_back( is ); }
278  if( b.Contains( a.B ) ) { is.p = a.B; aIp.push_back( is ); }
279  }
280  else
281  {
282  OPT_VECTOR2I p = a.Intersect( b );
283 
284  if( p )
285  {
286  is.p = *p;
287  is.our = a;
288  is.their = b;
289  aIp.push_back( is );
290  }
291  }
292  }
293  }
294 
295  return aIp.size();
296 }
297 
298 
300 {
301  int sum = 0;
302 
303  for( int i = 0; i < SegmentCount(); i++ )
304  {
305  const SEG seg = CSegment( i );
306  int d = seg.Distance( aP );
307 
308  if( d <= 1 )
309  {
310  sum += ( aP - seg.A ).EuclideanNorm();
311  return sum;
312  }
313  else
314  sum += seg.Length();
315  }
316 
317  return -1;
318 }
319 
320 
322 {
323  if( !m_closed || SegmentCount() < 3 )
324  return false;
325 
326  int cur = CSegment( 0 ).Side( aP );
327 
328  if( cur == 0 )
329  return false;
330 
331  for( int i = 1; i < SegmentCount(); i++ )
332  {
333  const SEG s = CSegment( i );
334 
335  if( aP == s.A || aP == s.B ) // edge does not belong to the interior!
336  return false;
337 
338  if( s.Side( aP ) != cur )
339  return false;
340  }
341 
342  return true;
343 }
344 
345 
347 {
348  if( !PointCount() )
349  return false;
350 
351  else if( PointCount() == 1 )
352  return m_points[0] == aP;
353 
354  for( int i = 0; i < SegmentCount(); i++ )
355  {
356  const SEG s = CSegment( i );
357 
358  if( s.A == aP || s.B == aP )
359  return true;
360 
361  if( s.Distance( aP ) <= 1 )
362  return true;
363  }
364 
365  return false;
366 }
367 
368 
370 {
371  for( int s1 = 0; s1 < SegmentCount(); s1++ )
372  {
373  for( int s2 = s1 + 1; s2 < SegmentCount(); s2++ )
374  {
375  const VECTOR2I s2a = CSegment( s2 ).A, s2b = CSegment( s2 ).B;
376 
377  if( s1 + 1 != s2 && CSegment( s1 ).Contains( s2a ) )
378  {
379  INTERSECTION is;
380  is.our = CSegment( s1 );
381  is.their = CSegment( s2 );
382  is.p = s2a;
383  return is;
384  }
385  else if( CSegment( s1 ).Contains( s2b ) &&
386  // for closed polylines, the ending point of the
387  // last segment == starting point of the first segment
388  // this is a normal case, not self intersecting case
389  !( IsClosed() && s1 == 0 && s2 == SegmentCount()-1 ) )
390  {
391  INTERSECTION is;
392  is.our = CSegment( s1 );
393  is.their = CSegment( s2 );
394  is.p = s2b;
395  return is;
396  }
397  else
398  {
399  OPT_VECTOR2I p = CSegment( s1 ).Intersect( CSegment( s2 ), true );
400 
401  if( p )
402  {
403  INTERSECTION is;
404  is.our = CSegment( s1 );
405  is.their = CSegment( s2 );
406  is.p = *p;
407  return is;
408  }
409  }
410  }
411  }
412 
413  return optional<INTERSECTION>();
414 }
415 
416 
418 {
419  std::vector<VECTOR2I> pts_unique;
420 
421  if( PointCount() < 2 )
422  {
423  return *this;
424  }
425  else if( PointCount() == 2 )
426  {
427  if( m_points[0] == m_points[1] )
428  m_points.pop_back();
429 
430  return *this;
431  }
432 
433  int i = 0;
434  int np = PointCount();
435 
436  // stage 1: eliminate duplicate vertices
437  while( i < np )
438  {
439  int j = i + 1;
440 
441  while( j < np && CPoint( i ) == CPoint( j ) )
442  j++;
443 
444  pts_unique.push_back( CPoint( i ) );
445  i = j;
446  }
447 
448  m_points.clear();
449  np = pts_unique.size();
450 
451  i = 0;
452 
453  // stage 1: eliminate collinear segments
454  while( i < np - 2 )
455  {
456  const VECTOR2I p0 = pts_unique[i];
457  const VECTOR2I p1 = pts_unique[i + 1];
458  int n = i;
459 
460  while( n < np - 2 && SEG( p0, p1 ).LineDistance( pts_unique[n + 2] ) <= 1 )
461  n++;
462 
463  m_points.push_back( p0 );
464 
465  if( n > i )
466  i = n;
467 
468  if( n == np )
469  {
470  m_points.push_back( pts_unique[n - 1] );
471  return *this;
472  }
473 
474  i++;
475  }
476 
477  if( np > 1 )
478  m_points.push_back( pts_unique[np - 2] );
479 
480  m_points.push_back( pts_unique[np - 1] );
481 
482  return *this;
483 }
484 
485 
487 {
488  int min_d = INT_MAX;
489  int nearest = 0;
490 
491  for( int i = 0; i < SegmentCount(); i++ )
492  {
493  int d = CSegment( i ).Distance( aP );
494 
495  if( d < min_d )
496  {
497  min_d = d;
498  nearest = i;
499  }
500  }
501 
502  return CSegment( nearest ).NearestPoint( aP );
503 }
504 
505 
506 const VECTOR2I SHAPE_LINE_CHAIN::NearestPoint( const SEG& aSeg, int& dist ) const
507 {
508  int nearest = 0;
509 
510  dist = INT_MAX;
511  for( int i = 0; i < PointCount(); i++ )
512  {
513  int d = aSeg.LineDistance( CPoint( i ) );
514 
515  if( d < dist )
516  {
517  dist = d;
518  nearest = i;
519  }
520  }
521 
522  return CPoint( nearest );
523 }
524 
525 
526 const std::string SHAPE_LINE_CHAIN::Format() const
527 {
528  std::stringstream ss;
529 
530  ss << m_points.size() << " " << ( m_closed ? 1 : 0 ) << " ";
531 
532  for( int i = 0; i < PointCount(); i++ )
533  ss << m_points[i].x << " " << m_points[i].y << " "; // Format() << " ";
534 
535  return ss.str();
536 }
537 
538 
540 {
541  SHAPE_LINE_CHAIN a(*this), b( aOther );
542  a.Simplify();
543  b.Simplify();
544 
545  if( a.m_points.size() != b.m_points.size() )
546  return false;
547 
548  for( int i = 0; i < a.PointCount(); i++)
549  if( a.CPoint( i ) != b.CPoint( i ) )
550  return false;
551  return true;
552 }
553 
554 
556 {
558  return Intersect( aChain, dummy ) != 0;
559 }
560 
561 
563 {
564  return new SHAPE_LINE_CHAIN( *this );
565 }
566 
567 bool SHAPE_LINE_CHAIN::Parse( std::stringstream& aStream )
568 {
569  int n_pts;
570 
571  m_points.clear();
572  aStream >> n_pts;
573 
574  // Rough sanity check, just make sure the loop bounds aren't absolutely outlandish
575  if( n_pts < 0 || n_pts > int( aStream.str().size() ) )
576  return false;
577 
578  aStream >> m_closed;
579 
580  for( int i = 0; i < n_pts; i++ )
581  {
582  int x, y;
583  aStream >> x;
584  aStream >> y;
585  m_points.push_back( VECTOR2I( x, y ) );
586  }
587 
588  return true;
589 }
590 
591 
592 const VECTOR2I SHAPE_LINE_CHAIN::PointAlong( int aPathLength ) const
593 {
594  int total = 0;
595 
596  if( aPathLength == 0 )
597  return CPoint( 0 );
598 
599  for( int i = 0; i < SegmentCount(); i++ )
600  {
601  const SEG& s = CSegment( i );
602  int l = s.Length();
603 
604  if( total + l >= aPathLength )
605  {
606  VECTOR2I d( s.B - s.A );
607  return s.A + d.Resize( aPathLength - total );
608  }
609 
610  total += l;
611  }
612 
613  return CPoint( -1 );
614 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:104
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
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:388
int PointCount() const
Function PointCount()
int Side(const VECTOR2I &aP) const
Function Side()
Definition: seg.h:123
int Length() const
Function Length()
Definition: seg.h:282
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
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
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:590
bool Collide(const VECTOR2I &aP, int aClearance=0) const override
Function Collide()
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
const boost::optional< INTERSECTION > SelfIntersecting() const
Function SelfIntersecting()
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.
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()
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:337
bool Intersects(const BOX2< Vec > &aRect) const
Function Intersects.
Definition: box2.h:224
Class SHAPE.
Definition: shape.h:57
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:354
Definition: seg.h:37
int Distance(const VECTOR2I &aP) const
Function Distance()
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.
VECTOR2I A
Definition: seg.h:47
static void reverse(privcurve_t *curve)
Definition: trace.cpp:1020
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:221
bool Contains(const VECTOR2I &aP) const
Definition: seg.cpp:155
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:185
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:48