Date: Thu, 20 Apr 95 11:20:24 CDT From: rusin (Dave Rusin) To: smayo@iii1.iii.net Subject: Re: *fastest* intersection lines in 2 space? Newsgroups: sci.math In article <35c0.smail.smayo@iii.net> you write: >Given two lines with equations in Ax + By + C = 0, it isn't >hard to find out where they intersect, if they do. But Given Ax + By + C = 0 Dx + Ey + F = 0 compute det=AE-BD. The lines intersect if det<>0. The other case is much rarer an more ornery. If det=0, the lines are parallel -- each is perpendicular to the vector (A,B) [which I'm assuming is non-zero -- you _have_ excluded the "lines" 0x+0y+0=0 and 0x+0y+1=0, haven't you?]; parallel lines don't intersect unless they're equal, and they're only equal if they're equidistant from the origin, which distance is C/sqrt(A^2+B^2). So the parallel lines are equal iff C^2*(D^2+E^2)=F^2*(A^2+B^2). For non-parallel lines, the unique point of intersection is trivial: (x) ( E -B ) ( -C ) ( ) = (1/det) ( ) ( ) (y) (-D A ) ( -F ) in matrix form, that is, x=(BF-EC)/det and y=(CD-AF)/det. I think there's a way to compute det and the two numerators faster: that is, although there appear to be 6 products to compute, I think you can get by with fewer if you do a couple extra adds. You can't avoid the division although you can replace two divides by one reciprocation and two multiplies, which is faster on many machines -- especially if you are going to compute a lot of intersections and you know that det is the same for many of them. dave