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}.

A ray pointing at a line segment
Will it intersect?

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.

Points on lines
Points on lines

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!

Ray-Line Segment Intersection Test in 2D

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

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

  2. 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.

  3. 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.

  4. 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);
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s