2
$\begingroup$

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:

  1. Is there a solution for this?
  2. Will there ever be one? (where does the difficulty lie?)
  3. 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:

enter image description here

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.

$\endgroup$
  • 1
    $\begingroup$ Can you maybe post the equation you want to solve? Are you looking for $x,y$ such that $${\bf a}(x)={\bf b}(y)$$ where $${\bf a}(t) = ({\bf a}_0 - 2{\bf a}_1 + {\bf a}_2)t^{2} + (-2{\bf a}_0 + 2{\bf a}_1)t + {\bf a}_0$$ and similarly for $\mathbf b$ and $\mathbf a_0,\mathbf a_1,\mathbf a_2,\mathbf b_0,\mathbf b_1,\mathbf b_2\in \mathbb R^2$ are given points? $\endgroup$ – User Jan 17 at 23:15
  • 1
    $\begingroup$ The intersection of 2 quadratic (resp. cubic) Bezier curves gives rise to a $2 \times 2 = 4$th (resp. $3 \times 3=9$th) degree polynomial equation. See the rather old link : groups.google.com/forum/#!msg/comp.graphics.algorithms/… (They mention a "Sturm sequence" which has interest only if you want to do arbitrary precision computation) $\endgroup$ – Jean Marie Jan 17 at 23:45
  • 1
    $\begingroup$ @MaximilianJanisch Sorry for explaining this without mathematical terms, I've edited the question. Feel free to edit further if not clear enough. $\endgroup$ – Valentin Radu Jan 17 at 23:47
  • 1
    $\begingroup$ @JeanMarie But that means, at least for quadratic Beziers (4th degree) there is a general formula, right? So, I'll only need to approximate for the cubic. $\endgroup$ – Valentin Radu Jan 17 at 23:55
  • 2
    $\begingroup$ @ValentinRadu Indeed. If you want, I can give you a solution for the quadratic case in terms of radicals, but it is not so pretty $\endgroup$ – User Jan 17 at 23:58
1
$\begingroup$

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)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I am sorry but what meaning do you attach to square roots of combination of products of points or quotients of points ? You should at least say that this can have a meaning only when these points are considered as complex numbers (x,y)↔x+iy. $\endgroup$ – Jean Marie Jan 18 at 9:40
  • 1
    $\begingroup$ @JeanMarie I am considering products/quotients of real numbers only as $P_0=(P_{0,0},P_{0,1})\in\mathbb R^2$ and so on (maybe I should clarify the beginning a little more?) $\endgroup$ – User Jan 18 at 10:10
  • $\begingroup$ My bad, I hadn't looked properly ; I beg your pardon. I thought your second indices were for distinguishing the first from the second curve... $\endgroup$ – Jean Marie Jan 18 at 10:12
  • $\begingroup$ @JeanMarie No problem 😄 I have made a very small edit for clarity nonetheless $\endgroup$ – User Jan 18 at 10:30
1
$\begingroup$

To solve this problem, you have to find the roots of a quartic (degree 4) polynomial. There are formulas for solving quartics, but they are messy, as you can see from the other answer. What’s more important: if you write naive code that simply implements these formulas, it won’t work very well. Specifically, you’ll get problems with overflow and round-off, unless you’re careful. I’d recommend that you go find a good quartic solver, written by an expert, rather than trying to write one yourself. One example here.

Alternatively, use numerical methods. You said you did this, and you refer to it as an “approximation”. If your code uses standard floating-point arithmetic, then almost everything is an approximation. Numerical methods will often give you more accurate answers that big messy formulas.

| cite | improve this answer | |
$\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.