given coordinates of beginning and end of two intersecting line segments how do I find coordinates of their intersection?

Question

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.

Answer 1

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

Answer 2

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.