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