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 CHANGELOG.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 
36 // Returns true if the point P is on the segment S.
37 // faster than TestSegmentHit() because P should be exactly on S
38 // therefore works fine only for H, V and 45 deg segm (suitable for wires in eeschema)
39 bool IsPointOnSegment( const wxPoint& aSegStart, const wxPoint& aSegEnd,
40  const wxPoint& aTestPoint )
41 {
42  wxPoint vectSeg = aSegEnd - aSegStart; // Vector from S1 to S2
43  wxPoint vectPoint = aTestPoint - aSegStart; // Vector from S1 to P
44 
45  // Use long long here to avoid overflow in calculations
46  if( (long long) vectSeg.x * vectPoint.y - (long long) vectSeg.y * vectPoint.x )
47  return false; /* Cross product non-zero, vectors not parallel */
48 
49  if( ( (long long) vectSeg.x * vectPoint.x + (long long) vectSeg.y * vectPoint.y ) <
50  ( (long long) vectPoint.x * vectPoint.x + (long long) vectPoint.y * vectPoint.y ) )
51  return false; /* Point not on segment */
52 
53  return true;
54 }
55 
56 
57 // Returns true if the segment 1 intersectd the segment 2.
58 bool SegmentIntersectsSegment( const wxPoint &a_p1_l1, const wxPoint &a_p2_l1,
59  const wxPoint &a_p1_l2, const wxPoint &a_p2_l2 )
60 {
61 
62  //We are forced to use 64bit ints because the internal units can oveflow 32bit ints when
63  // multiplied with each other, the alternative would be to scale the units down (i.e. divide
64  // by a fixed number).
65  long long dX_a, dY_a, dX_b, dY_b, dX_ab, dY_ab;
66  long long num_a, num_b, den;
67 
68  //Test for intersection within the bounds of both line segments using line equations of the
69  // form:
70  // x_k(u_k) = u_k * dX_k + x_k(0)
71  // y_k(u_k) = u_k * dY_k + y_k(0)
72  // with 0 <= u_k <= 1 and k = [ a, b ]
73 
74  dX_a = a_p2_l1.x - a_p1_l1.x;
75  dY_a = a_p2_l1.y - a_p1_l1.y;
76  dX_b = a_p2_l2.x - a_p1_l2.x;
77  dY_b = a_p2_l2.y - a_p1_l2.y;
78  dX_ab = a_p1_l2.x - a_p1_l1.x;
79  dY_ab = a_p1_l2.y - a_p1_l1.y;
80 
81  den = dY_a * dX_b - dY_b * dX_a ;
82 
83  //Check if lines are parallel
84  if( den == 0 )
85  return false;
86 
87  num_a = dY_ab * dX_b - dY_b * dX_ab;
88  num_b = dY_ab * dX_a - dY_a * dX_ab;
89 
90  //We wont calculate directly the u_k of the intersection point to avoid floating point
91  // division but they could be calculated with:
92  // u_a = (float) num_a / (float) den;
93  // u_b = (float) num_b / (float) den;
94 
95  if( den < 0 )
96  {
97  den = -den;
98  num_a = -num_a;
99  num_b = -num_b;
100  }
101 
102  //Test sign( u_a ) and return false if negative
103  if( num_a < 0 )
104  return false;
105 
106  //Test sign( u_b ) and return false if negative
107  if( num_b < 0 )
108  return false;
109 
110  //Test to ensure (u_a <= 1)
111  if( num_a > den )
112  return false;
113 
114  //Test to ensure (u_b <= 1)
115  if( num_b > den )
116  return false;
117 
118  return true;
119 }
120 
121 
122 /* Function TestSegmentHit
123  * test for hit on line segment
124  * i.e. a reference point is within a given distance from segment
125  * aRefPoint = reference point to test
126  * aStart, aEnd are coordinates of end points segment
127  * aDist = maximum distance for hit
128  * Note: for calculation time reasons, the distance between the ref point
129  * and the segment is not always exactly calculated
130  * (we only know if the actual dist is < aDist, not exactly know this dist.
131  * Because many times we have horizontal or vertical segments,
132  * a special calcultaion is made for them
133  * Note: sometimes we need to calculate the distande between 2 points
134  * A square root should be calculated.
135  * However, because we just compare 2 distnaces, to avoid calculating square root,
136  * the square of distances are compared.
137 */
138 static inline double square( int x ) // helper function to calculate x*x
139 {
140  return (double) x * x;
141 }
142 bool TestSegmentHit( const wxPoint &aRefPoint, wxPoint aStart,
143  wxPoint aEnd, int aDist )
144 {
145  // test for vertical or horizontal segment
146  if( aEnd.x == aStart.x )
147  {
148  // vertical segment
149  int ll = abs( aRefPoint.x - aStart.x );
150 
151  if( ll > aDist )
152  return false;
153 
154  // To have only one case to examine, ensure aEnd.y > aStart.y
155  if( aEnd.y < aStart.y )
156  std::swap( aStart.y, aEnd.y );
157 
158  if( aRefPoint.y <= aEnd.y && aRefPoint.y >= aStart.y )
159  return true;
160 
161  // there is a special case: x,y near an end point (distance < dist )
162  // the distance should be carefully calculated
163  if( (aStart.y - aRefPoint.y) < aDist )
164  {
165  double dd = square( aRefPoint.x - aStart.x) +
166  square( aRefPoint.y - aStart.y );
167  if( dd <= square( aDist ) )
168  return true;
169  }
170 
171  if( (aRefPoint.y - aEnd.y) < aDist )
172  {
173  double dd = square( aRefPoint.x - aEnd.x ) +
174  square( aRefPoint.y - aEnd.y );
175  if( dd <= square( aDist ) )
176  return true;
177  }
178  }
179  else if( aEnd.y == aStart.y )
180  {
181  // horizontal segment
182  int ll = abs( aRefPoint.y - aStart.y );
183 
184  if( ll > aDist )
185  return false;
186 
187  // To have only one case to examine, ensure xf > xi
188  if( aEnd.x < aStart.x )
189  std::swap( aStart.x, aEnd.x );
190 
191  if( aRefPoint.x <= aEnd.x && aRefPoint.x >= aStart.x )
192  return true;
193 
194  // there is a special case: x,y near an end point (distance < dist )
195  // the distance should be carefully calculated
196  if( (aStart.x - aRefPoint.x) <= aDist )
197  {
198  double dd = square( aRefPoint.x - aStart.x ) +
199  square( aRefPoint.y - aStart.y );
200  if( dd <= square( aDist ) )
201  return true;
202  }
203 
204  if( (aRefPoint.x - aEnd.x) <= aDist )
205  {
206  double dd = square( aRefPoint.x - aEnd.x ) +
207  square( aRefPoint.y - aEnd.y );
208  if( dd <= square( aDist ) )
209  return true;
210  }
211  }
212  else
213  {
214  // oblique segment:
215  // First, we need to calculate the distance between the point
216  // and the line defined by aStart and aEnd
217  // this dist should be < dist
218  //
219  // find a,slope such that aStart and aEnd lie on y = a + slope*x
220  double slope = (double) (aEnd.y - aStart.y) / (aEnd.x - aStart.x);
221  double a = (double) aStart.y - slope * aStart.x;
222  // find c,orthoslope such that (x,y) lies on y = c + orthoslope*x,
223  // where orthoslope=(-1/slope)
224  // to calculate xp, yp = near point from aRefPoint
225  // which is on the line defined by aStart, aEnd
226  double orthoslope = -1.0 / slope;
227  double c = (double) aRefPoint.y - orthoslope * aRefPoint.x;
228  // find nearest point to (x,y) on line defined by aStart, aEnd
229  double xp = (a - c) / (orthoslope - slope);
230  double yp = a + slope * xp;
231  // find distance to line, in fact the square of dist,
232  // because we just know if it is > or < aDist
233  double dd = square( aRefPoint.x - xp ) + square( aRefPoint.y - yp );
234  double dist = square( aDist );
235 
236  if( dd > dist ) // this reference point is not a good candiadte.
237  return false;
238 
239  // dd is < dist, therefore we should make a fine test
240  if( fabs( slope ) > 0.7 )
241  {
242  // line segment more vertical than horizontal
243  if( (aEnd.y > aStart.y && yp <= aEnd.y && yp >= aStart.y) ||
244  (aEnd.y < aStart.y && yp >= aEnd.y && yp <= aStart.y) )
245  return true;
246  }
247  else
248  {
249  // line segment more horizontal than vertical
250  if( (aEnd.x > aStart.x && xp <= aEnd.x && xp >= aStart.x) ||
251  (aEnd.x < aStart.x && xp >= aEnd.x && xp <= aStart.x) )
252  return true;
253  }
254 
255  // Here, the test point is still a good candidate,
256  // however it is not "between" the end points of the segment.
257  // It is "outside" the segment, but it could be near a segment end point
258  // Therefore, we test the dist from the test point to each segment end point
259  dd = square( aRefPoint.x - aEnd.x ) + square( aRefPoint.y - aEnd.y );
260  if( dd <= dist )
261  return true;
262  dd = square( aRefPoint.x - aStart.x ) + square( aRefPoint.y - aStart.y );
263  if( dd <= dist )
264  return true;
265  }
266 
267  return false; // no hit
268 }
269 
270 
271 double ArcTangente( int dy, int dx )
272 {
273 
274  /* gcc is surprisingly smart in optimizing these conditions in
275  a tree! */
276 
277  if( dx == 0 && dy == 0 )
278  return 0;
279 
280  if( dy == 0 )
281  {
282  if( dx >= 0 )
283  return 0;
284  else
285  return -1800;
286  }
287 
288  if( dx == 0 )
289  {
290  if( dy >= 0 )
291  return 900;
292  else
293  return -900;
294  }
295 
296  if( dx == dy )
297  {
298  if( dx >= 0 )
299  return 450;
300  else
301  return -1800 + 450;
302  }
303 
304  if( dx == -dy )
305  {
306  if( dx >= 0 )
307  return -450;
308  else
309  return 1800 - 450;
310  }
311 
312  // Of course dy and dx are treated as double
313  return RAD2DECIDEG( atan2( (double) dy, (double) dx ) );
314 }
315 
316 
317 void RotatePoint( int* pX, int* pY, double angle )
318 {
319  int tmp;
320 
321  NORMALIZE_ANGLE_POS( angle );
322 
323  // Cheap and dirty optimizations for 0, 90, 180, and 270 degrees.
324  if( angle == 0 )
325  return;
326 
327  if( angle == 900 ) /* sin = 1, cos = 0 */
328  {
329  tmp = *pX;
330  *pX = *pY;
331  *pY = -tmp;
332  }
333  else if( angle == 1800 ) /* sin = 0, cos = -1 */
334  {
335  *pX = -*pX;
336  *pY = -*pY;
337  }
338  else if( angle == 2700 ) /* sin = -1, cos = 0 */
339  {
340  tmp = *pX;
341  *pX = -*pY;
342  *pY = tmp;
343  }
344  else
345  {
346  double fangle = DECIDEG2RAD( angle );
347  double sinus = sin( fangle );
348  double cosinus = cos( fangle );
349  double fpx = (*pY * sinus ) + (*pX * cosinus );
350  double fpy = (*pY * cosinus ) - (*pX * sinus );
351  *pX = KiROUND( fpx );
352  *pY = KiROUND( fpy );
353  }
354 }
355 
356 
357 void RotatePoint( int* pX, int* pY, int cx, int cy, double angle )
358 {
359  int ox, oy;
360 
361  ox = *pX - cx;
362  oy = *pY - cy;
363 
364  RotatePoint( &ox, &oy, angle );
365 
366  *pX = ox + cx;
367  *pY = oy + cy;
368 }
369 
370 
371 void RotatePoint( wxPoint* point, const wxPoint& centre, double angle )
372 {
373  int ox, oy;
374 
375  ox = point->x - centre.x;
376  oy = point->y - centre.y;
377 
378  RotatePoint( &ox, &oy, angle );
379  point->x = ox + centre.x;
380  point->y = oy + centre.y;
381 }
382 
383 
384 void RotatePoint( double* pX, double* pY, double cx, double cy, double angle )
385 {
386  double ox, oy;
387 
388  ox = *pX - cx;
389  oy = *pY - cy;
390 
391  RotatePoint( &ox, &oy, angle );
392 
393  *pX = ox + cx;
394  *pY = oy + cy;
395 }
396 
397 
398 void RotatePoint( double* pX, double* pY, double angle )
399 {
400  double tmp;
401 
402  NORMALIZE_ANGLE_POS( angle );
403 
404  // Cheap and dirty optimizations for 0, 90, 180, and 270 degrees.
405  if( angle == 0 )
406  return;
407 
408  if( angle == 900 ) /* sin = 1, cos = 0 */
409  {
410  tmp = *pX;
411  *pX = *pY;
412  *pY = -tmp;
413  }
414  else if( angle == 1800 ) /* sin = 0, cos = -1 */
415  {
416  *pX = -*pX;
417  *pY = -*pY;
418  }
419  else if( angle == 2700 ) /* sin = -1, cos = 0 */
420  {
421  tmp = *pX;
422  *pX = -*pY;
423  *pY = tmp;
424  }
425  else
426  {
427  double fangle = DECIDEG2RAD( angle );
428  double sinus = sin( fangle );
429  double cosinus = cos( fangle );
430 
431  double fpx = (*pY * sinus ) + (*pX * cosinus );
432  double fpy = (*pY * cosinus ) - (*pX * sinus );
433  *pX = fpx;
434  *pY = fpy;
435  }
436 }
bool IsPointOnSegment(const wxPoint &aSegStart, const wxPoint &aSegEnd, const wxPoint &aTestPoint)
Function IsPointOnSegment.
Definition: trigo.cpp:39
static int KiROUND(double v)
KiROUND rounds a floating point number to an int using "round halfway cases away from zero"...
Definition: common.h:107
static const int dist[10][10]
Definition: dist.cpp:57
double RAD2DECIDEG(double rad)
Definition: trigo.h:196
void RotatePoint(int *pX, int *pY, double angle)
Definition: trigo.cpp:317
void NORMALIZE_ANGLE_POS(T &Angle)
Definition: trigo.h:222
#define abs(a)
Definition: auxiliary.h:84
This file contains miscellaneous commonly used macros and functions.
bool SegmentIntersectsSegment(const wxPoint &a_p1_l1, const wxPoint &a_p2_l1, const wxPoint &a_p1_l2, const wxPoint &a_p2_l2)
Function SegmentIntersectsSegment.
Definition: trigo.cpp:58
double ArcTangente(int dy, int dx)
Definition: trigo.cpp:271
static double square(int x)
Definition: trigo.cpp:138
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
double DECIDEG2RAD(double deg)
Definition: trigo.h:195
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:142