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)

The geometric solution checks that ACBD is a non-concave quadrilateral, after having checked a couple of special cases where an endpoint of one line coincides with that of another.

DECLARE FUNCTION norm# (x#)
DECLARE FUNCTION atan2# (y#, x#)
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 atan2 (y, x)
  IF x = 0 THEN
    atan2 = pi / 2 * SGN(y)
  ELSE
    IF x < 0 THEN
      atan2 = ATN(y / x) + pi
    ELSE
      atan2 = ATN(y / x)
    END IF
  END IF
END FUNCTION

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:
  'end point of one line is end point of another:
  IF Ax = Cx AND Ay = Cy OR Ax = Dx AND By = Dy OR Bx = Cx AND By = Cy OR Bx = Dx AND By = Dy THEN
    intersects = true: EXIT FUNCTION
  END IF

  angle1 = atan2(Cy - Ay, Cx - Ax)
  angle2 = atan2(By - Cy, Bx - Cx)
  angle3 = atan2(Dy - By, Dx - Bx)
  angle4 = atan2(Ay - Dy, Ax - Dx)
  a1 = norm(angle2 - angle1)
  a2 = norm(angle3 - angle2)
  a3 = norm(angle4 - angle3)
  a4 = norm(angle1 - angle4)
  
  ' check if end point of one line is along another line:
  IF a1 = 0 OR a2 = 0 OR a3 = 0 OR a4 = 0 THEN intersects = true: EXIT FUNCTION
  'check if all colinear but no overlap
  IF a1 = pi AND a2 = pi AND a3 = pi AND a4 = pi THEN
     intersects = false: EXIT FUNCTION
  END IF


  IF a1 > 0 OR a1 = 2 * pi THEN
    IF (a2 > 0 OR a2 = 2 * pi) AND (a3 > 0 OR a3 = 2 * pi) AND (a4 > 0 OR a4 = 2 * pi) THEN
      intersects = true
    ELSE
      intersects = false
    END IF
  ELSE
    IF (a2 < 0 OR a2 = 2 * pi) AND (a3 < 0 OR a3 = 2 * pi) AND (a4 < 0 OR a4 = 2 * pi) THEN
      intersects = true
    ELSE
      intersects = false
    END IF
  END IF
END FUNCTION

FUNCTION norm (x)
 n = x
 DO UNTIL n <= pi
   n = n - 2 * pi
 LOOP
 DO UNTIL n > -pi
   n = n + 2 * pi
 LOOP
 norm = n
END FUNCTION

Posted by Charlie on 2003-07-01 09:54:13