```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 ``` ```/* 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 #include #include #include #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.end.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.end.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 */ ```
 ```1 2 3 4 5 6 7 8 9 10 11 12 ``` ```Distance by method 1 = 0.0000000000 Distance by method 2 = 0.0000000000 Distance by method 1 = 2.8284271247 Distance by method 2 = 2.8284271247 Distance by method 1 = 0.0000000000 Distance by method 2 = 0.0000000000 Distance by method 1 = 16.1245154966 Distance by method 2 = 16.1245154966 ```