Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

i need to find the intersection point of 2 line segments (lines are finite, i.e., they have end points).

e.g. segment 1 from x1,y1 to x2,y2 -- segment 2 from x3,y3 to x4,y4

you can assume m1 and m2 are the gradients of segment 1 and segment 2 respectively

similarly, c1 and c2 being the y-intercepts of segment 1 and segment 2 respectively

using 'y=mx+c' i can easily find the equations of both lines and then derive the intersection point from those equations and check if that point actually lies on both line segments (intersection point may not be between the end points).

my problem is when i calculate the gradients (m1 and m2) i do [y2-y1]/[x2-x1] there for if one of the lines is vertical then im gonna have problems. how can i deal with this?

another problem is that if the two segments intersect at a point which is also the same as one of the end points then i want to assume that they are not intersecting..

e.g. if segment 1 is from 2,3 to 3,7 and segment 2 is from 3,7 to 7,3 then i want to assume they dont intersect.

share|improve this question

migrated from stackoverflow.com Dec 9 '11 at 0:15

This question came from our site for professional and enthusiast programmers.

1 Answer 1

up vote 2 down vote accepted

Instead of taking x,y as the variables to solve for, write (x,y) = (x1,y1)+t(x2-x1,y2-y1) = (x3,y3)+u(x4-x3,y4-y3) and solve for t and u. Then it doesn't matter a bit whether your line segments are horizontal or vertical or whatever, and you can check for being within the segments just by looking at whether 0 < t < 1 and 0 < u < 1.

Note that if the line segments are parallel you'll get zero in your denominator, and if they're almost parallel you'll get something very small there; you may want to take care about that unless something in your setup guarantees that the line segments aren't close to being parallel.

share|improve this answer
    
I don't really understand what is actually being calculated by doing "(x,y) = (x1,y1)+t(x2-x1,y2-y1) = (x3,y3)+u(x4-x3,y4-y3)". Could you explain a bit more please? –  temelm Mar 9 '11 at 20:34
    
Sure. (And I'm sorry I was too terse.) An arbitrary point on (x1,y1)..(x2,y2) is (x1,y1) plus some multiple of (x2-x1,y2-y1), the vector between them. That is, it has the form (x1,y1) + t(x2-x1,y2-y1). Or, if you prefer, (x1+t(x2-x1),y1+t(y2-y1)). t=0 is the point (x1,y1); t=1 is the point (x2,y2); the line segment (as opposed to the whole line) consists of all such points with 0 <= t <= 1. Similarly for the other line segment. Similarly for the other line segment, but I gave the parameter another name. [... to be continued] –  Gareth McCaughan Mar 9 '11 at 22:33
    
[continuation of previous comment:] The point we're looking for is on both line segments, so it's equal to (x1,y1) + t(x2-x1,y2-y1) for some t and to (x3,y3) + u(x4-x3,y4-y3) for some u. Equating the two gives us two simultaneous equations in the variables t,u. Solving those gives us the intersection point. If the two line segments are parallel then the equations aren't independent and we either get no solutions (the lines are parallel) or infinitely many (they're actually the same line). –  Gareth McCaughan Mar 9 '11 at 22:34
    
i see now, thanks a lot :) –  temelm Mar 9 '11 at 22:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.