How to determine the bezier control points from calculated points with lossy approximation?

Question

I have a question about calculating the bezier controls for a curve. The problem is as the following image shows:

I have the red points in an ordered list, including C and D. I need to find F and E. The problem is that not every point has to be on the curve (the curve does not need to pass through any point, except for start and end). It just has to be an "approximation".

I've already read about the following:

• Finding the control point of bezier curves - only works with horizontal aligned handles, I don't have a midpoint to start from. Does also only find the user-visible control points, not F and E
• Parametric reconstruction of a NURBS curve - that's fine if you want to interpolate between the red points, but that's not my goal

So my thought on how to solve this was:

1. Calculate the furthest point from a line through C and D
2. If the number of points is even, look at the previous and next point in the list, determine which one is further away from the imaginary line and calculate the midpoint between them
3. Three points are not enough to get the shape of the curve, I need the value at 25% and 75%. Luckily there are several methods for determining this: uniformly spaced method, arc length and centripedal method.
4. Now I have 5 points (begin, 25%, mid, 75%, end) to describe my curve. I know the t values for each one. The curve should look like this:

From this, I need to somehow insert the points into the bezier formula and then reverse-calculate the control points ... how?

Thanks in advance for any hints.

Answer 1

I wrote up how to do this over on "A Primer on Bézier Curves" in the "Creating a curve from three points" section, although you probably need to read the preceding two sections as well because they explain the supporting theory and code.

The important information is the fact that for any given t, there is a fixed point on the line {start,end} that connects to your on-curve point Bezier(t). In the following image, for instance, point C is always at the same distance ratio from the start and end. It doesn't matter what the curve looks like based on where you've placed the control points: at the t=0.5 mark, C will always be always mid-way between start and end. Additionally, the ratio between the length of the line segment {C,Bezier(t)} and line segment {Bezier(t),A} are fixed. So, if you know those first two points C and Bezier(t) --which you do-- then you immediately know where A goes, so you have all the information needed.

With that, you can reconstruct the curve however you like, with your only free parameter being the tangent at t, or more precisely, the left and right interpolation distances. Without more than three points, that's pretty much a guessed value and there's a few "aesthetically pleasing" options but none of those apply in your case: you have a bunch of points around your chosen t value then you can make an educated guess about tangents based on those, and you can simply reconstruct the cubic Bezier using that information.

And the absence of information, the safe route is to pick distances based on where the De Casteljau's algorithm says the interpolation line segments lie, and picking their centers:

But given your data, you can get a much better fit.

Answer 2

Easiest would be a least squares approximation. If B(t) is the equation of the bezier, P_i are the points to approximate, t_i are the corresponding parameter values, you want to minimize LSQ = ∑_i||B(t_i)-P_i||² = ∑_i ((B_x(t_i)-P_xi)² + ((B_y(t_i)-P_yi)²). You can take the coordinates of F and E as variables, so you get four linear equations, in four variables: ∂/∂_Fx(LSQ)=0, ∂/∂_Fy(LSQ)=0, ∂/∂_Ex(LSQ)=0, ∂/∂_Ey(LSQ)=0. They can be solved using standard methods. To find the corresponding parameter values you can use a chord-length approximation, which gives good results: t_i = ||P_i - P_i-1||/total, total = ||D-P_n|| + ∑||P_i-P_i-1|| (take P₀=C). If you need the best approximation, you can refine the parameters with an iterative algorithm.