# Line-Segment Bezier-Curve Intersection

When describing a line by two points $$\mathbf{A}=\left( \begin{array}{cc} A_x\\ A_y \end{array}\right)$$ and $$\mathbf{B}=\left( \begin{array}{cc} B_x\\ B_y \end{array}\right)$$, we can say that point $$\mathbf{P}=\left( \begin{array}{cc} x\\ y \end{array}\right)$$ is somewhere on that line. The slope of the line $$\vec{\mathbf{AB}}$$ and $$\vec{\mathbf{AP}}$$ is then

$\angle\vec{\mathbf{AB}} = \frac{A_y-B_y}{A_x-B_x}$

$\angle\vec{\mathbf{AP}} = \frac{y-A_y}{x-A_x}$

Since the points $$\mathbf{A}, \mathbf{B}$$ and $$\mathbf{P}$$ are colinear, the slopes $$\angle\vec{\mathbf{AB}}$$ and $$\angle\vec{\mathbf{AP}}$$ are equal, and thus

$\frac{A_y-B_y}{A_x-B_x}=\frac{y-A_y}{x-A_x}$

which can then be rewritten to

$\begin{array}{rrl} &(x-A_x)(A_y-B_y) &=(y-A_y)(A_x-B_x)\\ \Leftrightarrow& x(B_y-A_y)+y(A_x-B_x) &= A_x(B_y-A_y) + A_y(A_x-B_x)\\ \Leftrightarrow& \mathbf{v}\cdot \mathbf{P} &=d \end{array}$

with the vector $$\mathbf{v}=(B_y-A_y, A_x-B_x)$$.

On the other hand, a cubic Bezier curve with its control points $$\mathbf{C}_0, \mathbf{C}_1, \mathbf{C}_2$$ and $$\mathbf{C}_3$$ can be seen as

$\mathbf{C}(t)= (1-t)^3\mathbf{C}_0+3(1-t)^2t\mathbf{C}_1+3(1-t)t^2\mathbf{C}_2+t^3\mathbf{C}_3 \;\forall t\in [0, 1]$

Now substituting the line equation at our control points, yields

$\mathbf{C}(t)= (1-t)^3(\mathbf{v}\cdot \mathbf{C}_0 - d)+3(1-t)^2t(\mathbf{v}\cdot \mathbf{C}_1 - d)+3(1-t)t^2(\mathbf{v}\cdot \mathbf{C}_2 - d)+t^3(\mathbf{v}\cdot \mathbf{C}_3 - d)$

When rewriting the equation to a proper polynomial and setting the equation zero, we get

$0= \mathbf{v}\cdot(-\mathbf{C}_0 + 3 \mathbf{C}_1 - 3 \mathbf{C}_2 + \mathbf{C}_3) t^3+ \mathbf{v}\cdot( 3 \mathbf{C}_0 - 6 \mathbf{C}_1 + 3 \mathbf{C}_2) t^2 + \mathbf{v}\cdot(- 3 \mathbf{C}_0 + 3 \mathbf{C}_1) t + \mathbf{v}\cdot\mathbf{C}_0 - d$

This way the intersection problem becomes a root finding problem of a polynomial with degree 3.

## JavaScript Implementation

function lineBezier(A, B, C0, C1, C2, C3) {

const res = [];

const Ax = 3 * (C1.x - C2.x) + C3.x - C0.x;
const Ay = 3 * (C1.y - C2.y) + C3.y - C0.y;

const Bx = 3 * (C0.x - 2 * C1.x + C2.x);
const By = 3 * (C0.y - 2 * C1.y + C2.y);

const Cx = 3 * (C1.x - C0.x);
const Cy = 3 * (C1.y - C0.y);

const Dx = C0.x;
const Dy = C0.y;

const vx = B.y - A.y;
const vy = A.x - B.x;

const d = A.x * vx + A.y * vy;

const roots = cubicRoots(
vx * Ax + vy * Ay,
vx * Bx + vy * By,
vx * Cx + vy * Cy,
vx * Dx + vy * Dy - d
);

for (let t of roots) {
if (0 > t || t > 1) continue;
res.push({
x: ((Ax * t + Bx) * t + Cx) * t + Dx,
y: ((Ay * t + By) * t + Cy) * t + Dy
});
}
return res;
}

« Back to Book Overview