# Ray-Line Segment Intersection Test in 2D

#### Posted on June 20th, 2014

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 and direction intersects a line segment with end points and .

This problem can be converted into a Ray-Ray intersection problem if you turn the line segment into a ray with origin and direction 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

for .

The line segment on the other hand is

for .

Next we can set the two equations to be equal and find the values of and . Since there are two dimensions the equality can be split into the and counterparts and give us two equations to solve for the two unknowns. Once and are calculated the ray and the segment intersect if and . 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 , and . Intuitively, is just the direction perpendicular to . The result:

The symmetry is pretty cool!

## October 13, 2014 at 3:10 pm

Thanks, nice and clear, with correct explanation.

## October 28, 2014 at 10:19 pm

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

## October 28, 2014 at 10:29 pm

Thanks! In 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 .

## February 16, 2015 at 10:20 pm

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

## February 16, 2015 at 10:37 pm

Nope, the vector above is the origin of the ray and not the coordinate system origin.

## February 16, 2015 at 11:30 pm

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))

## February 16, 2015 at 11:46 pm

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

## February 17, 2015 at 3:29 am

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

## August 17, 2015 at 3:56 am

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.

## October 13, 2016 at 2:25 pm

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.

## October 13, 2016 at 4:26 pm

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);

}