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 nonconcave 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 AZ
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 AB and CD
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 20030701 09:54:13 