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.

There are two line segments. I know for sure they intersect (so I don't have to check it). For both line segment I know coordinates of its both ends. With what formula can I find coordinates of their intersection?

I know the method I can use (find their lines' equations and solve them), but I'm lazy and I want just to have ready to use formula.

share|improve this question
    
If you can do it for one pair of line segments, you can do it for an arbitrary line segment by just solving equations with variable coefficients instead of static ones. Note that not all pairs of line segments intersect. –  Daniel Rust Apr 28 '13 at 10:03
    
I'm afraid you misunderstood me. In my case there are only two line segments. –  user983447 Apr 28 '13 at 10:12
    
I understand. Just let one line segment have ends $(x_1,y_1)$ and $(x_2,y_2)$ and the other line segment have ends $(u_1,v_1)$ and $(u_2,v_2)$. You can find the equations of the lines which contain these segments in cartesian coordinates. These lines will have an intersection as long as they are not parallel (although the intersection might not be on the pair of line segments unless you know they cross). –  Daniel Rust Apr 28 '13 at 10:19
add comment

2 Answers

up vote 0 down vote accepted

one line segment from $(x_1,y_1)$ to $(x_2,y_2)$

another line segment from $(x_3,y_3)$ to $(x_4,y_4)$

the set of points on the first line segment is $$A = \{ (x_1 + (x_2-x_1)u,y_1 + (y_2-y_1)u) \in \mathbb R^2 \mid u \in [0,1] \}$$

the set of points on the second line segment is $$B = \{ (x_3 + (x_4-x_3)t,y_3 + (y_4-y_3)t) \in \mathbb R^2 \mid t \in [0,1] \}$$

we want to find $$A \cap B$$ which means finding $u \in [0,1]$, $t \in [0,1]$ such that $$(x_1 + (x_2-x_1)u,y_1 + (y_2-y_1)u)=(x_3 + (x_4-x_3)t,y_3 + (y_4-y_3)t)$$

split into components

$$x_1 + (x_2-x_1)u=x_3 + (x_4-x_3)t$$

$$y_1 + (y_2-y_1)u=y_3 + (y_4-y_3)t$$

solve for $u$ by eliminating $t$

$$\frac{(x_1-x_3) + (x_2-x_1)u}{(x_4-x_3)}=\frac{(y_1-y_3) + (y_2-y_1)u}{(y_4-y_3)}$$

$$\frac{(y_4-y_3)(x_1-x_3) - (x_4-x_3)(y_1-y_3)}{(x_4-x_3)(y_2-y_1) - (y_4-y_3)(x_2-x_1)} = u$$

now you can find the intersection of two lines by calculating this $u$ and checking its between 0 and 1, then calculating t (which is easy once you know u) and checking it's also between 0 and 1.

share|improve this answer
add comment

While waiting for answer, I solved it myself as well - and found out it was simpler I thought. If coordinates of one segment is (x1, y1), (x2, y2) and coordinates of the other is (u1, v1), (u2, v2), then coordinates of their intersection is:

x = -1 * ((x1 - x2) * (u1 * v2 - u2 * v1) - (u2 - u1) * (x2 * y1 - x1 * y2)) / ((v1 - v2) * (x1 - x2) - (u2 - u1) * (y2 - y1))

y = -1 * (u1 * v2 * y1 - u1 * v2 * y2 - u2 * v1 * y1 + u2 * v1 * y2 - v1 * x1 * y2 + v1 * x2 * y1 + v2 * x1 * y2 - v2 * x2 * y1) / (-1 * u1 * y1 + u1 * y2 + u2 * y1 - u2 * y2 + v1 * x1 - v1 * x2 - v2 * x1 + v2 * x2)

Solved it using wolfram alpha: http://www.wolframalpha.com/input/?i=%28x2-x1%29%28y-y1%29%3D%28y2-y1%29%28x-x1%29%2C%28u2-u1%29%28y-v1%29%3D%28v2-v1%29%28x-u1%29+for+x%2C+y

share|improve this answer
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.