math_for_graphics.h File Reference

Go to the source code of this file.

Functions

bool FindLineSegmentIntersection (double a, double b, int xi, int yi, int xf, int yf, double *x1, double *y1, double *x2, double *y2, double *dist=NULL)

bool FindSegmentIntersections (int xi, int yi, int xf, int yf, int xi2, int yi2, int xf2, int yf2)

bool TestForIntersectionOfStraightLineSegments (int x1i, int y1i, int x1f, int y1f, int x2i, int y2i, int x2f, int y2f, int *x=NULL, int *y=NULL, double *dist=NULL)
Function TestForIntersectionOfStraightLineSegments Test for intersection of line segments If lines are parallel, returns false If true, returns also intersection coords in x, y if false, returns min. More...

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)

double GetPointToLineSegmentDistance (int x, int y, int xi, int yi, int xf, int yf)
Function GetPointToLineSegmentDistance Get distance between line segment and point. More...

double GetPointToLineDistance (double a, double b, int x, int y, double *xp=NULL, double *yp=NULL)

double Distance (double x1, double y1, double x2, double y2)

◆ Distance()

 double Distance ( double x1, double y1, double x2, double y2 )
inline

Definition at line 66 of file math_for_graphics.h.

67 {
68  return hypot( x1 - x2, y1 - y2 );
69 }

◆ FindLineSegmentIntersection()

 bool FindLineSegmentIntersection ( double a, double b, int xi, int yi, int xf, int yf, double * x1, double * y1, double * x2, double * y2, double * dist = `NULL` )

Definition at line 41 of file math_for_graphics.cpp.

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 }
double GetPointToLineDistance(double a, double b, int x, int y, double *xpp, double *ypp)
static const int dist[10][10]
Definition: ar_matrix.cpp:320
static bool InRange(double x, double xi, double xf)
#define abs(a)
Definition: auxiliary.h:84
#define min(a, b)
Definition: auxiliary.h:85

References abs, dist, GetPointToLineDistance(), InRange(), and min.

Referenced by ZONE_CONTAINER::Hatch(), and TestForIntersectionOfStraightLineSegments().

◆ FindSegmentIntersections()

 bool FindSegmentIntersections ( int xi, int yi, int xf, int yf, int xi2, int yi2, int xf2, int yf2 )

Definition at line 20 of file math_for_graphics.cpp.

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 }
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...
#define max(a, b)
Definition: auxiliary.h:86
#define min(a, b)
Definition: auxiliary.h:85

References max, min, and TestForIntersectionOfStraightLineSegments().

◆ GetClearanceBetweenSegments()

 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 )

Definition at line 378 of file math_for_graphics.cpp.

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 }
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:121
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...
#define max(a, b)
Definition: auxiliary.h:86
#define min(a, b)
Definition: auxiliary.h:85

References dist, KiROUND(), max, min, and TestForIntersectionOfStraightLineSegments().

Referenced by DRC::doEdgeZoneDrc(), and DRC::TestZoneToZoneOutline().

◆ GetPointToLineDistance()

 double GetPointToLineDistance ( double a, double b, int x, int y, double * xp = `NULL`, double * yp = `NULL` )

Definition at line 420 of file math_for_graphics.cpp.

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 }
#define abs(a)
Definition: auxiliary.h:84
double Distance(double x1, double y1, double x2, double y2)

References abs, and Distance().

Referenced by FindLineSegmentIntersection().

◆ GetPointToLineSegmentDistance()

 double GetPointToLineSegmentDistance ( int x, int y, int xi, int yi, int xf, int yf )

Function GetPointToLineSegmentDistance Get distance between line segment and point.

Parameters
 x,y = point xi,yi,xf,yf = the end-points of the line segment
Returns
the distance
Parameters
 x,y = point xi,yi Start point of the line segament xf,yf End point of the line segment
Returns
the distance

Definition at line 461 of file math_for_graphics.cpp.

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 }
static bool InRange(double x, double xi, double xf)
#define abs(a)
Definition: auxiliary.h:84
double Distance(double x1, double y1, double x2, double y2)
#define min(a, b)
Definition: auxiliary.h:85

References abs, Distance(), InRange(), and min.

Referenced by TestForIntersectionOfStraightLineSegments().

◆ TestForIntersectionOfStraightLineSegments()

 bool TestForIntersectionOfStraightLineSegments ( int x1i, int y1i, int x1f, int y1f, int x2i, int y2i, int x2f, int y2f, int * x = `NULL`, int * y = `NULL`, double * dist = `NULL` )

Function TestForIntersectionOfStraightLineSegments Test for intersection of line segments If lines are parallel, returns false If true, returns also intersection coords in x, y if false, returns min.

distance in dist (may be 0.0 if parallel) and coords on nearest point in one of the segments in (x,y)

Parameters
 x1i,y1i,x1f,y1f = integer coordinates of the first segment x2i,y2i,x2f,y2f = integer coordinates of the other segment x,y = pointers on 2 integer to store the intersection coordinates (can be NULL) dist = pointeur on a double to store the dist.
Returns
true if intersect.

Definition at line 132 of file math_for_graphics.cpp.

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 }
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:121
static bool InRange(double x, double xi, double xf)
bool FindLineSegmentIntersection(double a, double b, int xi, int yi, int xf, int yf, double *x1, double *y1, double *x2, double *y2, double *dist)