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/vector2d.h>
37 
39 
40 class SEG
41 {
42 public:
44  friend inline std::ostream& operator<<( std::ostream& aStream, const SEG& aSeg );
45 
46  /* Start and the of the segment. Public, to make access simpler.
47  */
50 
54  SEG()
55  {
56  m_index = -1;
57  }
58 
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 
72  SEG( const VECTOR2I& aA, const VECTOR2I& aB ) :
73  A( aA ),
74  B( aB )
75  {
76  m_index = -1;
77  }
78 
86  SEG( const VECTOR2I& aA, const VECTOR2I& aB, int aIndex ) :
87  A( aA ),
88  B( aB )
89  {
90  m_index = aIndex;
91  }
92 
96  SEG( const SEG& aSeg ) :
97  A( aSeg.A ),
98  B( aSeg.B ),
99  m_index( aSeg.m_index )
100  {
101  }
102 
103  SEG& operator=( const SEG& aSeg )
104  {
105  A = aSeg.A;
106  B = aSeg.B;
107  m_index = aSeg.m_index;
108 
109  return *this;
110  }
111 
112  bool operator==( const SEG& aSeg ) const
113  {
114  return (A == aSeg.A && B == aSeg.B) ;
115  }
116 
117  bool operator!=( const SEG& aSeg ) const
118  {
119  return (A != aSeg.A || B != aSeg.B);
120  }
121 
122  static SEG::ecoord Square( int a )
123  {
124  return ecoord( a ) * a;
125  }
126 
134  VECTOR2I LineProject( const VECTOR2I& aP ) const;
135 
142  int Side( const VECTOR2I& aP ) const
143  {
144  const ecoord det = ( B - A ).Cross( aP - A );
145 
146  return det < 0 ? -1 : ( det > 0 ? 1 : 0 );
147  }
148 
158  int LineDistance( const VECTOR2I& aP, bool aDetermineSide = false ) const;
159 
166  double AngleDegrees( const SEG& aOther ) const;
167 
173  const VECTOR2I NearestPoint( const VECTOR2I& aP ) const;
174 
180  const VECTOR2I NearestPoint( const SEG &aSeg ) const;
181 
187  const VECTOR2I ReflectPoint( const VECTOR2I& aP ) const;
188 
198  OPT_VECTOR2I Intersect( const SEG& aSeg, bool aIgnoreEndpoints = false,
199  bool aLines = false ) const;
200 
201  bool Intersects( const SEG& aSeg ) const;
202 
209  OPT_VECTOR2I IntersectLines( const SEG& aSeg ) const
210  {
211  return Intersect( aSeg, false, true );
212  }
213 
220  SEG PerpendicularSeg( const VECTOR2I& aP ) const;
221 
228  SEG ParallelSeg( const VECTOR2I& aP ) const;
229 
230  bool Collide( const SEG& aSeg, int aClearance, int* aActual = nullptr ) const;
231 
232  ecoord SquaredDistance( const SEG& aSeg ) const;
233 
240  int Distance( const SEG& aSeg ) const;
241 
242  ecoord SquaredDistance( const VECTOR2I& aP ) const
243  {
244  return ( NearestPoint( aP ) - aP ).SquaredEuclideanNorm();
245  }
246 
253  int Distance( const VECTOR2I& aP ) const;
254 
255  void CanonicalCoefs( ecoord& qA, ecoord& qB, ecoord& qC ) const
256  {
257  qA = ecoord{ A.y } - B.y;
258  qB = ecoord{ B.x } - A.x;
259  qC = -qA * A.x - qB * A.y;
260  }
261 
268  bool Collinear( const SEG& aSeg ) const
269  {
270  ecoord qa, qb, qc;
271  CanonicalCoefs( qa, qb, qc );
272 
273  ecoord d1 = std::abs( aSeg.A.x * qa + aSeg.A.y * qb + qc );
274  ecoord d2 = std::abs( aSeg.B.x * qa + aSeg.B.y * qb + qc );
275 
276  return ( d1 <= 1 && d2 <= 1 );
277  }
278 
279  bool ApproxCollinear( const SEG& aSeg ) const
280  {
281  ecoord p, q, r;
282  CanonicalCoefs( p, q, r );
283 
284  ecoord dist1 = ( p * aSeg.A.x + q * aSeg.A.y + r ) / sqrt( p * p + q * q );
285  ecoord dist2 = ( p * aSeg.B.x + q * aSeg.B.y + r ) / sqrt( p * p + q * q );
286 
287  return std::abs( dist1 ) <= 1 && std::abs( dist2 ) <= 1;
288  }
289 
290  bool ApproxParallel ( const SEG& aSeg ) const
291  {
292  ecoord p, q, r;
293  CanonicalCoefs( p, q, r );
294 
295  ecoord dist1 = ( p * aSeg.A.x + q * aSeg.A.y + r ) / sqrt( p * p + q * q );
296  ecoord dist2 = ( p * aSeg.B.x + q * aSeg.B.y + r ) / sqrt( p * p + q * q );
297 
298  return std::abs( dist1 - dist2 ) <= 1;
299  }
300 
301  bool ApproxPerpendicular( const SEG& aSeg ) const
302  {
303  SEG perp = PerpendicularSeg( A );
304 
305  return aSeg.ApproxParallel( perp );
306  }
307 
308  bool Overlaps( const SEG& aSeg ) const
309  {
310  if( aSeg.A == aSeg.B ) // single point corner case
311  {
312  if( A == aSeg.A || B == aSeg.A )
313  return false;
314 
315  return Contains( aSeg.A );
316  }
317 
318  if( !Collinear( aSeg ) )
319  return false;
320 
321  if( Contains( aSeg.A ) || Contains( aSeg.B ) )
322  return true;
323 
324  if( aSeg.Contains( A ) || aSeg.Contains( B ) )
325  return true;
326 
327  return false;
328  }
329 
330 
331  bool Contains( const SEG& aSeg ) const
332  {
333  if( aSeg.A == aSeg.B ) // single point corner case
334  return Contains( aSeg.A );
335 
336  if( !Collinear( aSeg ) )
337  return false;
338 
339  if( Contains( aSeg.A ) && Contains( aSeg.B ) )
340  return true;
341 
342  return false;
343  }
344 
350  int Length() const
351  {
352  return ( A - B ).EuclideanNorm();
353  }
354 
356  {
357  return ( A - B ).SquaredEuclideanNorm();
358  }
359 
360  ecoord TCoef( const VECTOR2I& aP ) const;
361 
368  int Index() const
369  {
370  return m_index;
371  }
372 
373  bool Contains( const VECTOR2I& aP ) const;
374 
375  void Reverse()
376  {
377  std::swap( A, B );
378  }
379 
380  SEG Reversed() const
381  {
382  return SEG( B, A );
383  }
384 
386  VECTOR2I Center() const
387  {
388  return A + ( B - A ) / 2;
389  }
390 
391 private:
392  bool ccw( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I &aC ) const;
393 
394  bool intersects( const SEG& aSeg, bool aIgnoreEndpoints = false, bool aLines = false,
395  VECTOR2I* aPt = nullptr ) const;
396 
397 private:
399  int m_index;
400 };
401 
402 inline SEG::ecoord SEG::TCoef( const VECTOR2I& aP ) const
403 {
404  VECTOR2I d = B - A;
405  return d.Dot( aP - A);
406 }
407 
408 inline std::ostream& operator<<( std::ostream& aStream, const SEG& aSeg )
409 {
410  aStream << "[ " << aSeg.A << " - " << aSeg.B << " ]";
411 
412  return aStream;
413 }
414 
415 #endif // __SEG_H
int Length() const
Return the length (this).
Definition: seg.h:350
VECTOR2_TRAITS< T >::extended_type extended_type
Definition: vector2d.h:76
bool Intersects(const SEG &aSeg) const
Definition: seg.cpp:148
int Index() const
Return the index of this segment in its parent shape (applicable only to non-local segments).
Definition: seg.h:368
bool Overlaps(const SEG &aSeg) const
Definition: seg.h:308
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.cpp:285
void CanonicalCoefs(ecoord &qA, ecoord &qB, ecoord &qC) const
Definition: seg.h:255
ecoord SquaredLength() const
Definition: seg.h:355
bool ApproxPerpendicular(const SEG &aSeg) const
Definition: seg.h:301
SEG PerpendicularSeg(const VECTOR2I &aP) const
Compute a segment perpendicular to this one, passing through point aP.
Definition: seg.cpp:165
bool ccw(const VECTOR2I &aA, const VECTOR2I &aB, const VECTOR2I &aC) const
Definition: seg.cpp:183
SEG()
Create an empty (0, 0) segment.
Definition: seg.h:54
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:154
bool Collide(const SEG &aSeg, int aClearance, int *aActual=nullptr) const
Definition: seg.cpp:189
std::ostream & operator<<(std::ostream &aStream, const SEG &aSeg)
Definition: seg.h:408
VECTOR2I::extended_type ecoord
Definition: seg.h:43
const VECTOR2I ReflectPoint(const VECTOR2I &aP) const
Reflect a point using this segment as axis.
Definition: seg.cpp:249
bool operator!=(const SEG &aSeg) const
Definition: seg.h:117
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:39
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
Definition: seg.h:209
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.cpp:297
VECTOR2I Center() const
Definition: seg.h:386
friend std::ostream & operator<<(std::ostream &aStream, const SEG &aSeg)
Definition: seg.h:408
static SEG::ecoord Square(int a)
Definition: seg.h:122
SEG ParallelSeg(const VECTOR2I &aP) const
Compute a segment parallel to this one, passing through point aP.
Definition: seg.cpp:174
SEG & operator=(const SEG &aSeg)
Definition: seg.h:103
VECTOR2I LineProject(const VECTOR2I &aP) const
Compute the perpendicular projection point of aP on a line passing through ends of the segment.
Definition: seg.cpp:268
ecoord TCoef(const VECTOR2I &aP) const
Definition: seg.h:402
OPT< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:38
bool ApproxParallel(const SEG &aSeg) const
Definition: seg.h:290
VECTOR2I::extended_type ecoord
SEG(const VECTOR2I &aA, const VECTOR2I &aB)
Create a segment between (aA) and (aB).
Definition: seg.h:72
SEG(int aX1, int aY1, int aX2, int aY2)
Create a segment between (aX1, aY1) and (aX2, aY2).
Definition: seg.h:62
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
Definition: seg.cpp:227
bool ApproxCollinear(const SEG &aSeg) const
Definition: seg.h:279
SEG(const SEG &aSeg)
Copy constructor.
Definition: seg.h:96
SEG Reversed() const
Returns the center point of the line.
Definition: seg.h:380
bool Collinear(const SEG &aSeg) const
Check if segment aSeg lies on the same line as (this).
Definition: seg.h:268
Definition: seg.h:40
void Reverse()
Definition: seg.h:375
bool operator==(const SEG &aSeg) const
Definition: seg.h:112
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:242
bool intersects(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false, VECTOR2I *aPt=nullptr) const
Definition: seg.cpp:116
VECTOR2I A
Definition: seg.h:48
int m_index
< index within the parent shape (used when m_is_local == false)
Definition: seg.h:399
boost::optional< T > OPT
Definition: optional.h:7
double AngleDegrees(const SEG &aOther) const
Determine the smallest angle between two segments (result in degrees)
Definition: seg.cpp:61
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:86
int Side(const VECTOR2I &aP) const
Determine on which side of directed line passing via segment ends point aP lies.
Definition: seg.h:142
bool Contains(const SEG &aSeg) const
Definition: seg.h:331
VECTOR2I B
Definition: seg.h:49