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
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);
}
Move your mouse around inside the demo to move the end point. Click inside the demo to move the start point.