« funbyjohn.com — 2 august 2017

Deriving line segment intersection in 2D using Cramer's rule

A line can be described as the set of points $$\mathbf{p_s} + s(\mathbf{p_t} - \mathbf{p_s})$$ where $\mathbf{p_s} = \begin{pmatrix}x_1 \\ y_1\end{pmatrix}$ is the start point of the line segment that is contained in the line, and $\mathbf{p_t} = \begin{pmatrix}x_2 \\ y_2\end{pmatrix}$ is the end point of the line segment. The number $s$ represents how far along the line segment a point is located. If $s = 0$, we're at $\mathbf{p_s} + 0(\mathbf{p_t} - \mathbf{p_s}) = \mathbf{p_s}$. If $s = 1$, we're at $\mathbf{p_s} + 1(\mathbf{p_t} - \mathbf{p_s}) = \mathbf{p_s} + \mathbf{p_t} - \mathbf{p_s} = \mathbf{p_t}$. To simplify the expression, we can let $\mathbf{a} = \mathbf{p_t} - \mathbf{p_s} = \begin{pmatrix}x_2 - x_1 \\ y_2 - y_1\end{pmatrix}$ and then rename $\mathbf{p_s} \rightarrow \mathbf{p}$. Then our line is simply $\mathbf{p} + s\mathbf{a}$. Here's a demo to get some intuition of why this is a sensible definition:

Value of $s$: 0
As you can see, a point on the line lies on the line segment exactly if $0 \leq s \leq 1$.

Intersecting two line segments

Let the two lines be given as made up of the points $$\mathbf{p}+s\mathbf{a} = \begin{pmatrix}p_1 \\ p_2\end{pmatrix} + s\begin{pmatrix}a_1 \\ a_2\end{pmatrix} \,\,\,\,\textrm{and}\,\,\,\, \mathbf{q}+t\mathbf{b} = \begin{pmatrix}q_1 \\ q_2\end{pmatrix} + t\begin{pmatrix}b_1 \\ b_2\end{pmatrix}$$ Now, we're interested in knowing where these line segments intersect. To do this, we need to let them equal each other (that is, we want to find the vector $\begin{pmatrix}s \\ t\end{pmatrix}$ such that the lines intersect), and work from there: \begin{align} \mathbf{p} + s\mathbf{a} &= \mathbf{q} + t\mathbf{b} \\ -s\mathbf{a} + t\mathbf{b} &= \mathbf{p} - \mathbf{q} \\ s'\mathbf{a} + t\mathbf{b} &= \mathbf{p} - \mathbf{q} \end{align} where we let $s' = -s$ for the sake of saving our eyes! Then \begin{align} s'\mathbf{a} + t\mathbf{b} &= \mathbf{p} - \mathbf{q} \\ s'\begin{pmatrix}a_1 \\ a_2\end{pmatrix} + t\begin{pmatrix}b_1 \\ b_2\end{pmatrix} &= \begin{pmatrix}p_1 - q_1 \\ p_2 - q_2\end{pmatrix} \\ \begin{pmatrix}a_1 & b_1 \\ a_2 & b_2\end{pmatrix}\begin{pmatrix}s' \\ t\end{pmatrix} &= \begin{pmatrix}p_1 - q_1 \\ p_2 - q_2\end{pmatrix} \end{align} If that last step confuses you, look up matrix multiplication. Now our equation is on the form of an equation system $A\mathbf{x} = \mathbf{c}$, where $A$ is a $2 \times 2$ matrix. Such a matrix (a square matrix) has a number associated with it called the determinant $\textrm{det}(A)$. If $\textrm{det}(A) \ne 0$, our equation system has a unique solution, in other words: the lines intersect! To compute the determinant of a $2 \times 2$ matrix $\begin{pmatrix}a & b \\ c & d\end{pmatrix}$ you perform the following calculation: $$\textrm{det}\begin{pmatrix}a & b \\ c & d\end{pmatrix} = ad - bc$$ To solve the equation system we will be using a technique called Cramer's rule. It says that in order to get the value of the first variable ($s'$ in our case), you must substitute the first column in our matrix $A$ with our vector $\mathbf{c} = \begin{pmatrix}p_1 - q_1 \\ p_2 - q_2\end{pmatrix}$. We'll call this new matrix $A_1$. Similarly for the second variable (that is $t$), we'll take $A$ again and substitute the second column with $\mathbf{c}$ to get $A_2$. Now, according to Cramer's Rule the solution to our equation system is: $$s' = \frac{\textrm{det}(A_1)}{\textrm{det}(A)} = \frac{(p_1 - q_1)b_2 - (p_2 - q_2)b_1}{a_1 b_2 - a_2 b_1}$$ $$t = \frac{\textrm{det}(A_2)}{\textrm{det}(A)} = \frac{a_1(p_2 - q_2) - a_2(p_1 - q_1)}{a_1 b_2 - a_2 b_1}$$ Now remember to substitute $s'$ back to $s$, so we have $\begin{pmatrix}s \\ t\end{pmatrix} = \begin{pmatrix}-s' \\ t \end{pmatrix}$. We're not completely done though. Since $s = 0$ describes when the intersection is at the start of the first line segment, and $s = 1$ describes when it's at the end of the line segment, all values outside the interval $[0;1]$ will be outside the line segment. This leads to the condition that in order for the line SEGMENTS to intersect, we also need $$0 \leq s \leq 1 \,\,\textrm{and}\,\, 0 \leq t \leq 1$$ to hold. Here is an implementation in JavaScript, where the $s = -s'$ substitution is included:
	
// p, q are the starting points of the two lines.
// a, b are the differences between the end and start points of the lines.
// for example if p_s, p_t are two points that make up a line segment, same for q_s, q_t,
// then you'd use p_s and q_s as the arguments p and q in the function, and you'd calculate
// a and b like so:
let p_s = {x: 0, y: 0};
let p_t = {x: 100, y: 0};
let q_s = {x: 30, y: -70};
let q_t = {x: 30, y: 70};

let p = p_s;
let q = q_s;
let a = {x: p_t.x - p_s.x, y: p_t.y - p_s.y};
let b = {x: q_t.x - q_s.x, y: q_t.y - q_s.y};

// Computes s, t
function computeIntersection(p, a, q, b) {
let det = a.x * b.y - a.y * b.x;
if (det == 0) return [null, null];
let c1 = p.x - q.x;
let c2 = p.y - q.y;
return [
(c2 * b.x - c1 * b.y) / det,
(a.x * c2 - a.y * c1) / det
];
}

// Checks whether two line segments collide without providing intersection point
function segmentsIntersect(p, a, q, b) {
let [s, t] = computeIntersection(p, a, q, b);
if (s == null) return false;
return 0.0 <= s && s <= 1 && 0.0 <= t && t <= 1.0;
}

// Example of usage:
let [s, t] = computeIntersection(p, a, q, b);
if (s != null) {
// To get the collision point along p + sa you do:
let sPoint = {x: p.x + s * a.x, y: p.y + s * a.y};
// similarly for q + tb, you do:
let tPoint = {x: q.x + t * b.x, y: q.y + t * b.y};
// actually sPoint = tPoint, so you can use whichever you like.
console.log("s = %.1f, t = %.1f", s, t);
console.log("collision at (%.1f, %.1f)", sPoint.x, sPoint.y);
}


Let's make sure it works by trying it out in a demo!

Move your mouse around inside the demo to move the end point. Click inside the demo to move the start point.
If you'd like to know more about the math, the branch of mathematics used here is called linear algebra, and it is very useful! You'll find that a lot of primitive collisions tests are just applied linear algebra.