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)

I don't have any code or anything, but the basic idea is this:

Using the points given, find the Slope of each line - call them mAB and mCD. You'd need a check to see if |mAB| = |mCD| but that's a trivial case.

Next using the points given, and the all-purpose Line Equation y = m*x + b, find bAB and bCD.

For the moment, treat the two segments as lines and find the X coordinate of the "intersection point". This is easily done by substituting for y and solving for x: x' = (bAB - bCD)/(mCD - mAB)

Next you have to check to see if this intersection point exists on BOTH segments. This is easily done by checking to see if Ax <= x' <= Bx, and Cx <= x' <= Dx (note: those <= signs could be >= signs if Ax>=Bx or Cx>=Dx but you can easily check which cases you are dealing with first)

Using x' solve for y' and repeat the segment-check with Ay, By, Cy and Dy.

At first I thought the x' check was all that was needed, but then I considered a vertical segment and another segment that passes over it such that if you only extended the vertical segment there would be an intersection. In this case x' = Ax = Bx, and would satisfy Cx <= x' <= Dx, so you would come to a false conclusion. That's why you need to check y' too.

If the format of my answer isn't "valid" for the Algorithms section, I apologize and please let me know so I don't do it again.

Later!

Posted by nikki on 2003-07-02 13:41:53