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.)
re(2): No Code, just theory | Comment 15 of 20 |
(In reply to re: No Code, just theory by Charlie)


Good points! As you could probably tell from my writing, I pretty much skipped over the parallel segments, trying to get to the details of the rest of the algorithm. I definitely didn't think those cases out. Thank you! =)

Hmmm, ok, here's a second try at the parallel segments part:

Since we have to worry about vertical segments (I'm pretty sure we shouldn't divide by zero in a program) we shouldn't go straight for the slopes mAB and mCD. First look at delta_x_AB and delta_x_CD. By checking to see if either of the delta_x's = 0, we can determine if we are dealing with one, two or no vertical segments.

If we are dealing with ONE vertical segment (keeping track of if it is AB or CD that is vertical - but for simplicity let's say it is AB for the explanation) we know what the x-coordinate of the "intersection" is. In this example it would be Ax (or Bx since they are equal). We find the line equation for CD: y = mCD*x + bCD. Using x'=Ax, solve for y'. Now follow the same check I had in my last posting for seeing if that "intersection" point exists on both segments.

If we are dealing with TWO vertical segments we know they are parallel. To find out if they are the same line, simply see if Ax = Cx. If they are not equal, then the segments do not intersect and you are done. If they are equal, you need to see if the segments overlap. Assuming Cy <= Dy (if not, then just flip all the inequalities):

-------------------------------------------------------------
If (Cy <= Ay <= Dy) OR (Cy <= By <= Dy) then the segments overlap. Else, they don't and there is no intersection.
-------------------------------------------------------------

I'm running out of room! Please see "re(2): No Code, just theory Part 2" for the rest =)

  Posted by nikki on 2003-07-07 13:04:14

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 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information