Ray-Line Segment Intersection Test in 2D

In the Point in Polygon Test post we used a Ray-Line Segment intersection test in order to figure out how many sides of the polygon intersected a test ray. This post will explain how that test was derived.

Problem

Find out if a ray with origin ${\bf o}$ and direction ${\bf d}$ intersects a line segment with end points ${\bf a}$ and ${\bf b}$.

This problem can be converted into a Ray-Ray intersection problem if you turn the line segment into a ray with origin ${\bf a}$ and direction ${\bf b - a}$ but we are not going to do that. Well we are, but not explicitly.

Solution

Checking if two things intersect involves finding out if they share at least one common point. The first step is to express the ray and the line segment as sets of points.

In parametric form, the ray becomes

${\bf x}_1(t_1) = {\bf o} + {\bf d}t_1$ for $t_1 \in [0, \infty)$.

The line segment on the other hand is

${\bf x}_2(t_2) = {\bf a} + ({\bf b} - {\bf a})t_2$ for $t_2 \in [0, 1]$.

Next we can set the two equations to be equal ${\bf x}_1(t_1) = {\bf x}_2(t_2)$ and find the values of $t_1$ and $t_2$. Since there are two dimensions the equality can be split into the $x$ and $y$ counterparts and give us two equations to solve for the two unknowns. Once $t_1$ and $t_2$ are calculated the ray and the segment intersect if $t_1 \geq 0$ and $0 \leq t_2 \leq 1$. Under these conditions the point of intersection is on both the ray and the line segment.

After Some Algebra

The solution simplifies very neatly if you make some substitutions. Let ${\bf v}_1 = {\bf o} - {\bf a}$, ${\bf v}_2 = {\bf b} - {\bf a}$ and ${\bf v}_3 = (-{\bf d}_y, {\bf d}_x)$. Intuitively, ${\bf v}_3$ is just the direction perpendicular to ${\bf d}$. The result:

$t_1 = \displaystyle\frac{|{\bf v}_2 \times {\bf v}_1|}{{\bf v}_2 \cdot {\bf v}_3}$

$t_2 = \displaystyle\frac{{\bf v}_1 \cdot {\bf v}_3}{{\bf v}_2 \cdot {\bf v}_3}$

The symmetry is pretty cool!

12 thoughts on “Ray-Line Segment Intersection Test in 2D”

1. Dani says:

Thanks, nice and clear, with correct explanation.

2. Thanks for your glorious post. Just to clarify, is ‘||’ in t_1 referring to determinant instead of absolute value?

1. Thanks! In $t_1$ the $||$ is just the norm of the cross product and not the absolute value. Since it’s in 2D you can just think of it as the determinant $\begin{vmatrix} \mathbf{v_2}\\ \mathbf{v_1} \end{vmatrix}$.

3. JC says:

Your algorithm only works when Ray is shooting from the origin?

1. Nope, the vector $\mathbf{o}$ above is the origin of the ray and not the coordinate system origin.

4. Scala says:

Your algorithm only works when Ray is shooting from the origin?
I tried this and it failed:
Ray(Point(10, 20), Point(20, 20)), LineSegment((30, 10), Point(30, 30))

1. Ray direction should be a unit vector. Otherwise $t_1$ is scaled by the length of the direction vector.

1. Scala says:

If I don’t use Vec2, will it be the same to replace Vec2 by Data Structure Point with x and y?

5. Good post :D! but it’s discussed only one side of segment’s winding order(this tutorial used clock winding order and create normal vector by right hand rule). I think for all environment, it need to add some code that check location relation of two vectors(v1 = b-a, v2 = o – a).
if v1 x v2 > 0 or < 0, v3 need changed.((-y,x) or (y, -x)).

This is my C++11 code

pair IsAndGetCrossRayAndSegment(const Ray& r, const Segment& s)
{
// r = ray, s = segment.
Vec2 v1 = r.start – s.start;
Vec2 v2 = s.end – s.start;
Vec2 v3;
if((s.dir).cross(r.dir) > 0)
v3 = r.dir.getRPerp(); // Vec2(y, -x);
else
v3 = r.dir.getPerp(); // Vec2(-y, x);

float t1 = abs(v2.cross(v1)) / v2.dot(v3);
float t2 = v1.dot(v3) / v2.dot(v3);

if( t1 0 && t2 < 1) return make_pair(true, Vec2(r.start + r.dir * t1));

return make_pair(false, Vec2::ZERO);
}

it works good.

6. Well, intuitively it looks that to find an intersection point is a harder problem than to just find out if a ray and a segment have it.
However this is not necessarily true. But I was curious if we can do this in more efficient way.

There are some well-established techniques of ray-casting to find out this. You can google it. Despite this I wanted to use vectors to achieve same results. So here is my logic.

If we have segment A-B, and ray going out of point O towards point M: The basic idea is to find out whether vector OM is “between” vectors OA and OB. To find out this we can use cross product as cross product is not commutative. If sign(OA x OM) == sign(OM x OB) then OM is between OA and OB and hence there is an intersection.

Cross product in 2D is only one determinant of matrix 2×2, so it’s pretty simple.

There is additional condition in this method that needs to be satisfied: projection of OM on (OA + OB) should NOT be in negative direction of (OA + OB). If you draw a sketch you easily get the idea of why.

So in pseudocode:

boolean rayIntersectsSegment(O, M, A, B) {
v1 = (A.x – O.x, A.y – O.y)
v2 = (B.x – O.x, B.y – O.y)
v3 = (M.x – O.x, M.y – O.y)

if (sign(v1 x v3) == sign(v3 x v2) && (v3 · (v1 + v2) > 0) return true;
return false;
}

Where x denotes cross product in 2D:
double cross(v=(x1, y1), u=(x2, y2)) {
return x1*y2 – y1*x2;
}

Greg.

7. Oh, code in Java ( I have added some 10 unit tests for different situations including collinear placement of vectors etc..)

public static boolean linesIntersect(PointF A, PointF B, PointF O, PointF M) {
float v1[] = {A.x – O.x, A.y – O.y};
float v2[] = {B.x – O.x, B.y – O.y};
float v3[] = {M.x – O.x, M.y – O.y};
float v4[] = {A.x – M.x, A.y – M.y};
float v5[] = {B.x – M.x, B.y – M.y};

// Test if point is “below” line respective to O: (v1 + v2)•(v4 + v5) 0) return false;

// Otherwise point M is “above” line A-B, we need to test if its obscured
// Test: sign(v1 x v3) == sign(v3 x v2)
float crossV1V3 = v1[0]*v3[1] – v1[1]*v3[0];
float crossV3V2 = v3[0]*v2[1] – v3[1]*v2[0];
return (crossV1V3 < 0) == (crossV3V2 < 0);
}

8. sly says:

The formula is true only if v1.v2 >= 0.0 , other white the arbitrary direction of a-b (or b-a) change the sign of t.