Given An X Co-ordinate, How Do I Calculate The Y Co-ordinate For A Point So That It Rests On A Bezier Curve

I have a point (circled in pink) which has a known X co-ordinate and a known Y co-ordinate but the Y co-ordinate is incorrect. It is currently resting upon the point where the tar

Solution 1:

True maths answer: if you want precise answers, you need maths, the end; Bezier curves are parametric curves and can have multiple y values for a single x value (and vice versa) so you're not going to find those without actually understanding what you're doing.

The easier way to do this, imprecisely, as a programming exercise is to simply build coordinate LookUp Tables for each curve (e.g. {t=0 -> {x:...,y:...}, t=0.01 -> {x:...y:...}, ...}), and then simply search your LUT for a given x or y value in order to find (possibly multiple) corresponding y or x values. If you need y values for some x, you sort your LUT on x, and then do a binary search to find best matches. If you need x for some y, you sort on y and do the same.

Nice and simple.

But, if you want precise solutions, which as a programmer you really should care about, then what you want is to reorient the curve along the "line" you're trying to find values for (for instance, "all y values for some x" means you're looking for all intersections between the curve and the line (x=a, y=-inf)--(x=a,y=inf)) and then you simply check which t values you get when you do intersection detection.

If you want the actual true answers here, have a look at this Primer on Bezier Curves' section on intersection detection between curves and lines (which in turn relies on the section about root finding). If you're dealing with cubic curves, you'll need to understand how to align curves so that finding intersections is reduced to root finding, after which you need to run Cardano's algorithm to find the (possibly three) values you're interested in.

Solution 2:

Bezier curves are parametric

x(t)=fx(t)
y(t)=fy(t)

Where (x(t),y(t)) is point on Bezier curve, t is parameter and fx(),fy() are polynomial functions.

That means Bezier curves are not necessarily functions (can have multiple y values per single x). So you need to find all parameters t for such the x(t)=x0 where x0 is your x-coordinate.

As @Mike 'Pomax' Kamermans mentions in his answer you can use LUT or compute the roots of fx(t)-x0=0 (x0 moved to the other side of the equation x0 = fx(t)) polynomial algebraically.

There is also "simpler" option with use of approximation search (similar to binary search but usable also on non monotonic functions) which does not require too high math knowledge (but is slower of coarse). For example something like this C++ code:

double x0,y0;           // your point x0 valid y0 not yetdouble ax0,ax1,ax2,ax3; // cubic Bezier fx() polynomial coefficientsdouble ay0,ay1,ay2,ay3; // cubic Bezier fy() polynomial coefficientsdouble ee,x,t,tt,ttt;
approx aa;
for (aa.init(0.0,1.0,0.025,6,&ee); !aa.done; aa.step()) // search t
{
  t = aa.a;
  tt = t*t;
  ttt = tt*t;
  x = ax0 + ax1*t + ax2*tt + ax3*ttt; // compute the x=fx(t)
  ee = fabs(x-x0);              // compute error of solution for the approximation search
}
// here aa.a holds found `t0`
t = aa.a;
tt = t*t;
ttt = tt*t;
y0 = ay0 + ay1*t + ay2*tt + ay3*ttt; // compute the final y0=fx(t0)

If you need all the possible points then you need to recursively subdivide the search interval t=<0.0,1.0> to <0.0,t0) and (t0,1.0> until there is no new found solution.

[edit1] some more info (requested by Mike 'Pomax' Kamermans)

As 2D Bezier curves are not necessarily functions there may be more y values for single x coordinate. Like on this example:

The numbered blue points are control points of rendered 2D cubic Bezier curve. The yellow ones are found solutions with the recursion described above. Here some C++ example of this:

double x0;              // input x coordinate
List<double> y0;        // output y coordinatesdouble ax0,ax1,ax2,ax3; // cubic coefficientsdouble ay0,ay1,ay2,ay3;
double px0,px1,px2,px3; // control pointsdouble py0,py1,py2,py3;
//---------------------------------------------------------------------------boolfind_point(double t0,double t1,int layer)
    {
    approx aa;
    double ee,x,y,t,tt,ttt,dt;
    constdouble _zero=1e-4;    
    dt=0.025*(t1-t0); // approximation search step if (dt<=_zero) returnfalse; // stop if too small interval to search to avoid stack overflowsif (layer>10) returnfalse; // stop if too high recursion layer to avoid stack overflows (this also limits the max found solutionsfor (aa.init(t0,t1,dt,6,&ee); !aa.done; aa.step()) // search t
        {
        t  = aa.a;
        tt = t*t;
        ttt= tt*t;
        x  = ax0 + ax1*t + ax2*tt + ax3*ttt;    // compute the x=fx(t)
        ee = fabs(x-x0);                        // compute error of solution for the approximation search
        }
    // check the error of found solutionif (aa.e0>_zero) returnfalse;
    // here aa.aa holds found `t0`
    t  = aa.aa;
    // check bounds can cross the border a bitif (t<t0) returnfalse;
    if (t>t1) returnfalse;
    // add new solution
    tt = t*t;
    ttt= tt*t;
    y  = ay0 + ay1*t + ay2*tt + ay3*ttt;        // compute the final y0=fx(t0)
    y0.add(y);                                  // add to list of solutions// recursion to check for other solutions by dividing the interval by found solutionif (t0<t-dt) find_point(t0,t-dt,layer+1);
    if (t1>t+dt) find_point(t+dt,t1,layer+1);
    }
//---------------------------------------------------------------------------// here usagevoidtest()
 {
 // just compute the Bezier cubic polynomials from control points
 ax0=                              (    px0);
 ax1=                    (3.0*px1)-(3.0*px0);
 ax2=          (3.0*px2)-(6.0*px1)+(3.0*px0);
 ax3=(    px3)-(3.0*px2)+(3.0*px1)-(    px0);
 ay0=                              (    py0);
 ay1=                    (3.0*py1)-(3.0*py0);
 ay2=          (3.0*py2)-(6.0*py1)+(3.0*py0);
 ay3=(    py3)-(3.0*py2)+(3.0*py1)-(    py0);
 // Find the points from mouse x0 coordinate
 y0.num=0;              // clear found solutions list
 find_point(0.0,1.0,0); // recursively found solutions on interval t=<0,1> ,as highest recursion level 0
 }

This have a problem with vertical lines because there is infinite number of solutions there ... It will found just few of them instead. Otherwise is this safe to use. (added many checks so it should run smoothly)