non-parametric quadratic Bézier curve through 3 points in 2D (in R)

Question

This is about explicit/non-parametric quadratic Bézier curves. Normally you can't fit a quadratic Bézier curve to 3 points because the X-variable is also a function (Bézier = parametric function), but when the control points are equidistant, you can: it is called an explicit/non-parametric Bézier function. I want to fit a quadratic bernstein polynomial to 3 random points in a 2D plane, and the x-axis coordinates of the 3 control points have to be equidistant. Also, the (outer) control points don't have to coincide with the 2 outer data points like they normally do.

I guess this requires solving a set of equations, but which ones? And how do I do that in R given the limitations I set (curve through the 3 data points, control points same horizontal distance, and control points not necessarily on the data points?

The quadratic Bézier function is B(t)=(1-t)^2*P0+2*t*(1-t)*P1+t^2*P2,

if you run this in R, you will see what I meant:

# control points are equidistant: here the horizontal distance is 20
cpx<-c(-20,0,20)
# y-values can be random
cpy<-c(0,2,-4)
t<-seq(0,1,len=101)

# the 3 control points
P0<-matrix(data=c(cpx[1],cpy[1]),nrow=1,ncol=2,byrow=FALSE,dimnames=NULL)
P1<-matrix(data=c(cpx[2],cpy[2]),nrow=1,ncol=2,byrow=FALSE,dimnames=NULL)
P2<-matrix(data=c(cpx[3],cpy[3]),nrow=1,ncol=2,byrow=FALSE,dimnames=NULL)

# the quadratic Bernstein polynomial:
B<-(1-t)^2%*%P0+2*t*(1-t)%*%P1+t^2%*%P2

par(mfrow=c(1,1))
plot(cpx,cpy,type="p",pch=20,xlab="",ylab="")
abline(v=c(min(cpx),max(cpx)),lty=3,col='red')
text(cpx[1],cpy[1],"P0",cex=.8,pos=4)
text(cpx[2],cpy[2],"P1",cex=.8,pos=1)
text(cpx[3],cpy[3],"P2",cex=.8,pos=2)
segments(cpx[1],cpy[1],cpx[2],cpy[2],lty=3);segments(cpx[2],cpy[2],cpx[3],cpy[3],lty=3)
lines(B,col="DeepSkyBlue")

# 3 random points on the curve:
pnts<-sort(sample(1:length(t),3,replace=F),decreasing=F)
point1<-pnts[1]
point2<-pnts[2]
point3<-pnts[3]
points(B[point1,1],B[point1,2],col='orange',pch=20)
points(B[point2,1],B[point2,2],col='orange',pch=20)
points(B[point3,1],B[point3,2],col='orange',pch=20)
segments(B[point1,1],B[point1,2],B[point2,1],B[point2,2],lwd=2,col='orange',lty=1)
segments(B[point2,1],B[point2,2],B[point3,1],B[point3,2],lwd=2,col='orange',lty=1)

Here's a similar but not equal topic. Here and here some nice Bézier animations.

Richelieu

Answer 1

Normally you can't fit a quadratic Bézier curve to 3 points

A quadratic Bézier curve has 3 control points, which means it has 3 degrees of freedom and should be able to fit any 3 points without a problem. A linear Bézier curve would have trouble, but a quadratic or higher would be fine. To fit a parametric Bézier you need to specify t values for each of the points that you want to fit, but that is the only tricky bit.

If you want an explicit Bézier, we can probably do that. I assume that the points that you're trying to fit are going to be in your x range [-20..20] ?

If so, then the first thing you need to do is find the x value of each point you're fitting to, and then convert that to a t value. In your example your x range is [-20..20] and your t range is [0..1] if I'm reading your code correctly, so we'll need to normalize. Your t value is (x+20)/40.

Now that you have all 3 t values, you solve 3 equations for 3 unknowns, where the unknowns are the y values of the control points. The 3 equations all have the same form, specifically:

(1-tfit)^2*y0 + 2*tfit*(1-tfit)*y1 + tfit^2*y2 = yfit

where tfit is the t value of the point you're trying to fit, and yfit is the y value of the same point.

Solve the set of equations for y0, y1, and y2.

---

So, let's look at some sample data. We'll take as input your 3 data points:

d0 = (-4.8000, 0.3648)
d1 = (7.2000, -0.9792)
d2 = (8.4000, -1.1928)

We'll also take as input the range of your explicit quadratic bezier curve

rmin = -20
rmax = 20

Now we compute the t values for your data points

t0 = (d0.x - rmin) / (rmax - rmin)
t1 = (d1.x - rmin) / (rmax - rmin)
t2 = (d2.x - rmin) / (rmax - rmin)

More specifically, these are:

t0 = 0.38000000000000000
t1 = 0.68000000000000005
t2 = 0.70999999999999996

We now have 3 equations:

(1-t0)*(1-t0)*y0 + 2*(1-t0)*t0*y1 + t0*t0*y2 = d0.y
(1-t1)*(1-t1)*y0 + 2*(1-t1)*t1*y1 + t1*t1*y2 = d1.y
(1-t2)*(1-t2)*y0 + 2*(1-t2)*t2*y1 + t2*t2*y2 = d2.y

We are solving for y0, y1, and y2, which are the y values of the explicit bezier curve.

I had a LSQ solver handy so I used it, but other methods would work fine.

Here is the matrix I put in (A|b):

0.38440000000000002 0.47120000000000001 0.14440000000000000  | 0.36480000000000001
0.10239999999999996 0.43519999999999998 0.46240000000000009  | -0.97919999999999996
0.084100000000000022 0.41180000000000005 0.50409999999999999 | -1.1928000000000001

and here is the solution it produced:

y0 = -2.6513220228646483e-014
y1 = 2.0000000000000262
y2 = -4.0000000000000169

Hope that helps.. :)

Animadvert

Thanks for your reply, but " I assume that the points that you're trying to fit are going to be in your x range [-20..20] ?" No. I don't know where the control points are going to be, only that they have to be equidistant, and that the 3 X-axis coordinates of the data points are going to be between the X-axis coordinates of the control points. – Richelieu

I'd like to also add that I cover this in pomax.github.io/bezierinfo/#moulding (and the next section), with the source linked. You have a few degrees of freedom: for a quadratic curve, you get to pick which "t" value you want the "middle" point to represent, then it's a relatively straightforward solution. For cubic curves, you need to pick the "t" value, as well as the tangent vector, and then it's again a fairly straightforward solution. – Chericheria

"you get to pick which "t" value you want the "middle" point to represent", but what if this is not obvious, like in my question: this is not about fitting a non-parametric quadratic Bézier curve to 3 points: my outer control points don't coincide with my outer data points. I realize this is somehow different than most questions, but that's what makes it interesting, right? – Richelieu

"the 3 X-axis coordinates of the data points are going to be between the X-axis coordinates of the control points" - if the X-axis coordinates of the data points are unique, and between (or =) the min and max of the control points, that is enough for the approach to work. If you want to post some sample data points I could run you through an example. – Animadvert

Hi tfinniga, thanks for your kind proposal. Say the 3 points are: (-4.8000,0.3648);(7.2000 -0.9792);(8.4000,-1.1928) I know that these are on a quadratic non-parametric Bézier curve with control points (-20,0);(0,2);(20,-4). A step-by-step walk-through would come in handy to go from these 3 data points to the 3 control points. Thank you. – Richelieu

@Richelieu it's not generally reversible: even if you know the 3 point lie on a curve, that's not enough to reverse engineer the curve, you're still going to need that t value for the point between the start and end points, because there are literally infinite curves those three points can lie on without that degree of freedom clamped =) – Chericheria

MisterH, edited my answer to show you the solution on your example data. There's a bit of floating point noise, but it gets the correct answer. – Animadvert

@Pomax He's solving for an explicit bezier, which is a special case of the general parametric bezier. In an explicit bezier x == t, which consumes those degrees of freedom and produces a single unique answer. – Animadvert

@tfinniga: great step-by-step solution, but I don't know where the initial control points are, only that they are equidistant, and that the points fit a quadratic Bernstein polynomial.. What would you do in that case? – Richelieu

@Richelieu Well, if you're using an explicit Bezier curve, then you will need to manually specify a range of possible x values. I believe that the actual shape of the curve doesn't change if you select a different range, so maybe it doesn't matter for your application. You could just choose the xmin and xmax of your data. That would have the effect of truncating your curve to your data, although if you evaluate t outside of [0..1] then you can still get the entire curve. Your points are P0 = (d0.x, y0), P1 = ((d0.x+d1.x)/2, y1), P2 = (d2.x, y2). P1 will be at the midpoint in an explicit bezier – Animadvert

I am still struggling to do this in R.. Anyway, thanks again for the explanation. – Richelieu

I found an explanation that fits a quadratic Bézier to 3 points by only adjusting the middle control point: physicsforums.com/showthread.php?t=180711 – Richelieu

Yeah, moving the middle control point makes a lot of sense. You can set the first and last to be the first and last data point. Then you just need to solve one linear equation for the position of the middle control point. That's much simpler.. :) – Animadvert

If my initial 3 sample points (which are known to be on an explicit quadratic Bézier curve) are consecutive points (on the X-axis: if t goes from 0 to 1 in 101 steps, say the 36th, 37th & 38th value of t, being 0.35, 0.36 & 0.37), wouldn't that make it easier? – Richelieu

Yes, that'd be easier, mostly because the t value of the middle sample (t1) would be halfway in between the other two samples. There's probably a very simple closed-form equation that will give you the curve control points. – Animadvert