How can I get a cubic bezier curve closest to given points?

Question

Given n points:

p0, p1, p2, ..., pn;

How can I get the point c1, c2 so that the cubic bezier curve defined by

p0, c1, c2, pn

closest to the given points?

I tried least square method. I wrote this after I read the pdf document in http://www.mathworks.com/matlabcentral/fileexchange/15542-cubic-bezier-least-square-fitting. But I can't find a good t(i) function.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows;

namespace BezierFitting
{
    class CubicBezierFittingCalculator
    {
        private List<Point> data;

        public CubicBezierFittingCalculator(List<Point> data)
        {
            this.data = data;
        }

        private double t(int i)
        {
            return (double)(i - 1) / (data.Count - 1);
            // double s = 0.0, d = 0.0;
            // 
            // for (int j = 1; j < data.Count; j++)
            // {
            //     if (j < i)
            //     {
            //         s += (data[j] - data[j - 1]).Length;
            //     }
            //     d += (data[j] - data[j - 1]).Length;
            // }
            // return s / d;
        }

        public void Calc(ref Point p1, ref Point p2)
        {
            double n = data.Count;
            Vector p0 = (Vector)data.First();
            Vector p3 = (Vector)data.Last();

            double a1 = 0.0, a2 = 0.0, a12 = 0.0;
            Vector c1 = new Vector(0.0, 0.0), c2 = new Vector(0.0, 0.0);
            for (int i = 1; i <= n; i++)
            {
                double ti = t(i), qi = 1 - ti;
                double ti2 = ti * ti, qi2 = qi * qi;
                double ti3 = ti * ti2, qi3 = qi * qi2;
                double ti4 = ti * ti3, qi4 = qi * qi3;
                a1 += ti2 * qi4;
                a2 += ti4 * qi2;
                a12 += ti3 * qi3;

                Vector pi = (Vector)data[i - 1];
                Vector m = pi - qi3 * p0 - ti3 * p3;
                c1 += ti * qi2 * m;
                c2 += ti2 * qi * m;
            }
            a1 *= 9.0;
            a2 *= 9.0;
            a12 *= 9.0;
            c1 *= 3.0;
            c2 *= 3.0;

            double d = a1 * a2 - a12 * a12;
            p1 = (Point)((a2 * c1 - a12 * c2) / d);
            p2 = (Point)((a1 * c2 - a12 * c1) / d);
        }
    }
}

What's the best way to get a cubic bezier curve closest to given points?

For example, here are 30 points:

Those points are distributed around the the cubic bezier curve controled by four points:

P0 (0, 256), P1 (512, 0), P2 (0, 0), P3 (256, 256).

Suppose the curve is from (0, 256) to (256, 256), how to get rest two control points close to the origional points?

Are you fitting a single cubic polynomial to the given points? Introducing "control points" c1 and c2 uniquely determines a cubic polynomial that fits the four points p0, c1, c2, pn. Now "the best way" requires a criterion for closeness. Suppose your data consists of 2D points, the x-coordinate being an independent value and the y-coordinate a (functionally) dependent value, and that points p0,...,pn are arranged by (distinct) increasing x-coordinates. Your curve fits the first and last points exactly, so "closest curve" might minimize sum of squares error in y-values or other objective. — hardmath
It'a cubic bezier curve I want to fit. Not a single cubic polynomial. — EFanZh
You could use the Bernstein basis for calculating the new control points, as explained in reference.wolfram.com/mathematica/ref/BezierCurve.html, under the Applications-interpolation section — Dr. belisarius
Don't take this the wrong way but it looks to me you are missing the basic understanding of this. "Bezier" is not a type of curve, just like a "spline" is not a type of curve (so to say). It is, to put it, a method of constructing curves that "work together" and depend on their border conditions. So what @hardmath is saying does make sense. — Rook
I think a cubic bezier curve is like a curve we can use Pen tools to draw in Photoshop and it is controled by four points. A cubic polynomial is something like y = a * x^3 + b * x^2 + c * x + d. Those are not the same kind of curve. Am I right? — EFanZh

Frank Hileman Frank Hileman · Accepted Answer · 2011-10-13T20:40:14

Your problem is very hard if you want to create curves with cusps. I can think of a heuristic to create an initial set of control points. For the first control point, try taking the first 1/3 of the points you have available, when sorted from the distance to the first anchor point. The sorting is necessary, otherwise, you may be jumping all over. Take that 1/3 of your points and do a linear least squares fit, which is has linear time complexity. That gives you the direction your curve needs to take off. Do the same thing with the last 1/3, and you have the "landing" direction.

Use those linear solutions to create vectors pointing away from the anchor points, then try making those vectors longer and shorter, trying to minimize the error. The control points would be along those vectors from the anchor points.

Here are some other ideas (I can only post two links!): physics forum question bezier curve fitting thesis

How can I get a cubic bezier curve closest to given points?

5 Answers