/** * This does a few geometric calculations to make life easier for * us. * @author Pinkfish * @started Fri Apr 5 15:47:05 PST 2002 */ class point { int x; int y; } // A nice small number so we avoid division errors. #define SMALL_NUM 0.00001 /** * Return the intersection of a line and a line segment. * @param lx1 the line x top * @param ly1 the line y top * @param lx2 the line x bottom * @param ly2 the line y bottom * @param sx1 the line segement x start * @param sy1 the line segement y start * @param sx2 the line segement x end * @param sy2 the line segement y end * @return the intersection point */ class point intersection_of_line_and_segment(int lx1, int ly1, int lx2, int ly2, int sx1, int sy1, int sx2, int sy2) { float den; float uanum; float ubnum; float ua; float ub; class point p; den = to_float(sy2 - sy1) * to_float(lx2 - lx1) - to_float(sx2 - sx1) * to_float(ly2 - ly1); if (den == 0.0) { return 0; } ubnum = to_float(lx2 - lx1) * to_float(ly1 - sy1) - to_float(ly2 - ly1) * to_float(lx1 - sx1); ub = ubnum / den; if (ub < 0.0 || ub > 1.0) { return 0; } uanum = to_float(sx2 - sx1) * to_float(ly1 - sy1) - to_float(sy2 - sy1) * to_float(lx1 - sx1); ua = uanum / den; //printf("%O %O %O (%O %O)\n", den, ua, ub, ua / den, ub / den); p = new(class point); p->x = lx1 + to_int(ua * (lx2 - lx1)); p->y = ly1 + to_int(ub * (ly2 - ly1)); //printf("%O\n", p); return p; } /** * Finds the distance from a point to a line segment. * @param x1 the start of the line segment * @param y1 the start of the line segment * @param x2 the end of the line segment * @param y2 the end of the line segment * @param point_x the point * @param point_y the point * @return the distance */ int distance_point_to_line_segment(int x1, int y1, int x2, int y2, int point_x, int point_y) { float v1_x; float v1_y; float v2_x; float v2_y; float distance; float dot1; float dot2; float b; float vm_x; float vm_y; v1_x = to_float(x1 - x2); v1_y = to_float(y1 - y2); v2_x = to_float(point_x - x2); v2_y = to_float(point_y - y2); dot1 = v1_x * v2_x + v1_y * v2_y; if (dot1 <= 0.0) { // Distance to p1 distance = sqrt(pow(x2 - point_x, 2) + pow(y2 - point_y, 2)); } else { dot2 = v1_x * v1_x + v1_y * v1_y; if (dot2 <= dot1) { // Distance to p2. distance = sqrt(pow(x1 - point_x, 2) + pow(y1 - point_y, 2)); } else { b = dot1 / dot2; vm_x = to_float(x2) + b * v1_x; vm_y = to_float(y2) + b * v1_y; // Distance to vm. distance = sqrt(pow(vm_x - point_x, 2) + pow(vm_y - point_y, 2)); } } return to_int(distance); } /** * This method finds the minimum distance between two line segments. * @param x1_1 the start of the first line * @param y1_1 the start of the first line * @param x2_1 the end of the first line * @param y2_1 the end of the first line * @param x1_2 the start of the second line * @param y1_2 the start of the second line * @param x2_2 the end of the second line * @param y2_2 the end of the second line * @return the minimum distance */ int distance_between_two_line_segments( int x1_1, int y1_1, int x2_1, int y2_1, int x1_2, int y1_2, int x2_2, int y2_2) { float ux; float uy; float vx; float vy; float wx; float wy; float dpx; float dpy; float a; float b; float c; float d; float e; float dist; float sc; float sn; float sd; float tc; float tn; float td; ux = to_float(x2_1) - to_float(x1_1); uy = to_float(y2_1) - to_float(y1_1); vx = to_float(x2_2) - to_float(x1_2); vy = to_float(y2_2) - to_float(y1_2); wx = to_float(x1_1) - to_float(x1_2); wy = to_float(y1_1) - to_float(y1_2); a = ux * ux + uy * uy; b = ux * vx + uy * vy; c = vx * vx + vy * vy; d = ux * wx + uy * wy; e = vx * wx + vy * wy; dist = a * c - b * b; sd = dist; td = dist; if (dist < SMALL_NUM) { // Almost parallel. // Set one bit as 0. sn = 0.0; sd = 1.0; tn = e; td = c; } else { // get the closest points on the infinte lines. sn = b * e - c * d; tn = a * e - b * d; if (sn < 0.0) { // sc < 0 => the s=0 edge is visible. sn = 0.0; tn = e; td = c; } else if (sn > sd) { // sc > 1 => s1 = edge is visible. sn = sd; tn = e + b; td = c; } if (tn < 0.0) { // tc < 0 -> t0 edge is visible. tn = 0.0; if (-d < 0.0) { sn = 0.0; } else if (-d > a) { sn = sd; } else { sn = -d; sd = a; } } else if (tn > td) { // tc > 1 => the t1 edge is visible tn = td; if ((-d + b) < 0) { sn = 0.0; } else if ((-d + b) > a) { sn = sd; } else { sn = -d + b; sd = a; } } } // finally do the division to get sc and tc sc = sn / sd; tc = tn / td; //printf("%O / %O = %O, %O / %O = %O\n", sn, sd, sc, tn, td, tc); // get the difference between the two closet points dpx = wx + (sc * ux) - (tc * vx); dpy = wy + (sc * uy) - (tc * vy); //printf("%O + %O = %O -- %O %O\n", dpx * dpx, dpy * dpy, dpx * dpx + dpy * dpy, sqrt(dpx * dpx + dpy * dpy), to_int(sqrt(dpx * dpx + dpy * dpy))); dist = sqrt(dpx * dpx + dpy * dpy); if (dist > pow(2, 30)) { return to_int(pow(2, 30)); } return to_int(sqrt(dpx * dpx + dpy * dpy)); }