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 const int dist[10][10]
Definition: ar_matrix.cpp:320
static int KiROUND(double v)
Round a floating point number to an integer using "round halfway cases away from zero".
Definition: common.h:120
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)
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