KiCad PCB EDA Suite
seg.cpp
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  * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors.
7  *
8  * This program is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU General Public License
10  * as published by the Free Software Foundation; either version 2
11  * of the License, or (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, you may find one here:
20  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
21  * or you may search the http://www.gnu.org website for the version 2 license,
22  * or you may write to the Free Software Foundation, Inc.,
23  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
24  */
25 
26 #include <algorithm> // for min
27 #include <geometry/seg.h>
28 #include <math/util.h> // for rescale
29 #include <math/vector2d.h> // for VECTOR2I, VECTOR2
30 #include <trigo.h> // for RAD2DEG
31 
32 template <typename T>
33 int sgn( T aVal )
34 {
35  return ( T( 0 ) < aVal ) - ( aVal < T( 0 ) );
36 }
37 
38 
39 SEG::ecoord SEG::SquaredDistance( const SEG& aSeg ) const
40 {
41  if( Intersects( aSeg ) )
42  return 0;
43 
44  const VECTOR2I pts[4] =
45  {
46  aSeg.NearestPoint( A ) - A,
47  aSeg.NearestPoint( B ) - B,
48  NearestPoint( aSeg.A ) - aSeg.A,
49  NearestPoint( aSeg.B ) - aSeg.B
50  };
51 
53 
54  for( int i = 0; i < 4; i++ )
55  m = std::min( m, pts[i].SquaredEuclideanNorm() );
56 
57  return m;
58 }
59 
60 
61 double SEG::AngleDegrees( const SEG& aOther ) const
62 {
63  VECTOR2I thisVec = A - B;
64  VECTOR2I otherVec = aOther.A - aOther.B;
65 
66  double thisVecAngle = NormalizeAngle180( RAD2DECIDEG( thisVec.Angle() ) );
67  double otherVecAngle = NormalizeAngle180( RAD2DECIDEG( otherVec.Angle() ) );
68  double angleDegrees = std::abs( NormalizeAngle180( thisVecAngle - otherVecAngle ) ) / 10.0;
69 
70  return std::min( 180.0 - angleDegrees, angleDegrees );
71 }
72 
73 
74 const VECTOR2I SEG::NearestPoint( const SEG& aSeg ) const
75 {
76  if( OPT_VECTOR2I p = Intersect( aSeg ) )
77  return *p;
78 
79  const VECTOR2I pts_origin[4] =
80  {
81  aSeg.NearestPoint( A ),
82  aSeg.NearestPoint( B ),
83  NearestPoint( aSeg.A ),
84  NearestPoint( aSeg.B )
85  };
86 
87 
88  const VECTOR2I* pts_out[4] =
89  {
90  &A,
91  &B,
92  &pts_origin[2],
93  &pts_origin[3]
94  };
95 
96  const ecoord pts_dist[4] =
97  {
98  ( pts_origin[0] - A ).SquaredEuclideanNorm(),
99  ( pts_origin[1] - B ).SquaredEuclideanNorm(),
100  ( pts_origin[2] - aSeg.A ).SquaredEuclideanNorm(),
101  ( pts_origin[3] - aSeg.B ).SquaredEuclideanNorm()
102  };
103 
104  int min_i = 0;
105 
106  for( int i = 0; i < 4; i++ )
107  {
108  if( pts_dist[i] < pts_dist[min_i] )
109  min_i = i;
110  }
111 
112  return *pts_out[min_i];
113 }
114 
115 
116 bool SEG::intersects( const SEG& aSeg, bool aIgnoreEndpoints, bool aLines, VECTOR2I* aPt ) const
117 {
118  const VECTOR2I e( B - A );
119  const VECTOR2I f( aSeg.B - aSeg.A );
120  const VECTOR2I ac( aSeg.A - A );
121 
122  ecoord d = f.Cross( e );
123  ecoord p = f.Cross( ac );
124  ecoord q = e.Cross( ac );
125 
126  if( d == 0 )
127  return false;
128 
129  if( !aLines && d > 0 && ( q < 0 || q > d || p < 0 || p > d ) )
130  return false;
131 
132  if( !aLines && d < 0 && ( q < d || p < d || p > 0 || q > 0 ) )
133  return false;
134 
135  if( !aLines && aIgnoreEndpoints && ( q == 0 || q == d ) && ( p == 0 || p == d ) )
136  return false;
137 
138  if( aPt )
139  {
140  *aPt = VECTOR2I( aSeg.A.x + rescale( q, (ecoord) f.x, d ),
141  aSeg.A.y + rescale( q, (ecoord) f.y, d ) );
142  }
143 
144  return true;
145 }
146 
147 
148 bool SEG::Intersects( const SEG& aSeg ) const
149 {
150  return intersects( aSeg );
151 }
152 
153 
154 OPT_VECTOR2I SEG::Intersect( const SEG& aSeg, bool aIgnoreEndpoints, bool aLines ) const
155 {
156  VECTOR2I ip;
157 
158  if( intersects( aSeg, aIgnoreEndpoints, aLines, &ip ) )
159  return ip;
160  else
161  return OPT_VECTOR2I();
162 }
163 
164 
166 {
167  VECTOR2I slope( B - A );
168  VECTOR2I endPoint = slope.Perpendicular() + aP;
169 
170  return SEG( aP, endPoint );
171 }
172 
173 
174 SEG SEG::ParallelSeg( const VECTOR2I& aP ) const
175 {
176  VECTOR2I slope( B - A );
177  VECTOR2I endPoint = slope + aP;
178 
179  return SEG( aP, endPoint );
180 }
181 
182 
183 bool SEG::ccw( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I& aC ) const
184 {
185  return (ecoord) ( aC.y - aA.y ) * ( aB.x - aA.x ) > (ecoord) ( aB.y - aA.y ) * ( aC.x - aA.x );
186 }
187 
188 
189 bool SEG::Collide( const SEG& aSeg, int aClearance, int* aActual ) const
190 {
191  // check for intersection
192  // fixme: move to a method
193  if( ccw( A, aSeg.A, aSeg.B ) != ccw( B, aSeg.A, aSeg.B ) &&
194  ccw( A, B, aSeg.A ) != ccw( A, B, aSeg.B ) )
195  {
196  if( aActual )
197  *aActual = 0;
198 
199  return true;
200  }
201 
202  ecoord dist_sq = VECTOR2I::ECOORD_MAX;
203 
204  dist_sq = std::min( dist_sq, SquaredDistance( aSeg.A ) );
205  dist_sq = std::min( dist_sq, SquaredDistance( aSeg.B ) );
206  dist_sq = std::min( dist_sq, aSeg.SquaredDistance( A ) );
207  dist_sq = std::min( dist_sq, aSeg.SquaredDistance( B ) );
208 
209  if( dist_sq == 0 || dist_sq < (ecoord) aClearance * aClearance )
210  {
211  if( aActual )
212  *aActual = sqrt( dist_sq );
213 
214  return true;
215  }
216 
217  return false;
218 }
219 
220 
221 bool SEG::Contains( const VECTOR2I& aP ) const
222 {
223  return Distance( aP ) <= 1;
224 }
225 
226 
227 const VECTOR2I SEG::NearestPoint( const VECTOR2I& aP ) const
228 {
229  VECTOR2I d = B - A;
230  ecoord l_squared = d.Dot( d );
231 
232  if( l_squared == 0 )
233  return A;
234 
235  ecoord t = d.Dot( aP - A );
236 
237  if( t < 0 )
238  return A;
239  else if( t > l_squared )
240  return B;
241 
242  int xp = rescale( t, (ecoord) d.x, l_squared );
243  int yp = rescale( t, (ecoord) d.y, l_squared );
244 
245  return A + VECTOR2I( xp, yp );
246 }
247 
248 
249 const VECTOR2I SEG::ReflectPoint( const VECTOR2I& aP ) const
250 {
251  VECTOR2I d = B - A;
252  VECTOR2I::extended_type l_squared = d.Dot( d );
253  VECTOR2I::extended_type t = d.Dot( aP - A );
254  VECTOR2I c;
255 
256  if( !l_squared )
257  c = aP;
258  else
259  {
260  c.x = A.x + rescale( t, static_cast<VECTOR2I::extended_type>( d.x ), l_squared );
261  c.y = A.y + rescale( t, static_cast<VECTOR2I::extended_type>( d.y ), l_squared );
262  }
263 
264  return 2 * c - aP;
265 }
266 
267 
269 {
270  VECTOR2I d = B - A;
271  ecoord l_squared = d.Dot( d );
272 
273  if( l_squared == 0 )
274  return A;
275 
276  ecoord t = d.Dot( aP - A );
277 
278  int xp = rescale( t, ecoord{ d.x }, l_squared );
279  int yp = rescale( t, ecoord{ d.y }, l_squared );
280 
281  return A + VECTOR2I( xp, yp );
282 }
283 
284 
285 int SEG::Distance( const SEG& aSeg ) const
286 {
287  return KiROUND( sqrt( SquaredDistance( aSeg ) ) );
288 }
289 
290 
291 int SEG::Distance( const VECTOR2I& aP ) const
292 {
293  return KiROUND( sqrt( SquaredDistance( aP ) ) );
294 }
295 
296 
297 int SEG::LineDistance( const VECTOR2I& aP, bool aDetermineSide ) const
298 {
299  ecoord p = ecoord{ A.y } - B.y;
300  ecoord q = ecoord{ B.x } - A.x;
301  ecoord r = -p * A.x - q * A.y;
302 
303  ecoord dist = KiROUND( ( p * aP.x + q * aP.y + r ) / sqrt( p * p + q * q ) );
304 
305  return aDetermineSide ? dist : std::abs( dist );
306 }
307 
VECTOR2_TRAITS< T >::extended_type extended_type
Definition: vector2d.h:76
extended_type Cross(const VECTOR2< T > &aVector) const
Compute cross product of self with aVector.
Definition: vector2d.h:513
bool Intersects(const SEG &aSeg) const
Definition: seg.cpp:148
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.cpp:285
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
VECTOR2< T > Perpendicular() const
Compute the perpendicular vector.
Definition: vector2d.h:314
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
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
double RAD2DECIDEG(double rad)
Definition: trigo.h:234
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:39
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
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
SEG ParallelSeg(const VECTOR2I &aP) const
Compute a segment parallel to this one, passing through point aP.
Definition: seg.cpp:174
T NormalizeAngle180(T Angle)
Normalize angle to be in the -180.0 .. 180.0 range.
Definition: trigo.h:387
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:79
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
OPT< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:38
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
Definition: seg.cpp:227
int sgn(T aVal)
Definition: seg.cpp:33
double Angle() const
Compute the angle of the vector.
Definition: vector2d.h:307
Definition: seg.h:40
extended_type Dot(const VECTOR2< T > &aVector) const
Compute dot product of self with aVector.
Definition: vector2d.h:521
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
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
Definition: util.h:98
constexpr ret_type KiROUND(fp_type v)
Round a floating point number to an integer using "round halfway cases away from zero".
Definition: util.h:73
double AngleDegrees(const SEG &aOther) const
Determine the smallest angle between two segments (result in degrees)
Definition: seg.cpp:61
bool Contains(const SEG &aSeg) const
Definition: seg.h:331
VECTOR2I B
Definition: seg.h:49