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 <cstdio>
29 #include <climits>
30 
31 #include <math/vector2d.h>
32 #include <core/optional.h>
33 
35 
36 class SEG
37 {
38 public:
40  friend inline std::ostream& operator<<( std::ostream& aStream, const SEG& aSeg );
41 
42  /* Start and the of the segment. Public, to make access simpler.
43  */
46 
50  SEG()
51  {
52  m_index = -1;
53  }
54 
59  SEG( int aX1, int aY1, int aX2, int aY2 ) :
60  A ( VECTOR2I( aX1, aY1 ) ),
61  B ( VECTOR2I( aX2, aY2 ) )
62  {
63  m_index = -1;
64  }
65 
70  SEG( const VECTOR2I& aA, const VECTOR2I& aB ) : A( aA ), B( aB )
71  {
72  m_index = -1;
73  }
74 
82  SEG( const VECTOR2I& aA, const VECTOR2I& aB, int aIndex ) : A( aA ), B( aB )
83  {
84  m_index = aIndex;
85  }
86 
90  SEG( const SEG& aSeg ) : A( aSeg.A ), B( aSeg.B ), m_index( aSeg.m_index )
91  {
92  }
93 
94  SEG& operator=( const SEG& aSeg )
95  {
96  A = aSeg.A;
97  B = aSeg.B;
98  m_index = aSeg.m_index;
99 
100  return *this;
101  }
102 
103  bool operator==( const SEG& aSeg ) const
104  {
105  return (A == aSeg.A && B == aSeg.B) ;
106  }
107 
108  bool operator!=( const SEG& aSeg ) const
109  {
110  return (A != aSeg.A || B != aSeg.B);
111  }
112 
121  VECTOR2I LineProject( const VECTOR2I& aP ) const;
122 
130  int Side( const VECTOR2I& aP ) const
131  {
132  const ecoord det = ( B - A ).Cross( aP - A );
133 
134  return det < 0 ? -1 : ( det > 0 ? 1 : 0 );
135  }
136 
147  int LineDistance( const VECTOR2I& aP, bool aDetermineSide = false ) const;
148 
155  const VECTOR2I NearestPoint( const VECTOR2I &aP ) const;
156 
161  const VECTOR2I NearestPoint( const SEG &aSeg ) const;
162 
173  OPT_VECTOR2I Intersect( const SEG& aSeg, bool aIgnoreEndpoints = false,
174  bool aLines = false ) const;
175 
183  OPT_VECTOR2I IntersectLines( const SEG& aSeg ) const
184  {
185  return Intersect( aSeg, false, true );
186  }
187 
188  bool Collide( const SEG& aSeg, int aClearance ) const;
189 
190  ecoord SquaredDistance( const SEG& aSeg ) const;
191 
199  int Distance( const SEG& aSeg ) const
200  {
201  return sqrt( SquaredDistance( aSeg ) );
202  }
203 
204  ecoord SquaredDistance( const VECTOR2I& aP ) const
205  {
206  return ( NearestPoint( aP ) - aP ).SquaredEuclideanNorm();
207  }
208 
216  int Distance( const VECTOR2I& aP ) const
217  {
218  return sqrt( SquaredDistance( aP ) );
219  }
220 
221  void CanonicalCoefs( ecoord& qA, ecoord& qB, ecoord& qC ) const
222  {
223  qA = A.y - B.y;
224  qB = B.x - A.x;
225  qC = -qA * A.x - qB * A.y;
226  }
227 
235  bool Collinear( const SEG& aSeg ) const
236  {
237  ecoord qa, qb, qc;
238  CanonicalCoefs( qa, qb, qc );
239 
240  ecoord d1 = std::abs( aSeg.A.x * qa + aSeg.A.y * qb + qc );
241  ecoord d2 = std::abs( aSeg.B.x * qa + aSeg.B.y * qb + qc );
242 
243  return ( d1 <= 1 && d2 <= 1 );
244  }
245 
246  bool ApproxCollinear( const SEG& aSeg ) const
247  {
248  ecoord p, q, r;
249  CanonicalCoefs( p, q, r );
250 
251  ecoord dist1 = ( p * aSeg.A.x + q * aSeg.A.y + r ) / sqrt( p * p + q * q );
252  ecoord dist2 = ( p * aSeg.B.x + q * aSeg.B.y + r ) / sqrt( p * p + q * q );
253 
254  return std::abs( dist1 ) <= 1 && std::abs( dist2 ) <= 1;
255  }
256 
257  bool ApproxParallel ( const SEG& aSeg ) const
258  {
259  ecoord p, q, r;
260  CanonicalCoefs( p, q, r );
261 
262  ecoord dist1 = ( p * aSeg.A.x + q * aSeg.A.y + r ) / sqrt( p * p + q * q );
263  ecoord dist2 = ( p * aSeg.B.x + q * aSeg.B.y + r ) / sqrt( p * p + q * q );
264 
265  return std::abs( dist1 - dist2 ) <= 1;
266  }
267 
268 
269  bool Overlaps( const SEG& aSeg ) const
270  {
271  if( aSeg.A == aSeg.B ) // single point corner case
272  {
273  if( A == aSeg.A || B == aSeg.A )
274  return false;
275 
276  return Contains( aSeg.A );
277  }
278 
279  if( !Collinear( aSeg ) )
280  return false;
281 
282  if( Contains( aSeg.A ) || Contains( aSeg.B ) )
283  return true;
284  if( aSeg.Contains( A ) || aSeg.Contains( B ) )
285  return true;
286 
287  return false;
288  }
289 
296  int Length() const
297  {
298  return ( A - B ).EuclideanNorm();
299  }
300 
302  {
303  return ( A - B ).SquaredEuclideanNorm();
304  }
305 
306  ecoord TCoef( const VECTOR2I& aP ) const;
307 
314  int Index() const
315  {
316  return m_index;
317  }
318 
319  bool Contains( const VECTOR2I& aP ) const;
320 
321  bool PointCloserThan( const VECTOR2I& aP, int aDist ) const;
322 
323  void Reverse()
324  {
325  std::swap( A, B );
326  }
327 
329  VECTOR2I Center() const
330  {
331  return A + ( B - A ) / 2;
332  }
333 
334 private:
335  bool ccw( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I &aC ) const;
336 
338  int m_index;
339 };
340 
341 inline VECTOR2I SEG::LineProject( const VECTOR2I& aP ) const
342 {
343  VECTOR2I d = B - A;
344  ecoord l_squared = d.Dot( d );
345 
346  if( l_squared == 0 )
347  return A;
348 
349  ecoord t = d.Dot( aP - A );
350 
351  int xp = rescale( t, (ecoord)d.x, l_squared );
352  int yp = rescale( t, (ecoord)d.y, l_squared );
353 
354  return A + VECTOR2I( xp, yp );
355 }
356 
357 inline int SEG::LineDistance( const VECTOR2I& aP, bool aDetermineSide ) const
358 {
359  ecoord p = A.y - B.y;
360  ecoord q = B.x - A.x;
361  ecoord r = -p * A.x - q * A.y;
362 
363  ecoord dist = ( p * aP.x + q * aP.y + r ) / sqrt( p * p + q * q );
364 
365  return aDetermineSide ? dist : std::abs( dist );
366 }
367 
368 inline SEG::ecoord SEG::TCoef( const VECTOR2I& aP ) const
369 {
370  VECTOR2I d = B - A;
371  return d.Dot( aP - A);
372 }
373 
374 inline const VECTOR2I SEG::NearestPoint( const VECTOR2I& aP ) const
375 {
376  VECTOR2I d = B - A;
377  ecoord l_squared = d.Dot( d );
378 
379  if( l_squared == 0 )
380  return A;
381 
382  ecoord t = d.Dot( aP - A );
383 
384  if( t < 0 )
385  return A;
386  else if( t > l_squared )
387  return B;
388 
389  int xp = rescale( t, (ecoord)d.x, l_squared );
390  int yp = rescale( t, (ecoord)d.y, l_squared );
391 
392  return A + VECTOR2I( xp, yp );
393 }
394 
395 inline std::ostream& operator<<( std::ostream& aStream, const SEG& aSeg )
396 {
397  aStream << "[ " << aSeg.A << " - " << aSeg.B << " ]";
398 
399  return aStream;
400 }
401 
402 #endif // __SEG_H
int Length() const
Function Length()
Definition: seg.h:296
VECTOR2_TRAITS< int >::extended_type extended_type
Definition: vector2d.h:77
int Index() const
Function Index()
Definition: seg.h:314
bool Overlaps(const SEG &aSeg) const
Definition: seg.h:269
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:199
static const int dist[10][10]
Definition: ar_matrix.cpp:320
void CanonicalCoefs(ecoord &qA, ecoord &qB, ecoord &qC) const
Definition: seg.h:221
ecoord SquaredLength() const
Definition: seg.h:301
bool ccw(const VECTOR2I &aA, const VECTOR2I &aB, const VECTOR2I &aC) const
Definition: seg.cpp:161
SEG()
Default constructor Creates an empty (0, 0) segment.
Definition: seg.h:50
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Function Intersect()
Definition: seg.cpp:132
std::ostream & operator<<(std::ostream &aStream, const SEG &aSeg)
Definition: seg.h:395
VECTOR2I::extended_type ecoord
Definition: seg.h:39
bool operator!=(const SEG &aSeg) const
Definition: seg.h:108
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:76
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Function IntersectLines()
Definition: seg.h:183
int LineDistance(const VECTOR2I &aP, bool aDetermineSide=false) const
Function LineDistance()
Definition: seg.h:357
VECTOR2I Center() const
Returns the center point of the line
Definition: seg.h:329
friend std::ostream & operator<<(std::ostream &aStream, const SEG &aSeg)
Definition: seg.h:395
VECTOR2< int > VECTOR2I
Definition: vector2d.h:587
#define abs(a)
Definition: auxiliary.h:84
bool PointCloserThan(const VECTOR2I &aP, int aDist) const
Definition: seg.cpp:34
SEG & operator=(const SEG &aSeg)
Definition: seg.h:94
VECTOR2I LineProject(const VECTOR2I &aP) const
Function LineProject()
Definition: seg.h:341
ecoord TCoef(const VECTOR2I &aP) const
Definition: seg.h:368
OPT< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:34
bool ApproxParallel(const SEG &aSeg) const
Definition: seg.h:257
VECTOR2I::extended_type ecoord
SEG(const VECTOR2I &aA, const VECTOR2I &aB)
Constructor Creates a segment between (aA) and (aB)
Definition: seg.h:70
bool Contains(const VECTOR2I &aP) const
Definition: seg.cpp:188
SEG(int aX1, int aY1, int aX2, int aY2)
Constructor Creates a segment between (aX1, aY1) and (aX2, aY2)
Definition: seg.h:59
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
Definition: seg.h:374
bool ApproxCollinear(const SEG &aSeg) const
Definition: seg.h:246
SEG(const SEG &aSeg)
Copy constructor.
Definition: seg.h:90
int Distance(const VECTOR2I &aP) const
Function Distance()
Definition: seg.h:216
bool Collinear(const SEG &aSeg) const
Function Collinear()
Definition: seg.h:235
Definition: seg.h:36
void Reverse()
Definition: seg.h:323
bool operator==(const SEG &aSeg) const
Definition: seg.h:103
extended_type Dot(const VECTOR2< T > &aVector) const
Function Dot() computes dot product of self with aVector.
Definition: vector2d.h:485
ecoord SquaredDistance(const VECTOR2I &aP) const
Definition: seg.h:204
T rescale(T aNumerator, T aValue, T aDenominator)
Function rescale()
VECTOR2I A
Definition: seg.h:44
int m_index
index withing the parent shape (used when m_is_local == false)
Definition: seg.h:338
boost::optional< T > OPT
Definition: optional.h:7
bool Collide(const SEG &aSeg, int aClearance) const
Definition: seg.cpp:167
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:82
int Side(const VECTOR2I &aP) const
Function Side()
Definition: seg.h:130
VECTOR2I B
Definition: seg.h:45