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 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 intersects (Ax, Ay, Bx, By, Cx, Cy, Dx, Dy)
' Lines segments are AB and CD
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 noncoincident 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 20030701 09:45:39 