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.
$\endgroup$ 33 Answers
$\begingroup$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.
$\endgroup$ 1 $\begingroup$There is one omission in the method. If both segmenth are parallel to different axes, it may give wrong answer or don't calculate it at all. You may take for instance {{0,0},{0,-3}} and {{2,3},{2,-3}} And you should also consider the case when they are parallel
$\endgroup$ $\begingroup$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:
$\endgroup$ 1
