codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
/* Find minimum distance between a point and a line _segment_ */ /* 1. Vector calculation (drop a perpendicular) method */ /* 2. Ternary search (Enough binary search :) let's move to ternary */ #include <stdio.h> #include <math.h> #include <float.h> #include <assert.h> #define const struct point { double x, y; }; struct line { struct point start, end; }; double dist_sq(double x0, double y0, double x1, double y1) { const double xDiff = x1 - x0, yDiff = y1 - y0; return xDiff * xDiff + yDiff * yDiff; } /* Finding perpendicular from pt dropping on the ln */ double find_min_dist1(struct line ln, struct point pt) { const double x0 = ln.start.x, y0 = ln.start.y; const double x1 = ln.end.x, y1 = ln.start.y; const double x2 = pt.x, y2 = pt.y; const double xDiff = x1 - x0, yDiff = y1 - y0; /* Dividing line into two parts of length in ratio * r : (1-r) * Joining this point with pt gives the minimum distance */ double r = ( (x2-x0) * xDiff + (y2-y0) * yDiff) / (xDiff * xDiff + yDiff * yDiff); /* r = std::min( 1.0, std::max(0.0, r) ); */ if(r < 0.0) r = 0.0; // If perpendicular drops off the line, if(r > 1.0) r = 1.0; // pick the nearest point { const double joinxdif = (x0 + xDiff * r - x2); const double joinydif = (y0 + yDiff * r - y2); /* printf("DEBUG:: @(%g, %g)\n", x0 + xDiff * r, y0 + yDiff * r); */ return sqrt( joinxdif * joinxdif + joinydif * joinydif ); } } /* Using ternary search */ double find_min_dist2(struct line ln, struct point pt) { double x0 = ln.start.x, y0 = ln.start.y; double x1 = ln.end.x, y1 = ln.start.y; const double x2 = pt.x, y2 = pt.y; const double xDiff = x1 - x0, yDiff = y1 - y0; double s = 0.0, e = 1.0; while(e - s > DBL_EPSILON) { /* Find two ternary points */ double lft = (s * 2.0 + e) / 3.0; double rgt = (e * 2.0 + s) / 3.0; if(s == lft) lft = s + DBL_EPSILON; if(e == rgt) rgt = e - DBL_EPSILON; if(lft >= rgt) break; { const double xs[] = {ln.start.x + lft * xDiff , ln.start.x + rgt * xDiff}; const double ys[] = {ln.start.y + lft * yDiff , ln.start.y + rgt * yDiff}; const double ds[] = { dist_sq(xs[0], ys[0], x2, y2) , dist_sq(xs[1], ys[1], x2, y2) }; if(ds[0] < ds[1]) e = rgt; else s = lft; } } /* printf("DEBUG:: @(%g, %g)\n", ln.start.x + e * xDiff, ln.start.y + e * yDiff); */ return sqrt( dist_sq(ln.start.x + e * xDiff , ln.start.y + e * yDiff , x2 , y2) ); } int main() { struct line line1 = { {1.0, 2.0}, {5.0, 6.0} }; struct point pt1 = {3.0, 4.0}; struct line line2 = { {1.0, 2.0}, {3.0, 4.0} }; struct point pt2 = {5.0, 6.0}; struct line line3 = { {1.0, 2.0}, {11.0, 2.0} }; struct point pt3 = {5.0, 2.0}; struct line line4 = { {21.0, 62.0}, {11.0, 5.0} }; struct point pt4 = {-3.0, -3.0}; printf( "Distance by method 1 = %.10lf\n", find_min_dist1(line1, pt1) ); printf( "Distance by method 2 = %.10lf\n", find_min_dist2(line1, pt1) ); printf("\n"); printf( "Distance by method 1 = %.10lf\n", find_min_dist1(line2, pt2) ); printf( "Distance by method 2 = %.10lf\n", find_min_dist2(line2, pt2) ); printf("\n"); printf( "Distance by method 1 = %.10lf\n", find_min_dist1(line3, pt3) ); printf( "Distance by method 2 = %.10lf\n", find_min_dist2(line3, pt3) ); printf("\n"); printf( "Distance by method 1 = %.10lf\n", find_min_dist1(line4, pt4) ); printf( "Distance by method 2 = %.10lf\n", find_min_dist2(line4, pt4) ); printf("\n"); return 0; } /* End of program */
Private
[
?
]
Run code
Submit