Finding parametric distance on quadratic curve from given $(x,y)$ point

Question

I want to get the parametric distance (the "$t$" value) at a location on a quadratic Bezier curve, given the "$x$" and "$y$" coordinates of the point.

I have start point, end point and control point of the curve.

How can I get it? Is there any direct formula to get the "$t$" value?

Please advice.

Answer 1

Bezier curves of a particular order have a closed form based on their control points. In the case of quadratics, that form is: $p = (1-t)^2 \cdot a + 2t(1-t) \cdot b + t^2 \cdot c$, where a, b, and c are the control points in order. Given the x value, you can solve $p_x = (1-t)^2 \cdot a_x + 2t(1-t) \cdot b_x + t^2 \cdot c_x$ for t. You can also do this for y; if the t values match up, then the point is on the quadratic curve.

Note that you can get 0, 1, or 2 values for t from each coordinate, most likely 2. This is perfectly okay: remember that from most directions, you will cross parabolas twice. Simply choose the t value that's in both.

Answer 2

Assuming you want to compute the shortest distance between a point $\vec P$ and a quadratic Bezier arc $\vec Q(1-t)^2+2t(1-t)\vec R+t^2\vec S$, $0<t<1$, you need to minimize $$\delta^2(t)=\min_{t,0<t<1}\left(\vec{PQ}(1-t)^2+2t(1-t)\vec{PR}+t^2\vec{PS}\right)^2.$$ Deriving with respect to $t$, you have $$\frac{d\delta^2(t)}{dt}=4\left(\vec{PQ}(t-1)+(1-2t)\vec{PR}+t\vec{PS}\right)\cdot\left(\vec{PQ}(1-t)^2+2t(1-t)\vec{PR}+t^2\vec{PS}\right).$$ Expanding, you will find a third degree polynomial that has one or three real roots. Keep the roots in $(0,1)$, compute the corresponding distances, and find the smallest among them, plus the distances to the endpoints, $\vec{PQ}^2$ and $\vec{PS}^2$.

Answer 3

Please see this answer. It covers the case of a cubic Bezier curve, but quadratic curves are even simpler, of course.

As that answer states, this "inversion" problem is covered thoroughly in these notes by Tom Sederberg. He provides techniques for "inversion" of polynomial and rational Bezier curves, based on the use of resultants.

Specifically, on page 200, you will find a formula for doing "inversion" of a quadratic curve written in Bezier form -- equation (17.5). If you look closely at the formulae for his quantities $l_{ij}$, you will see that they represent areas of triangles. This is to be expected, in view of my comment about barycentric coordinates above.

For both quadratic and cubic curves, the inversion equation is linear, so it just involves simple algebraic operations -- no quadratic equation solving, and no square roots.

Suppose we have a quadratic Bezier curve with control points $\mathbf{P}_i = (x_i, y_i, z_i)$, where $i=0,1,2$, and we have a given point $\mathbf{P} = (x, y, z)$. Then, using Sederberg's techniques, the "$t$" value corresponding to the point $\mathbf{P}$ can be calculated using the following simple code:

 c10 = (x - x1)*(y - y0) - (x - x0)*(y - y1)
 c20 = (x - x2)*(y - y0) - (x - x0)*(y - y2)
 t = c10/(c10 - 0.5*c20)

Here we use the symbols $c_{ij}$ instead of the $l_{ij}$ in Sederberg's notes, because the letter "l" causes confusion in code. Note that the computation requires nothing more than a few subtractions and multiplications, and one division.