Warning first, I have no formal mathematical education, I might butcher some of the terms below.
I've recently had to build an algorithm to find the intersections between two arbitrary paths. I managed to solve the equations for line to line, line to quadratic bezier and line to cubic bezier. For bezier to bezier I had to go with an approximation.
Naturally, I wanted to resolve it mathematically as well, however, I found out that there is no current way to do it. Then on all kinds of obscure places on the internet, people were saying it has been done, or that they have the solution, but I didn't found a proof. I'm a bit confused, I'm not sure if it's possible or not, it sure thing looks extremely difficult, but other difficult things have been solved before.
So I'm looking for authoritative answer on:
- Is there a solution for this?
- Will there ever be one? (where does the difficulty lie?)
- Is this moving in any direction? What are people looking at in order to solve it (if the idea was not abandoned already)
I'm guessing it might have something to do with the resulting polynomial high degree, which is impossible to solve?
EDIT: A bit of clarification:
Given the parametric quadratic bezier equation:
I would like to find all the t's at which b(x) = a(x) (basically, the intersection)
Here's how you'd do it with a line and a bezier:
Intersections Between a Cubic Bézier Curve and a Line
I'm looking for the next step, bezier to bezier.
Best Answer
Let $Q_k=(Q_{k,0},Q_{k,1})\in\mathbb R^2$ for $k=0,1,2$. And the same for $P_k\in\mathbb R^2$. Let $A=(A_1,A_2)$ be the Bezier curve with the points $Q_k$ and let $B=(B_1,B_2)$ be the Bezier curve with the points $P_k$.
Then Mathematica gives that $A_1(t)=B_1(t)$ is equivalent to (note that I am not assuming that $t\in[0,1]$ here, you will have to check that. Also, there are many conditions to avoid pathological cases such as the two Bezier curves being identical), where $\land$ is the logical and operator and $\lor$ is the logical or operator, $$\left(P_{0,0}+P_{2,0}+2 Q_{1,0}\neq 2 P_{1,0}+Q_{0,0}+Q_{2,0}\land \left(t=-\frac{\sqrt{-2 P_{1,0} Q_{1,0}+P_{2,0} Q_{0,0}+P_{0,0} \left(Q_{2,0}-P_{2,0}\right)+P_{1,0}^2+Q_{1,0}^2-Q_{0,0} Q_{2,0}}+P_{0,0}-P_{1,0}-Q_{0,0}+Q_{1,0}}{-P_{0,0}+2 P_{1,0}-P_{2,0}+Q_{0,0}-2 Q_{1,0}+Q_{2,0}}\lor t=\frac{\sqrt{-2 P_{1,0} Q_{1,0}+P_{2,0} Q_{0,0}+P_{0,0} \left(Q_{2,0}-P_{2,0}\right)+P_{1,0}^2+Q_{1,0}^2-Q_{0,0} Q_{2,0}}-P_{0,0}+P_{1,0}+Q_{0,0}-Q_{1,0}}{-P_{0,0}+2 P_{1,0}-P_{2,0}+Q_{0,0}-2 Q_{1,0}+Q_{2,0}}\right)\right)\lor \left(P_{0,0}+P_{2,0}+2 Q_{1,0}=2 P_{1,0}+Q_{0,0}+Q_{2,0}\land P_{1,0}+Q_{2,0}\neq P_{2,0}+Q_{1,0}\land t=\frac{2 P_{1,0}-P_{2,0}-2 Q_{1,0}+Q_{2,0}}{2 \left(P_{1,0}-P_{2,0}-Q_{1,0}+Q_{2,0}\right)}\right)\lor \left(P_{2,0}=Q_{2,0}\land P_{1,0}=Q_{1,0}\land P_{0,0}=Q_{0,0}\right)$$ and analogously $A_2(t)=B_2(t)$ is equivalent to $$\left(P_{0,1}+P_{2,1}+2 Q_{1,1}\neq 2 P_{1,1}+Q_{0,1}+Q_{2,1}\land \left(t=-\frac{\sqrt{-2 P_{1,1} Q_{1,1}+P_{2,1} Q_{0,1}+P_{0,1} \left(Q_{2,1}-P_{2,1}\right)+P_{1,1}^2+Q_{1,1}^2-Q_{0,1} Q_{2,1}}+P_{0,1}-P_{1,1}-Q_{0,1}+Q_{1,1}}{-P_{0,1}+2 P_{1,1}-P_{2,1}+Q_{0,1}-2 Q_{1,1}+Q_{2,1}}\lor t=\frac{\sqrt{-2 P_{1,1} Q_{1,1}+P_{2,1} Q_{0,1}+P_{0,1} \left(Q_{2,1}-P_{2,1}\right)+P_{1,1}^2+Q_{1,1}^2-Q_{0,1} Q_{2,1}}-P_{0,1}+P_{1,1}+Q_{0,1}-Q_{1,1}}{-P_{0,1}+2 P_{1,1}-P_{2,1}+Q_{0,1}-2 Q_{1,1}+Q_{2,1}}\right)\right)\lor \left(P_{0,1}+P_{2,1}+2 Q_{1,1}=2 P_{1,1}+Q_{0,1}+Q_{2,1}\land P_{1,1}+Q_{2,1}\neq P_{2,1}+Q_{1,1}\land t=\frac{2 P_{1,1}-P_{2,1}-2 Q_{1,1}+Q_{2,1}}{2 \left(P_{1,1}-P_{2,1}-Q_{1,1}+Q_{2,1}\right)}\right)\lor \left(P_{2,1}=Q_{2,1}\land P_{1,1}=Q_{1,1}\land P_{0,1}=Q_{0,1}\right).$$
We have $A(t)=B(t)\iff A_1(t)=B_1(t)\land A_2(t)=B_2(t)$.