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.)
Solution 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
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 (3)
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