How to determine if a ray intersects a line?

Question

I'm trying to determine how you could check if a ray, given an origin and a direction, and a line, given 2 points (Not a line segment) intersect.

Ray: Origin(x,y), direction(x,y)

Line: point1(x,y), point2(x,y)

I thought about doing a case analysis, such as checking if they are parallel, check if the ray is to the left of the line then check the direction etc. but I believe there is a better way to do it involving the cross products.

I'm trying to write a program to do this check, but my issue lies with coming up with a method to perform this check. I'm kind of clueless as to doing an overly complicated case-analysis.

Answer 1

Let’s put some names to things. We have to origin of the ray $O(x_0,y_0)$ and its direction $\mathbf v(x_v,y_v)$. The two points on the line we’ll call $P_1(x_1,y_1)$ and $P_2(x_2,y_2)$. A simple way to proceed is to find the intersection $Q$ of the two lines and then compare the direction of $Q-O$ to $\mathbf v$.

Working in homogeneous coordinates, $\overline{P_1P_2}$ is $\mathbf l=(x_1,y_1,1)\times(x_2,y_2,1)$ and the line that contains the ray is $\mathbf m=(x_0,y_0,1)\times(x_v,y_v,0)$. Their intersection is $\mathbf l\times\mathbf m$. If the third element of the result is zero, then the lines are parallel. Otherwise, convert back to Cartesian coordinates by dividing through by this third coordinate to get $Q(x_q,y_q)$. Compute $Q-O$ and compare the sign of a non-zero component of this pair to the corresponding component of $\mathbf v$. If they’re the same, then the intersection lies on the ray.

Answer 2

Two lines through points $z_1,z_2$ and $z_3,z_4$ intersect at a point ($\overline{z}$ is the complex conjugate of $z$): \begin{align} z&= f_{\times}(z_1,z_2,z_3,z_4)= \frac{ (z_1-z_2)\,(\overline{z_3}\,z_4-\overline{z_4}\,z_3) -(z_3-z_4)\,(\overline{z_1}\,z_2-\overline{z_2}\,z_1) }{ (z_1-z_2)\,(\overline{z_3}-\overline{z_4}) -(z_3-z_4)\,(\overline{z_1}-\overline{z_2}) } \tag{1}\label{1} , \end{align} unless the denominator is zero, which is a special case that need to be treated separately.

If we set $z_1=0$, $z_2=d$ (direction of the ray), and the endpoints of given segment $A=z_3,\ B=z_4$, then \eqref{1} simplifies to

\begin{align} z&= \frac{d\,(\overline{A}\,B-\overline{B}\,A)}{ d\,(\overline{A}-\overline{B}) -\overline{d}\,(A-B)} \tag{2}\label{2} . \end{align}

Given that, consider two real numbers $t,\,s$ such that conditions \begin{align} z&=t\cdot d ,\\ \text{along with }\quad z&=(1-s)\cdot A+s\cdot B \quad\text{hold} . \end{align}

If $t\ge0$ and $s\in[0,1]$ then $z$ is the sought point.