1
$\begingroup$

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?
$\endgroup$
2
$\begingroup$
  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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.