Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!swrinde!ucsd!ames!sgi!shinobu!odin!bruceh
From: bruceh@sgi.com (Bruce R. Holloway)
Newsgroups: comp.graphics
Subject: Re: Intersections
Message-ID: <1990Oct2.001141.11766@odin.corp.sgi.com>
Date: 2 Oct 90 00:11:41 GMT
References: <31960@nigel.ee.udel.edu>
Sender: news@odin.corp.sgi.com (Net News)
Organization: Silicon Graphics, Inc., Mountain View, CA
Lines: 42

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