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

Home > Algorithms
Intersecting lines (Posted on 2003-07-01) Difficulty: 3 of 5
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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (9)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information