Intersection between two parametric cubic functions?

Question

If I have two parametric cubic functions in 2D space defined by $$\vec r(t) = \vec A_1t^3 + \vec B_1t^2 + \vec C_1t + \vec D_1$$ and $$\vec q(t) = \vec A_2t^3 + \vec B_2t^2 + \vec C_2t + \vec D_2$$ how can I find all the points of intersection $$\vec P_0, \vec P_1, ..., \vec P_n$$ between them?

Answer 1

Method 1:

You can convert one of the cubics to implicit form (a cubic equation) and plug the parametric equation of the second. Solve the resulting nonic polynomial equation and check that $t$ is in the useful range.

If you survive, you get a medal.

Method 2:

Convert the cubics to Bezier form and use the hull property to design a recursive split algorithm: if the two bounding boxes* of the control points overlap, split both curves (using the De Casteljau formula) and repeat with the four combinations. Do this recursively until the boxes are small enough (of finish with Newton).

*In principle you should use the convex hulls, but the extra complexity of constructing and intersecting the hulls is not worth the effort.

Answer 2

In principles, if $r_x,r_y, q_x, q_y$ are the coordinates of $\vec r, \vec q$, you have to find $(t_1, t_2) \in \mathbb R^2$ such that

$$\begin{cases} r_x(t_1)&= q_x(t_2)\\ r_y(t_1)&= q_y(t_2) \end{cases}$$

You have two variables and two equations... which looks good. This is the theory in a couple of lines. Now, if you're interested in solving the problem with a computer, I suggest that you Google

planar curves intersection algorithm computer aided design

as it is a very common topic in computer aided design.

You may have a look to open source package named OPEN CASCADE.

Answer 3

Look at these notes by Tom Sederberg. Chapter 7 is all about intersecting polynomial curves.