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.)
 Geometric Solution | Comment 2 of 20 |
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

 Search: Search body:
Forums (0)