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

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

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!