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 
33 #include <boost/optional/optional.hpp>
34 
36 
37 class SEG
38 {
39 private:
43 
44 public:
45  friend inline std::ostream& operator<<( std::ostream& aStream, const SEG& aSeg );
46 
47  /* Start and the of the segment. Public, to make access simpler. These are references
48  * to an object the segment belongs to (e.g. a line chain) or references to locally stored
49  * points (m_a, m_b).
50  */
53 
57  SEG() :
58  A( m_a ),
59  B( m_b )
60  {
61  m_index = -1;
62  }
63 
68  SEG( int aX1, int aY1, int aX2, int aY2 ) :
69  A( m_a ),
70  B( m_b )
71  {
72  A = VECTOR2I( aX1, aY1 );
73  B = VECTOR2I( aX2, aY2 );
74  m_index = -1;
75  }
76 
81  SEG( const VECTOR2I& aA, const VECTOR2I& aB ) :
82  A( m_a ),
83  B( m_b )
84  {
85  A = aA;
86  B = aB;
87  m_index = -1;
88  }
89 
94  SEG( VECTOR2I& aA, VECTOR2I& aB ) :
95  A( aA ),
96  B( aB )
97  {
98  m_index = -1;
99  }
100 
105  SEG( VECTOR2I& aA, VECTOR2I& aB, int aIndex ) :
106  A( aA ),
107  B( aB )
108  {
109  m_index = aIndex;
110  }
111 
119  SEG( const VECTOR2I& aA, const VECTOR2I& aB, int aIndex ) :
120  A( m_a ),
121  B( m_b )
122  {
123  A = aA;
124  B = aB;
125  m_index = aIndex;
126  }
127 
131  SEG( const SEG& aSeg ) :
132  A( m_a ),
133  B( m_b ),
134  m_index( aSeg.m_index )
135  {
136  A = aSeg.A;
137  B = aSeg.B;
138  }
139 
140  SEG& operator=( const SEG& aSeg )
141  {
142  A = aSeg.A;
143  B = aSeg.B;
144  m_index = aSeg.m_index;
145 
146  return *this;
147  }
148 
157  VECTOR2I LineProject( const VECTOR2I& aP ) const;
158 
166  int Side( const VECTOR2I& aP ) const
167  {
168  const ecoord det = ( B - A ).Cross( aP - A );
169 
170  return det < 0 ? -1 : ( det > 0 ? 1 : 0 );
171  }
172 
182  int LineDistance( const VECTOR2I& aP, bool aDetermineSide = false ) const;
183 
190  const VECTOR2I NearestPoint( const VECTOR2I &aP ) const;
191 
202  OPT_VECTOR2I Intersect( const SEG& aSeg, bool aIgnoreEndpoints = false,
203  bool aLines = false ) const;
204 
212  OPT_VECTOR2I IntersectLines( const SEG& aSeg ) const
213  {
214  return Intersect( aSeg, false, true );
215  }
216 
217  bool Collide( const SEG& aSeg, int aClearance ) const;
218 
219  ecoord SquaredDistance( const SEG& aSeg ) const;
220 
228  int Distance( const SEG& aSeg ) const
229  {
230  return sqrt( SquaredDistance( aSeg ) );
231  }
232 
233  ecoord SquaredDistance( const VECTOR2I& aP ) const
234  {
235  return ( NearestPoint( aP ) - aP ).SquaredEuclideanNorm();
236  }
237 
245  int Distance( const VECTOR2I& aP ) const
246  {
247  return sqrt( SquaredDistance( aP ) );
248  }
249 
250  void CanonicalCoefs( ecoord& qA, ecoord& qB, ecoord& qC ) const
251  {
252  qA = A.y - B.y;
253  qB = B.x - A.x;
254  qC = -qA * A.x - qB * A.y;
255  }
256 
264  bool Collinear( const SEG& aSeg ) const
265  {
266  ecoord qa, qb, qc;
267  CanonicalCoefs( qa, qb, qc );
268 
269  ecoord d1 = std::abs( aSeg.A.x * qa + aSeg.A.y * qb + qc );
270  ecoord d2 = std::abs( aSeg.B.x * qa + aSeg.B.y * qb + qc );
271 
272  return ( d1 <= 1 && d2 <= 1 );
273  }
274 
275  bool ApproxCollinear( const SEG& aSeg ) const
276  {
277  ecoord p, q, r;
278  CanonicalCoefs( p, q, r );
279 
280  ecoord dist1 = ( p * aSeg.A.x + q * aSeg.A.y + r ) / sqrt( p * p + q * q );
281  ecoord dist2 = ( p * aSeg.B.x + q * aSeg.B.y + r ) / sqrt( p * p + q * q );
282 
283  return std::abs( dist1 ) <= 1 && std::abs( dist2 ) <= 1;
284  }
285 
286  bool ApproxParallel ( const SEG& aSeg ) const
287  {
288  ecoord p, q, r;
289  CanonicalCoefs( p, q, r );
290 
291  ecoord dist1 = ( p * aSeg.A.x + q * aSeg.A.y + r ) / sqrt( p * p + q * q );
292  ecoord dist2 = ( p * aSeg.B.x + q * aSeg.B.y + r ) / sqrt( p * p + q * q );
293 
294  return std::abs( dist1 - dist2 ) <= 1;
295  }
296 
297 
298  bool Overlaps( const SEG& aSeg ) const
299  {
300  if( aSeg.A == aSeg.B ) // single point corner case
301  {
302  if( A == aSeg.A || B == aSeg.A )
303  return false;
304 
305  return Contains( aSeg.A );
306  }
307 
308  if( !Collinear( aSeg ) )
309  return false;
310 
311  if( Contains( aSeg.A ) || Contains( aSeg.B ) )
312  return true;
313  if( aSeg.Contains( A ) || aSeg.Contains( B ) )
314  return true;
315 
316  return false;
317  }
318 
325  int Length() const
326  {
327  return ( A - B ).EuclideanNorm();
328  }
329 
330  ecoord SquaredLength() const
331  {
332  return ( A - B ).SquaredEuclideanNorm();
333  }
334 
335  ecoord TCoef( const VECTOR2I& aP ) const;
336 
343  int Index() const
344  {
345  return m_index;
346  }
347 
348  bool Contains( const VECTOR2I& aP ) const;
349 
350  bool PointCloserThan( const VECTOR2I& aP, int aDist ) const;
351 
352  void Reverse()
353  {
354  std::swap( A, B );
355  }
356 
357 private:
358  bool ccw( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I &aC ) const;
359 
361  int m_index;
362 };
363 
364 inline VECTOR2I SEG::LineProject( const VECTOR2I& aP ) const
365 {
366  VECTOR2I d = B - A;
367  ecoord l_squared = d.Dot( d );
368 
369  if( l_squared == 0 )
370  return A;
371 
372  ecoord t = d.Dot( aP - A );
373 
374  int xp = rescale( t, (ecoord)d.x, l_squared );
375  int yp = rescale( t, (ecoord)d.y, l_squared );
376 
377  return A + VECTOR2I( xp, yp );
378 }
379 
380 inline int SEG::LineDistance( const VECTOR2I& aP, bool aDetermineSide ) const
381 {
382  ecoord p = A.y - B.y;
383  ecoord q = B.x - A.x;
384  ecoord r = -p * A.x - q * A.y;
385 
386  ecoord dist = ( p * aP.x + q * aP.y + r ) / sqrt( p * p + q * q );
387 
388  return aDetermineSide ? dist : std::abs( dist );
389 }
390 
391 inline SEG::ecoord SEG::TCoef( const VECTOR2I& aP ) const
392 {
393  VECTOR2I d = B - A;
394  return d.Dot( aP - A);
395 }
396 
397 inline const VECTOR2I SEG::NearestPoint( const VECTOR2I& aP ) const
398 {
399  VECTOR2I d = B - A;
400  ecoord l_squared = d.Dot( d );
401 
402  if( l_squared == 0 )
403  return A;
404 
405  ecoord t = d.Dot( aP - A );
406 
407  if( t < 0 )
408  return A;
409  else if( t > l_squared )
410  return B;
411 
412  int xp = rescale( t, (ecoord)d.x, l_squared );
413  int yp = rescale( t, (ecoord)d.y, l_squared );
414 
415  return A + VECTOR2I( xp, yp );
416 }
417 
418 inline std::ostream& operator<<( std::ostream& aStream, const SEG& aSeg )
419 {
420  aStream << "[ " << aSeg.A << " - " << aSeg.B << " ]";
421 
422  return aStream;
423 }
424 
425 #endif // __SEG_H
int Index() const
Function Index()
Definition: seg.h:343
void CanonicalCoefs(ecoord &qA, ecoord &qB, ecoord &qC) const
Definition: seg.h:250
VECTOR2_TRAITS< T >::extended_type extended_type
Definition: vector2d.h:81
ecoord SquaredLength() const
Definition: seg.h:330
VECTOR2I & B
Definition: seg.h:52
extended_type Dot(const VECTOR2< T > &aVector) const
Function Dot() computes dot product of self with aVector.
Definition: vector2d.h:488
int Side(const VECTOR2I &aP) const
Function Side()
Definition: seg.h:166
int Length() const
Function Length()
Definition: seg.h:325
SEG()
Default constructor Creates an empty (0, 0) segment, locally-referenced.
Definition: seg.h:57
VECTOR2I LineProject(const VECTOR2I &aP) const
Function LineProject()
Definition: seg.h:364
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Function IntersectLines()
Definition: seg.h:212
std::ostream & operator<<(std::ostream &aStream, const SEG &aSeg)
Definition: seg.h:418
static const int dist[10][10]
Definition: dist.cpp:57
friend std::ostream & operator<<(std::ostream &aStream, const SEG &aSeg)
Definition: seg.h:418
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:590
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:275
SEG & operator=(const SEG &aSeg)
Definition: seg.h:140
ecoord TCoef(const VECTOR2I &aP) const
Definition: seg.h:391
VECTOR2I & A
Definition: seg.h:51
bool ccw(const VECTOR2I &aA, const VECTOR2I &aB, const VECTOR2I &aC) const
Definition: seg.cpp:128
SEG(const VECTOR2I &aA, const VECTOR2I &aB)
Constructor Creates a segment between (aA) and (aB), locally referenced.
Definition: seg.h:81
int LineDistance(const VECTOR2I &aP, bool aDetermineSide=false) const
Function LineDistance()
Definition: seg.h:380
SEG(int aX1, int aY1, int aX2, int aY2)
Constructor Creates a segment between (aX1, aY1) and (aX2, aY2), locally referenced.
Definition: seg.h:68
SEG(const SEG &aSeg)
Copy constructor.
Definition: seg.h:131
ecoord SquaredDistance(const VECTOR2I &aP) const
Definition: seg.h:233
boost::optional< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:35
VECTOR2I m_b
Definition: seg.h:42
SEG(VECTOR2I &aA, VECTOR2I &aB, int aIndex)
Constructor Creates a segment between (aA) and (aB), referencing the passed points.
Definition: seg.h:105
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:397
Definition: seg.h:37
void Reverse()
Definition: seg.h:352
bool Overlaps(const SEG &aSeg) const
Definition: seg.h:298
int m_index
index withing the parent shape (used when m_is_local == false)
Definition: seg.h:361
int Distance(const VECTOR2I &aP) const
Function Distance()
Definition: seg.h:245
VECTOR2I::extended_type ecoord
Definition: seg.h:40
VECTOR2I m_a
Definition: seg.h:41
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:264
bool ApproxParallel(const SEG &aSeg) const
Definition: seg.h:286
bool Contains(const VECTOR2I &aP) const
Definition: seg.cpp:155
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:228
double Cross(const Point &a, const Point &b)
Perform the cross product on two vectors. In 2D this produces a scalar.
Definition: shapes.h:287
SEG(VECTOR2I &aA, VECTOR2I &aB)
Constructor Creates a segment between (aA) and (aB), referencing the passed points.
Definition: seg.h:94
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:119