You are given two straight line segments, each defined by the coordinates of its endpoints. Segment AB goes from (Ax,Ay) to (Bx,By) and segment CD - from (Cx,Cy) to (Dx,Dy).

How would you determine if the two line segments intersect?

(Assume that you can't just draw the lines and see)

(In reply to re: No Code, just theory by Charlie)

Ok, when I left off last I was using the following if statment to determine if two vertical segments (that I had already determined existed on the same line) overlapped at all:

-------------------------------------------------------------
If (Cy <= Ay <= Dy) OR (Cy <= By <= Dy) then the segments overlap. Else, they don't and there is no intersection.
-------------------------------------------------------------

I am pretty sure that statement covers if the two segments touch endpoints, if the segments overlap a little, or if one segment is a subset of the other.

And finally, if we are dealing with NO vertical segments then we can check to see if mAB = mCD (since we know we aren't dealing with an infinite slope). If they are not equal, then go into the check I explained in my very first posting "No Code, just theory".

If they are equal, we next have to see if the two segments exist on the same line (this is very similar to the two vertical segments portion in "re(2): No Code, just theory"). We do this by solving for bAB and bCD in the two line equations, and checking to see if they are equal. If they are not equal, then the two segments do not exist on the same line, so there is no intersection. If they are equal then we have to check if the two segments overlap at all. Since the two segments have the same line equation, we only need to check either x-coordinates or y-coordinates (not both). The equation in the "box" up there can be used again to determine if the segments overlap at all.

Wow! I hope that covers it. I can't believe I thought the parallel line cases were trivial! Shame on me =)

Thanks Charlie!

Posted by nikki on 2003-07-07 13:08:33