Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!usc!apple!turk
From: turk@Apple.COM (Ken "Turk" Turkowski)
Newsgroups: comp.graphics
Subject: Re: Intersections
Message-ID: <10669@goofy.Apple.COM>
Date: 11 Oct 90 06:24:42 GMT
References: <31960@nigel.ee.udel.edu>
Organization: Advanced Technology Graphics, Apple Computer, Cupertino, CA, USA
Lines: 26

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