Path: utzoo!attcan!uunet!wuarchive!udel!princeton!gauss!markv
From: markv@gauss.Princeton.EDU (Mark VandeWettering)
Newsgroups: comp.graphics
Subject: Re: Intersections
Message-ID: <2953@idunno.Princeton.EDU>
Date: 30 Sep 90 19:28:06 GMT
References: <31960@nigel.ee.udel.edu>
Sender: news@idunno.Princeton.EDU
Reply-To: markv@gauss.Princeton.EDU (Mark VandeWettering)
Organization: Princeton University
Lines: 29

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?

You betray the fact that you are trying to represent your line as the 
typical y = mx + b type for form.  Much easier to deal with is a vector
equation P1 + t (P2 - P1), where P1 = {x1, y1}, and P2 = {x2, y2}, and 
t ranges between zero and one.

Given your segments L1 = P1 + s (P2 - P1) and L2 = P3 + t (P4 - P2), 
you need to find the s and t values where they are equal.  Well, this 
means that 	
		x1 + s (x2 - x1) = x3 + t (x4 - x3)
		y1 + s (y2 - y1) = y3 + t (y4 - y3)
	
which are two equations in two unknowns, which you can easily solve
by substituting one into the other.   The case where the lines are 
parallel is exactly when (x2 - x1) == (x4 - x3) and (y2 - y1) == 
(y4 - y3).  Otherwise they cross.

Conversion to integer math is left as an exercise, as I hate using machines
without blazingly fast floating point :-)

Mark