0

I would like to ask whether there is a known way of finding the intersection of 2 vectors/segments. Suppose that you have a segment a consisting of 2 points: A[1,2], B[3,4] and a segment w consisting of: W[5,1], Q[2,3]

For example, if we have 2 segments, both given by 2 points:
AB: A[1,1], B[3,3]
CD: C[1,4], D[5,4]
They have no intersection but if we took into account the lines they form, they would have an intersection. I am asking about analytic solution for segments. Are there any formulas for this?

Thank you

samokosik
  • 1
  • Assuming neither is vertical (handle that case separately) and the lines are not parallel, you can assume the lines have equations $y=m_ix+b_i$ ($i=1,2$). If they meet at $(x_0,y_0)$, then $m_1x_0+b_1 = m_2x_0+b_2$. You should be able to go from there. – MPW Sep 27 '23 at 19:27

1 Answers1

1

Of course there are many ways of finding the intersection. This is a very common programming task. The way I usually approach it is parametrically: The points on the segment from $A$ to $B$ all have the form $$t \mapsto (1-t)A + tB = \big[(1-t)x_A + tx_B,(1-t)y_A + ty_B\big]$$ This can also be written as $A + t(B - A)$. In fact, the entire line through $A$ and $B$ can be parametrized this way. The points of the line segment correspond to values of $t$ between $0$ and $1$. The points on line on the opposite side $A$ from $B$ correspond to values of $t < 0$, while the points on the line on other side of $B$ from $A$ correspond to $t > 1$.

One can similarly parametrize the line through $W$ and $Q$ $$s \mapsto W + s(Q-W)$$.

Assuming the two lines intersect, there must be values of the parameters $t, s$ that both provide that same point of intersection. So $$A + t(B - A) = W + s(Q - W)$$ This vector equation is actually two equations in the coordinates: $$x_A + t(x_B - x_A) = x_W + s(x_Q - x_W)\\y_A + t(y_B - y_A) = y_W + s(y_Q - y_W)$$ This system can be solved for $t, s$: $$t = \frac{(y_A - y_W)(x_Q - x_W) - (x_A - x_W)(y_Q - y_W)}{(x_B - x_A)(y_Q - y_W)-(y_B - y_A)(x_Q - x_W)}\\ s = \frac{(x_W - x_A)(y_B - y_A)-(y_W - y_A)(x_B - x_A)}{(x_B - x_A)(y_Q - y_W)-(y_B - y_A)(x_Q - x_W)}$$

  • If the common denominator is $0$, the two lines are either parallel, or they are the same line.
  • If both $s$ and $t$ are between $0$ and $1$, the two segments intersect, and the point of intersection is $A + t(B-A) = W + s(Q - W)$.
  • Otherwise the two line segments do not intersect.
Paul Sinclair
  • 43,643