3
$\begingroup$

I'm trying to create an algorithm that could tell if a point lies on a Bézier curve (or very close to it) analytically.

I know that I can check if that's the case by solving $t$ for some ${x,y}$:

$x = a_x(1-t)^3 + 3b_xt(1-t)^2 + 3c_xt^2(1-t)+d_xt^3$

$y = a_y(1-t)^3 + 3b_yt(1-t)^2 + 3c_yt^2(1-t)+d_yt^3$

and if it has solutions in range $[0,1]$, then the point belongs to a Bézier.

$a_x, a_y, ... d_x, d_y $ are Bézier's start point, controls points and end point.

I know how to do that on a piece of paper if I substitute $a_x, a_y, ... d_x, d_y $ with some values, but I have no idea how to create an algorithm for doing that with my computer (mainly because I'm not able to combine polynomial terms since they are connected to $a_x, a_y, ... d_x, d_y $). Could someone please point me to a technique that can be used in such cases or to some source code that does what I want to achieve?

$\endgroup$
  • $\begingroup$ Another possibility is to find the point on the Bézier curve that is closest to the given point. $\endgroup$ – lhf Feb 8 '18 at 18:19
5
$\begingroup$

You have to eliminate ("Elimination" is an important keyword) variable $t$ in order to turn your parametric representation into a cartesian implicit equation $f(x,y)=0$, because it is easy to test if $f(x,y)=0$ or, more realisticaly, $ -\varepsilon < f(x,y) < + \varepsilon$ for some small $\varepsilon$.

How to do that ? The answer, adapted to computer programs, is : by using Sylvester's resultant. I refer you to the recent answer I made here in a similar case.

In order to simplify a little the computations, let us assume that the initial point ($t=0$) is the origin (it is always possible to do that), expanding formulas for $x$ and $y$ as polynomials in $t$ :

$$\begin{cases}U_xt^3+V_xt^2+W_xt-x=0\\ U_yt^3+V_yt^2+W_yt-y=0\end{cases}$$

$$\begin{cases}U_x&:=&3b_x-3c_x+d_x\\V_x&:=&3c_x-6b_x\\ W_x&:=& 3b_x\end{cases} \ \ \text{and} \ \ \begin{cases}U_y&:=&3b_y-3c_y+d_y\\V_y&:=&3c_y-6b_y\\ W_y&:=& 3b_y\end{cases}$$

one gets the following "determinantal" expression for $f$:

$$f(x,y)=\left|\begin{array}{rrrrrrrr} U_x&V_x&W_x&-x&0&0&0\\ 0&U_x&V_x&W_x&-x&0&0\\ 0&0&U_x&V_x&W_x&-x&0\\ 0&0&0&U_x&V_x&W_x&-x\\ U_y&V_y&W_y&-y&0&0&0 \\ 0&U_y&V_y&W_y&-y&0&0\\ 0&0&U_y&V_y&W_y&-y&0 \\ 0&0&0&U_y&V_y&W_y&-y \end{array}\right|=0.$$

You could leave it under this form if you use a software like Matlab. But if you have to do the operation $\approx10^9$ times, it is your interest to expand it once for all (using a CAS) in order to get a much more efficient formula.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I have added the explicit formula (in the case where $A$ is considered as the origin). $\endgroup$ – Jean Marie Feb 8 '18 at 17:41
  • $\begingroup$ We just had an exchange with @CADJunkie who advised to look at the works of Tom Sederberg. He has written a book (tom.cs.byu.edu/~557/text/cagd.pdf) avalable on line where you will find uses of resultants in the Bézier framework. $\endgroup$ – Jean Marie Feb 8 '18 at 18:23
  • $\begingroup$ Thank you very much! I thought that maybe there exists some efficient algorithm for doing that and I could use it in my application but it seems to me now that I should rather approximate curves with lines. But I'll implement what you described anyway, just to learn something new, so, once again, thank you! $\endgroup$ – liew Feb 8 '18 at 19:56
  • $\begingroup$ Thanks for your thanks... $\endgroup$ – Jean Marie Feb 8 '18 at 20:26
  • $\begingroup$ @JeanMarie Hi, I'm wondering if you might be able to provide a new link to that book you referred to? Seems that the link is dead >.< $\endgroup$ – netigger Oct 14 '18 at 17:17
0
$\begingroup$

See my answer to this question.

Elimination and implicitization are the key ideas, as @Jean Marie points out.

The comments mention these notes by Tom Sederberg. In those notes, you will find some very simple techniques for "inversion" of polynomial and rational curves, based on the use of resultants. Specifically, on page 200, you will find a formula for doing "inversion" of a cubic curve written in Bezier form, and there's a nice worked example on page 201. This is exactly what you need.

Sederberg's approach is somewhat simpler than the Sylvester resultant, and it does not require converting the curve into algebraic form. The conversion occasionally causes numerical problems, though it should be OK with cubic curves.

If the given point (call it $\mathbf{P}$) is not exactly on the curve, you can apply the inversion formula, anyway, and it will give you some value of $t$. I'm not 100% sure what point this value of $t$ represents. I don't think it's the point on the curve that's closest to $\mathbf{P}$, but it should be good enough if $\mathbf{P}$ is already very close to the curve.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ You are right in that Bezout's resultant is more "economical" than Sylvester's resultant. $\endgroup$ – Jean Marie Feb 15 '18 at 21:47

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.