Finding the formula for a parabola from the control points of a bezier

Question

I'm trying to write a program that can detect whether the mouse is inside the parabola defined by three Bezier control points. I first tried doing this by looping through each line in the "string art" Bezier and then detecting whether the mouse is on the correct side of each line. If it's on the correct side of each line, then it's inside the parabola. The two problems of that was that it was very slow and that it had a limited resolution. So I wanted to figure out a computationally simpler approach.

Now what I want to do is find the equation for the parabola created by the bezier and use an inequality to determine whether the mouse is inside or outside the parabola. I found this similar question, but the conclusion was that it was impossible as the parabola will almost always be rotated at some angle. However, according to this wikipedia article there is a general formula for a parabola that accounts for such rotations. I also found this question which again had the same problem.

Thus, I want to find out how to take the parametric equation of a bezier:

$P = A(1 - t)^2 + 2Bt(1 - t) + Ct^2$

(Where $P$ is a point on the Bezier and $A$, $B$, and $C$ are control points)

and turn it into an equation for a parabola probably of the form

$\frac{(ax+by+c)^2}{a^2+b^2} = (x-f_1)^2 + (y-f_2)^2$

The answer to this question suggests using implicitization to do basically the same thing, but the example (section 1.4.2) it gives is only for cubic beziers, and I don't know how to do implicitization myself to figure it out for a quadratic bezier. The other answer to that question includes a working example, but I can neither figure out how it works nor successfully replicate it on my own, partly because the link the article where the algorithm came from is down and partly because I'm just not good enough at math.

So how could I find an equation for the parabola created by a quadratic Bezier such that I could turn it into an inequality to determine whether a point is on the inside or outside of that curve?

(PS. If whatever solution you come up with only works with $0 \le t \le 1$ without coming up with an equation for the entire parabola, that's fine since my original program only needs to detect whether the mouse is in a 90 degree wedge bound by the section of the parabola created by the bezier)

Answer 1

Let

$$P_t = A(1 - t)^2 + 2Bt(1 - t) + Ct^2\tag{1}$$

be the parametric equation of Bézier curve $(B)$.

Here is a solution based on barycentric coordinates $(a,b,c)$ of point $M$ to be tested ; it relies on the following formula :

$$\left(\dfrac{1-t}{t}\right)^2 \ \ \iff \ \ t=\dfrac{1}{1+\sqrt{a/c}}\tag{2}$$

giving the value of parameter $t$ such that point

$$P_t = \text{line BM } \ \cap \ (B)$$

It remains plainly to test whether $BM/BP_t$ is $<1$ or $>1$.

Here is a figure showing it on random points (Matlab program) :

Explanation : Let us recall that (1) expresses naturally

$$(1 - t)^2, \ \ 2t(1 - t), \ \ t^2$$

as the barycentric cordinates of $P_t$ with respect to triangle $ABC$.

Let $(a,b,c)$ be the barycentric coordinates of point $M$.

As all points $(a',b',c')$ of line $BM$ are equally attracted by $A$ and by $C$, they are characterized by $a'/c'=a/c$, explaining relationship (2).

Now, how can we "short-circuit" barycentric coordinates ? Plainly by expressing them in "areal" terms :

$$a=\text{area MBC}, \ \ b=\text{area AMC}, \ \ c=\text{area ABM}\tag{3}$$

(no normalization needed for our purpose ; important : these areas are oriented areas).

---

Summary : being given $M$, one has to

1) compute ratio $ a/c = \text{area MBC}/\text{area ABM}$ (areas obtained by computing determinants)

2) apply formula (2) obtain $t$ (formula (2))

3) test whether $BM/BP_t \ \binom{<}{\geq}1.$

Remark : testing whether $M$ is inside triangle $ABC$ is easy using criteria $b=\text{area AMC}>0$ .

Answer 2

While Jean Marie's answer is less computationally expensive and better for my purposes, I figured that I would just post the answer I ended up coming up with since it gives the equation for the entire parabola in case anyone else needs to find the entire parabola.

Since the parametric equation splits up into two equations, one for $x$ and one for $y$, we can simply solve for $t$ and plug it into the second equation to check if the point $P$ satisfies the equation.

First, we can get the Bezier equation in quadratic form to solve for $t$

$P = A(1-t)^2 + 2Bt(1-t)+Ct^2$

$(C - 2B + A)t^2 + (2B - 2A)t + A - P = 0$

Thus, we can say that

$a = C - 2B + A$

$b = 2B - 2A$

$c = A - P$

which then gives us

$at^2 + bt + c = 0$

when substituted back in. Note that this still represents two equations. Let's split them up into their $x$ and $y$ equations now.

$a_xt^2 + b_xt + c_x = 0$

$a_yt^2 + b_yt + c_y = 0$

That equation can just be solved with the quadratic formula. We can use either one. I chose the $x$ one:

$t = \frac{2b_x + \sqrt{b_x^2-4a_xc_x}}{2a_x}$

I'm not sure why we use addition here (the quadratic equation says there should be two answers, one with addition and one with subtraction), but I've tested that subtraction doesn't work while addition does, so... yeah. Also note that if $a = 0$, then $t^2$ term cancels out leaving us with $t = -\frac{c_x}{b_x}$.

Now that we know $t$, we can substitute it into the other equation for $y$:

$a_yt^2 + b_yt + c = 0$

There are no unknown terms here, so if the equation is true, then the original point is on the parabola. To check which side of the parabola it's on, just check whether all that is $< 0$ or if its $> 0$.

A code version of this (in JavaScript) is as follows:

var A = [0, 0]; // Control Point 1
var B = [100, 100]; // Control Point 2
var C = [200, 0]; // Control Point 3
var P = [50, 50]; // Test Point

// P = A(1-t)^2 + 2Bt(1-t) + Ct^2
// P = A(1-2t+t^2) + 2Bt - 2Bt^2 + Ct^2
// P = A - 2At + At^2 + 2Bt - 2Bt^2 + Ct^2
// P = Ct^2 - 2Bt^2 + At^2 + 2Bt - 2At + A
// t^2(C - 2B + A) + t*(2B - 2A) + A - P = 0
// t^2*a + t*b + c = 0

var a = [
    C[0] - 2*B[0] + A[0],
    C[1] - 2*B[1] + A[1]
];
var b = [
    2*B[0] - 2*A[0],
    2*B[1] - 2*A[1]
];
var c = [
    A[0] - P[0],
    A[1] - P[1]
];
var t;

// t = (2*b.x +- sqrt(b.x*b.x - 4*a.x*c.x)) / (2*a.x)
// if a.x = 0
// t = - c.x / b.x

if (a[0] === 0) {
    t = - c[0] / b[0];
}
else {
    t = (2*b[0] + sqrt(b[0]*b[0] - 4*a[0]*c[0])) / (2*a[0]);
}

// t^2*a.y + t*b.y + c.y = 0

var pointIsInside = t*t*a[1] + t*b[1] + c[1] <= 0;

Answer 3

The second answer that you linked provides an algorithm that avoids an explicit implicitization. It references a Microsoft paper whose link is broken (as you noticed); you can find the paper here. According to this paper, we work in projective 2D space, so that the mouse position $(x,y)$ is converted into a 3-tuple $P:=(x, y, 1)$. To test inside vs. outside, first express your parametric Bézier equation $$ \begin{align} x&=a_xt^2+b_xt+c_x\\ y&=a_yt^2+b_yt+c_y \end{align}\tag1 $$ in matrix form $$ \begin{pmatrix}x&y&1\end{pmatrix}= \begin{pmatrix}1&t&t^2 \end{pmatrix} \begin{pmatrix}c_x &c_y&1\\ b_x&b_y&0\\ a_x&a_y&0\\ \end{pmatrix}.\tag2 $$ Writing $C$ for the $3\times3$ matrix on the RHS of (2), compute $$\Psi:=C^{-1}F,\tag3$$ where $F$ is the $3\times 3$ matrix $$F:=\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}.\tag4 $$ Now test the mouse position $P:=(x,y,1)$ by multiplying $P$ on the right by $\Psi$. This transforms $P$ into new coordinates $Q:=(u,v,1):=P\Psi$. Read off the $u$ and $v$ values from $Q$ and compute the discriminant $$f(u,v):=u^2-v.\tag5 $$ If the discriminant is negative, then $P$ lies inside the parabola; if it's negative, it's outside, and if zero then $P$ is on the parabola.

---

Here's a worked example: If the control points are $(1,0)$, $(0,0)$, and $(0,1)$, then the parametric equations for the Bézier curve are $x=(1-t)^2$ and $y=t^2$, giving the matrix $$ C:=\begin{pmatrix}1&0&1\\-2&0&0\\1&1&0\end{pmatrix}. $$ The transformation matrix $\Psi$ is then $$\Psi:=C^{-1}F=\begin{pmatrix}0&-\frac12&0\\0&\frac12&1\\1& \frac12&0\end{pmatrix} \begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}= \begin{pmatrix}-\frac12&0&0\\\frac12&1&0\\\frac12&0&1\end{pmatrix}. $$ To test the mouse position $P:=(x,y,1)$ we compute $$\begin{pmatrix}u&v&1\end{pmatrix}=P\Psi= \begin{pmatrix} \frac{-x+y+1}2 & y & 1 \end{pmatrix} $$ so the discriminant is $u^2-v=\left(\frac{-x+y+1}2\right)^2-y$. As a check, we can eliminate $t$ from the original parametric equations to obtain $\sqrt x + \sqrt y=1$, which implies $x +2\sqrt{xy}+y=1$ and $(x+y-1)^2=4xy$. This last equation is algebraically equivalent to $(x-y-1)^2=4y$; in other words the discriminant is zero for points on the Bézier curve.