KiCad PCB EDA Suite
seg.h
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 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 #ifndef __SEG_H
26 #define __SEG_H
27 
28 #include <math.h> // for sqrt
29 #include <stdlib.h> // for abs
30 #include <ostream> // for operator<<, ostream, basic_os...
31 #include <type_traits> // for swap
32 
33 #include <core/optional.h>
34 #include <math/util.h> // for rescale
35 #include <math/vector2d.h>
36 
38 
39 class SEG
40 {
41 public:
43  friend inline std::ostream& operator<<( std::ostream& aStream, const SEG& aSeg );
44 
45  /* Start and the of the segment. Public, to make access simpler.
46  */
49 
53  SEG()
54  {
55  m_index = -1;
56  }
57 
62  SEG( int aX1, int aY1, int aX2, int aY2 ) :
63  A ( VECTOR2I( aX1, aY1 ) ),
64  B ( VECTOR2I( aX2, aY2 ) )
65  {
66  m_index = -1;
67  }
68 
73  SEG( const VECTOR2I& aA, const VECTOR2I& aB ) : A( aA ), B( aB )
74  {
75  m_index = -1;
76  }
77 
85  SEG( const VECTOR2I& aA, const VECTOR2I& aB, int aIndex ) : A( aA ), B( aB )
86  {
87  m_index = aIndex;
88  }
89 
93  SEG( const SEG& aSeg ) : A( aSeg.A ), B( aSeg.B ), m_index( aSeg.m_index )
94  {
95  }
96 
97  SEG& operator=( const SEG& aSeg )
98  {
99  A = aSeg.A;
100  B = aSeg.B;
101  m_index = aSeg.m_index;
102 
103  return *this;
104  }
105 
106  bool operator==( const SEG& aSeg ) const
107  {
108  return (A == aSeg.A && B == aSeg.B) ;
109  }
110 
111  bool operator!=( const SEG& aSeg ) const
112  {
113  return (A != aSeg.A || B != aSeg.B);
114  }
115 
124  VECTOR2I LineProject( const VECTOR2I& aP ) const;
125 
133  int Side( const VECTOR2I& aP ) const
134  {
135  const ecoord det = ( B - A ).Cross( aP - A );
136 
137  return det < 0 ? -1 : ( det > 0 ? 1 : 0 );
138  }
139 
150  int LineDistance( const VECTOR2I& aP, bool aDetermineSide = false ) const;
151 
158  const VECTOR2I NearestPoint( const VECTOR2I &aP ) const;
159 
164  const VECTOR2I NearestPoint( const SEG &aSeg ) const;
165 
176  OPT_VECTOR2I Intersect( const SEG& aSeg, bool aIgnoreEndpoints = false,
177  bool aLines = false ) const;
178 
186  OPT_VECTOR2I IntersectLines( const SEG& aSeg ) const
187  {
188  return Intersect( aSeg, false, true );
189  }
190 
191  bool Collide( const SEG& aSeg, int aClearance ) const;
192 
193  ecoord SquaredDistance( const SEG& aSeg ) const;
194 
202  int Distance( const SEG& aSeg ) const
203  {
204  return sqrt( SquaredDistance( aSeg ) );
205  }
206 
207  ecoord SquaredDistance( const VECTOR2I& aP ) const
208  {
209  return ( NearestPoint( aP ) - aP ).SquaredEuclideanNorm();
210  }
211 
219  int Distance( const VECTOR2I& aP ) const
220  {
221  return sqrt( SquaredDistance( aP ) );
222  }
223 
224  void CanonicalCoefs( ecoord& qA, ecoord& qB, ecoord& qC ) const
225  {
226  qA = A.y - B.y;
227  qB = B.x - A.x;
228  qC = -qA * A.x - qB * A.y;
229  }
230 
238  bool Collinear( const SEG& aSeg ) const
239  {
240  ecoord qa, qb, qc;
241  CanonicalCoefs( qa, qb, qc );
242 
243  ecoord d1 = std::abs( aSeg.A.x * qa + aSeg.A.y * qb + qc );
244  ecoord d2 = std::abs( aSeg.B.x * qa + aSeg.B.y * qb + qc );
245 
246  return ( d1 <= 1 && d2 <= 1 );
247  }
248 
249  bool ApproxCollinear( const SEG& aSeg ) const
250  {
251  ecoord p, q, r;
252  CanonicalCoefs( p, q, r );
253 
254  ecoord dist1 = ( p * aSeg.A.x + q * aSeg.A.y + r ) / sqrt( p * p + q * q );
255  ecoord dist2 = ( p * aSeg.B.x + q * aSeg.B.y + r ) / sqrt( p * p + q * q );
256 
257  return std::abs( dist1 ) <= 1 && std::abs( dist2 ) <= 1;
258  }
259 
260  bool ApproxParallel ( const SEG& aSeg ) const
261  {
262  ecoord p, q, r;
263  CanonicalCoefs( p, q, r );
264 
265  ecoord dist1 = ( p * aSeg.A.x + q * aSeg.A.y + r ) / sqrt( p * p + q * q );
266  ecoord dist2 = ( p * aSeg.B.x + q * aSeg.B.y + r ) / sqrt( p * p + q * q );
267 
268  return std::abs( dist1 - dist2 ) <= 1;
269  }
270 
271 
272  bool Overlaps( const SEG& aSeg ) const
273  {
274  if( aSeg.A == aSeg.B ) // single point corner case
275  {
276  if( A == aSeg.A || B == aSeg.A )
277  return false;
278 
279  return Contains( aSeg.A );
280  }
281 
282  if( !Collinear( aSeg ) )
283  return false;
284 
285  if( Contains( aSeg.A ) || Contains( aSeg.B ) )
286  return true;
287  if( aSeg.Contains( A ) || aSeg.Contains( B ) )
288  return true;
289 
290  return false;
291  }
292 
293 
294  bool Contains( const SEG& aSeg ) const
295  {
296  if( aSeg.A == aSeg.B ) // single point corner case
297  return Contains( aSeg.A );
298 
299  if( !Collinear( aSeg ) )
300  return false;
301 
302  if( Contains( aSeg.A ) && Contains( aSeg.B ) )
303  return true;
304 
305  return false;
306  }
307 
314  int Length() const
315  {
316  return ( A - B ).EuclideanNorm();
317  }
318 
320  {
321  return ( A - B ).SquaredEuclideanNorm();
322  }
323 
324  ecoord TCoef( const VECTOR2I& aP ) const;
325 
332  int Index() const
333  {
334  return m_index;
335  }
336 
337  bool Contains( const VECTOR2I& aP ) const;
338 
339  bool PointCloserThan( const VECTOR2I& aP, int aDist ) const;
340 
341  void Reverse()
342  {
343  std::swap( A, B );
344  }
345 
347  VECTOR2I Center() const
348  {
349  return A + ( B - A ) / 2;
350  }
351 
352 private:
353  bool ccw( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I &aC ) const;
354 
356  int m_index;
357 };
358 
359 inline VECTOR2I SEG::LineProject( const VECTOR2I& aP ) const
360 {
361  VECTOR2I d = B - A;
362  ecoord l_squared = d.Dot( d );
363 
364  if( l_squared == 0 )
365  return A;
366 
367  ecoord t = d.Dot( aP - A );
368 
369  int xp = rescale( t, (ecoord)d.x, l_squared );
370  int yp = rescale( t, (ecoord)d.y, l_squared );
371 
372  return A + VECTOR2I( xp, yp );
373 }
374 
375 inline int SEG::LineDistance( const VECTOR2I& aP, bool aDetermineSide ) const
376 {
377  ecoord p = A.y - B.y;
378  ecoord q = B.x - A.x;
379  ecoord r = -p * A.x - q * A.y;
380 
381  ecoord dist = ( p * aP.x + q * aP.y + r ) / sqrt( p * p + q * q );
382 
383  return aDetermineSide ? dist : std::abs( dist );
384 }
385 
386 inline SEG::ecoord SEG::TCoef( const VECTOR2I& aP ) const
387 {
388  VECTOR2I d = B - A;
389  return d.Dot( aP - A);
390 }
391 
392 inline const VECTOR2I SEG::NearestPoint( const VECTOR2I& aP ) const
393 {
394  VECTOR2I d = B - A;
395  ecoord l_squared = d.Dot( d );
396 
397  if( l_squared == 0 )
398  return A;
399 
400  ecoord t = d.Dot( aP - A );
401 
402  if( t < 0 )
403  return A;
404  else if( t > l_squared )
405  return B;
406 
407  int xp = rescale( t, (ecoord)d.x, l_squared );
408  int yp = rescale( t, (ecoord)d.y, l_squared );
409 
410  return A + VECTOR2I( xp, yp );
411 }
412 
413 inline std::ostream& operator<<( std::ostream& aStream, const SEG& aSeg )
414 {
415  aStream << "[ " << aSeg.A << " - " << aSeg.B << " ]";
416 
417  return aStream;
418 }
419 
420 #endif // __SEG_H
int Length() const
Function Length()
Definition: seg.h:314
VECTOR2_TRAITS< T >::extended_type extended_type
Definition: vector2d.h:77
int Index() const
Function Index()
Definition: seg.h:332
bool Overlaps(const SEG &aSeg) const
Definition: seg.h:272
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:202
static const int dist[10][10]
Definition: ar_matrix.cpp:326
void CanonicalCoefs(ecoord &qA, ecoord &qB, ecoord &qC) const
Definition: seg.h:224
ecoord SquaredLength() const
Definition: seg.h:319
bool ccw(const VECTOR2I &aA, const VECTOR2I &aB, const VECTOR2I &aC) const
Definition: seg.cpp:173
SEG()
Default constructor Creates an empty (0, 0) segment.
Definition: seg.h:53
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Function Intersect()
Definition: seg.cpp:144
std::ostream & operator<<(std::ostream &aStream, const SEG &aSeg)
Definition: seg.h:413
VECTOR2I::extended_type ecoord
Definition: seg.h:42
bool operator!=(const SEG &aSeg) const
Definition: seg.h:111
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:88
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Function IntersectLines()
Definition: seg.h:186
int LineDistance(const VECTOR2I &aP, bool aDetermineSide=false) const
Function LineDistance()
Definition: seg.h:375
VECTOR2I Center() const
Returns the center point of the line
Definition: seg.h:347
friend std::ostream & operator<<(std::ostream &aStream, const SEG &aSeg)
Definition: seg.h:413
VECTOR2< int > VECTOR2I
Definition: vector2d.h:594
bool PointCloserThan(const VECTOR2I &aP, int aDist) const
Definition: seg.cpp:37
SEG & operator=(const SEG &aSeg)
Definition: seg.h:97
VECTOR2I LineProject(const VECTOR2I &aP) const
Function LineProject()
Definition: seg.h:359
ecoord TCoef(const VECTOR2I &aP) const
Definition: seg.h:386
OPT< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:37
bool ApproxParallel(const SEG &aSeg) const
Definition: seg.h:260
VECTOR2I::extended_type ecoord
SEG(const VECTOR2I &aA, const VECTOR2I &aB)
Constructor Creates a segment between (aA) and (aB)
Definition: seg.h:73
SEG(int aX1, int aY1, int aX2, int aY2)
Constructor Creates a segment between (aX1, aY1) and (aX2, aY2)
Definition: seg.h:62
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
Definition: seg.h:392
bool ApproxCollinear(const SEG &aSeg) const
Definition: seg.h:249
SEG(const SEG &aSeg)
Copy constructor.
Definition: seg.h:93
int Distance(const VECTOR2I &aP) const
Function Distance()
Definition: seg.h:219
bool Collinear(const SEG &aSeg) const
Function Collinear()
Definition: seg.h:238
Definition: seg.h:39
void Reverse()
Definition: seg.h:341
bool operator==(const SEG &aSeg) const
Definition: seg.h:106
extended_type Dot(const VECTOR2< T > &aVector) const
Function Dot() computes dot product of self with aVector.
Definition: vector2d.h:492
ecoord SquaredDistance(const VECTOR2I &aP) const
Definition: seg.h:207
VECTOR2I A
Definition: seg.h:47
int m_index
index withing the parent shape (used when m_is_local == false)
Definition: seg.h:356
T rescale(T aNumerator, T aValue, T aDenominator)
Function rescale()
Definition: util.h:84
boost::optional< T > OPT
Definition: optional.h:7
bool Collide(const SEG &aSeg, int aClearance) const
Definition: seg.cpp:179
SEG(const VECTOR2I &aA, const VECTOR2I &aB, int aIndex)
Constructor Creates a segment between (aA) and (aB), referenced to a multi-segment shape.
Definition: seg.h:85
int Side(const VECTOR2I &aP) const
Function Side()
Definition: seg.h:133
bool Contains(const SEG &aSeg) const
Definition: seg.h:294
VECTOR2I B
Definition: seg.h:48