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 bool TestSegmentHit( const wxPoint &aRefPoint, wxPoint aStart, wxPoint aEnd, int aDist )
123 {
124  int xmin = aStart.x;
125  int xmax = aEnd.x;
126  int ymin = aStart.y;
127  int ymax = aEnd.y;
128  wxPoint delta = aStart - aRefPoint;
129 
130  if( xmax < xmin )
131  std::swap( xmax, xmin );
132 
133  if( ymax < ymin )
134  std::swap( ymax, ymin );
135 
136  // First, check if we are outside of the bounding box
137  if( ( ymin - aRefPoint.y > aDist ) || ( aRefPoint.y - ymax > aDist ) )
138  return false;
139 
140  if( ( xmin - aRefPoint.x > aDist ) || ( aRefPoint.x - xmax > aDist ) )
141  return false;
142 
143  // Next, eliminate easy cases
144  if( aStart.x == aEnd.x && aRefPoint.y > ymin && aRefPoint.y < ymax )
145  return std::abs( delta.x ) <= aDist;
146 
147  if( aStart.y == aEnd.y && aRefPoint.x > xmin && aRefPoint.x < xmax )
148  return std::abs( delta.y ) <= aDist;
149 
150  wxPoint len = aEnd - aStart;
151  // Precision note here:
152  // These are 32-bit integers, so squaring requires 64 bits to represent
153  // exactly. 64-bit Doubles have only 52 bits in the mantissa, so we start to lose
154  // precision at 2^53, which corresponds to ~ ±1nm @ 9.5cm, 2nm at 90cm, etc...
155  // Long doubles avoid this ambiguity as well as the more expensive denormal double calc
156  // Long doubles usually (sometimes more if SIMD) have at least 64 bits in the mantissa
157  long double length_square = (long double) len.x * len.x + (long double) len.y * len.y;
158  long double cross = std::abs( (long double) len.x * delta.y - (long double) len.y * delta.x );
159  long double dist_square = (long double) aDist * aDist;
160 
161  // The perpendicular distance to a line is the vector magnitude of the line from
162  // a test point to the test line. That is the 2d determinant. Because we handled
163  // the zero length case above, so we are guaranteed a unique solution.
164 
165  return ( ( length_square >= cross && dist_square >= cross ) ||
166  ( length_square * dist_square >= cross * cross ) );
167 }
168 
169 
170 double ArcTangente( int dy, int dx )
171 {
172 
173  /* gcc is surprisingly smart in optimizing these conditions in
174  a tree! */
175 
176  if( dx == 0 && dy == 0 )
177  return 0;
178 
179  if( dy == 0 )
180  {
181  if( dx >= 0 )
182  return 0;
183  else
184  return -1800;
185  }
186 
187  if( dx == 0 )
188  {
189  if( dy >= 0 )
190  return 900;
191  else
192  return -900;
193  }
194 
195  if( dx == dy )
196  {
197  if( dx >= 0 )
198  return 450;
199  else
200  return -1800 + 450;
201  }
202 
203  if( dx == -dy )
204  {
205  if( dx >= 0 )
206  return -450;
207  else
208  return 1800 - 450;
209  }
210 
211  // Of course dy and dx are treated as double
212  return RAD2DECIDEG( atan2( (double) dy, (double) dx ) );
213 }
214 
215 
216 void RotatePoint( int* pX, int* pY, double angle )
217 {
218  int tmp;
219 
220  NORMALIZE_ANGLE_POS( angle );
221 
222  // Cheap and dirty optimizations for 0, 90, 180, and 270 degrees.
223  if( angle == 0 )
224  return;
225 
226  if( angle == 900 ) /* sin = 1, cos = 0 */
227  {
228  tmp = *pX;
229  *pX = *pY;
230  *pY = -tmp;
231  }
232  else if( angle == 1800 ) /* sin = 0, cos = -1 */
233  {
234  *pX = -*pX;
235  *pY = -*pY;
236  }
237  else if( angle == 2700 ) /* sin = -1, cos = 0 */
238  {
239  tmp = *pX;
240  *pX = -*pY;
241  *pY = tmp;
242  }
243  else
244  {
245  double fangle = DECIDEG2RAD( angle );
246  double sinus = sin( fangle );
247  double cosinus = cos( fangle );
248  double fpx = (*pY * sinus ) + (*pX * cosinus );
249  double fpy = (*pY * cosinus ) - (*pX * sinus );
250  *pX = KiROUND( fpx );
251  *pY = KiROUND( fpy );
252  }
253 }
254 
255 
256 void RotatePoint( int* pX, int* pY, int cx, int cy, double angle )
257 {
258  int ox, oy;
259 
260  ox = *pX - cx;
261  oy = *pY - cy;
262 
263  RotatePoint( &ox, &oy, angle );
264 
265  *pX = ox + cx;
266  *pY = oy + cy;
267 }
268 
269 
270 void RotatePoint( wxPoint* point, const wxPoint& centre, double angle )
271 {
272  int ox, oy;
273 
274  ox = point->x - centre.x;
275  oy = point->y - centre.y;
276 
277  RotatePoint( &ox, &oy, angle );
278  point->x = ox + centre.x;
279  point->y = oy + centre.y;
280 }
281 
282 void RotatePoint( VECTOR2I& point, const VECTOR2I& centre, double angle )
283 {
284  wxPoint c( centre.x, centre.y );
285  wxPoint p( point.x, point.y );
286 
287  RotatePoint(&p, c, angle);
288 
289  point.x = p.x;
290  point.y = p.y;
291 }
292 
293 
294 void RotatePoint( double* pX, double* pY, double cx, double cy, double angle )
295 {
296  double ox, oy;
297 
298  ox = *pX - cx;
299  oy = *pY - cy;
300 
301  RotatePoint( &ox, &oy, angle );
302 
303  *pX = ox + cx;
304  *pY = oy + cy;
305 }
306 
307 
308 void RotatePoint( double* pX, double* pY, double angle )
309 {
310  double tmp;
311 
312  NORMALIZE_ANGLE_POS( angle );
313 
314  // Cheap and dirty optimizations for 0, 90, 180, and 270 degrees.
315  if( angle == 0 )
316  return;
317 
318  if( angle == 900 ) /* sin = 1, cos = 0 */
319  {
320  tmp = *pX;
321  *pX = *pY;
322  *pY = -tmp;
323  }
324  else if( angle == 1800 ) /* sin = 0, cos = -1 */
325  {
326  *pX = -*pX;
327  *pY = -*pY;
328  }
329  else if( angle == 2700 ) /* sin = -1, cos = 0 */
330  {
331  tmp = *pX;
332  *pX = -*pY;
333  *pY = tmp;
334  }
335  else
336  {
337  double fangle = DECIDEG2RAD( angle );
338  double sinus = sin( fangle );
339  double cosinus = cos( fangle );
340 
341  double fpx = (*pY * sinus ) + (*pX * cosinus );
342  double fpy = (*pY * cosinus ) - (*pX * sinus );
343  *pX = fpx;
344  *pY = fpy;
345  }
346 }
bool IsPointOnSegment(const wxPoint &aSegStart, const wxPoint &aSegEnd, const wxPoint &aTestPoint)
Function IsPointOnSegment.
Definition: trigo.cpp:39
static int KiROUND(double v)
Round a floating point number to an integer using "round halfway cases away from zero".
Definition: common.h:120
Class VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:61
double RAD2DECIDEG(double rad)
Definition: trigo.h:204
void RotatePoint(int *pX, int *pY, double angle)
Definition: trigo.cpp:216
void NORMALIZE_ANGLE_POS(T &Angle)
Definition: trigo.h:241
#define abs(a)
Definition: auxiliary.h:84
static const int delta[8][2]
Definition: solve.cpp:112
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:170
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
double DECIDEG2RAD(double deg)
Definition: trigo.h:203
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:122