Intersecting a line segment with a cubic Bézier curve is a small problem with an important distinction: solving for the infinite supporting line is not enough. Every candidate must lie both on the curve and between the two segment endpoints. Keeping those two tests separate leads to an algorithm that also handles vertical lines, endpoint contacts, and tangencies without special cases.
Drag the four curve controls or the two square segment endpoints below. The dashed line is infinite; the solid red part is the segment. Only intersections on the solid part are reported.
The Geometric Predicate
Let the segment endpoints be \(\mathbf A\) and \(\mathbf D\), with nonzero direction \(\mathbf d=\mathbf D-\mathbf A\). For vectors in the plane, define the scalar cross product
\[ \mathbf a\mathbin{\times}\mathbf b=a_xb_y-a_yb_x. \]
The oriented area function
\[ F(\mathbf X)=\mathbf d\mathbin{\times}(\mathbf X-\mathbf A) \]
is zero precisely when \(\mathbf X\) lies on the supporting line through \(\mathbf A\) and \(\mathbf D\). Its sign identifies the side of the line. Unlike a slope equation, this predicate performs no division and treats horizontal, vertical, and oblique lines identically.
Restricting the Curve to the Line
A cubic Bézier curve with controls \(\mathbf P_0,\ldots,\mathbf P_3\) is
\[ \mathbf B(t)=(1-t)^3\mathbf P_0+3(1-t)^2t\mathbf P_1 +3(1-t)t^2\mathbf P_2+t^3\mathbf P_3, \qquad 0\leq t\leq1. \]
The function \(F\) is affine, so applying it to the curve applies it independently to every control point. Write \(q_i=F(\mathbf P_i)\). The two-dimensional intersection problem then becomes the scalar Bernstein polynomial
\[ f(t)=F(\mathbf B(t)) =q_0(1-t)^3+3q_1(1-t)^2t+3q_2(1-t)t^2+q_3t^3. \]
A parameter \(t\) places the curve on the supporting line exactly when \(f(t)=0\). Expanding into the power basis gives
\[ f(t)=c_3t^3+c_2t^2+c_1t+c_0, \]
\[ \begin{aligned} c_3&=-q_0+3q_1-3q_2+q_3,\\ c_2&=3(q_0-2q_1+q_2),\\ c_1&=3(q_1-q_0),\\ c_0&=q_0. \end{aligned} \]
Solve this polynomial over the reals and retain roots in \([0,1]\). Leading coefficients can vanish, so a robust implementation reduces the equation to quadratic or linear form when necessary. A repeated real root represents tangency: the curve touches the line without crossing it. Numerically distinct approximations to the same repeated root must be clustered before points are returned.
What the Bernstein Coefficients Reveal
Expanding into the power basis is convenient for an analytic cubic solver, but the original coefficients \(q_0,\ldots,q_3\) contain geometric information that the expansion hides. Every Bernstein basis function is nonnegative on \([0,1]\), and their sum is one. Consequently, \(f(t)\) is a convex combination of its coefficients:
\[ \min_i q_i\leq f(t)\leq\max_i q_i, \qquad 0\leq t\leq1. \]
If all \(q_i\) are strictly positive or all are strictly negative, the curve cannot meet the supporting line. Mixed signs mean that a root is possible, not that one is guaranteed. More generally, the number of roots in the open interval, counted with multiplicity, cannot exceed the number of sign changes in the coefficient sequence. This variation-diminishing bound gives a cheap rejection and complexity test before any root is calculated.
Root Isolation by Subdivision
The same bound works on every parameter subinterval. Applying de Casteljau's algorithm at a split parameter produces the exact Bernstein coefficients of the left and right polynomial pieces; no sampling or interpolation is involved. A root-isolation algorithm therefore maintains a tree of parameter intervals:
- Start with \([0,1]\) and the coefficients \(q_i\).
- Discard an interval if the convex hull of its coefficients excludes zero.
- Accept it as an isolated root interval when its width is below the parameter tolerance.
- Otherwise split it with de Casteljau and process both children.
- Merge adjacent terminal intervals that represent the same multiple root.
Unlike endpoint sign tests, this procedure does not require a sign change and can therefore retain intervals containing tangential roots. A forced midpoint split also guarantees progress when a tighter clipping step fails to shorten the current interval sufficiently.
Bézier Clipping
Subdivision always halves an interval. Bézier clipping can often remove more. Because \(t=\sum_{i=0}^{n}(i/n)b_{i,n}(t)\), the graph \((t,f(t))\) is itself a planar Bézier curve with controls \(\mathbf Q_i=(i/n,q_i)\). Every root lies where this curve meets the horizontal axis, so the intersection of the control-point convex hull with that axis bounds the parameter values that can still contain roots.
For a polynomial of degree greater than three, an additional acceleration is to approximate it by a cubic, elevate that cubic back to the original degree, and bound the Bernstein coefficients of the residual by \(d\). The original graph is then trapped between the two cubic envelopes \(R_3(t)-d\) and \(R_3(t)+d\), and only intervals where those envelopes straddle zero survive. This approach is sometimes called cubic clipping. For the cubic intersection polynomial derived above, the approximation is already exact and \(d=0\), so the direct cubic solver is both simpler and more informative.
Clipping to the Finite Segment
A valid curve parameter still describes only a point on the infinite line. For each candidate \(\mathbf X=\mathbf B(t)\), project onto the segment direction:
\[ u=\frac{(\mathbf X-\mathbf A)\cdot\mathbf d}{\mathbf d\cdot\mathbf d}. \]
The point lies on the closed segment exactly when \(0\leq u\leq1\). Thus the complete result consists of pairs \((t,u)\): \(t\) locates the point on the Bézier curve and \(u\) locates the same point on the segment. This second interval test is what an infinite-line intersection omits.
Algorithm
function intersectSegment(curve, A, D) {
const d = { x: D.x - A.x, y: D.y - A.y };
const length2 = d.x * d.x + d.y * d.y;
if (length2 === 0) throw new RangeError('Segment endpoints must differ');
const q = curve.points.map(P =>
d.x * (P.y - A.y) - d.y * (P.x - A.x)
);
const coefficients = [
q[0],
3 * (q[1] - q[0]),
3 * (q[0] - 2 * q[1] + q[2]),
-q[0] + 3 * q[1] - 3 * q[2] + q[3]
];
return realPolynomialRoots(coefficients)
.filter(t => 0 <= t && t <= 1)
.map(t => {
const point = curve.get(t);
const u = ((point.x - A.x) * d.x + (point.y - A.y) * d.y) / length2;
return { ...point, t, u };
})
.filter(hit => 0 <= hit.u && hit.u <= 1);
} Production code should compare against scale-aware tolerances rather than exact zero, clamp roots that differ from an endpoint only by roundoff, and deduplicate repeated roots. The reusable implementation used by the figure is available in Bezier.js as curve.intersectsLine(A, D).
Degenerate and Non-Isolated Cases
- Zero-length segment: \(\mathbf A=\mathbf D\) makes the line direction undefined. Treat this as a separate point-on-curve problem or reject it explicitly.
- Coincident curve: if every \(q_i=0\), the whole Bézier curve lies on the supporting line. The roots are not isolated; intersecting two one-dimensional parameter intervals is then the correct problem.
- Endpoint contact: roots at \(t=0\) or \(t=1\), and segment parameters \(u=0\) or \(u=1\), are valid for closed curves and segments.
- Tangency: an even-multiplicity root touches the line without changing the sign of \(f\). Sign-change searches alone therefore miss valid contacts.
- Near-degeneracy: coefficient and interval tolerances must scale with the geometry. A single fixed world-space epsilon is unreliable across very small and very large coordinate systems.
Why the Reduction Matters
The line predicate converts planar geometry into one scalar polynomial while preserving the Bézier basis. For a degree-\(n\) curve the same construction produces a degree-at-most-\(n\) equation; only the root solver changes. Subdivision methods are useful at higher degree, but cubics permit direct real-root classification and preserve repeated tangencies that coarse polyline intersection can miss.
References
- [Farin2002]Gerald Farin, Curves and Surfaces for CAGD: A Practical Guide, fifth edition, Morgan Kaufmann, 2002.
- [Goldman2003]Ron Goldman, Pyramid Algorithms: A Dynamic Programming Approach to Curves and Surfaces for Geometric Modeling, Morgan Kaufmann, 2003.
- [SederbergNishita1990]Thomas W. Sederberg and Tomoyuki Nishita, Curve Intersection Using Bézier Clipping, Computer-Aided Design 22(9), 1990.