Intersection of cubic bezier curve and circle

Question

Let $B$ be a cubic Bézier curve with control points $P_0,P_1,P_2,P_3 \in \mathbb{R}^2$, and $C$ be a circle with center $P_C$ and radius $r$.

1. How can I find all intersections of $B$ and $C$?
2. Is there a fast heuristic algorithm to solve this problem?

Answer 1

1. The parametric equation for $B$ is $B(t) = (1-t)^3 P_0 + 3t(1-t)^2 P_1 + 3t^2(1-t) P_2 + t^3 P_3$. By projecting that onto $x$ and $y$ and adding the constraint of the circle's parametric equation you get a sextic $$\left( (1-t)^3 x_0 + \ldots + t^3 x_3 - x_C \right)^2 + \left( (1-t)^3 y_0 + \ldots + t^3 y_3 - y_C \right)^2 = r^2$$

   In general this won't be soluble algebraically, so you'll have to solve it numerically using a method like Newton-Raphson.

2. The convex hull property of Bézier curves and de Casteljau's algorithm give a good heuristic. Except when the curves almost touch or overlap only slightly, you'll get a quick answer; but you'll need to limit the level of recursion to handle the borderline cases (and that's where the heuristic element comes in).