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