typedef struct point { int x; int y; } point; typedef struct line { point p1; point p2; } line; /* * check_lines: * This is based off an explanation and expanded math presented by Paul Bourke: * * It takes two lines as inputs and returns 1 if they intersect, 0 if they do * not. hitp returns the point where the two lines intersected. * * This function expects integer value inputs and stores an integer value * in hitp if the two lines interesect. The internal calculations are fixed * point with a 14 bit fractional precision for processors without floating * point units. */ int check_lines(line *line1, line *line2, point *hitp) { /* Introduction: * This code is based on the solution of these two input equations: * Pa = P1 + ua (P2-P1) * Pb = P3 + ub (P4-P3) * * Where line one is composed of points P1 and P2 and line two is composed * of points P3 and P4. * * ua/b is the fractional value you can multiple the x and y legs of the * triangle formed by each line to find a point on the line. * * The two equations can be expanded to their x/y components: * Pa.x = p1.x + ua(p2.x - p1.x) * Pa.y = p1.y + ua(p2.y - p1.y) * * Pb.x = p3.x + ub(p4.x - p3.x) * Pb.y = p3.y + ub(p4.y - p3.y) * * When Pa.x == Pb.x and Pa.y == Pb.y the lines intersect so you can come * up with two equations (one for x and one for y): * * p1.x + ua(p2.x - p1.x) = p3.x + ub(p4.x - p3.x) * p1.y + ua(p2.y - p1.y) = p3.y + ub(p4.y - p3.y) * * ua and ub can then be individually solved for. This results in the * equations used in the following code. */ /* Denominator for ua and ub are the same so store this calculation */ int d = (line2->p2.y - line2->p1.y)*(line1->p2.x-line1->p1.x) - (line2->p2.x - line2->p1.x)*(line1->p2.y-line1->p1.y); /* n_a and n_b are calculated as seperate values for readability */ int n_a = (line2->p2.x - line2->p1.x)*(line1->p1.y-line2->p1.y) - (line2->p2.y - line2->p1.y)*(line1->p1.x-line2->p1.x); int n_b = (line1->p2.x - line1->p1.x)*(line1->p1.y - line2->p1.y) - (line1->p2.y - line1->p1.y)*(line1->p1.x - line2->p1.x); /* Make sure there is not a division by zero - this also indicates that * the lines are parallel. * * If n_a and n_b were both equal to zero the lines would be on top of each * other (coincidental). This check is not done because it is not * necessary for this implementation (the parallel check accounts for this). */ if(d == 0) return 0; /* Calculate the intermediate fractional point that the lines potentially * intersect. */ int ua = (n_a << 14)/d; int ub = (n_b << 14)/d; /* The fractional point will be between 0 and 1 inclusive if the lines * intersect. If the fractional calculation is larger than 1 or smaller * than 0 the lines would need to be longer to intersect. */ if(ua >=0 && ua <= (1<<14) && ub >= 0 && ub <= (1<<14)) { hitp->x = line1->p1.x + ((ua * (line1->p2.x - line1->p1.x))>>14); hitp->y = line1->p1.y + ((ua * (line1->p2.y - line1->p1.y))>>14); return 1; } return 0; }