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 the following function, I make use of a check that a given number n is between two other numbers a and b, by checking if (a - n)*(n - b)>=0, so as to avoid checking two possible orders of size.

If both segments are vertical, they can "intersect" only if they are at the same x coordinate, and then only if at least one of the endpoints of oneone line lies between the endpoints (y values) of the other.

If only one segment is vertical that segment must lie between the x limits of the other segment, and the equation of that line is computed and the y value at the vertical segment's x value must lie between that segment's end y values.

Otherwise the equations of the two lines are checked. If the lines are parallel (same slopes) they must be coincident for any intersection, and at least one end x coordinate of one must lie between the other segment's end x coordinates.

If the lines are not parallel, the point of intersection is found by solving simultaneously, and the x coordinate of the point of intersection must lie between the x coordinates of the endpoints for each of the two segments.

DEFDBL A-Z
DECLARE FUNCTION intersects# (Ax#, Ay#, Bx#, By#, Cx#, Cy#, Dx#, Dy#)
DIM SHARED pi

pi = ATN(1) * 4

DO
  INPUT x1, y1, x2, y2, x3, y3, x4, y4
  PRINT intersects(x1, y1, x2, y2, x3, y3, x4, y4)
LOOP

FUNCTION intersects (Ax, Ay, Bx, By, Cx, Cy, Dx, Dy)
  ' Lines segments are A-B and C-D
  false = 0: true = NOT false

  'exceptional cases first:
  IF Ax = Bx THEN
    IF Cx = Dx THEN ' both segments vertical
      IF Cx <> Ax THEN intersects = false: EXIT FUNCTION
      IF (Cy - Ay) * (By - Cy) >= 0 OR (Dy - Ay) * (By - Dy) >= 0 OR (Ay - Cy) * (Dy - Ay) >= 0 OR (By - Cy) * (Dy - By) >= 0 THEN
        'C between A and B or D between A and B or A between C and D or B between C and D
        intersects = true: EXIT FUNCTION
      ELSE
        intersects = false: EXIT FUNCTION
      END IF
    ELSE
      IF (Dx - Ax) * (Ax - Cx) < 0 THEN
        ' Ax not between Cx and Dx
        intersects = false: EXIT FUNCTION
      END IF
      slope = (Dy - Cy) / (Dx - Cx)
      yForx = slope * (Ax - Cx) + Cy
      IF (By - yForx) * (yForx - Ay) >= 0 THEN
        'line at Ax (which is also Bx) is between Ay and By
        intersects = true: EXIT FUNCTION
      ELSE
        intersects = false: EXIT FUNCTION
      END IF
    END IF
  ELSEIF Cx = Dx THEN
      IF (Bx - Cx) * (Cx - Ax) < 0 THEN
        ' Cx not between Ax and Bx
        intersects = false: EXIT FUNCTION
      END IF
      slope = (By - Ay) / (Bx - Ax)
      yForx = slope * (Cx - Ax) + Ay
      IF (Cy - yForx) * (yForx - Dy) >= 0 THEN
        'line at Cx (which is also Dx) is between Cy and Dy
        intersects = true: EXIT FUNCTION
      ELSE
        intersects = false: EXIT FUNCTION
      END IF
  ELSE
    slopeA = (By - Ay) / (Bx - Ax)
    slopeC = (Dy - Cy) / (Dx - Cx)
    IF slopeA = slopeC THEN
      yForx = slopeA * (Cx - Ax) + Ay
      IF yForx <> Cy THEN intersects = false: EXIT FUNCTION' parallel non-coincident lines
      ' what remains are segments sharing the same line
      IF (Cx - Ax) * (Bx - Cx) >= 0 OR (Dx - Ax) * (Bx - Dx) >= 0 OR (Ax - Cx) * (Dx - Ax) >= 0 OR (Bx - Cx) * (Dx - Bx) >= 0 THEN
        intersects = true: EXIT FUNCTION
      ELSE
        intersects = false: EXIT FUNCTION
      END IF
    ELSE
      x = (slopeA * Ax - slopeC * Cx + Cy - Ay) / (slopeA - slopeC)
      IF (Ax - x) * (x - Bx) >= 0 AND (Cx - x) * (x - Dx) >= 0 THEN
        ' x coord of point of intersection of lines is within
        ' x boundaries of both segments
        intersects = true: EXIT FUNCTION
      ELSE
        intersects = false: EXIT FUNCTION
      END IF
    END IF
  END IF

END FUNCTION

Posted by Charlie on 2003-07-01 09:45:39