KiCad PCB EDA Suite
math_for_graphics.cpp File Reference
#include <vector>
#include <cmath>
#include <float.h>
#include <limits.h>
#include <common.h>
#include <cstdlib>
#include <algorithm>
#include <math_for_graphics.h>

Go to the source code of this file.

Functions

static bool InRange (double x, double xi, double xf)
 
bool FindSegmentIntersections (int xi, int yi, int xf, int yf, int xi2, int yi2, int xf2, int yf2)
 
bool FindLineSegmentIntersection (double a, double b, int xi, int yi, int xf, int yf, double *x1, double *y1, double *x2, double *y2, double *dist)
 
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 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 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. More...
 

Function Documentation

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

Definition at line 41 of file math_for_graphics.cpp.

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

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

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

References max, min, and TestForIntersectionOfStraightLineSegments().

Referenced by CPolyLine::IsPolygonSelfIntersecting().

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

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

Referenced by CPolyLine::Distance(), DRC::doEdgeZoneDrc(), and BOARD::Test_Drc_Areas_Outlines_To_Areas_Outlines().

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 int KiROUND(double v)
KiROUND rounds a floating point number to an int using "round halfway cases away from zero"...
Definition: common.h:106
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 const int dist[10][10]
Definition: dist.cpp:57
#define max(a, b)
Definition: auxiliary.h:86
#define min(a, b)
Definition: auxiliary.h:85
double GetPointToLineDistance ( double  a,
double  b,
int  x,
int  y,
double *  xpp,
double *  ypp 
)

Definition at line 420 of file math_for_graphics.cpp.

References abs, and Distance().

Referenced by FindLineSegmentIntersection().

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)
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,yiStart point of the line segament
xf,yfEnd point of the line segment
Returns
the distance

Definition at line 461 of file math_for_graphics.cpp.

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

Referenced by CPolyLine::Distance(), CPolyLine::HitTestForEdge(), and TestForIntersectionOfStraightLineSegments().

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
bool InRange ( double  x,
double  xi,
double  xf 
)
static

Definition at line 505 of file math_for_graphics.cpp.

Referenced by FindLineSegmentIntersection(), GetPointToLineSegmentDistance(), and TestForIntersectionOfStraightLineSegments().

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 }
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.

References dist, FindLineSegmentIntersection(), GetPointToLineSegmentDistance(), InRange(), and KiROUND().

Referenced by FindSegmentIntersections(), GetClearanceBetweenSegments(), poly2polyDRC(), and poly2segmentDRC().

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 int KiROUND(double v)
KiROUND rounds a floating point number to an int using "round halfway cases away from zero"...
Definition: common.h:106
static bool InRange(double x, double xi, double xf)
static const int dist[10][10]
Definition: dist.cpp:57
bool FindLineSegmentIntersection(double a, double b, int xi, int yi, int xf, int yf, double *x1, double *y1, double *x2, double *y2, double *dist)