KiCad PCB EDA Suite
trigo.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) 2014 Jean-Pierre Charras, jp.charras at wanadoo.fr
5  * Copyright (C) 2014 KiCad Developers, see AUTHORS.txt for contributors.
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 
30 #include <fctsys.h>
31 #include <macros.h>
32 #include <trigo.h>
33 #include <common.h>
34 #include <math_for_graphics.h>
35 #include <geometry/seg.h>
36 
37 // Returns true if the point P is on the segment S.
38 // faster than TestSegmentHit() because P should be exactly on S
39 // therefore works fine only for H, V and 45 deg segm (suitable for wires in eeschema)
40 bool IsPointOnSegment( const wxPoint& aSegStart, const wxPoint& aSegEnd,
41  const wxPoint& aTestPoint )
42 {
43  wxPoint vectSeg = aSegEnd - aSegStart; // Vector from S1 to S2
44  wxPoint vectPoint = aTestPoint - aSegStart; // Vector from S1 to P
45 
46  // Use long long here to avoid overflow in calculations
47  if( (long long) vectSeg.x * vectPoint.y - (long long) vectSeg.y * vectPoint.x )
48  return false; /* Cross product non-zero, vectors not parallel */
49 
50  if( ( (long long) vectSeg.x * vectPoint.x + (long long) vectSeg.y * vectPoint.y ) <
51  ( (long long) vectPoint.x * vectPoint.x + (long long) vectPoint.y * vectPoint.y ) )
52  return false; /* Point not on segment */
53 
54  return true;
55 }
56 
57 
58 // Returns true if the segment 1 intersectd the segment 2.
59 bool SegmentIntersectsSegment( const wxPoint &a_p1_l1, const wxPoint &a_p2_l1,
60  const wxPoint &a_p1_l2, const wxPoint &a_p2_l2,
61  wxPoint* aIntersectionPoint )
62 {
63 
64  //We are forced to use 64bit ints because the internal units can oveflow 32bit ints when
65  // multiplied with each other, the alternative would be to scale the units down (i.e. divide
66  // by a fixed number).
67  long long dX_a, dY_a, dX_b, dY_b, dX_ab, dY_ab;
68  long long num_a, num_b, den;
69 
70  //Test for intersection within the bounds of both line segments using line equations of the
71  // form:
72  // x_k(u_k) = u_k * dX_k + x_k(0)
73  // y_k(u_k) = u_k * dY_k + y_k(0)
74  // with 0 <= u_k <= 1 and k = [ a, b ]
75 
76  dX_a = a_p2_l1.x - a_p1_l1.x;
77  dY_a = a_p2_l1.y - a_p1_l1.y;
78  dX_b = a_p2_l2.x - a_p1_l2.x;
79  dY_b = a_p2_l2.y - a_p1_l2.y;
80  dX_ab = a_p1_l2.x - a_p1_l1.x;
81  dY_ab = a_p1_l2.y - a_p1_l1.y;
82 
83  den = dY_a * dX_b - dY_b * dX_a ;
84 
85  //Check if lines are parallel
86  if( den == 0 )
87  return false;
88 
89  num_a = dY_ab * dX_b - dY_b * dX_ab;
90  num_b = dY_ab * dX_a - dY_a * dX_ab;
91 
92  // Only compute the intersection point if requested
93  if( aIntersectionPoint )
94  {
95  *aIntersectionPoint = a_p1_l1;
96  aIntersectionPoint->x += KiROUND( dX_a * ( double )num_a / ( double )den );
97  aIntersectionPoint->y += KiROUND( dY_a * ( double )num_b / ( double )den );
98  }
99 
100  if( den < 0 )
101  {
102  den = -den;
103  num_a = -num_a;
104  num_b = -num_b;
105  }
106 
107  //Test sign( u_a ) and return false if negative
108  if( num_a < 0 )
109  return false;
110 
111  //Test sign( u_b ) and return false if negative
112  if( num_b < 0 )
113  return false;
114 
115  //Test to ensure (u_a <= 1)
116  if( num_a > den )
117  return false;
118 
119  //Test to ensure (u_b <= 1)
120  if( num_b > den )
121  return false;
122 
123  return true;
124 }
125 
126 
127 bool TestSegmentHit( const wxPoint &aRefPoint, wxPoint aStart, wxPoint aEnd, int aDist )
128 {
129  int xmin = aStart.x;
130  int xmax = aEnd.x;
131  int ymin = aStart.y;
132  int ymax = aEnd.y;
133  wxPoint delta = aStart - aRefPoint;
134 
135  if( xmax < xmin )
136  std::swap( xmax, xmin );
137 
138  if( ymax < ymin )
139  std::swap( ymax, ymin );
140 
141  // First, check if we are outside of the bounding box
142  if( ( ymin - aRefPoint.y > aDist ) || ( aRefPoint.y - ymax > aDist ) )
143  return false;
144 
145  if( ( xmin - aRefPoint.x > aDist ) || ( aRefPoint.x - xmax > aDist ) )
146  return false;
147 
148  // Next, eliminate easy cases
149  if( aStart.x == aEnd.x && aRefPoint.y > ymin && aRefPoint.y < ymax )
150  return std::abs( delta.x ) <= aDist;
151 
152  if( aStart.y == aEnd.y && aRefPoint.x > xmin && aRefPoint.x < xmax )
153  return std::abs( delta.y ) <= aDist;
154 
155  SEG segment( aStart, aEnd );
156  return segment.PointCloserThan( aRefPoint, aDist + 1 );
157 }
158 
159 
160 double ArcTangente( int dy, int dx )
161 {
162 
163  /* gcc is surprisingly smart in optimizing these conditions in
164  a tree! */
165 
166  if( dx == 0 && dy == 0 )
167  return 0;
168 
169  if( dy == 0 )
170  {
171  if( dx >= 0 )
172  return 0;
173  else
174  return -1800;
175  }
176 
177  if( dx == 0 )
178  {
179  if( dy >= 0 )
180  return 900;
181  else
182  return -900;
183  }
184 
185  if( dx == dy )
186  {
187  if( dx >= 0 )
188  return 450;
189  else
190  return -1800 + 450;
191  }
192 
193  if( dx == -dy )
194  {
195  if( dx >= 0 )
196  return -450;
197  else
198  return 1800 - 450;
199  }
200 
201  // Of course dy and dx are treated as double
202  return RAD2DECIDEG( atan2( (double) dy, (double) dx ) );
203 }
204 
205 
206 void RotatePoint( int* pX, int* pY, double angle )
207 {
208  int tmp;
209 
211 
212  // Cheap and dirty optimizations for 0, 90, 180, and 270 degrees.
213  if( angle == 0 )
214  return;
215 
216  if( angle == 900 ) /* sin = 1, cos = 0 */
217  {
218  tmp = *pX;
219  *pX = *pY;
220  *pY = -tmp;
221  }
222  else if( angle == 1800 ) /* sin = 0, cos = -1 */
223  {
224  *pX = -*pX;
225  *pY = -*pY;
226  }
227  else if( angle == 2700 ) /* sin = -1, cos = 0 */
228  {
229  tmp = *pX;
230  *pX = -*pY;
231  *pY = tmp;
232  }
233  else
234  {
235  double fangle = DECIDEG2RAD( angle );
236  double sinus = sin( fangle );
237  double cosinus = cos( fangle );
238  double fpx = (*pY * sinus ) + (*pX * cosinus );
239  double fpy = (*pY * cosinus ) - (*pX * sinus );
240  *pX = KiROUND( fpx );
241  *pY = KiROUND( fpy );
242  }
243 }
244 
245 
246 void RotatePoint( int* pX, int* pY, int cx, int cy, double angle )
247 {
248  int ox, oy;
249 
250  ox = *pX - cx;
251  oy = *pY - cy;
252 
253  RotatePoint( &ox, &oy, angle );
254 
255  *pX = ox + cx;
256  *pY = oy + cy;
257 }
258 
259 
260 void RotatePoint( wxPoint* point, const wxPoint& centre, double angle )
261 {
262  int ox, oy;
263 
264  ox = point->x - centre.x;
265  oy = point->y - centre.y;
266 
267  RotatePoint( &ox, &oy, angle );
268  point->x = ox + centre.x;
269  point->y = oy + centre.y;
270 }
271 
272 void RotatePoint( VECTOR2I& point, const VECTOR2I& centre, double angle )
273 {
274  wxPoint c( centre.x, centre.y );
275  wxPoint p( point.x, point.y );
276 
277  RotatePoint(&p, c, angle);
278 
279  point.x = p.x;
280  point.y = p.y;
281 }
282 
283 
284 void RotatePoint( double* pX, double* pY, double cx, double cy, double angle )
285 {
286  double ox, oy;
287 
288  ox = *pX - cx;
289  oy = *pY - cy;
290 
291  RotatePoint( &ox, &oy, angle );
292 
293  *pX = ox + cx;
294  *pY = oy + cy;
295 }
296 
297 
298 void RotatePoint( double* pX, double* pY, double angle )
299 {
300  double tmp;
301 
303 
304  // Cheap and dirty optimizations for 0, 90, 180, and 270 degrees.
305  if( angle == 0 )
306  return;
307 
308  if( angle == 900 ) /* sin = 1, cos = 0 */
309  {
310  tmp = *pX;
311  *pX = *pY;
312  *pY = -tmp;
313  }
314  else if( angle == 1800 ) /* sin = 0, cos = -1 */
315  {
316  *pX = -*pX;
317  *pY = -*pY;
318  }
319  else if( angle == 2700 ) /* sin = -1, cos = 0 */
320  {
321  tmp = *pX;
322  *pX = -*pY;
323  *pY = tmp;
324  }
325  else
326  {
327  double fangle = DECIDEG2RAD( angle );
328  double sinus = sin( fangle );
329  double cosinus = cos( fangle );
330 
331  double fpx = (*pY * sinus ) + (*pX * cosinus );
332  double fpy = (*pY * cosinus ) - (*pX * sinus );
333  *pX = fpx;
334  *pY = fpy;
335  }
336 }
337 
338 
339 const VECTOR2I GetArcCenter( const VECTOR2I& aStart, const VECTOR2I& aMid, const VECTOR2I& aEnd )
340 {
341  VECTOR2I center;
342  double yDelta_21 = aMid.y - aStart.y;
343  double xDelta_21 = aMid.x - aStart.x;
344  double yDelta_32 = aEnd.y - aMid.y;
345  double xDelta_32 = aEnd.x - aMid.x;
346 
347  // This is a special case for aMid as the half-way point when aSlope = 0 and bSlope = inf
348  // or the other way around. In that case, the center lies in a straight line between
349  // aStart and aEnd
350  if( ( ( xDelta_21 == 0.0 ) && ( yDelta_32 == 0.0 ) ) ||
351  ( ( yDelta_21 == 0.0 ) && ( xDelta_32 == 0.0 ) ) )
352  {
353  center.x = KiROUND( ( aStart.x + aEnd.x ) / 2.0 );
354  center.y = KiROUND( ( aStart.y + aEnd.y ) / 2.0 );
355  return center;
356  }
357 
358  // Prevent div=0 errors
359  if( xDelta_21 == 0.0 )
360  xDelta_21 = std::numeric_limits<double>::epsilon();
361 
362  if( xDelta_32 == 0.0 )
363  xDelta_32 = -std::numeric_limits<double>::epsilon();
364 
365  double aSlope = yDelta_21 / xDelta_21;
366  double bSlope = yDelta_32 / xDelta_32;
367 
368  // If the points are colinear, the center is at infinity, so offset
369  // the slope by a minimal amount
370  // Warning: This will induce a small error in the center location
371  if( yDelta_32 * xDelta_21 == yDelta_21 * xDelta_32 )
372  {
373  aSlope += std::numeric_limits<double>::epsilon();
374  bSlope -= std::numeric_limits<double>::epsilon();
375  }
376 
377  if( aSlope == 0.0 )
378  aSlope = std::numeric_limits<double>::epsilon();
379 
380  if( bSlope == 0.0 )
381  bSlope = -std::numeric_limits<double>::epsilon();
382 
383 
384  double result = ( aSlope * bSlope * ( aStart.y - aEnd.y ) +
385  bSlope * ( aStart.x + aMid.x ) -
386  aSlope * ( aMid.x + aEnd.x ) ) / ( 2 * ( bSlope - aSlope ) );
387 
388  center.x = KiROUND( Clamp<double>( double( std::numeric_limits<int>::min() / 2 ),
389  result,
390  double( std::numeric_limits<int>::max() / 2 ) ) );
391 
392  result = ( ( ( aStart.x + aMid.x ) / 2.0 - center.x ) / aSlope +
393  ( aStart.y + aMid.y ) / 2.0 );
394 
395  center.y = KiROUND( Clamp<double>( double( std::numeric_limits<int>::min() / 2 ),
396  result,
397  double( std::numeric_limits<int>::max() / 2 ) ) );
398 
399  return center;
400 }
bool IsPointOnSegment(const wxPoint &aSegStart, const wxPoint &aSegEnd, const wxPoint &aTestPoint)
Function IsPointOnSegment.
Definition: trigo.cpp:40
double RAD2DECIDEG(double rad)
Definition: trigo.h:215
void RotatePoint(int *pX, int *pY, double angle)
Definition: trigo.cpp:206
void NORMALIZE_ANGLE_POS(T &Angle)
Definition: trigo.h:252
#define abs(a)
Definition: auxiliary.h:84
This file contains miscellaneous commonly used macros and functions.
bool PointCloserThan(const VECTOR2I &aP, int aDist) const
Definition: seg.cpp:34
double ArcTangente(int dy, int dx)
Definition: trigo.cpp:160
Definition: seg.h:36
#define max(a, b)
Definition: auxiliary.h:86
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
double DECIDEG2RAD(double deg)
Definition: trigo.h:214
bool SegmentIntersectsSegment(const wxPoint &a_p1_l1, const wxPoint &a_p2_l1, const wxPoint &a_p1_l2, const wxPoint &a_p2_l2, wxPoint *aIntersectionPoint)
Function SegmentIntersectsSegment.
Definition: trigo.cpp:59
The common library.
bool TestSegmentHit(const wxPoint &aRefPoint, wxPoint aStart, wxPoint aEnd, int aDist)
Function TestSegmentHit test for hit on line segment i.e.
Definition: trigo.cpp:127
const VECTOR2I GetArcCenter(const VECTOR2I &aStart, const VECTOR2I &aMid, const VECTOR2I &aEnd)
Determine the center of an arc/circle, given three points on its circumference.
Definition: trigo.cpp:339
constexpr ret_type KiROUND(fp_type v)
Round a floating point number to an integer using "round halfway cases away from zero".
Definition: common.h:114
#define min(a, b)
Definition: auxiliary.h:85