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