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  * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors.
6  *
7  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
8  *
9  * This program is free software; you can redistribute it and/or
10  * modify it under the terms of the GNU General Public License
11  * as published by the Free Software Foundation; either version 2
12  * of the License, or (at your option) any later version.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, you may find one here:
21  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
22  * or you may search the http://www.gnu.org website for the version 2 license,
23  * or you may write to the Free Software Foundation, Inc.,
24  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
25  */
26 
27 #ifndef __SEG_H
28 #define __SEG_H
29 
30 #include <math.h> // for sqrt
31 #include <stdlib.h> // for abs
32 #include <ostream> // for operator<<, ostream, basic_os...
33 #include <type_traits> // for swap
34 
35 #include <core/optional.h>
36 #include <math/util.h> // for rescale
37 #include <math/vector2d.h>
38 
40 
41 class SEG
42 {
43 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.
48  */
51 
55  SEG()
56  {
57  m_index = -1;
58  }
59 
63  SEG( int aX1, int aY1, int aX2, int aY2 ) :
64  A( VECTOR2I( aX1, aY1 ) ),
65  B( VECTOR2I( aX2, aY2 ) )
66  {
67  m_index = -1;
68  }
69 
73  SEG( const VECTOR2I& aA, const VECTOR2I& aB ) :
74  A( aA ),
75  B( aB )
76  {
77  m_index = -1;
78  }
79 
87  SEG( const VECTOR2I& aA, const VECTOR2I& aB, int aIndex ) :
88  A( aA ),
89  B( aB )
90  {
91  m_index = aIndex;
92  }
93 
97  SEG( const SEG& aSeg ) :
98  A( aSeg.A ),
99  B( aSeg.B ),
100  m_index( aSeg.m_index )
101  {
102  }
103 
104  SEG& operator=( const SEG& aSeg )
105  {
106  A = aSeg.A;
107  B = aSeg.B;
108  m_index = aSeg.m_index;
109 
110  return *this;
111  }
112 
113  bool operator==( const SEG& aSeg ) const
114  {
115  return (A == aSeg.A && B == aSeg.B) ;
116  }
117 
118  bool operator!=( const SEG& aSeg ) const
119  {
120  return (A != aSeg.A || B != aSeg.B);
121  }
122 
123  static SEG::ecoord Square( int a )
124  {
125  return ecoord( a ) * a;
126  }
127 
135  VECTOR2I LineProject( const VECTOR2I& aP ) const;
136 
143  int Side( const VECTOR2I& aP ) const
144  {
145  const ecoord det = ( B - A ).Cross( aP - A );
146 
147  return det < 0 ? -1 : ( det > 0 ? 1 : 0 );
148  }
149 
159  int LineDistance( const VECTOR2I& aP, bool aDetermineSide = false ) const;
160 
166  const VECTOR2I NearestPoint( const VECTOR2I &aP ) const;
167 
173  const VECTOR2I NearestPoint( const SEG &aSeg ) const;
174 
184  OPT_VECTOR2I Intersect( const SEG& aSeg, bool aIgnoreEndpoints = false,
185  bool aLines = false ) const;
186 
193  OPT_VECTOR2I IntersectLines( const SEG& aSeg ) const
194  {
195  return Intersect( aSeg, false, true );
196  }
197 
204  SEG PerpendicularSeg( const VECTOR2I& aP ) const;
205 
212  SEG ParallelSeg( const VECTOR2I& aP ) const;
213 
214  bool Collide( const SEG& aSeg, int aClearance, int* aActual = nullptr ) const;
215 
216  ecoord SquaredDistance( const SEG& aSeg ) const;
217 
224  int Distance( const SEG& aSeg ) const
225  {
226  return sqrt( SquaredDistance( aSeg ) );
227  }
228 
229  ecoord SquaredDistance( const VECTOR2I& aP ) const
230  {
231  return ( NearestPoint( aP ) - aP ).SquaredEuclideanNorm();
232  }
233 
240  int Distance( const VECTOR2I& aP ) const
241  {
242  return sqrt( SquaredDistance( aP ) );
243  }
244 
245  void CanonicalCoefs( ecoord& qA, ecoord& qB, ecoord& qC ) const
246  {
247  qA = ecoord{ A.y } - B.y;
248  qB = ecoord{ B.x } - A.x;
249  qC = -qA * A.x - qB * A.y;
250  }
251 
258  bool Collinear( const SEG& aSeg ) const
259  {
260  ecoord qa, qb, qc;
261  CanonicalCoefs( qa, qb, qc );
262 
263  ecoord d1 = std::abs( aSeg.A.x * qa + aSeg.A.y * qb + qc );
264  ecoord d2 = std::abs( aSeg.B.x * qa + aSeg.B.y * qb + qc );
265 
266  return ( d1 <= 1 && d2 <= 1 );
267  }
268 
269  bool ApproxCollinear( const SEG& aSeg ) const
270  {
271  ecoord p, q, r;
272  CanonicalCoefs( p, q, r );
273 
274  ecoord dist1 = ( p * aSeg.A.x + q * aSeg.A.y + r ) / sqrt( p * p + q * q );
275  ecoord dist2 = ( p * aSeg.B.x + q * aSeg.B.y + r ) / sqrt( p * p + q * q );
276 
277  return std::abs( dist1 ) <= 1 && std::abs( dist2 ) <= 1;
278  }
279 
280  bool ApproxParallel ( const SEG& aSeg ) const
281  {
282  ecoord p, q, r;
283  CanonicalCoefs( p, q, r );
284 
285  ecoord dist1 = ( p * aSeg.A.x + q * aSeg.A.y + r ) / sqrt( p * p + q * q );
286  ecoord dist2 = ( p * aSeg.B.x + q * aSeg.B.y + r ) / sqrt( p * p + q * q );
287 
288  return std::abs( dist1 - dist2 ) <= 1;
289  }
290 
291  bool ApproxPerpendicular( const SEG& aSeg ) const
292  {
293  SEG perp = PerpendicularSeg( A );
294 
295  return aSeg.ApproxParallel( perp );
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 
314  if( aSeg.Contains( A ) || aSeg.Contains( B ) )
315  return true;
316 
317  return false;
318  }
319 
320 
321  bool Contains( const SEG& aSeg ) const
322  {
323  if( aSeg.A == aSeg.B ) // single point corner case
324  return Contains( aSeg.A );
325 
326  if( !Collinear( aSeg ) )
327  return false;
328 
329  if( Contains( aSeg.A ) && Contains( aSeg.B ) )
330  return true;
331 
332  return false;
333  }
334 
340  int Length() const
341  {
342  return ( A - B ).EuclideanNorm();
343  }
344 
346  {
347  return ( A - B ).SquaredEuclideanNorm();
348  }
349 
350  ecoord TCoef( const VECTOR2I& aP ) const;
351 
358  int Index() const
359  {
360  return m_index;
361  }
362 
363  bool Contains( const VECTOR2I& aP ) const;
364 
365  void Reverse()
366  {
367  std::swap( A, B );
368  }
369 
370  SEG Reversed() const
371  {
372  return SEG( B, A );
373  }
374 
376  VECTOR2I Center() const
377  {
378  return A + ( B - A ) / 2;
379  }
380 
381 private:
382  bool ccw( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I &aC ) const;
383 
384 private:
386  int m_index;
387 };
388 
389 inline VECTOR2I SEG::LineProject( const VECTOR2I& aP ) const
390 {
391  VECTOR2I d = B - A;
392  ecoord l_squared = d.Dot( d );
393 
394  if( l_squared == 0 )
395  return A;
396 
397  ecoord t = d.Dot( aP - A );
398 
399  int xp = rescale( t, ecoord{ d.x }, l_squared );
400  int yp = rescale( t, ecoord{ d.y }, l_squared );
401 
402  return A + VECTOR2I( xp, yp );
403 }
404 
405 inline int SEG::LineDistance( const VECTOR2I& aP, bool aDetermineSide ) const
406 {
407  ecoord p = ecoord{ A.y } - B.y;
408  ecoord q = ecoord{ B.x } - A.x;
409  ecoord r = -p * A.x - q * A.y;
410 
411  ecoord dist = ( p * aP.x + q * aP.y + r ) / sqrt( p * p + q * q );
412 
413  return aDetermineSide ? dist : std::abs( dist );
414 }
415 
416 inline SEG::ecoord SEG::TCoef( const VECTOR2I& aP ) const
417 {
418  VECTOR2I d = B - A;
419  return d.Dot( aP - A);
420 }
421 
422 inline const VECTOR2I SEG::NearestPoint( const VECTOR2I& aP ) const
423 {
424  VECTOR2I d = B - A;
425  ecoord l_squared = d.Dot( d );
426 
427  if( l_squared == 0 )
428  return A;
429 
430  ecoord t = d.Dot( aP - A );
431 
432  if( t < 0 )
433  return A;
434  else if( t > l_squared )
435  return B;
436 
437  int xp = rescale( t, (ecoord)d.x, l_squared );
438  int yp = rescale( t, (ecoord)d.y, l_squared );
439 
440  return A + VECTOR2I( xp, yp );
441 }
442 
443 inline std::ostream& operator<<( std::ostream& aStream, const SEG& aSeg )
444 {
445  aStream << "[ " << aSeg.A << " - " << aSeg.B << " ]";
446 
447  return aStream;
448 }
449 
450 #endif // __SEG_H
int Length() const
Return the length (this).
Definition: seg.h:340
VECTOR2_TRAITS< T >::extended_type extended_type
Definition: vector2d.h:76
int Index() const
Return the index of this segment in its parent shape (applicable only to non-local segments).
Definition: seg.h:358
bool Overlaps(const SEG &aSeg) const
Definition: seg.h:298
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.h:224
void CanonicalCoefs(ecoord &qA, ecoord &qB, ecoord &qC) const
Definition: seg.h:245
ecoord SquaredLength() const
Definition: seg.h:345
bool ApproxPerpendicular(const SEG &aSeg) const
Definition: seg.h:291
SEG PerpendicularSeg(const VECTOR2I &aP) const
Compute a segment perpendicular to this one, passing through point aP.
Definition: seg.cpp:134
bool ccw(const VECTOR2I &aA, const VECTOR2I &aB, const VECTOR2I &aC) const
Definition: seg.cpp:152
SEG()
Create an empty (0, 0) segment.
Definition: seg.h:55
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Compute intersection point of segment (this) with segment aSeg.
Definition: seg.cpp:105
bool Collide(const SEG &aSeg, int aClearance, int *aActual=nullptr) const
Definition: seg.cpp:158
std::ostream & operator<<(std::ostream &aStream, const SEG &aSeg)
Definition: seg.h:443
VECTOR2I::extended_type ecoord
Definition: seg.h:44
bool operator!=(const SEG &aSeg) const
Definition: seg.h:118
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:38
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
Definition: seg.h:193
int LineDistance(const VECTOR2I &aP, bool aDetermineSide=false) const
Return the closest Euclidean distance between point aP and the line defined by the ends of segment (t...
Definition: seg.h:405
VECTOR2I Center() const
Definition: seg.h:376
friend std::ostream & operator<<(std::ostream &aStream, const SEG &aSeg)
Definition: seg.h:443
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
static SEG::ecoord Square(int a)
Definition: seg.h:123
SEG ParallelSeg(const VECTOR2I &aP) const
Compute a segment parallel to this one, passing through point aP.
Definition: seg.cpp:143
SEG & operator=(const SEG &aSeg)
Definition: seg.h:104
VECTOR2I LineProject(const VECTOR2I &aP) const
Compute the perpendicular projection point of aP on a line passing through ends of the segment.
Definition: seg.h:389
ecoord TCoef(const VECTOR2I &aP) const
Definition: seg.h:416
OPT< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:39
bool ApproxParallel(const SEG &aSeg) const
Definition: seg.h:280
VECTOR2I::extended_type ecoord
SEG(const VECTOR2I &aA, const VECTOR2I &aB)
Create a segment between (aA) and (aB).
Definition: seg.h:73
SEG(int aX1, int aY1, int aX2, int aY2)
Create a segment between (aX1, aY1) and (aX2, aY2).
Definition: seg.h:63
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
Definition: seg.h:422
bool ApproxCollinear(const SEG &aSeg) const
Definition: seg.h:269
SEG(const SEG &aSeg)
Copy constructor.
Definition: seg.h:97
int Distance(const VECTOR2I &aP) const
Compute minimum Euclidean distance to point aP.
Definition: seg.h:240
SEG Reversed() const
Returns the center point of the line.
Definition: seg.h:370
bool Collinear(const SEG &aSeg) const
Check if segment aSeg lies on the same line as (this).
Definition: seg.h:258
Definition: seg.h:41
void Reverse()
Definition: seg.h:365
bool operator==(const SEG &aSeg) const
Definition: seg.h:113
extended_type Dot(const VECTOR2< T > &aVector) const
Compute dot product of self with aVector.
Definition: vector2d.h:521
ecoord SquaredDistance(const VECTOR2I &aP) const
Definition: seg.h:229
VECTOR2I A
Definition: seg.h:49
int m_index
< index withing the parent shape (used when m_is_local == false)
Definition: seg.h:386
T rescale(T aNumerator, T aValue, T aDenominator)
Function rescale()
Definition: util.h:95
boost::optional< T > OPT
Definition: optional.h:7
SEG(const VECTOR2I &aA, const VECTOR2I &aB, int aIndex)
Create a segment between (aA) and (aB), referenced to a multi-segment shape.
Definition: seg.h:87
int Side(const VECTOR2I &aP) const
Determine on which side of directed line passing via segment ends point aP lies.
Definition: seg.h:143
bool Contains(const SEG &aSeg) const
Definition: seg.h:321
VECTOR2I B
Definition: seg.h:50