boutell@freezer.it.udel.edu (Tom Boutell) (10/01/90)
Having failed to find this one in the frequently asked questions cate- gory, I'm going to go ahead and post it. I need a decent algorithm for determining the intersections of lines. No, I haven't forgotten all my algebra (-:, but the standard formulas have something lacking when one *or* both lines are nearly vertical; the degree of error tends to be great. Is there an accepted solution to the problem for integer arithmetic, reliable down to one- pixel accuracy? -- What do you want from the fish of the fish that you fished when you fished for the fish that you fished? How many numchuks could Chuck chuck if Chuck could chuck numchuks? boutell@freezer.it.udel.edu? Or 27.598234821? Or not?
markv@gauss.Princeton.EDU (Mark VandeWettering) (10/01/90)
In article <31960@nigel.ee.udel.edu> boutell@freezer.it.udel.edu (Tom Boutell) writes: >Having failed to find this one in the frequently asked questions cate- >gory, I'm going to go ahead and post it. I need a decent algorithm >for determining the intersections of lines. No, I haven't forgotten >all my algebra (-:, but the standard formulas have something lacking >when one *or* both lines are nearly vertical; the degree of error >tends to be great. Is there an accepted solution to the problem for >integer arithmetic, reliable down to one- pixel accuracy? You betray the fact that you are trying to represent your line as the typical y = mx + b type for form. Much easier to deal with is a vector equation P1 + t (P2 - P1), where P1 = {x1, y1}, and P2 = {x2, y2}, and t ranges between zero and one. Given your segments L1 = P1 + s (P2 - P1) and L2 = P3 + t (P4 - P2), you need to find the s and t values where they are equal. Well, this means that x1 + s (x2 - x1) = x3 + t (x4 - x3) y1 + s (y2 - y1) = y3 + t (y4 - y3) which are two equations in two unknowns, which you can easily solve by substituting one into the other. The case where the lines are parallel is exactly when (x2 - x1) == (x4 - x3) and (y2 - y1) == (y4 - y3). Otherwise they cross. Conversion to integer math is left as an exercise, as I hate using machines without blazingly fast floating point :-) Mark
bruceh@sgi.com (Bruce R. Holloway) (10/02/90)
In article <31960@nigel.ee.udel.edu> boutell@freezer.it.udel.edu (Tom Boutell) writes: >Having failed to find this one in the frequently asked questions cate- >gory, I'm going to go ahead and post it. I need a decent algorithm >for determining the intersections of lines. No, I haven't forgotten >all my algebra (-:, but the standard formulas have something lacking >when one *or* both lines are nearly vertical; the degree of error >tends to be great. Is there an accepted solution to the problem for >integer arithmetic, reliable down to one- pixel accuracy? The equation of a line in 2-space may be expressed without any division as | x y 1 | | x1 y1 1 | = 0, | x2 y2 1 | where (x1,y1) and (x2,y2) are points on the line. This may also be written | x1 y1 | x(y1-y2) - y(x1-x2) + | x2 y2 | = 0. For a second line through (x3,y3) and (x4,y4), | x3 y3 | x(y3-y4) - y(x3-x4) + | x4 y4 | = 0. Solving simultaneously, | x1 y1 | | x3 y3 | | x2 y2 |(x3-x4) - (x1-x2)| x4 y4 | x = -----------------------------------, and | (x1-x2) (y1-y2) | | (x3-x4) (y3-y4) | | x1 y1 | | x3 y3 | | x2 y2 |(y3-y4) - (y1-y2)| x4 y4 | y = -----------------------------------, | (x1-x2) (y1-y2) | | (x3-x4) (y3-y4) | which can be evaluated with integer arithmetic of sufficient precision. Regards, bruceh
turk@Apple.COM (Ken "Turk" Turkowski) (10/11/90)
In article <31960@nigel.ee.udel.edu> boutell@freezer.it.udel.edu (Tom Boutell) writes: >Having failed to find this one in the frequently asked questions cate- >gory, I'm going to go ahead and post it. I need a decent algorithm >for determining the intersections of lines. No, I haven't forgotten >all my algebra (-:, but the standard formulas have something lacking >when one *or* both lines are nearly vertical; the degree of error >tends to be great. Is there an accepted solution to the problem for >integer arithmetic, reliable down to one- pixel accuracy? Good that you remember your algebra. Remember Gaussian elimination with partial or full pivoting from your elementary numerical methods course? You can cast the line intersection problem as a matrix equation: [x y] | A B | = [e f] | C D | With floating-point arithmetic, you can get away with partial pivoting (pivoting aroung the largest magnitude element in a row), but for fixed-point arithmetic, you need to do full pivoting (pivoting around the largest element in the matrix). -- Ken Turkowski @ Apple Computer, Inc., Cupertino, CA Internet: turk@apple.com Applelink: TURK UUCP: sun!apple!turk
chris@ncmicro.lonestar.org (Chris Arps) (10/12/90)
/* Intersection of two 2d lines - Chris Arps, NC Microproducts Inc. */
/* $Func - interltl() intersect two lines */
/* $Input - x1,y1 start point of line #1 */
/* x2,y2 end point of line #1 */
/* x3,y3 start point of line #2 */
/* x4,y4 end point of line #2 */
/* $Output - x5,y5 intersection point of two lines */
/* $Returns - < 0 no intersection due to parallel,too small, etc. */
/* x5,y5 are NOT computed */
/* 0 x5,y5 computed , line segments do not touch */
/* 1 x5,y5 computed , line segments touch */
#define ABSZERO 1.0E-10 /* tolerance for zero, works on PC/Sun */
int interltl(x1,y1,x2,y2,x3,y3,x4,y4,x5,y5)
double x1,y1,x2,y2,x3,y3,x4,y4;
double *x5,*y5;
{
extern double fabs(),sqrt();
double a1,b1,c1,a2,b2,c2;
double x,y,t0,t1;
a1 = y1 - y2;
b1 = x2 - x1;
c1 = x1*y2 - x2*y1;
a2 = y3 - y4;
b2 = x4 - x3;
c2 = x3*y4 - x4*y3;
y = a1*b2 - a2*b1;
x = a1 - a2;
if ( fabs(y) < ABSZERO) { /* parallel */
x = x1*y2 + x3*y1 + x2*y3 - x3*y2 - x1*y3 - x2*y1;
if ( fabs(x) < ABSZERO ) return -2; /* collinear */
return -1;
}
y = (a2*c1 - a1*c2) / y;
if ( fabs(x) < ABSZERO) return -3; /* both horizontal */
x = (b2*y - b1*y + c2 - c1) / x;
if ( fabs(x2-x1) < ABSZERO ) {
if (fabs(y2-y1) < ABSZERO ) return -4; /* line too small */
else t0 = (y - y1) / (y2 - y1);
}
else t0 = (x - x1) / (x2 - x1);
if ( fabs(x4-x3) < ABSZERO ) {
if (fabs(y4-y3) < ABSZERO ) return -4; /* line too small */
else t1 = (y - y3) / (y4 - y3);
}
else t1 = (x - x3) / (x4 - x3);
*x5 = x;
*y5 = y;
if ( t0 < ABSZERO || t0 > (1.0 - ABSZERO) ||
t1 < ABSZERO || t1 > (1.0 - ABSZERO) ) return 0;
return 1;
}