KiCad PCB EDA Suite
math_for_graphics.cpp
Go to the documentation of this file.
1 // math for graphics utility routines and RC, from FreePCB
2 
3 #include <vector>
4 
5 #include <cmath>
6 #include <float.h>
7 #include <limits.h>
8 #include <common.h>
9 #include <cstdlib> // for abs function on ints
10 #include <algorithm>
11 #include <math_for_graphics.h>
12 
13 static bool InRange( double x, double xi, double xf );
14 
15 /* Function FindSegmentIntersections
16  * find intersections between line segment (xi,yi) to (xf,yf)
17  * and line segment (xi2,yi2) to (xf2,yf2)
18  * returns true if intersection found
19  */
20 bool FindSegmentIntersections( int xi, int yi, int xf, int yf,
21  int xi2, int yi2, int xf2, int yf2 )
22 {
23  if( std::max( xi, xf ) < std::min( xi2, xf2 )
24  || std::min( xi, xf ) > std::max( xi2, xf2 )
25  || std::max( yi, yf ) < std::min( yi2, yf2 )
26  || std::min( yi, yf ) > std::max( yi2, yf2 ) )
27  return false;
28 
29  return TestForIntersectionOfStraightLineSegments( xi, yi, xf, yf,
30  xi2, yi2, xf2, yf2 );
31 }
32 
33 
34 /* Function FindLineSegmentIntersection
35  * find intersection between line y = a + bx and line segment (xi,yi) to (xf,yf)
36  * if b > DBL_MAX/10, assume vertical line at x = a
37  * return false if no intersection or true if intersect
38  * return coords of intersections in *x1, *y1, *x2, *y2
39  * if no intersection, returns min distance in dist
40  */
41 bool FindLineSegmentIntersection( double a, double b, int xi, int yi, int xf, int yf,
42  double* x1, double* y1, double* x2, double* y2,
43  double* dist )
44 {
45  double xx = 0, yy = 0; // Init made to avoid C compil "uninitialized" warning
46  bool bVert = false;
47 
48  if( b > DBL_MAX / 10.0 )
49  bVert = true;
50 
51  if( xf != xi ) // non-vertical segment, get intersection
52  {
53  // horizontal or oblique straight segment
54  // put into form y = c + dx;
55  double d = (double) (yf - yi) / (double) (xf - xi);
56  double c = yf - d * xf;
57 
58  if( bVert )
59  {
60  // if vertical line, easy
61  if( InRange( a, xi, xf ) )
62  {
63  *x1 = a;
64  *y1 = c + d * a;
65  return 1;
66  }
67  else
68  {
69  if( dist )
70  *dist = std::min( std::abs( a - xi ), std::abs( a - xf ) );
71 
72  return false;
73  }
74  }
75 
76  if( std::abs( b - d ) < 1E-12 )
77  {
78  // parallel lines
79  if( dist )
80  {
81  *dist = GetPointToLineDistance( a, b, xi, xf );
82  }
83 
84  return false; // lines parallel
85  }
86 
87  // calculate intersection
88  xx = (c - a) / (b - d);
89  yy = a + b * (xx);
90 
91  // see if intersection is within the line segment
92  if( yf == yi )
93  {
94  // horizontal line
95  if( (xx>=xi && xx>xf) || (xx<=xi && xx<xf) )
96  return false;
97  }
98  else
99  {
100  // oblique line
101  if( (xx>=xi && xx>xf) || (xx<=xi && xx<xf)
102  || (yy>yi && yy>yf) || (yy<yi && yy<yf) )
103  return false;
104  }
105  }
106  else
107  {
108  // vertical line segment
109  if( bVert )
110  return false;
111 
112  xx = xi;
113  yy = a + b * xx;
114 
115  if( (yy>=yi && yy>yf) || (yy<=yi && yy<yf) )
116  return 0;
117  }
118 
119  *x1 = xx;
120  *y1 = yy;
121  return true;
122 }
123 
124 
125 /*
126  * Function TestForIntersectionOfStraightLineSegments
127  * Test for intersection of line segments
128  * If lines are parallel, returns false
129  * If true, returns also intersection coords in x, y
130  * if false, returns min. distance in dist (may be 0.0 if parallel)
131  */
132 bool TestForIntersectionOfStraightLineSegments( int x1i, int y1i, int x1f, int y1f,
133  int x2i, int y2i, int x2f, int y2f,
134  int* x, int* y, double* d )
135 {
136  double a, b, dist;
137 
138  // first, test for intersection
139  if( x1i == x1f && x2i == x2f )
140  {
141  // both segments are vertical, can't intersect
142  }
143  else if( y1i == y1f && y2i == y2f )
144  {
145  // both segments are horizontal, can't intersect
146  }
147  else if( x1i == x1f && y2i == y2f )
148  {
149  // first seg. vertical, second horizontal, see if they cross
150  if( InRange( x1i, x2i, x2f )
151  && InRange( y2i, y1i, y1f ) )
152  {
153  if( x )
154  *x = x1i;
155 
156  if( y )
157  *y = y2i;
158 
159  if( d )
160  *d = 0.0;
161 
162  return true;
163  }
164  }
165  else if( y1i == y1f && x2i == x2f )
166  {
167  // first seg. horizontal, second vertical, see if they cross
168  if( InRange( y1i, y2i, y2f )
169  && InRange( x2i, x1i, x1f ) )
170  {
171  if( x )
172  *x = x2i;
173 
174  if( y )
175  *y = y1i;
176 
177  if( d )
178  *d = 0.0;
179 
180  return true;
181  }
182  }
183  else if( x1i == x1f )
184  {
185  // first segment vertical, second oblique
186  // get a and b for second line segment, so that y = a + bx;
187  b = double( y2f - y2i ) / (x2f - x2i);
188  a = (double) y2i - b * x2i;
189 
190  double x1, y1, x2, y2;
191  int test = FindLineSegmentIntersection( a, b, x1i, y1i, x1f, y1f,
192  &x1, &y1, &x2, &y2 );
193 
194  if( test )
195  {
196  if( InRange( y1, y1i, y1f ) && InRange( x1, x2i, x2f ) && InRange( y1, y2i, y2f ) )
197  {
198  if( x )
199  *x = KiROUND( x1 );
200 
201  if( y )
202  *y = KiROUND( y1 );
203 
204  if( d )
205  *d = 0.0;
206 
207  return true;
208  }
209  }
210  }
211  else if( y1i == y1f )
212  {
213  // first segment horizontal, second oblique
214  // get a and b for second line segment, so that y = a + bx;
215  b = double( y2f - y2i ) / (x2f - x2i);
216  a = (double) y2i - b * x2i;
217 
218  double x1, y1, x2, y2;
219  int test = FindLineSegmentIntersection( a, b, x1i, y1i, x1f, y1f,
220  &x1, &y1, &x2, &y2 );
221 
222  if( test )
223  {
224  if( InRange( x1, x1i, x1f ) && InRange( x1, x2i, x2f ) && InRange( y1, y2i, y2f ) )
225  {
226  if( x )
227  *x = KiROUND( x1 );
228 
229  if( y )
230  *y = KiROUND( y1 );
231 
232  if( d )
233  *d = 0.0;
234 
235  return true;
236  }
237  }
238  }
239  else if( x2i == x2f )
240  {
241  // second segment vertical, first oblique
242  // get a and b for first line segment, so that y = a + bx;
243  b = double( y1f - y1i ) / (x1f - x1i);
244  a = (double) y1i - b * x1i;
245 
246  double x1, y1, x2, y2;
247  int test = FindLineSegmentIntersection( a, b, x2i, y2i, x2f, y2f,
248  &x1, &y1, &x2, &y2 );
249 
250  if( test )
251  {
252  if( InRange( x1, x1i, x1f ) && InRange( y1, y1i, y1f ) && InRange( y1, y2i, y2f ) )
253  {
254  if( x )
255  *x = KiROUND( x1 );
256 
257  if( y )
258  *y = KiROUND( y1 );
259 
260  if( d )
261  *d = 0.0;
262 
263  return true;
264  }
265  }
266  }
267  else if( y2i == y2f )
268  {
269  // second segment horizontal, first oblique
270  // get a and b for second line segment, so that y = a + bx;
271  b = double( y1f - y1i ) / (x1f - x1i);
272  a = (double) y1i - b * x1i;
273 
274  double x1, y1, x2, y2;
275  int test = FindLineSegmentIntersection( a, b, x2i, y2i, x2f, y2f,
276  &x1, &y1, &x2, &y2 );
277 
278  if( test )
279  {
280  if( InRange( x1, x1i, x1f ) && InRange( y1, y1i, y1f ) )
281  {
282  if( x )
283  *x = KiROUND( x1 );
284 
285  if( y )
286  *y = KiROUND( y1 );
287 
288  if( d )
289  *d = 0.0;
290 
291  return true;
292  }
293  }
294  }
295  else
296  {
297  // both segments oblique
298  if( long( y1f - y1i ) * (x2f - x2i) != long( y2f - y2i ) * (x1f - x1i) )
299  {
300  // not parallel, get a and b for first line segment, so that y = a + bx;
301  b = double( y1f - y1i ) / (x1f - x1i);
302  a = (double) y1i - b * x1i;
303 
304  double x1, y1, x2, y2;
305  int test = FindLineSegmentIntersection( a, b, x2i, y2i, x2f, y2f,
306  &x1, &y1, &x2, &y2 );
307 
308  // both segments oblique
309  if( test )
310  {
311  if( InRange( x1, x1i, x1f ) && InRange( y1, y1i, y1f ) )
312  {
313  if( x )
314  *x = KiROUND( x1 );
315 
316  if( y )
317  *y = KiROUND( y1 );
318 
319  if( d )
320  *d = 0.0;
321 
322  return true;
323  }
324  }
325  }
326  }
327 
328  // don't intersect, get shortest distance between each endpoint and the other line segment
329  dist = GetPointToLineSegmentDistance( x1i, y1i, x2i, y2i, x2f, y2f );
330 
331  double xx = x1i;
332  double yy = y1i;
333  double dd = GetPointToLineSegmentDistance( x1f, y1f, x2i, y2i, x2f, y2f );
334 
335  if( dd < dist )
336  {
337  dist = dd;
338  xx = x1f;
339  yy = y1f;
340  }
341 
342  dd = GetPointToLineSegmentDistance( x2i, y2i, x1i, y1i, x1f, y1f );
343 
344  if( dd < dist )
345  {
346  dist = dd;
347  xx = x2i;
348  yy = y2i;
349  }
350 
351  dd = GetPointToLineSegmentDistance( x2f, y2f, x1i, y1i, x1f, y1f );
352 
353  if( dd < dist )
354  {
355  dist = dd;
356  xx = x2f;
357  yy = y2f;
358  }
359 
360  if( x )
361  *x = KiROUND( xx );
362 
363  if( y )
364  *y = KiROUND( yy );
365 
366  if( d )
367  *d = dist;
368 
369  return false;
370 }
371 
372 
373 /* Function GetClearanceBetweenSegments
374  * Get clearance between 2 segments
375  * Returns coordinates of the closest point between these 2 segments in x, y
376  * If clearance > max_cl, just returns max_cl+1 and doesn't return x,y
377  */
378 int GetClearanceBetweenSegments( int x1i, int y1i, int x1f, int y1f, int w1,
379  int x2i, int y2i, int x2f, int y2f, int w2,
380  int max_cl, int* x, int* y )
381 {
382  // check clearance between bounding rectangles
383  int min_dist = max_cl + ( (w1 + w2) / 2 );
384 
385  if( std::min( x1i, x1f ) - std::max( x2i, x2f ) > min_dist )
386  return max_cl+1;
387 
388  if( std::min( x2i, x2f ) - std::max( x1i, x1f ) > min_dist )
389  return max_cl+1;
390 
391  if( std::min( y1i, y1f ) - std::max( y2i, y2f ) > min_dist )
392  return max_cl+1;
393 
394  if( std::min( y2i, y2f ) - std::max( y1i, y1f ) > min_dist )
395  return max_cl+1;
396 
397  int xx, yy;
398  double dist;
399  TestForIntersectionOfStraightLineSegments( x1i, y1i, x1f, y1f,
400  x2i, y2i, x2f, y2f, &xx, &yy, &dist );
401  int d = KiROUND( dist ) - ((w1 + w2) / 2);
402  if( d < 0 )
403  d = 0;
404 
405  if( x )
406  *x = xx;
407 
408  if( y )
409  *y = yy;
410 
411  return d;
412 }
413 
414 
415 /* Function GetPointToLineDistance
416  * Get min. distance from (x,y) to line y = a + bx
417  * if b > DBL_MAX/10, assume vertical line at x = a
418  * returns closest point on line in xpp, ypp
419  */
420 double GetPointToLineDistance( double a, double b, int x, int y, double* xpp, double* ypp )
421 {
422  if( b > DBL_MAX / 10 )
423  {
424  // vertical line
425  if( xpp && ypp )
426  {
427  *xpp = a;
428  *ypp = y;
429  }
430 
431  return std::abs( a - x );
432  }
433 
434  // find c,d such that (x,y) lies on y = c + dx where d=(-1/b)
435  double d = -1.0 / b;
436  double c = (double) y - d * x;
437 
438  // find nearest point to (x,y) on line through (xi,yi) to (xf,yf)
439  double xp = (a - c) / (d - b);
440  double yp = a + b * xp;
441 
442  if( xpp && ypp )
443  {
444  *xpp = xp;
445  *ypp = yp;
446  }
447 
448  // find distance
449  return Distance( x, y, xp, yp );
450 }
451 
452 
461 double GetPointToLineSegmentDistance( int x, int y, int xi, int yi, int xf, int yf )
462 {
463  // test for vertical or horizontal segment
464  if( xf==xi )
465  {
466  // vertical line segment
467  if( InRange( y, yi, yf ) )
468  return std::abs( x - xi );
469  else
470  return std::min( Distance( x, y, xi, yi ), Distance( x, y, xf, yf ) );
471  }
472  else if( yf==yi )
473  {
474  // horizontal line segment
475  if( InRange( x, xi, xf ) )
476  return std::abs( y - yi );
477  else
478  return std::min( Distance( x, y, xi, yi ), Distance( x, y, xf, yf ) );
479  }
480  else
481  {
482  // oblique segment
483  // find a,b such that (xi,yi) and (xf,yf) lie on y = a + bx
484  double b = (double) (yf - yi) / (xf - xi);
485  double a = (double) yi - b * xi;
486 
487  // find c,d such that (x,y) lies on y = c + dx where d=(-1/b)
488  double d = -1.0 / b;
489  double c = (double) y - d * x;
490 
491  // find nearest point to (x,y) on line through (xi,yi) to (xf,yf)
492  double xp = (a - c) / (d - b);
493  double yp = a + b * xp;
494 
495  // find distance
496  if( InRange( xp, xi, xf ) && InRange( yp, yi, yf ) )
497  return Distance( x, y, xp, yp );
498  else
499  return std::min( Distance( x, y, xi, yi ), Distance( x, y, xf, yf ) );
500  }
501 }
502 
503 
504 // test for value within range
505 bool InRange( double x, double xi, double xf )
506 {
507  if( xf > xi )
508  {
509  if( x >= xi && x <= xf )
510  return true;
511  }
512  else
513  {
514  if( x >= xf && x <= xi )
515  return true;
516  }
517 
518  return false;
519 }
double GetPointToLineDistance(double a, double b, int x, int y, double *xpp, double *ypp)
double GetPointToLineSegmentDistance(int x, int y, int xi, int yi, int xf, int yf)
Function GetPointToLineSegmentDistance Get distance between line segment and point.
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
bool TestForIntersectionOfStraightLineSegments(int x1i, int y1i, int x1f, int y1f, int x2i, int y2i, int x2f, int y2f, int *x, int *y, double *d)
Function TestForIntersectionOfStraightLineSegments Test for intersection of line segments If lines ar...
static bool InRange(double x, double xi, double xf)
static const int dist[10][10]
Definition: dist.cpp:57
int GetClearanceBetweenSegments(int x1i, int y1i, int x1f, int y1f, int w1, int x2i, int y2i, int x2f, int y2f, int w2, int max_cl, int *x, int *y)
#define abs(a)
Definition: auxiliary.h:84
bool FindLineSegmentIntersection(double a, double b, int xi, int yi, int xf, int yf, double *x1, double *y1, double *x2, double *y2, double *dist)
#define max(a, b)
Definition: auxiliary.h:86
The common library.
bool FindSegmentIntersections(int xi, int yi, int xf, int yf, int xi2, int yi2, int xf2, int yf2)
double Distance(double x1, double y1, double x2, double y2)
#define min(a, b)
Definition: auxiliary.h:85