We are given the 2D coordinates of 2 points: the first point is where the ray starts and it goes through the second point. We are given another ray in the same way. How do we determine if they have a point of intersection? I would like to know the general algorithm and its explanation, don't mind about the extreme cases (e.g. when the rays have the same starting point). P.S. I saw a similar question on another stack exchange, but the answers did were not backed up by explanation.
3
-
$\begingroup$ All you need to do is to present these two straight lines as a set of points (x,y) depending on the parameter which is the length along the line. Then finding the intersection boils down to solving a small linear system, and from the determinant of it you can see it there is a solution. $\endgroup$– Maxim UmanskyDec 3, 2020 at 5:02
-
1$\begingroup$ You might find a previous question/answer helpful, see scicomp.stackexchange.com/a/18713/2107. It computes the intersection of two infinite lines. To handle the case of two semi-infinite rays, you only need to add some checks at the end (that s>0 and t>0). $\endgroup$– rchilton1980Dec 3, 2020 at 14:33
-
$\begingroup$ The distance between two skew lines is $|\vec a\times\vec b|$ which is the absolute value of the cross product. If the vectors are $\vec a =(a_x,a_y),\; \vec b=(b_x,b_y)$ then the cross product is $a_yb_x - b_ya_x$ which will be zero if the lines intersect. $\endgroup$– porphyrinDec 10, 2020 at 14:09
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
Not sure if it answers your question, but here's something I wrote a few years ago for a paper.
Let $\mathbf{p}_0$ and $\mathbf{p}_1$ be the end points of the first segment and let $\mathbf{q}_0$ and $\mathbf{q}_1$ be the end points of the second segment. Then the parametric equations of the two lines are $$ \mathbf{p}(t_p) = (1 - t_p) \mathbf{p}_0 + t_p \mathbf{p}_1 \quad \text{and}\quad \mathbf{q}(t_q) = (1 - t_q) \mathbf{q}_0 + t_q \mathbf{q}_1 \,. $$ At the point of intersection, $\mathbf{p} = \mathbf{q}$, i.e., $$ (1 - t_p) \mathbf{p}_0 + t_p \mathbf{p}_1 = (1 - t_q) \mathbf{q}_0 + t_q \mathbf{q}_1 \,. $$ Rearrangement of the equation gives $$ \mathbf{q}_0 - \mathbf{p}_0 = \begin{bmatrix}\mathbf{p}_1 - \mathbf{p}_0 & -(\mathbf{q}_1 - \mathbf{q}_0)\end{bmatrix} \begin{bmatrix} t_p \\ t_q \end{bmatrix} \,. $$ Therefore, $$ \begin{bmatrix} t_p \\ t_q \end{bmatrix} = \begin{bmatrix}\mathbf{p}_1 - \mathbf{p}_0 & -(\mathbf{q}_1 - \mathbf{q}_0)\end{bmatrix}^{-1} (\mathbf{q}_0 - \mathbf{p}_0) $$ Once we have solved for $t_p$ and $t_q$ we can find the point of intersection readily. If the intersection point is outside the $\mathbf{p}$ line then $t_p \notin [0, 1]$. Similarly, for the other segment, if the intersection point is outside the segment, then $t_q \notin [0, 1]$.
$\begingroup$
$\endgroup$
3
Since any two non-parallel lines must intersect somewhere (according to Euclid) I imagine that the OP intended a slightly different question. For example, do the rays intersect within the convex hull of the four given (really, implied) points? (the convex hull is the region enclosed by an elastic band stretched round all four points without crossing.) That is the problem solved by Biswajit Banerjee. You do need to know where the intersection is.
-
$\begingroup$ Rays are not lines. It is not the case that any two non-parallel rays must intersect. Rays have a starting point and extend to infinity in only one direction, not two. The convex hull of $p_0, p_1, q_0, q_1$ doesn't matter; the rays may intersect either inside or outside this hull. $\endgroup$ Dec 3, 2020 at 23:52
-
$\begingroup$ en.wikipedia.org/wiki/Ray_(geometry)#Ray A ray is not a line segment. A ray starting at $p_0$ and continuing to $p_1$ also continues infinitely beyond $p_1$. This is why they can intersect outside the convex hull of $p_0, p_1, q_0, q_1$. $\endgroup$ Dec 4, 2020 at 0:10
-
$\begingroup$ @causative. Ah Thank you for the explanation! $\endgroup$ Dec 4, 2020 at 0:20
$\begingroup$
$\endgroup$
If you only need to know whether the rays intersect, you don't have to find the point of intersection. The following may be more stable and efficient than solving the equations for the point of intersection, as it only involves subtraction and dot products, no division.
You have your first ray starting at $p_0$ and going in the direction of $p_1$ (and infinitely beyond $p_1$), and your second ray starting at $q_0$ and going in the direction of $q_1$ (and infinitely beyond $q_1$). Think about it visually. For a fixed $p_0$, $p_1$, and $q_0$, which values of $q_1$ result in an intersection? The answer is that $q_1$ must lie in a wedge-shaped region of the plane. One side of the wedge is the line between $q_0$ and $p_0$, and the other side of the wedge is parallel to the first ray. In the diagram, $q_1$ must be in the blue region for the rays to intersect.
We can express one side of the wedge by saying that $q_1$ must be on the same side of the $q_0$ to $p_0$ line as $p_1$ is. If $p_0 - q_0 = (l_x, l_y)$, then we can rotate $(l_x, l_y)$ 90 degrees to get a vector perpendicular to the line: $(-l_y, l_x)$. Then to check that $q_1$ and $p_1$ are on the same side, we check that $(q_1 - q_0) \cdot (-l_y, l_x)$ has the same sign as $(p_1 - q_0) \cdot (-l_y, l_x)$.
We can express the other side of the wedge by looking at the line passing through $q_0$ and $q_0 + (p_1 - p_0)$. $q_1$ and $p_1$ must be on the same side of this line. A vector parallel to the line is $p_1 - p_0 = (m_x, m_y)$ which we rotate 90 degrees to get $(-m_y, m_x)$. To check that $q_1$ and $p_1$ are on the same side of this line, we check that $(p_1 - q_0) \cdot (-m_y, m_x)$ has the same sign as $(q_1 - q_0) \cdot (-m_y, m_x)$.
So to sum up: the two rays intersect if and only if $(q_1 - q_0) \cdot (-l_y, l_x)$ has the same sign as $(p_1 - q_0) \cdot (-l_y, l_x)$, and $(p_1 - q_0) \cdot (-m_y, m_x)$ has the same sign as $(q_1 - q_0) \cdot (-m_y, m_x)$.
