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)

Good points! As you could probably tell from my writing, I pretty much skipped over the parallel segments, trying to get to the details of the rest of the algorithm. I definitely didn't think those cases out. Thank you! =)

Hmmm, ok, here's a second try at the parallel segments part:

Since we have to worry about vertical segments (I'm pretty sure we shouldn't divide by zero in a program) we shouldn't go straight for the slopes mAB and mCD. First look at delta_x_AB and delta_x_CD. By checking to see if either of the delta_x's = 0, we can determine if we are dealing with one, two or no vertical segments.

If we are dealing with ONE vertical segment (keeping track of if it is AB or CD that is vertical - but for simplicity let's say it is AB for the explanation) we know what the x-coordinate of the "intersection" is. In this example it would be Ax (or Bx since they are equal). We find the line equation for CD: y = mCD*x + bCD. Using x'=Ax, solve for y'. Now follow the same check I had in my last posting for seeing if that "intersection" point exists on both segments.

If we are dealing with TWO vertical segments we know they are parallel. To find out if they are the same line, simply see if Ax = Cx. If they are not equal, then the segments do not intersect and you are done. If they are equal, you need to see if the segments overlap. Assuming Cy <= Dy (if not, then just flip all the inequalities):

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

I'm running out of room! Please see "re(2): No Code, just theory Part 2" for the rest =)

Posted by nikki on 2003-07-07 13:04:14