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:

22, 245
26, 240
39, 242
51, 231
127, 189
136, 185
140, 174
147, 171
163, 162
169, 155
179, 107
181, 147
189, 168
193, 187
196, 75
199, 76
200, 185
201, 68
204, 73
205, 68
208, 123
213, 118
216, 210
216, 211
218, 68
226, 65
227, 110
228, 102
229, 87
252, 247

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?

Answer 1

You might want to have a look at this page : http://www.antigrain.com/research/bezier_interpolation/index.html

It's a very good implementation, though as the author writes : "This method is pure heuristic and empiric. It probably gives a wrong result from the point of view of strict mathematical modeling. But in practice the result is good enough and it requires absolute minimum of calculations. "

It's in C++ but is really easily portable to any language... Pass each of your "edges" through the control points calculation function, then through the bezier calculation one, and you have it. To perform bezier smooth on a polygon, pass a last edge with your last and first point.