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 {\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!

Share

Point in Polygon Test

Posted on May 26th, 2014

Given a polygon and a point, how do you tell if the point is inside or outside the polygon?

Idea

In 2D let’s think of the polygon as dividing the whole space into two regions. The finite region inside the polygon and the infinite region outside. Imagine yourself standing at the point which we wish to classify as being inside or outside. Next, pick a direction and start walking in a straight line. As you walk, keep track of the number of times you cross an edge of the polygon. After a long while when you are certain you have left the polygon behind, maybe at infinity, take a break and consider the number of times you crossed its edges.

Every edge crossing implies that you have either left or entered the polygon so it toggles your current state of being inside or outside. An odd number of crossings means that your current state is opposite of what it was when you started while an even number of crossings means it is the same. So as you take your break at infinity far outside of the polygon you know that if the number of crossings was odd you started on the inside and if it was even you started outside.

Implementation

Now let’s convert the idea into some code. Here is what a polygon looks like:

struct Polygon
{
    vec2 *Vertices;
    int   NumVertices;
};

A polygon is a list of vertices. The edges are implied by the order of the vertices with each pair of consecutive vertices forming an edge. In this case the algorithm translates to code fairly naturally:

// This function returns true if the ray with origin o and direction d intersects a line segment
// with endpoints a and b.
bool RayLineSegmentIntersection( const vec2 &o, const vec2 &d, const vec2 &a, const vec2 &b );

bool IsInside( const vec2 &point, const Polygon &polygon )
{
    int numCrossings = 0;

    // Loop over all edges in the polygon.
    for( int i = 0; i < polygon.NumVertices; ++i )
    {
        int j = ( i + 1 ) % polygon.NumVertices;

        // Check if a ray in the positive x direction crosses the current edge.
        if( RayLineSegmentIntersection( point, vec2( 1, 0 ), polygon.Vertices[ i ], polygon.Vertices[ j ] ) )
            ++numCrossings;
    }

    // If the number of crossings is odd, the point was inside the polygon.
    return ( numCrossings % 2 ) == 1;
}

The implementation above does exactly what we described. It shoots a ray from the point in question down the x axis(the direction doesn’t matter since a polygon will completely surround us if we’re inside) and counts how many edges it intersects. Then depending on the count the point is classified.

Ray-Line Segment Intersection Test

Here is a way to test a ray against a line segment. To get this result just set the ray \mathbf{x_1}(t_1)=\mathbf{o}+\mathbf{d}t_1 equal to the line segment \mathbf{x_2}(t_2)=\mathbf{a} + (\mathbf{b} - \mathbf{a})t_2 and solve for t_1, t_2. The ray will hit the line segment if t_1 \geq 0(line segment is in front of the ray) and 0 \leq t_2 \leq 1(the ray crosses the line segment between \mathbf{a} and \mathbf{b}).

bool RayLineSegmentIntersection( const vec2 &o, const vec2 &d, const vec2 &a, const vec2 &b )
{
    vec2 ortho( -d.y, d.x );
    vec2 aToO( o - a );
    vec2 aToB( b - a );

    float denom = dot( aToB, ortho );

    // Here would be a good time to see if denom is zero in which case the line segment and
    // the ray are parallel.

    // The length of this cross product can also be written as abs( aToB.x * aToO.y - aToO.x * aToB.y ).
    float t1 = length( cross( aToB, aToO ) ) / denom;
    float t2 = dot( aToO, ortho ) / denom;

    return t2 >= 0 && t2 <= 1 && t1 >= 0;
}

That is all there is to it. In a future post we’re going to revisit and solve this problem using some tricks!

Share