5
$\begingroup$

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$
  • $\begingroup$ 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. $\endgroup$ – Dan Rust Apr 28 '13 at 10:03
  • $\begingroup$ I'm afraid you misunderstood me. In my case there are only two line segments. $\endgroup$ – user983447 Apr 28 '13 at 10:12
  • $\begingroup$ 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). $\endgroup$ – Dan Rust Apr 28 '13 at 10:19
2
$\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$
  • $\begingroup$ This fails when the lines are collinear and touch only at a vertex, like (-1, 2), (1, 2) and (1, 2), (2, 2). $\endgroup$ – Ben C. Leggiero Mar 8 '17 at 3:08
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$
0
$\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: 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

$\endgroup$
  • $\begingroup$ This fails when the lines are collinear and touch only at a vertex, like (-1, 2), (1, 2) and (1, 2), (2, 2). $\endgroup$ – Ben C. Leggiero Mar 8 '17 at 3:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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