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 private:
40 
41 public:
42  friend inline std::ostream& operator<<( std::ostream& aStream, const SEG& aSeg );
43 
44  /* Start and the of the segment. Public, to make access simpler.
45  */
48 
52  SEG()
53  {
54  m_index = -1;
55  }
56 
61  SEG( int aX1, int aY1, int aX2, int aY2 ) :
62  A ( VECTOR2I( aX1, aY1 ) ),
63  B ( VECTOR2I( aX2, aY2 ) )
64  {
65  m_index = -1;
66  }
67 
72  SEG( const VECTOR2I& aA, const VECTOR2I& aB ) : A( aA ), B( aB )
73  {
74  m_index = -1;
75  }
76 
84  SEG( const VECTOR2I& aA, const VECTOR2I& aB, int aIndex ) : A( aA ), B( aB )
85  {
86  m_index = aIndex;
87  }
88 
92  SEG( const SEG& aSeg ) : A( aSeg.A ), B( aSeg.B ), m_index( aSeg.m_index )
93  {
94  }
95 
96  SEG& operator=( const SEG& aSeg )
97  {
98  A = aSeg.A;
99  B = aSeg.B;
100  m_index = aSeg.m_index;
101 
102  return *this;
103  }
104 
105  bool operator==( const SEG& aSeg ) const
106  {
107  return (A == aSeg.A && B == aSeg.B) ;
108  }
109 
110  bool operator!=( const SEG& aSeg ) const
111  {
112  return (A != aSeg.A || B != aSeg.B);
113  }
114 
123  VECTOR2I LineProject( const VECTOR2I& aP ) const;
124 
132  int Side( const VECTOR2I& aP ) const
133  {
134  const ecoord det = ( B - A ).Cross( aP - A );
135 
136  return det < 0 ? -1 : ( det > 0 ? 1 : 0 );
137  }
138 
149  int LineDistance( const VECTOR2I& aP, bool aDetermineSide = false ) const;
150 
157  const VECTOR2I NearestPoint( const VECTOR2I &aP ) const;
158 
169  OPT_VECTOR2I Intersect( const SEG& aSeg, bool aIgnoreEndpoints = false,
170  bool aLines = false ) const;
171 
179  OPT_VECTOR2I IntersectLines( const SEG& aSeg ) const
180  {
181  return Intersect( aSeg, false, true );
182  }
183 
184  bool Collide( const SEG& aSeg, int aClearance ) const;
185 
186  ecoord SquaredDistance( const SEG& aSeg ) const;
187 
195  int Distance( const SEG& aSeg ) const
196  {
197  return sqrt( SquaredDistance( aSeg ) );
198  }
199 
200  ecoord SquaredDistance( const VECTOR2I& aP ) const
201  {
202  return ( NearestPoint( aP ) - aP ).SquaredEuclideanNorm();
203  }
204 
212  int Distance( const VECTOR2I& aP ) const
213  {
214  return sqrt( SquaredDistance( aP ) );
215  }
216 
217  void CanonicalCoefs( ecoord& qA, ecoord& qB, ecoord& qC ) const
218  {
219  qA = A.y - B.y;
220  qB = B.x - A.x;
221  qC = -qA * A.x - qB * A.y;
222  }
223 
231  bool Collinear( const SEG& aSeg ) const
232  {
233  ecoord qa, qb, qc;
234  CanonicalCoefs( qa, qb, qc );
235 
236  ecoord d1 = std::abs( aSeg.A.x * qa + aSeg.A.y * qb + qc );
237  ecoord d2 = std::abs( aSeg.B.x * qa + aSeg.B.y * qb + qc );
238 
239  return ( d1 <= 1 && d2 <= 1 );
240  }
241 
242  bool ApproxCollinear( const SEG& aSeg ) const
243  {
244  ecoord p, q, r;
245  CanonicalCoefs( p, q, r );
246 
247  ecoord dist1 = ( p * aSeg.A.x + q * aSeg.A.y + r ) / sqrt( p * p + q * q );
248  ecoord dist2 = ( p * aSeg.B.x + q * aSeg.B.y + r ) / sqrt( p * p + q * q );
249 
250  return std::abs( dist1 ) <= 1 && std::abs( dist2 ) <= 1;
251  }
252 
253  bool ApproxParallel ( const SEG& aSeg ) const
254  {
255  ecoord p, q, r;
256  CanonicalCoefs( p, q, r );
257 
258  ecoord dist1 = ( p * aSeg.A.x + q * aSeg.A.y + r ) / sqrt( p * p + q * q );
259  ecoord dist2 = ( p * aSeg.B.x + q * aSeg.B.y + r ) / sqrt( p * p + q * q );
260 
261  return std::abs( dist1 - dist2 ) <= 1;
262  }
263 
264 
265  bool Overlaps( const SEG& aSeg ) const
266  {
267  if( aSeg.A == aSeg.B ) // single point corner case
268  {
269  if( A == aSeg.A || B == aSeg.A )
270  return false;
271 
272  return Contains( aSeg.A );
273  }
274 
275  if( !Collinear( aSeg ) )
276  return false;
277 
278  if( Contains( aSeg.A ) || Contains( aSeg.B ) )
279  return true;
280  if( aSeg.Contains( A ) || aSeg.Contains( B ) )
281  return true;
282 
283  return false;
284  }
285 
292  int Length() const
293  {
294  return ( A - B ).EuclideanNorm();
295  }
296 
297  ecoord SquaredLength() const
298  {
299  return ( A - B ).SquaredEuclideanNorm();
300  }
301 
302  ecoord TCoef( const VECTOR2I& aP ) const;
303 
310  int Index() const
311  {
312  return m_index;
313  }
314 
315  bool Contains( const VECTOR2I& aP ) const;
316 
317  bool PointCloserThan( const VECTOR2I& aP, int aDist ) const;
318 
319  void Reverse()
320  {
321  std::swap( A, B );
322  }
323 
325  VECTOR2I Center() const
326  {
327  return A + ( B - A ) / 2;
328  }
329 
330 private:
331  bool ccw( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I &aC ) const;
332 
334  int m_index;
335 };
336 
337 inline VECTOR2I SEG::LineProject( const VECTOR2I& aP ) const
338 {
339  VECTOR2I d = B - A;
340  ecoord l_squared = d.Dot( d );
341 
342  if( l_squared == 0 )
343  return A;
344 
345  ecoord t = d.Dot( aP - A );
346 
347  int xp = rescale( t, (ecoord)d.x, l_squared );
348  int yp = rescale( t, (ecoord)d.y, l_squared );
349 
350  return A + VECTOR2I( xp, yp );
351 }
352 
353 inline int SEG::LineDistance( const VECTOR2I& aP, bool aDetermineSide ) const
354 {
355  ecoord p = A.y - B.y;
356  ecoord q = B.x - A.x;
357  ecoord r = -p * A.x - q * A.y;
358 
359  ecoord dist = ( p * aP.x + q * aP.y + r ) / sqrt( p * p + q * q );
360 
361  return aDetermineSide ? dist : std::abs( dist );
362 }
363 
364 inline SEG::ecoord SEG::TCoef( const VECTOR2I& aP ) const
365 {
366  VECTOR2I d = B - A;
367  return d.Dot( aP - A);
368 }
369 
370 inline const VECTOR2I SEG::NearestPoint( const VECTOR2I& aP ) const
371 {
372  VECTOR2I d = B - A;
373  ecoord l_squared = d.Dot( d );
374 
375  if( l_squared == 0 )
376  return A;
377 
378  ecoord t = d.Dot( aP - A );
379 
380  if( t < 0 )
381  return A;
382  else if( t > l_squared )
383  return B;
384 
385  int xp = rescale( t, (ecoord)d.x, l_squared );
386  int yp = rescale( t, (ecoord)d.y, l_squared );
387 
388  return A + VECTOR2I( xp, yp );
389 }
390 
391 inline std::ostream& operator<<( std::ostream& aStream, const SEG& aSeg )
392 {
393  aStream << "[ " << aSeg.A << " - " << aSeg.B << " ]";
394 
395  return aStream;
396 }
397 
398 #endif // __SEG_H
int Index() const
Function Index()
Definition: seg.h:310
void CanonicalCoefs(ecoord &qA, ecoord &qB, ecoord &qC) const
Definition: seg.h:217
VECTOR2_TRAITS< T >::extended_type extended_type
Definition: vector2d.h:77
ecoord SquaredLength() const
Definition: seg.h:297
extended_type Dot(const VECTOR2< T > &aVector) const
Function Dot() computes dot product of self with aVector.
Definition: vector2d.h:487
bool operator==(const SEG &aSeg) const
Definition: seg.h:105
int Side(const VECTOR2I &aP) const
Function Side()
Definition: seg.h:132
int Length() const
Function Length()
Definition: seg.h:292
SEG()
Default constructor Creates an empty (0, 0) segment.
Definition: seg.h:52
VECTOR2I LineProject(const VECTOR2I &aP) const
Function LineProject()
Definition: seg.h:337
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Function IntersectLines()
Definition: seg.h:179
static const int dist[10][10]
Definition: dist.cpp:57
friend std::ostream & operator<<(std::ostream &aStream, const SEG &aSeg)
Definition: seg.h:391
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Function Intersect()
Definition: seg.cpp:99
VECTOR2< int > VECTOR2I
Definition: vector2d.h:589
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:76
#define abs(a)
Definition: auxiliary.h:84
bool ApproxCollinear(const SEG &aSeg) const
Definition: seg.h:242
SEG & operator=(const SEG &aSeg)
Definition: seg.h:96
ecoord TCoef(const VECTOR2I &aP) const
Definition: seg.h:364
bool ccw(const VECTOR2I &aA, const VECTOR2I &aB, const VECTOR2I &aC) const
Definition: seg.cpp:128
VECTOR2I Center() const
Returns the center point of the line
Definition: seg.h:325
OPT< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:34
SEG(const VECTOR2I &aA, const VECTOR2I &aB)
Constructor Creates a segment between (aA) and (aB)
Definition: seg.h:72
int LineDistance(const VECTOR2I &aP, bool aDetermineSide=false) const
Function LineDistance()
Definition: seg.h:353
SEG(int aX1, int aY1, int aX2, int aY2)
Constructor Creates a segment between (aX1, aY1) and (aX2, aY2)
Definition: seg.h:61
SEG(const SEG &aSeg)
Copy constructor.
Definition: seg.h:92
ecoord SquaredDistance(const VECTOR2I &aP) const
Definition: seg.h:200
int rescale(int aNumerator, int aValue, int aDenominator)
Definition: math_util.cpp:32
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
Definition: seg.h:370
Definition: seg.h:36
void Reverse()
Definition: seg.h:319
bool Overlaps(const SEG &aSeg) const
Definition: seg.h:265
VECTOR2I A
Definition: seg.h:46
int m_index
index withing the parent shape (used when m_is_local == false)
Definition: seg.h:334
int Distance(const VECTOR2I &aP) const
Function Distance()
Definition: seg.h:212
boost::optional< T > OPT
Definition: optional.h:7
VECTOR2I::extended_type ecoord
Definition: seg.h:39
bool PointCloserThan(const VECTOR2I &aP, int aDist) const
Definition: seg.cpp:34
bool Collide(const SEG &aSeg, int aClearance) const
Definition: seg.cpp:134
bool Collinear(const SEG &aSeg) const
Function Collinear()
Definition: seg.h:231
bool ApproxParallel(const SEG &aSeg) const
Definition: seg.h:253
bool Contains(const VECTOR2I &aP) const
Definition: seg.cpp:155
bool operator!=(const SEG &aSeg) const
Definition: seg.h:110
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:195
double Cross(const Point &a, const Point &b)
Perform the cross product on two vectors. In 2D this produces a scalar.
Definition: shapes.h:269
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:84
VECTOR2I B
Definition: seg.h:47