Line-Segment Bezier-Curve Intersection

When describing a line-segment 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}}\) then is

\[\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;
}