All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Intersecting lines (Posted on 2003-07-01)
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)

 See The Solution Submitted by levik Rating: 4.0000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Algebraic Solution | Comment 1 of 20
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

 Search: Search body:
Forums (0)