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
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)
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